FIFE
be64c707dea6b3250bd4355bf5c825d25920087d
|
MultiLayerSearch using A*. More...
#include <multilayersearch.h>
Public Member Functions | |
MultiLayerSearch (Route *route, const int32_t sessionId) | |
Constructor. More... | |
~MultiLayerSearch () | |
Destructor. More... | |
void | updateSearch () |
Updates the search. More... | |
void | calcPath () |
Calculates final path. More... | |
Public Member Functions inherited from FIFE::RoutePatherSearch | |
RoutePatherSearch (Route *route, const int32_t sessionId) | |
Constructor. More... | |
virtual | ~RoutePatherSearch () |
int32_t | getSessionId () const |
Retrieves the session id. More... | |
int32_t | getSearchStatus () const |
A small function which returns the current status of the search. More... | |
Route * | getRoute () |
Returns the associated route for this search. More... | |
Private Member Functions | |
void | createSearchFrontier (int32_t startInt, CellCache *cache) |
Creates or resets the SearchFrontier. More... | |
void | calcPathStep () |
Calculates path parts per layer. More... | |
void | searchBetweenTargetsNeighbor () |
Fetch targets from neighbor layers. More... | |
void | searchBetweenTargetsMap () |
Fetch targets from map. More... | |
Private Attributes | |
Location | m_to |
A location object representing where the search started. More... | |
Location | m_from |
A location object representing where the search ended. More... | |
CellCache * | m_startCache |
A pointer to the start CellCache. More... | |
CellCache * | m_endCache |
A pointer to the end CellCache. More... | |
CellCache * | m_currentCache |
A pointer to the currently used CellCache. More... | |
Zone * | m_startZone |
Zone * | m_endZone |
int32_t | m_startCoordInt |
The start coordinate as an int32_t. More... | |
int32_t | m_lastStartCoordInt |
The last used start coordinate as an int32_t. More... | |
int32_t | m_destCoordInt |
The destination coordinate as an int32_t. More... | |
int32_t | m_lastDestCoordInt |
The last used destination coordinate as an int32_t. More... | |
int32_t | m_next |
The next coordinate to check out. More... | |
std::vector< int32_t > | m_spt |
The shortest path tree. More... | |
std::vector< int32_t > | m_sf |
The search frontier. More... | |
std::vector< double > | m_gCosts |
A table to hold the costs. More... | |
PriorityQueue< int32_t, double > | m_sortedFrontier |
Priority queue to hold nodes on the sf in order. More... | |
std::list< Cell * > | m_betweenTargets |
List of targets that need to be solved to reach the real target. More... | |
bool | m_foundLast |
Indicates if last between target could be achieved. More... | |
Path | m_path |
Path to which all steps are added. More... | |
Additional Inherited Members | |
Public Types inherited from FIFE::RoutePatherSearch | |
enum | SearchStatus { search_status_failed, search_status_complete, search_status_incomplete } |
An enumeration of the different status the search can be in. More... | |
Protected Member Functions inherited from FIFE::RoutePatherSearch | |
void | setSearchStatus (const SearchStatus status) |
Sets the current status of the search. More... | |
Protected Attributes inherited from FIFE::RoutePatherSearch | |
Route * | m_route |
Pointer to route. More... | |
bool | m_specialCost |
Indicates if the search should use special costs. More... | |
bool | m_multicell |
Indicates if the route is for a multi cell object. More... | |
bool | m_ignoreDynamicBlockers |
Indicates if dynamic blockers should be ignored. More... | |
std::vector< Cell * > | m_ignoredBlockers |
Blockers from a multi cell object which should be ignored. More... | |
MultiLayerSearch using A*.
Definition at line 45 of file multilayersearch.h.
FIFE::MultiLayerSearch::MultiLayerSearch | ( | Route * | route, |
const int32_t | sessionId | ||
) |
Constructor.
route | A pointer to the route for which a path should be searched. |
sessionId | A integer containing the session id for this search. |
Definition at line 42 of file multilayersearch.cpp.
References FIFE::CellCache::getCell(), FIFE::Location::getLayerCoordinates(), FIFE::Cell::getNeighbors(), FIFE::Cell::isZoneProtected(), m_betweenTargets, m_endCache, m_endZone, m_from, FIFE::RoutePatherSearch::m_route, m_startCache, m_startZone, m_to, FIFE::ROUTE_FAILED, FIFE::RoutePatherSearch::search_status_failed, searchBetweenTargetsMap(), searchBetweenTargetsNeighbor(), FIFE::Route::setRouteStatus(), and FIFE::RoutePatherSearch::setSearchStatus().
FIFE::MultiLayerSearch::~MultiLayerSearch | ( | ) |
Destructor.
Definition at line 107 of file multilayersearch.cpp.
|
virtual |
Calculates final path.
If the search is successful then a path is created.
Implements FIFE::RoutePatherSearch.
Definition at line 323 of file multilayersearch.cpp.
References FIFE::CellCache::convertIntToCoord(), FIFE::CellCache::getCell(), FIFE::CellCache::getLayer(), m_currentCache, m_lastDestCoordInt, m_lastStartCoordInt, m_path, FIFE::RoutePatherSearch::m_route, m_spt, FIFE::ROUTE_FAILED, FIFE::RoutePatherSearch::search_status_failed, FIFE::Location::setLayerCoordinates(), FIFE::Route::setPath(), FIFE::Route::setRouteStatus(), and FIFE::RoutePatherSearch::setSearchStatus().
|
private |
Calculates path parts per layer.
Definition at line 297 of file multilayersearch.cpp.
References FIFE::CellCache::convertIntToCoord(), FIFE::Location::getExactLayerCoordinatesRef(), FIFE::CellCache::getLayer(), m_currentCache, m_from, m_lastDestCoordInt, m_lastStartCoordInt, m_path, FIFE::RoutePatherSearch::m_route, m_spt, FIFE::ROUTE_FAILED, FIFE::RoutePatherSearch::search_status_failed, FIFE::Location::setLayerCoordinates(), FIFE::Route::setRouteStatus(), and FIFE::RoutePatherSearch::setSearchStatus().
Referenced by updateSearch().
|
private |
Creates or resets the SearchFrontier.
startInt | The start coordinate as integer identifier. |
cache | A pointer to the start CellCache. |
Definition at line 110 of file multilayersearch.cpp.
References FIFE::PriorityQueue< index_type, priority_type >::clear(), FIFE::CellCache::getMaxIndex(), m_gCosts, m_next, m_sf, m_sortedFrontier, m_spt, and FIFE::PriorityQueue< index_type, priority_type >::pushElement().
Referenced by updateSearch().
|
private |
Fetch targets from map.
Definition at line 388 of file multilayersearch.cpp.
References ABS, FIFE::PriorityQueue< index_type, priority_type >::changeElementPriority(), utf8::distance(), FIFE::PriorityQueue< index_type, priority_type >::empty(), FIFE::CellCache::getCell(), FIFE::Layer::getCellCache(), FIFE::Location::getLayer(), FIFE::Cell::getLayer(), FIFE::Cell::getLayerCoordinates(), FIFE::Location::getLayerDistanceTo(), FIFE::Map::getLayers(), FIFE::Layer::getMap(), FIFE::PriorityQueue< index_type, priority_type >::getPriorityElement(), FIFE::Cell::getTransition(), FIFE::Zone::getTransitionCells(), FIFE::CellCache::getTransitionCells(), FIFE::Cell::getZone(), FIFE::CellCache::getZones(), m_betweenTargets, m_endCache, m_endZone, m_from, FIFE::TransitionInfo::m_layer, FIFE::TransitionInfo::m_mc, m_startCache, m_startZone, utf8::next(), FIFE::PriorityQueue< index_type, priority_type >::popElement(), FIFE::PriorityQueue< index_type, priority_type >::pushElement(), FIFE::Location::setLayer(), and FIFE::Location::setLayerCoordinates().
Referenced by MultiLayerSearch().
|
private |
Fetch targets from neighbor layers.
Definition at line 347 of file multilayersearch.cpp.
References FIFE::CellCache::getCell(), FIFE::Layer::getCellCache(), FIFE::CellCache::getLayer(), FIFE::Location::getLayerDistanceTo(), FIFE::Cell::getTransition(), FIFE::CellCache::getTransitionCells(), FIFE::Cell::getZone(), m_betweenTargets, m_endCache, m_endZone, m_from, FIFE::TransitionInfo::m_layer, FIFE::TransitionInfo::m_mc, m_startCache, m_startZone, m_to, FIFE::Location::setLayer(), and FIFE::Location::setLayerCoordinates().
Referenced by MultiLayerSearch().
|
virtual |
Updates the search.
Each update checks all neighbors of the last checked coordinate and selects the most favorable.
Implements FIFE::RoutePatherSearch.
Definition at line 125 of file multilayersearch.cpp.
References ABS, calcPathStep(), FIFE::PriorityQueue< index_type, priority_type >::changeElementPriority(), FIFE::PriorityQueue< index_type, priority_type >::clear(), FIFE::CellCache::convertCoordToInt(), FIFE::CellCache::convertIntToCoord(), createSearchFrontier(), FIFE::PriorityQueue< index_type, priority_type >::empty(), FIFE::CellCache::getAdjacentCost(), FIFE::getAngleBetween(), FIFE::CellCache::getCell(), FIFE::Layer::getCellCache(), FIFE::Layer::getCellGrid(), FIFE::Cell::getCellType(), FIFE::Route::getCostId(), FIFE::CellGrid::getHeuristicCost(), FIFE::CellCache::getLayer(), FIFE::Cell::getLayer(), FIFE::Location::getLayerCoordinates(), FIFE::Cell::getLayerCoordinates(), FIFE::Route::getLimitedAreas(), FIFE::Cell::getNeighbors(), FIFE::Route::getOccupiedCells(), FIFE::PriorityQueue< index_type, priority_type >::getPriorityElement(), FIFE::RoutePatherSearch::getSearchStatus(), FIFE::Route::getZStepRange(), FIFE::Route::isAreaLimited(), FIFE::CellCache::isCellInArea(), m_betweenTargets, m_currentCache, m_destCoordInt, m_endCache, m_foundLast, m_gCosts, FIFE::RoutePatherSearch::m_ignoredBlockers, FIFE::RoutePatherSearch::m_ignoreDynamicBlockers, m_lastDestCoordInt, m_lastStartCoordInt, FIFE::TransitionInfo::m_layer, FIFE::TransitionInfo::m_mc, FIFE::RoutePatherSearch::m_multicell, m_next, FIFE::RoutePatherSearch::m_route, m_sf, m_sortedFrontier, FIFE::RoutePatherSearch::m_specialCost, m_spt, m_to, FIFE::PriorityQueue< index_type, priority_type >::popElement(), FIFE::PriorityQueue< index_type, priority_type >::pushElement(), FIFE::ROUTE_FAILED, FIFE::ROUTE_SEARCHED, FIFE::RoutePatherSearch::search_status_complete, FIFE::RoutePatherSearch::search_status_failed, FIFE::Location::setLayerCoordinates(), FIFE::Route::setRouteStatus(), FIFE::RoutePatherSearch::setSearchStatus(), FIFE::CellGrid::toMultiCoordinates(), and FIFE::PointType3D< T >::z.
|
private |
List of targets that need to be solved to reach the real target.
Definition at line 131 of file multilayersearch.h.
Referenced by MultiLayerSearch(), searchBetweenTargetsMap(), searchBetweenTargetsNeighbor(), and updateSearch().
|
private |
A pointer to the currently used CellCache.
Definition at line 103 of file multilayersearch.h.
Referenced by calcPath(), calcPathStep(), and updateSearch().
|
private |
The destination coordinate as an int32_t.
Definition at line 115 of file multilayersearch.h.
Referenced by updateSearch().
|
private |
A pointer to the end CellCache.
Definition at line 101 of file multilayersearch.h.
Referenced by MultiLayerSearch(), searchBetweenTargetsMap(), searchBetweenTargetsNeighbor(), and updateSearch().
|
private |
Definition at line 108 of file multilayersearch.h.
Referenced by MultiLayerSearch(), searchBetweenTargetsMap(), and searchBetweenTargetsNeighbor().
|
private |
Indicates if last between target could be achieved.
Definition at line 133 of file multilayersearch.h.
Referenced by updateSearch().
|
private |
A location object representing where the search ended.
Definition at line 96 of file multilayersearch.h.
Referenced by calcPathStep(), MultiLayerSearch(), searchBetweenTargetsMap(), and searchBetweenTargetsNeighbor().
|
private |
A table to hold the costs.
Definition at line 126 of file multilayersearch.h.
Referenced by createSearchFrontier(), and updateSearch().
|
private |
The last used destination coordinate as an int32_t.
Definition at line 117 of file multilayersearch.h.
Referenced by calcPath(), calcPathStep(), and updateSearch().
|
private |
The last used start coordinate as an int32_t.
Definition at line 113 of file multilayersearch.h.
Referenced by calcPath(), calcPathStep(), and updateSearch().
|
private |
The next coordinate to check out.
Definition at line 119 of file multilayersearch.h.
Referenced by createSearchFrontier(), and updateSearch().
|
private |
Path to which all steps are added.
Definition at line 135 of file multilayersearch.h.
Referenced by calcPath(), and calcPathStep().
|
private |
The search frontier.
Definition at line 124 of file multilayersearch.h.
Referenced by createSearchFrontier(), and updateSearch().
|
private |
Priority queue to hold nodes on the sf in order.
Definition at line 128 of file multilayersearch.h.
Referenced by createSearchFrontier(), and updateSearch().
|
private |
The shortest path tree.
Definition at line 122 of file multilayersearch.h.
Referenced by calcPath(), calcPathStep(), createSearchFrontier(), and updateSearch().
|
private |
A pointer to the start CellCache.
Definition at line 99 of file multilayersearch.h.
Referenced by MultiLayerSearch(), searchBetweenTargetsMap(), and searchBetweenTargetsNeighbor().
|
private |
The start coordinate as an int32_t.
Definition at line 111 of file multilayersearch.h.
|
private |
Definition at line 106 of file multilayersearch.h.
Referenced by MultiLayerSearch(), searchBetweenTargetsMap(), and searchBetweenTargetsNeighbor().
|
private |
A location object representing where the search started.
Definition at line 94 of file multilayersearch.h.
Referenced by MultiLayerSearch(), searchBetweenTargetsNeighbor(), and updateSearch().