44 m_to(route->getEndNode()),
45 m_from(route->getStartNode()),
46 m_startCache(m_from.getLayer()->getCellCache()),
47 m_endCache(m_to.getLayer()->getCellCache()),
49 m_startZone(m_startCache->getCell(m_from.getLayerCoordinates())->getZone()),
50 m_endZone(m_endCache->getCell(m_to.getLayerCoordinates())->getZone()),
51 m_startCoordInt(m_startCache->convertCoordToInt(m_from.getLayerCoordinates())),
52 m_lastStartCoordInt(m_startCoordInt),
53 m_destCoordInt(m_endCache->convertCoordToInt(m_to.getLayerCoordinates())),
54 m_lastDestCoordInt(-1),
61 const std::vector<Cell*>& neighbors = endcell->
getNeighbors();
62 for (std::vector<Cell*>::const_iterator it = neighbors.begin();
63 it != neighbors.end(); ++it) {
64 Zone* tmpzone = (*it)->getZone();
84 const std::vector<Cell*>& neighbors = startCell->
getNeighbors();
85 for (std::vector<Cell*>::const_iterator it = neighbors.begin();
86 it != neighbors.end(); ++it) {
87 Zone* tmpzone = (*it)->getZone();
119 m_spt.resize(max_index, -1);
120 m_sf.resize(max_index, -1);
184 bool zLimited = maxZ != -1;
185 const std::vector<Cell*>& adjacents = nextCell->
getNeighbors();
186 if (adjacents.empty()) {
189 for (std::vector<Cell*>::const_iterator i = adjacents.begin(); i != adjacents.end(); ++i) {
196 int32_t adjacentInt = (*i)->getCellId();
197 if (
m_sf[adjacentInt] != -1 &&
m_spt[adjacentInt] != -1) {
200 if (zLimited &&
ABS(cellZ-(*i)->getLayerCoordinates().z) > maxZ) {
220 Location adjacentLoc((*i)->getLayer());
224 std::vector<ModelCoordinate> coords = grid-> toMultiCoordinates(adjacentLoc.getLayerCoordinates(),
m_route->
getOccupiedCells(rotation));
225 std::vector<ModelCoordinate>::iterator coord_it = coords.begin();
226 for (; coord_it != coords.end(); ++coord_it) {
245 bool sameAreas =
false;
247 std::list<std::string>::const_iterator area_it = areas.begin();
248 for (; area_it != areas.end(); ++area_it) {
266 if (
m_sf[adjacentInt] == -1) {
270 }
else if (gCost <
m_gCosts[adjacentInt] &&
m_spt[adjacentInt] == -1) {
285 path.push_back(newnode);
286 while(current != end) {
287 if (
m_spt[current] < 0 ) {
293 current =
m_spt[current];
295 path.push_front(newnode);
312 path.push_back(newnode);
313 while(current != end) {
314 if (
m_spt[current] < 0 ) {
320 current =
m_spt[current];
322 path.push_front(newnode);
330 if (!cells.empty()) {
334 for (std::vector<Cell*>::iterator it = cells.begin(); it != cells.end(); ++it) {
353 Location loc2((*it)->getTransition()->m_layer);
356 double temp_distance = temp.getLayerDistanceTo(
m_from) + loc2.getLayerDistanceTo(
m_to);
358 if (current_distance > temp_distance) {
371 std::vector<Cell*> endTransCells;
373 std::vector<Cell*>::iterator tcell_it = tmpTransCells.begin();
374 for (; tcell_it != tmpTransCells.end(); ++tcell_it) {
375 Zone* zone = (*tcell_it)->getZone();
377 endTransCells.push_back(*tcell_it);
380 if (endTransCells.empty()) {
384 std::vector<Cell*> startTransCells;
386 tcell_it = tmpTransCells.begin();
387 for (; tcell_it != tmpTransCells.end(); ++tcell_it) {
388 Zone* zone = (*tcell_it)->getZone();
390 startTransCells.push_back(*tcell_it);
393 if (startTransCells.empty()) {
398 std::vector<Zone*> zones;
400 std::list<Layer*>::const_iterator lay_it = allLayers.begin();
401 for (; lay_it != allLayers.end(); ++lay_it) {
402 CellCache* cache = (*lay_it)->getCellCache();
404 const std::vector<Zone*>& tmp_zones = cache->
getZones();
405 zones.insert(zones.end(), tmp_zones.begin(), tmp_zones.end());
410 std::map<Zone*, int32_t> zoneDistanceMap;
411 std::map<int32_t, Zone*> distanceZoneMap;
412 for (std::vector<Zone*>::iterator zit = zones.begin(); zit != zones.end(); ++zit) {
415 zoneDistanceMap.insert(std::pair<Zone*, int32_t>(*zit, distance));
416 distanceZoneMap.insert(std::pair<int32_t, Zone*>(distance, *zit));
419 int32_t startZone = zoneDistanceMap.find(
m_startZone)->second;
421 int32_t targetZone = zoneDistanceMap.find(
m_endZone)->second;
427 int32_t max_index = zones.size();
429 std::vector<int32_t> spt(max_index, -1);
431 std::vector<int32_t> sf(max_index, -1);
433 std::vector<double> costs(max_index, 0.0);
437 if (sortedfrontier.
empty()) {
442 next = topvalue.first;
445 if (targetZone == next) {
449 Zone* nextZone = distanceZoneMap.find(next)->second;
452 if (transCells.empty()) {
455 std::vector<Cell*>::iterator cell_it = transCells.begin();
456 for (; cell_it != transCells.end(); ++cell_it) {
464 int32_t nextInt = zoneDistanceMap.find(transCelle->
getZone())->second;
465 if (nextInt == next && nextInt != targetZone) {
469 double cost = costs[
next] +
static_cast<double>(
ABS(nextInt-startZone));
470 if (sf[nextInt] == -1) {
472 costs[nextInt] = cost;
474 }
else if (cost < costs[nextInt] && spt[nextInt] == -1) {
476 costs[nextInt] = cost;
484 int32_t current = targetZone;
485 int32_t end = startZone;
487 std::list<Zone*> betweenZones;
488 Zone* tempZone = distanceZoneMap.find(current)->second;
489 betweenZones.push_back(tempZone);
490 while(current != end) {
491 if (spt[current] < 0 ) {
494 current = spt[current];
495 tempZone = distanceZoneMap.find(current)->second;
496 betweenZones.push_front(tempZone);
500 for (std::list<Zone*>::iterator lit = betweenZones.begin(); lit != betweenZones.end(); ++lit) {
502 if (lit == betweenZones.end()) {
505 Zone* nextZone = *lit;
507 Zone* currentZone = *lit;
509 if (tempCells.empty()) {
513 Cell* transCell = NULL;
514 double nextCost = 0.0;
516 for (std::vector<Cell*>::iterator cit = tempCells.begin(); cit != tempCells.end(); ++cit) {
517 Cell* nextCell = *cit;
521 if (nextZone != transTargetCell->
getZone()) {
525 Location tmpLoc((*cit)->getLayer());
528 if (!transCell || locCost < nextCost) {
void createSearchFrontier(int32_t startInt, CellCache *cache)
Creates or resets the SearchFrontier.
CellCache * m_startCache
A pointer to the start CellCache.
Map * getMap() const
Get the map this layer is contained in.
int32_t getAngleBetween(const Location &loc1, const Location &loc2)
Gets angle of vector defined by given locations.
void setLayerCoordinates(const ModelCoordinate &coordinates)
Sets "cell precise" layer coordinates to this location.
Layer * m_layer
target layer
int32_t convertCoordToInt(const ModelCoordinate &coord) const
Convertes coordinate to unique identifier.
void setSearchStatus(const SearchStatus status)
Sets the current status of the search.
std::list< Location > Path
A path is a list with locations. Each location holds the coordinate for one cell. ...
int32_t getZStepRange()
Returns z-step range from object.
int32_t m_lastStartCoordInt
The last used start coordinate as an int32_t.
uint32_t next(octet_iterator &it, octet_iterator end)
Layer * getLayer()
Returns the current layer.
bool isCellInArea(const std::string &id, Cell *cell)
Returns true if cell is part of the area, otherwise false.
void setRouteStatus(RouteStatusInfo status)
Sets route status.
Layer * getLayer()
Returns layer.
void setLayer(Layer *layer)
Sets layer where this location is pointing to.
void calcPathStep()
Calculates path parts per layer.
A CellCache is an abstract depiction of one or a few layers and contains additional information...
int32_t getSearchStatus() const
A small function which returns the current status of the search.
bool m_specialCost
Indicates if the search should use special costs.
Location m_to
A location object representing where the search started.
CellCache * getCellCache()
Returns the CellCache of this layer.
MultiLayerSearch(Route *route, const int32_t sessionId)
Constructor.
int32_t m_destCoordInt
The destination coordinate as an int32_t.
~MultiLayerSearch()
Destructor.
void pushElement(const value_type &element)
Pushes a new element onto the queue.
Layer * getLayer() const
Gets the layer where this location is pointing to.
std::vector< int32_t > m_sf
The search frontier.
ModelCoordinate getLayerCoordinates() const
Gets cell precision layer coordinates set to this location.
void searchBetweenTargetsNeighbor()
Fetch targets from neighbor layers.
const value_type getPriorityElement(void) const
Retrieves the element with the highest priority.
const std::vector< Zone * > & getZones()
Returns zones of this CellCache.
ModelCoordinate convertIntToCoord(const int32_t cell) const
Convertes unique identifier to coordinate.
const std::list< std::string > getLimitedAreas()
CellCache * m_endCache
A pointer to the end CellCache.
double getAdjacentCost(const ModelCoordinate &adjacent, const ModelCoordinate &next)
Returns cost for movement between these two adjacent coordinates.
void setPath(const Path &path)
Sets the path for the route.
std::vector< int32_t > m_spt
The shortest path tree.
Simple class to hold the data for transistions.
virtual double getHeuristicCost(const ModelCoordinate &curpos, const ModelCoordinate &target)=0
Returns distance const from curpos to target point.
Cell * getCell(const ModelCoordinate &mc)
Returns cell on this coordinate.
bool isZoneProtected()
Returns whether the zone on this cell is protected.
std::vector< Cell * > m_ignoredBlockers
Blockers from a multi cell object which should be ignored.
CellTypeInfo getCellType()
Returns blocker type.
std::vector< Cell * > getTransitionCells(Layer *layer=NULL)
Returns transistion cells of this CellCache.
void searchBetweenTargetsMap()
Fetch targets from map.
const std::vector< Cell * > & getNeighbors()
Returns the layer coordinates of this cell.
Path m_path
Path to which all steps are added.
ExactModelCoordinate & getExactLayerCoordinatesRef()
Gets reference to exact layer coordinates.
A basic cell on a CellCache.
std::iterator_traits< octet_iterator >::difference_type distance(octet_iterator first, octet_iterator last)
CellGrid * getCellGrid() const
Get the Cellgrid.
void clear(void)
Removes all elements from the priority queue.
const ModelCoordinate getLayerCoordinates() const
Returns the layer coordinates of this cell.
Zone * getZone()
Returns zone.
std::vector< double > m_gCosts
A table to hold the costs.
void popElement(void)
Pops the element with the highest priority from the queue.
RoutePatherSearch using A*.
int32_t m_next
The next coordinate to check out.
const std::list< Layer * > & getLayers() const
Get the layers on this map.
const std::string & getCostId()
Returns cost identifier which is used for pathfinding.
void updateSearch()
Updates the search.
bool changeElementPriority(const index_type &index, const priority_type &newPriority)
Changes the priority of an element.
std::vector< ModelCoordinate > getOccupiedCells(int32_t rotation)
Returns relative coordinates for multi cell object based on rotation.
PriorityQueue< int32_t, double > m_sortedFrontier
Priority queue to hold nodes on the sf in order.
Location m_from
A location object representing where the search ended.
std::list< Cell * > m_betweenTargets
List of targets that need to be solved to reach the real target.
bool m_multicell
Indicates if the route is for a multi cell object.
int32_t m_lastDestCoordInt
The last used destination coordinate as an int32_t.
TransitionInfo * getTransition()
Returns the transition.
bool empty(void) const
Determines whether the queue is currently empty.
A pq which stores index-value pairs for elements.
double getLayerDistanceTo(const Location &location) const
Gets layer distance to another location.
CellCache * m_currentCache
A pointer to the currently used CellCache.
Route * m_route
Pointer to route.
std::vector< Cell * > getTransitionCells(Layer *layer=NULL)
Returns transistion cells of this zone.
int32_t getMaxIndex() const
Returns the number of cells on this CellCache.
A Zone is an abstract depiction of a CellCache or of a part of it.
ModelCoordinate m_mc
target coordinates
void calcPath()
Calculates final path.
bool m_foundLast
Indicates if last between target could be achieved.