Changeset 3849


Ignore:
Timestamp:
02/22/12 17:59:24 (2 years ago)
Author:
helios2000
Message:
  • Pathfinder uses now Cellcache instead of SearchSpace?. ref[t:647]
Location:
branches/active/cell_pathfinding/engine/core/pathfinder/routepather
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • branches/active/cell_pathfinding/engine/core/pathfinder/routepather/routepather.cpp

    r3621 r3849  
    3232#include "model/structures/instance.h" 
    3333#include "model/structures/layer.h" 
    34  
    35 #include "pathfinder/searchspace.h" 
     34#include "model/structures/cellcache.h" 
    3635 
    3736#include "routepather.h" 
     
    3938 
    4039namespace FIFE { 
    41         void RoutePather::setMap(Map* map) { 
    42                 if(!map) { 
    43                         return; 
    44                 } 
    45                 m_map = map; 
    46         } 
    4740 
    4841        int32_t RoutePather::makeSessionId() { 
     
    5144         
    5245        void RoutePather::makePlan(const Instance *instance, const Location& target, int32_t session_id, int32_t priority) { 
    53                 SearchSpace* searchspace = getSearchSpace(target.getLayer()); 
    54                 if(!searchspace) { 
    55                         searchspace = new SearchSpace(target.getLayer()); 
    56                         addSearchSpace(searchspace); 
    57                 } 
    58                 if(searchspace->isInSearchSpace(target)) { 
    59                         RoutePatherSearch* newSearch = new RoutePatherSearch(session_id, instance->getLocation(), target, searchspace); 
     46                Cellcache* cache = instance->getLocation().getLayer()->getCellcache(); 
     47                if (!cache) { 
     48                        return; 
     49                } 
     50                if (cache->isInCellcache(target)) { 
     51                        RoutePatherSearch* newSearch = new RoutePatherSearch(session_id, instance->getLocation(), target, cache); 
    6052                        m_sessions.pushElement(SessionQueue::value_type(newSearch, priority)); 
    6153                        addSessionId(session_id); 
     
    6557         
    6658        bool RoutePather::locationsEqual(const Location &a, const Location &b) { 
    67                  
    6859                const ModelCoordinate a_coord = a.getLayerCoordinates(); 
    6960                const ModelCoordinate b_coord = b.getLayerCoordinates(); 
     
    7465        bool RoutePather::testStep(const Instance *instance, Path& path) { 
    7566                Location instanceLoc = instance->getLocation(); 
    76                 if(!path.empty() &&  
    77                    !locationsEqual(path.front(), instanceLoc) && 
    78                    instanceLoc.getLayer()->cellContainsBlockingInstance(path.front().getLayerCoordinates())) { 
     67                if (!path.empty() && 
     68                        !locationsEqual(path.front(), instanceLoc) && 
     69                        instanceLoc.getLayer()->cellContainsBlockingInstance(path.front().getLayerCoordinates())) { 
     70                         
    7971                        const bool last_step = path.front() == path.back(); 
    8072                        path.clear(); 
     
    247239                return false; 
    248240        } 
    249          
    250         bool RoutePather::addSearchSpace(SearchSpace* search_space) { 
    251                 std::pair<SearchSpaceMap::iterator, bool> res = m_searchspaces.insert(SearchSpaceMap::value_type(search_space->getLayer(), search_space)); 
    252                  
    253                 return res.second; 
    254         } 
    255          
    256         SearchSpace* RoutePather::getSearchSpace(Layer * const layer) { 
    257                 SearchSpaceMap::iterator i = m_searchspaces.find(layer); 
    258                 if(i == m_searchspaces.end()) { 
    259                         return 0; 
    260                 } 
    261                 return i->second; 
    262         } 
    263241} 
  • branches/active/cell_pathfinding/engine/core/pathfinder/routepather/routepather.h

    r3689 r3849  
    4040namespace FIFE { 
    4141 
    42         class Search; 
    43         class SearchSpace; 
     42        class Cellcache; 
    4443        class RoutePatherSearch; 
    4544 
     
    5251                } 
    5352 
    54                 void setMap(Map* map); 
    5553                int32_t getNextLocation(const Instance* instance, const Location& target, 
    5654                                    double distance_to_travel, Location& nextLocation, 
     
    7674                bool cancelSession(const int32_t session_id); 
    7775 
    78                 /** Adds a search space to the route pather. 
    79                  * 
    80                  * @param search_space A pointer to the search space to add. 
    81                  * @return a boolean signifying whether the search space was correctly added or not. 
    82                  */ 
    83                 bool addSearchSpace(SearchSpace* search_space); 
    84  
    85                 /** Retrieves a searchspace associated with the given layer. 
    86                  * 
    87                  * @param A pointer to the search space 
    88                  * @return A pointer to the search space if it could be found, 0 otherwise. 
    89                  */ 
    90                 SearchSpace* getSearchSpace(Layer * const layer); 
    91  
    9276                std::string getName() const { return "RoutePather"; }; 
    9377        private: 
     
    9680                typedef std::list<int32_t> SessionList; 
    9781                typedef std::map<int32_t, Path> PathMap; 
    98                 typedef std::map<Layer*, SearchSpace*> SearchSpaceMap; 
    9982                typedef std::map<int32_t, Location> LocationMap; 
    10083                /** Makes the instance follow the given path. 
     
    161144 
    162145                //The map the search is running on. 
    163                 Map*          m_map; 
     146                Map* m_map; 
    164147 
    165148                //A map of currently running sessions (searches). 
    166                 SessionQueue   m_sessions; 
     149                SessionQueue m_sessions; 
    167150 
    168151                //A list of session ids that have been registered. 
    169                 SessionList    m_registeredSessionIds; 
     152                SessionList m_registeredSessionIds; 
    170153 
    171154                //Calculated paths for the movement phase. 
    172                 PathMap            m_paths; 
     155                PathMap m_paths; 
    173156 
    174157                //The endpoints for which those paths were calculated 
    175                 LocationMap        m_path_targets; 
    176  
    177                 //A map of searchspaces. 
    178                 SearchSpaceMap m_searchspaces; 
     158                LocationMap m_path_targets; 
    179159 
    180160                //The next free session id. 
    181                 int32_t            m_nextFreeSessionId; 
     161                int32_t m_nextFreeSessionId; 
    182162 
    183163                //The maximum number of ticks allowed. 
    184                 int32_t                    m_maxticks; 
     164                int32_t m_maxticks; 
    185165        }; 
    186166} 
  • branches/active/cell_pathfinding/engine/core/pathfinder/routepather/routepathersearch.cpp

    r3624 r3849  
    3232#include "model/structures/layer.h" 
    3333#include "model/structures/instancetree.h" 
     34#include "model/structures/cellcache.h" 
    3435#include "model/metamodel/object.h" 
    35 #include "pathfinder/searchspace.h" 
    3636#include "pathfinder/heuristic.h" 
    3737#include "util/math/fife_math.h" 
     
    4040 
    4141namespace FIFE { 
    42         RoutePatherSearch::RoutePatherSearch(const int32_t session_id, const Location& from, const Location& to, SearchSpace* searchSpace) 
    43                 : m_to(to),  
    44                   m_from(from),  
    45                   m_sessionId(session_id),  
    46                   m_searchspace(searchSpace),  
    47                   m_status(search_status_incomplete),  
    48                   m_startCoordInt(searchSpace->convertCoordToInt(from.getLayerCoordinates())), 
    49                   m_destCoordInt(searchSpace->convertCoordToInt(to.getLayerCoordinates())), 
    50                   m_next(0), 
    51                   m_heuristic(Heuristic::getHeuristic(searchSpace->getLayer()->getCellGrid()->getType()))  
    52         { 
     42        RoutePatherSearch::RoutePatherSearch(const int32_t session_id, const Location& from, const Location& to, Cellcache* cache): 
     43                m_to(to),  
     44                m_from(from),  
     45                m_sessionId(session_id),  
     46                m_cellcache(cache),  
     47                m_status(search_status_incomplete),  
     48                m_startCoordInt(cache->convertCoordToInt(from.getLayerCoordinates())), 
     49                m_destCoordInt(cache->convertCoordToInt(to.getLayerCoordinates())), 
     50                m_next(0), 
     51                m_heuristic(Heuristic::getHeuristic(cache->getLayer()->getCellGrid()->getType()))       { 
     52 
    5353                m_sortedfrontier.pushElement(PriorityQueue<int32_t, double>::value_type(m_startCoordInt, 0.0)); 
    54                 int32_t max_index = m_searchspace->getMaxIndex(); 
    55                 m_spt.resize(max_index + 1, -1); 
    56                 m_sf.resize(max_index + 1, -1); 
    57                 m_gCosts.resize(max_index + 1, 0.0f);; 
     54                int32_t max_index = m_cellcache->getMaxIndex(); 
     55                m_spt.resize(max_index, -1); 
     56                m_sf.resize(max_index, -1); 
     57                m_gCosts.resize(max_index, 0.0f);; 
    5858        } 
    5959 
     
    7575                //use destination layer for getting the cell coordinates for now, this should be moved 
    7676                //into search space. 
    77                 ModelCoordinate nextCoord = m_searchspace->convertIntToCoord(m_next); 
     77                ModelCoordinate nextCoord = m_cellcache->convertIntToCoord(m_next); 
    7878                std::vector<ModelCoordinate> adjacents; 
    79                 m_searchspace->getLayer()->getCellGrid()->getAccessibleCoordinates(nextCoord, adjacents); 
     79                m_cellcache->getLayer()->getCellGrid()->getAccessibleCoordinates(nextCoord, adjacents); 
     80                Location loc(m_cellcache->getLayer()); 
    8081                for(std::vector<ModelCoordinate>::iterator i = adjacents.begin(); i != adjacents.end(); ++i) { 
    8182                        //first determine if coordinate is in search space. 
    82                         Location loc; 
    83                         loc.setLayer(m_searchspace->getLayer()); 
    8483                        loc.setLayerCoordinates((*i)); 
    85                         int32_t adjacentInt = m_searchspace->convertCoordToInt((*i)); 
    86                         if(m_searchspace->isInSearchSpace(loc)) { 
     84                        int32_t adjacentInt = m_cellcache->convertCoordToInt((*i)); 
     85                        if (m_cellcache->isInCellcache(loc)) { 
    8786                                if((adjacentInt == m_next || loc.getLayer()->cellContainsBlockingInstance(loc.getLayerCoordinates())) && 
    8887                                        adjacentInt != m_destCoordInt) { 
    8988                                        continue; 
    9089                                } 
    91                                         double hCost = m_heuristic->calculate((*i), destCoord); 
     90                                double hCost = m_heuristic->calculate((*i), destCoord); 
    9291                                //float hCost = Heuristic::getHeuristic(m_searchspace->getLayer()->getCellGrid()->getType())->calculate((*i), destCoord); 
    9392                                double gCost = m_gCosts[m_next] + loc.getLayer()->getCellGrid()->getAdjacentCost(nextCoord, (*i)); 
     
    114113                to.setExactLayerCoordinates(FIFE::intPt2doublePt(to.getLayerCoordinates())); 
    115114                path.push_back(to); 
     115                Location newnode(m_cellcache->getLayer()); 
    116116                while(current != end) { 
    117                         if(m_spt[current] < 0 ) { 
    118                              // This is when the size of m_spt can not handle the distance of the location 
    119                              setSearchStatus(search_status_failed); 
    120                              break; 
    121                         } 
    122                         current = m_spt[current]; 
    123                         Location newnode; 
    124                         newnode.setLayer(m_searchspace->getLayer()); 
    125                         ModelCoordinate currentCoord = m_searchspace->convertIntToCoord(current); 
     117                        if(m_spt[current] < 0 ) { 
     118                                // This is when the size of m_spt can not handle the distance of the location 
     119                                setSearchStatus(search_status_failed); 
     120                                break; 
     121                        } 
     122                        current = m_spt[current]; 
     123                        ModelCoordinate currentCoord = m_cellcache->convertIntToCoord(current); 
    126124                        newnode.setLayerCoordinates(currentCoord); 
    127125                        path.push_front(newnode); 
    128                 } 
     126                } 
    129127                path.front().setExactLayerCoordinates(m_from.getExactLayerCoordinates()); 
    130128                return path; 
  • branches/active/cell_pathfinding/engine/core/pathfinder/routepather/routepathersearch.h

    r3624 r3849  
    3535namespace FIFE { 
    3636 
    37         class Map; 
    38         class SearchSpace; 
     37        class Cellcache; 
    3938        class Heuristic; 
    4039 
     
    4544        class RoutePatherSearch { 
    4645        public: 
    47                 RoutePatherSearch(const int32_t session_id, const Location& from, const Location& to, SearchSpace* searchSpace); 
     46                RoutePatherSearch(const int32_t session_id, const Location& from, const Location& to, Cellcache* cache); 
    4847 
    49                 typedef std::list<Location> Path; 
    50                 /** An enumeration of the different status the search can be in. 
    51                  * 
    52                  */ 
    53                 enum SearchStatus { 
    54                         search_status_failed, 
    55                         search_status_complete, 
    56                         search_status_incomplete 
    57                 }; 
     48                typedef std::list<Location> Path; 
     49                 
     50                /** An enumeration of the different status the search can be in. 
     51                 * 
     52                 */ 
     53                enum SearchStatus { 
     54                        search_status_failed, 
     55                        search_status_complete, 
     56                        search_status_incomplete 
     57                }; 
    5858 
    5959                virtual void updateSearch(); 
     
    6161                virtual Path calcPath(); 
    6262 
    63                 /** Retrieves the session id. 
    64                  * 
    65                  * @return The searches session id in the pather. 
    66                  */ 
    67                 int32_t getSessionId() const { 
    68                         return m_sessionId; 
    69                 } 
     63                /** Retrieves the session id. 
     64                 * 
     65                 * @return The searches session id in the pather. 
     66                 */ 
     67                int32_t getSessionId() const { return m_sessionId; } 
    7068 
    71                 /** Retrieves the pather. 
    72                  * 
    73                  * @return A pointer to the abstract pather which 
    74                  */ 
    75                 SearchSpace* getSearchSpace() const { 
    76                         return m_searchspace; 
    77                 } 
     69                /** A small function which returns the current status of the search. 
     70                 * 
     71                 * @return An integer value representing the status, which is enumerated by this class. 
     72                 */ 
     73                int32_t getSearchStatus() const { return m_status; } 
    7874 
    79                 /** A small function which returns the current status of the search. 
    80                  * 
    81                  * @return An integer value representing the status, which is enumerated by this class. 
    82                  */ 
    83                 int32_t getSearchStatus() const { 
    84                         return m_status; 
    85                 } 
     75        protected: 
     76                /** Sets the current status of the search. 
     77                 * 
     78                 * @param status The status to set. 
     79                 */ 
     80                void setSearchStatus(const SearchStatus status) { m_status = status; } 
    8681 
    87          protected: 
    88                 /** Sets the current status of the search. 
    89                  * 
    90                  * @param status The status to set. 
    91                  */ 
    92                 void setSearchStatus(const SearchStatus status) { 
    93                         m_status = status; 
    94                 } 
     82        private: 
     83                // A location object representing where the search started. 
     84                Location m_to; 
    9585 
    96          private: 
    97                 //A location object representing where the search started. 
    98                 Location                m_to; 
     86                // A location object representing where the search ended. 
     87                Location m_from; 
    9988 
    100                 //A location object representing where the search ended. 
    101                 Location                m_from; 
     89                // An integer containing the session id for this search. 
     90                int32_t m_sessionId; 
    10291 
    103                 //An integer containing the session id for this search. 
    104                 int32_t                             m_sessionId; 
     92                // A pointer to the Cellcache. 
     93                Cellcache* m_cellcache; 
    10594 
    106                 //A pointer to the pather that owns this search. 
    107                 SearchSpace*    m_searchspace; 
     95                // An enumeration of the searches current status. 
     96                SearchStatus m_status; 
    10897 
    109                 //An enumeration of the searches current status. 
    110                 SearchStatus    m_status; 
    111                  
    112                 //The start coordinate as an int32_t. 
    113                 int32_t             m_startCoordInt; 
    114                  
    115                 //The destination coordinate as an int32_t. 
    116                 int32_t             m_destCoordInt; 
    117                  
    118                 //The next coordinate to check out. 
    119                 int32_t             m_next; 
     98                // The start coordinate as an int32_t. 
     99                int32_t m_startCoordInt; 
    120100 
    121                 //The class to use to calculate the heuristic value. 
    122                 Heuristic*                m_heuristic; 
     101                // The destination coordinate as an int32_t. 
     102                int32_t m_destCoordInt; 
    123103 
    124                 //The shortest path tree. 
    125                 std::vector<int32_t>          m_spt; 
     104                // The next coordinate to check out. 
     105                int32_t m_next; 
    126106 
    127                 //The search frontier. 
    128                 std::vector<int32_t>          m_sf; 
     107                // The class to use to calculate the heuristic value. 
     108                Heuristic* m_heuristic; 
    129109 
    130                 //A table to hold the costs. 
    131                 std::vector<double>               m_gCosts; 
     110                // The shortest path tree. 
     111                std::vector<int32_t> m_spt; 
    132112 
    133                 //priority queue to hold nodes on the sf in order.  
     113                // The search frontier. 
     114                std::vector<int32_t> m_sf; 
     115 
     116                // A table to hold the costs. 
     117                std::vector<double> m_gCosts; 
     118 
     119                // Priority queue to hold nodes on the sf in order.  
    134120                PriorityQueue<int32_t, double> m_sortedfrontier; 
    135121        }; 
Note: See TracChangeset for help on using the changeset viewer.