FIFE  6e1afdbeda11afe9ac53e6023a4be96ef88f1dc6
multilayersearch.cpp
Go to the documentation of this file.
1 /***************************************************************************
2  * Copyright (C) 2005-2017 by the FIFE team *
3  * http://www.fifengine.net *
4  * This file is part of FIFE. *
5  * *
6  * FIFE is free software; you can redistribute it and/or *
7  * modify it under the terms of the GNU Lesser General Public *
8  * License as published by the Free Software Foundation; either *
9  * version 2.1 of the License, or (at your option) any later version. *
10  * *
11  * This library is distributed in the hope that it will be useful, *
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of *
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
14  * Lesser General Public License for more details. *
15  * *
16  * You should have received a copy of the GNU Lesser General Public *
17  * License along with this library; if not, write to the *
18  * Free Software Foundation, Inc., *
19  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA *
20  ***************************************************************************/
21 
22 // Standard C++ library includes
23 #include <algorithm>
24 
25 // 3rd party library includes
26 
27 // FIFE includes
28 // These includes are split up in two parts, separated by one empty line
29 // First block: files included from the FIFE root src directory
30 // Second block: files included from the same folder
32 #include "model/structures/layer.h"
34 #include "model/structures/cell.h"
35 #include "model/structures/map.h"
36 #include "pathfinder/route.h"
37 #include "util/math/fife_math.h"
38 
39 #include "multilayersearch.h"
40 
41 namespace FIFE {
42  MultiLayerSearch::MultiLayerSearch(Route* route, const int32_t sessionId):
43  RoutePatherSearch(route, sessionId),
44  m_to(route->getEndNode()),
45  m_from(route->getStartNode()),
46  m_startCache(m_from.getLayer()->getCellCache()),
47  m_endCache(m_to.getLayer()->getCellCache()),
48  m_currentCache(NULL),
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),
55  m_next(0),
56  m_foundLast(true) {
57 
58  // if end zone is invalid (static blocker) then change it
59  if (!m_endZone) {
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();
65  if (tmpzone) {
66  m_endZone = tmpzone;
67  if (tmpzone == m_startZone) {
68  break;
69  }
70  }
71  }
72  }
74 
75  // here we hope to find between targets
76  // first test if target can be reached easy
78  // if no betweenTargets could be found we check as second the whole map
79  if (m_betweenTargets.empty()) {
81  }
82  // if it is a protected cell it can have a second startzone
83  if (m_betweenTargets.empty() && startCell->isZoneProtected()) {
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();
88  if (tmpzone) {
89  if (tmpzone != m_startZone) {
90  m_startZone = tmpzone;
91  break;
92  }
93  }
94  }
96  if (m_betweenTargets.empty()) {
98  }
99  }
100  // failed to find between targets, no Path can be created
101  if (m_betweenTargets.empty()) {
104  }
105  }
106 
108  }
109 
110  void MultiLayerSearch::createSearchFrontier(int32_t startInt, CellCache* cache) {
111  // reset all
113  m_spt.clear();
114  m_sf.clear();
115  m_gCosts.clear();
116  // fill with defaults
118  int32_t max_index = cache->getMaxIndex();
119  m_spt.resize(max_index, -1);
120  m_sf.resize(max_index, -1);
121  m_gCosts.resize(max_index, 0.0);
122  m_next = 0;
123  }
124 
126  if (m_sortedFrontier.empty()) {
130  return;
131  }
132  if (m_betweenTargets.empty()) {
134  if (trans) {
136  }
139  } else {
140  if (m_lastDestCoordInt != -1) {
142  if (trans) {
144  }
145  }
146  m_currentCache = m_betweenTargets.front()->getLayer()->getCellCache();
147  m_lastDestCoordInt = m_betweenTargets.front()->getCellId();
148  m_betweenTargets.pop_front();
149  m_foundLast = false;
150  }
152  }
153 
156  m_next = topvalue.first;
157  m_spt[m_next] = m_sf[m_next];
158  // found destination
159  if (m_destCoordInt == m_next && m_betweenTargets.empty()) {
160  if (m_endCache == m_currentCache) {
163  return;
164  }
165  }
166 
167  // found between target
168  if (m_lastDestCoordInt == m_next) {
169  calcPathStep();
171  m_foundLast = true;
172  return;
173  }
174 
178  Cell* nextCell = m_currentCache->getCell(nextCoord);
179  if (!nextCell) {
180  return;
181  }
182  int32_t cellZ = nextCell->getLayerCoordinates().z;
183  int32_t maxZ = m_route->getZStepRange();
184  bool zLimited = maxZ != -1;
185  uint8_t blockerThreshold = m_ignoreDynamicBlockers ? 2 : 1;
186  bool limitedArea = m_route->isAreaLimited();
187  const std::vector<Cell*>& adjacents = nextCell->getNeighbors();
188  if (adjacents.empty()) {
189  return;
190  }
191  for (std::vector<Cell*>::const_iterator i = adjacents.begin(); i != adjacents.end(); ++i) {
192  if (*i == NULL) {
193  continue;
194  }
195  if ((*i)->getLayer()->getCellCache() != m_currentCache) {
196  continue;
197  }
198  int32_t adjacentInt = (*i)->getCellId();
199  if (m_sf[adjacentInt] != -1 && m_spt[adjacentInt] != -1) {
200  continue;
201  }
202  if (zLimited && ABS(cellZ-(*i)->getLayerCoordinates().z) > maxZ) {
203  continue;
204  }
205  bool blocker = (*i)->getCellType() > blockerThreshold;
206  ModelCoordinate adjacentCoord = (*i)->getLayerCoordinates();
207  if ((adjacentInt == m_next || blocker) && adjacentInt != m_destCoordInt) {
208  if (blocker && m_multicell) {
209  std::vector<Cell*>::iterator bc_it = std::find(m_ignoredBlockers.begin(), m_ignoredBlockers.end(), *i);
210  if (bc_it == m_ignoredBlockers.end()) {
211  continue;
212  }
213  } else {
214  continue;
215  }
216  }
217  // search if there are blockers which could block multicell object
218  if (m_multicell) {
219  blocker = false;
220  Location currentLoc(nextCell->getLayer());
221  currentLoc.setLayerCoordinates(nextCell->getLayerCoordinates());
222  Location adjacentLoc((*i)->getLayer());
223  adjacentLoc.setLayerCoordinates((*i)->getLayerCoordinates());
224 
225  int32_t rotation = getAngleBetween(currentLoc, adjacentLoc);
226  std::vector<ModelCoordinate> coords = grid->toMultiCoordinates(adjacentLoc.getLayerCoordinates(), m_route->getOccupiedCells(rotation));
227  std::vector<ModelCoordinate>::iterator coord_it = coords.begin();
228  for (; coord_it != coords.end(); ++coord_it) {
229  Cell* cell = m_currentCache->getCell(*coord_it);
230  if (cell) {
231  if (cell->getCellType() > blockerThreshold) {
232  std::vector<Cell*>::iterator bc_it = std::find(m_ignoredBlockers.begin(), m_ignoredBlockers.end(), cell);
233  if (bc_it == m_ignoredBlockers.end()) {
234  blocker = true;
235  break;
236  }
237  }
238  if (limitedArea) {
239  // check if cell is on one of the areas
240  bool sameAreas = false;
241  const std::list<std::string> areas = m_route->getLimitedAreas();
242  std::list<std::string>::const_iterator area_it = areas.begin();
243  for (; area_it != areas.end(); ++area_it) {
244  if (m_currentCache->isCellInArea(*area_it, cell)) {
245  sameAreas = true;
246  break;
247  }
248  }
249  if (!sameAreas) {
250  blocker = true;
251  break;
252  }
253  }
254  } else {
255  blocker = true;
256  break;
257  }
258  }
259  if (blocker) {
260  continue;
261  }
262  } else if (limitedArea) {
263  // check if cell is on one of the areas
264  bool sameAreas = false;
265  const std::list<std::string> areas = m_route->getLimitedAreas();
266  std::list<std::string>::const_iterator area_it = areas.begin();
267  for (; area_it != areas.end(); ++area_it) {
268  if (m_currentCache->isCellInArea(*area_it, *i)) {
269  sameAreas = true;
270  break;
271  }
272  }
273  if (!sameAreas) {
274  continue;
275  }
276  }
277 
278  double gCost = m_gCosts[m_next];
279  if (m_specialCost) {
280  gCost += m_currentCache->getAdjacentCost(adjacentCoord ,nextCoord, m_route->getCostId());
281  } else {
282  gCost += m_currentCache->getAdjacentCost(adjacentCoord ,nextCoord);
283  }
284  double hCost = grid->getHeuristicCost(adjacentCoord, destCoord);
285  if (m_sf[adjacentInt] == -1) {
287  m_gCosts[adjacentInt] = gCost;
288  m_sf[adjacentInt] = m_next;
289  } else if (gCost < m_gCosts[adjacentInt] && m_spt[adjacentInt] == -1) {
290  m_sortedFrontier.changeElementPriority(adjacentInt, gCost + hCost);
291  m_gCosts[adjacentInt] = gCost;
292  m_sf[adjacentInt] = m_next;
293  }
294  }
295  }
296 
298  int32_t current = m_lastDestCoordInt;
299  int32_t end = m_lastStartCoordInt;
300  Location newnode(m_currentCache->getLayer());
301  Path path;
302  // This assures that the agent always steps into the center of the target cell.
304  path.push_back(newnode);
305  while(current != end) {
306  if (m_spt[current] < 0 ) {
307  // This is when the size of m_spt can not handle the distance of the location
310  break;
311  }
312  current = m_spt[current];
313  newnode.setLayerCoordinates(m_currentCache->convertIntToCoord(current));
314  path.push_front(newnode);
315  }
316  // set exact start coordinates
317  if (m_path.empty()) {
318  path.front().setExactLayerCoordinates(m_from.getExactLayerCoordinatesRef());
319  }
320  m_path.insert(m_path.end(), path.begin(), path.end());
321  }
322 
324  int32_t current = m_lastDestCoordInt;
325  int32_t end = m_lastStartCoordInt;
326  Location newnode(m_currentCache->getLayer());
327  Path path;
328  // This assures that the agent always steps into the center of the target cell.
329  newnode.setLayerCoordinates(
330  m_currentCache->getCell(m_currentCache->convertIntToCoord(current))->getLayerCoordinates());
331  path.push_back(newnode);
332  while(current != end) {
333  if (m_spt[current] < 0 ) {
334  // This is when the size of m_spt can not handle the distance of the location
337  break;
338  }
339  current = m_spt[current];
340  newnode.setLayerCoordinates(m_currentCache->convertIntToCoord(current));
341  path.push_front(newnode);
342  }
343  m_path.insert(m_path.end(), path.begin(), path.end());
345  }
346 
348  std::vector<Cell*> cells = m_startCache->getTransitionCells(m_endCache->getLayer());
349  if (!cells.empty()) {
350  Location loc;
351  Cell* cell = NULL;
352  // find nearest portal (air-line distance)
353  for (std::vector<Cell*>::iterator it = cells.begin(); it != cells.end(); ++it) {
354  if ((*it)->getZone() != m_startZone) {
355  continue;
356  }
357  TransitionInfo* trans = (*it)->getTransition();
358  Cell* transTarget = trans->m_layer->getCellCache()->getCell(trans->m_mc);
359  if (transTarget->getZone() != m_endZone) {
360  continue;
361  }
362  if (!cell) {
363  loc.setLayer((*it)->getLayer());
364  loc.setLayerCoordinates((*it)->getLayerCoordinates());
365  cell = *it;
366  continue;
367  }
368  Location temp((*it)->getLayer());
369  temp.setLayerCoordinates((*it)->getLayerCoordinates());
370  Location loc1(cell->getTransition()->m_layer);
371  loc1.setLayerCoordinates(cell->getTransition()->m_mc);
372  Location loc2((*it)->getTransition()->m_layer);
373  loc2.setLayerCoordinates((*it)->getTransition()->m_mc);
374 
375  double temp_distance = temp.getLayerDistanceTo(m_from) + loc2.getLayerDistanceTo(m_to);
376  double current_distance = loc.getLayerDistanceTo(m_from) + loc1.getLayerDistanceTo(m_to);
377  if (current_distance > temp_distance) {
378  loc = temp;
379  cell = *it;
380  }
381  }
382  if (cell) {
383  m_betweenTargets.push_back(cell);
384  }
385  }
386  }
387 
389  // in case no transition is there then return
390  std::vector<Cell*> endTransCells;
391  std::vector<Cell*> tmpTransCells = m_endCache->getTransitionCells();
392  std::vector<Cell*>::iterator tcell_it = tmpTransCells.begin();
393  for (; tcell_it != tmpTransCells.end(); ++tcell_it) {
394  Zone* zone = (*tcell_it)->getZone();
395  if (zone == m_endZone) {
396  endTransCells.push_back(*tcell_it);
397  }
398  }
399  if (endTransCells.empty()) {
400  return;
401  }
402  // in case no transition is there then return
403  std::vector<Cell*> startTransCells;
404  tmpTransCells = m_startCache->getTransitionCells();
405  tcell_it = tmpTransCells.begin();
406  for (; tcell_it != tmpTransCells.end(); ++tcell_it) {
407  Zone* zone = (*tcell_it)->getZone();
408  if (zone == m_startZone) {
409  startTransCells.push_back(*tcell_it);
410  }
411  }
412  if (startTransCells.empty()) {
413  return;
414  }
415 
416  // fetch zones
417  std::vector<Zone*> zones;
418  const std::list<Layer*>& allLayers = m_from.getLayer()->getMap()->getLayers();
419  std::list<Layer*>::const_iterator lay_it = allLayers.begin();
420  for (; lay_it != allLayers.end(); ++lay_it) {
421  CellCache* cache = (*lay_it)->getCellCache();
422  if (cache) {
423  const std::vector<Zone*>& tmp_zones = cache->getZones();
424  zones.insert(zones.end(), tmp_zones.begin(), tmp_zones.end());
425  }
426  }
427 
428  // sort zones by iterator distance
429  std::map<Zone*, int32_t> zoneDistanceMap;
430  std::map<int32_t, Zone*> distanceZoneMap;
431  for (std::vector<Zone*>::iterator zit = zones.begin(); zit != zones.end(); ++zit) {
432  // pseudo distance
433  int32_t distance = std::distance(zones.begin(), zit);
434  zoneDistanceMap.insert(std::pair<Zone*, int32_t>(*zit, distance));
435  distanceZoneMap.insert(std::pair<int32_t, Zone*>(distance, *zit));
436  }
437  // start zone
438  int32_t startZone = zoneDistanceMap.find(m_startZone)->second;
439  // target zone
440  int32_t targetZone = zoneDistanceMap.find(m_endZone)->second;
441  // Priority queue to sort zones
442  PriorityQueue<int32_t, double> sortedfrontier;
443  // add start zone
444  sortedfrontier.pushElement(PriorityQueue<int32_t, double>::value_type(startZone, 0.0));
445  // max size zones
446  int32_t max_index = zones.size();
447  // shortest tree
448  std::vector<int32_t> spt(max_index, -1);
449  // search frontier
450  std::vector<int32_t> sf(max_index, -1);
451  // costs
452  std::vector<double> costs(max_index, 0.0);
453  bool found = false;
454  while (!found) {
455  if (sortedfrontier.empty()) {
456  break;
457  }
459  sortedfrontier.popElement();
460  int32_t next = topvalue.first;
461  spt[next] = sf[next];
462  // found destination zone
463  if (targetZone == next) {
464  found = true;
465  break;
466  }
467  Zone* nextZone = distanceZoneMap.find(next)->second;
468  // look in zone for tranistions
469  std::vector<Cell*> transCells = nextZone->getTransitionCells();
470  if (transCells.empty()) {
471  continue;
472  }
473  std::vector<Cell*>::iterator cell_it = transCells.begin();
474  for (; cell_it != transCells.end(); ++cell_it) {
475  // transition info
476  TransitionInfo* trans = (*cell_it)->getTransition();
477  // target transition cache
478  CellCache* transCache = trans->m_layer->getCellCache();
479  // target transition cell
480  Cell* transCelle = transCache->getCell(trans->m_mc);
481  // next zone as int
482  int32_t nextInt = zoneDistanceMap.find(transCelle->getZone())->second;
483  if (nextInt == next && nextInt != targetZone) {
484  continue;
485  }
486  // iterator distance as cost
487  double cost = costs[next] + static_cast<double>(ABS(nextInt-startZone));
488  if (sf[nextInt] == -1) {
489  sortedfrontier.pushElement(PriorityQueue<int32_t, double>::value_type(nextInt, cost));
490  costs[nextInt] = cost;
491  sf[nextInt] = next;
492  } else if (cost < costs[nextInt] && spt[nextInt] == -1) {
493  sortedfrontier.changeElementPriority(nextInt, cost);
494  costs[nextInt] = cost;
495  sf[nextInt] = next;
496  }
497  }
498  }
499  // startZone to endZone could be solved
500  if (found) {
501  // fetch sorted zones
502  int32_t current = targetZone;
503  int32_t end = startZone;
504 
505  std::list<Zone*> betweenZones;
506  Zone* tempZone = distanceZoneMap.find(current)->second;
507  betweenZones.push_back(tempZone);
508  while(current != end) {
509  if (spt[current] < 0 ) {
510  return;
511  }
512  current = spt[current];
513  tempZone = distanceZoneMap.find(current)->second;
514  betweenZones.push_front(tempZone);
515  }
516  // so here we fetch the transistions
517  Location lastLoc = m_from;
518  for (std::list<Zone*>::iterator lit = betweenZones.begin(); lit != betweenZones.end(); ++lit) {
519  ++lit;
520  if (lit == betweenZones.end()) {
521  break;
522  }
523  Zone* nextZone = *lit;
524  --lit;
525  Zone* currentZone = *lit;
526  std::vector<Cell*> tempCells = currentZone->getTransitionCells();
527  if (tempCells.empty()) {
528  continue;
529  }
530 
531  Cell* transCell = NULL;
532  double nextCost = 0.0;
533  Location newLoc = lastLoc;
534  for (std::vector<Cell*>::iterator cit = tempCells.begin(); cit != tempCells.end(); ++cit) {
535  Cell* nextCell = *cit;
536  TransitionInfo* nextTrans = nextCell->getTransition();
537  Cell* transTargetCell = nextTrans->m_layer->getCellCache()->getCell(nextTrans->m_mc);
538  // skip wrong transitions
539  if (nextZone != transTargetCell->getZone()) {
540  continue;
541  }
542  // nearest transistion (air-line distance)
543  Location tmpLoc((*cit)->getLayer());
544  tmpLoc.setLayerCoordinates((*cit)->getLayerCoordinates());
545  double locCost = lastLoc.getLayerDistanceTo(tmpLoc);
546  if (!transCell || locCost < nextCost) {
547  nextCost = locCost;
548  transCell = *cit;
549  newLoc.setLayer(transTargetCell->getLayer());
550  newLoc.setLayerCoordinates(transTargetCell->getLayerCoordinates());
551  }
552  }
553  // found valid transition cell
554  if (transCell) {
555  m_betweenTargets.push_back(transCell);
556  lastLoc = newLoc;
557  }
558  }
559  }
560  }
561 }
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.
Definition: layer.cpp:89
virtual std::vector< ModelCoordinate > toMultiCoordinates(const ModelCoordinate &position, const std::vector< ModelCoordinate > &orig, bool reverse=false)=0
Returns point vector with coordinates for a multi object.
int32_t getAngleBetween(const Location &loc1, const Location &loc2)
Gets angle of vector defined by given locations.
Definition: angles.cpp:98
void setLayerCoordinates(const ModelCoordinate &coordinates)
Sets "cell precise" layer coordinates to this location.
Definition: location.cpp:94
Layer * m_layer
target layer
Definition: cell.h:85
int32_t convertCoordToInt(const ModelCoordinate &coord) const
Convertes coordinate to unique identifier.
Definition: cellcache.cpp:835
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. ...
Definition: ipather.h:38
#define ABS(x)
Definition: fife_math.h:41
int32_t getZStepRange()
Returns z-step range from object.
Definition: route.cpp:270
int32_t m_lastStartCoordInt
The last used start coordinate as an int32_t.
uint32_t next(octet_iterator &it, octet_iterator end)
Definition: checked.h:137
Layer * getLayer()
Returns the current layer.
Definition: cell.cpp:540
bool isCellInArea(const std::string &id, Cell *cell)
Returns true if cell is part of the area, otherwise false.
Definition: cellcache.cpp:1482
void setRouteStatus(RouteStatusInfo status)
Sets route status.
Definition: route.cpp:57
Layer * getLayer()
Returns layer.
Definition: cellcache.cpp:802
void setLayer(Layer *layer)
Sets layer where this location is pointing to.
Definition: location.cpp:79
void calcPathStep()
Calculates path parts per layer.
A CellCache is an abstract depiction of one or a few layers and contains additional information...
Definition: cellcache.h:111
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.
Definition: layer.cpp:573
MultiLayerSearch(Route *route, const int32_t sessionId)
Constructor.
int32_t m_destCoordInt
The destination coordinate as an int32_t.
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.
Definition: location.cpp:83
std::vector< int32_t > m_sf
The search frontier.
ModelCoordinate getLayerCoordinates() const
Gets cell precision layer coordinates set to this location.
Definition: location.cpp:113
A basic route.
Definition: route.h:64
void searchBetweenTargetsNeighbor()
Fetch targets from neighbor layers.
const value_type getPriorityElement(void) const
Retrieves the element with the highest priority.
Definition: priorityqueue.h:99
const std::vector< Zone * > & getZones()
Returns zones of this CellCache.
Definition: cellcache.cpp:1273
ModelCoordinate convertIntToCoord(const int32_t cell) const
Convertes unique identifier to coordinate.
Definition: cellcache.cpp:840
const std::list< std::string > getLimitedAreas()
Definition: route.cpp:286
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.
Definition: cellcache.cpp:1102
void setPath(const Path &path)
Sets the path for the route.
Definition: route.cpp:163
unsigned char uint8_t
Definition: core.h:38
std::vector< int32_t > m_spt
The shortest path tree.
Simple class to hold the data for transistions.
Definition: cell.h:82
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.
Definition: cellcache.cpp:706
bool isZoneProtected()
Returns whether the zone on this cell is protected.
Definition: cell.cpp:487
std::vector< Cell * > m_ignoredBlockers
Blockers from a multi cell object which should be ignored.
CellTypeInfo getCellType()
Returns blocker type.
Definition: cell.cpp:495
std::vector< Cell * > getTransitionCells(Layer *layer=NULL)
Returns transistion cells of this CellCache.
Definition: cellcache.cpp:1234
void searchBetweenTargetsMap()
Fetch targets from map.
bool m_ignoreDynamicBlockers
Indicates if dynamic blockers should be ignored.
bool isAreaLimited()
Definition: route.cpp:277
const std::vector< Cell * > & getNeighbors()
Returns the layer coordinates of this cell.
Definition: cell.cpp:523
Path m_path
Path to which all steps are added.
ExactModelCoordinate & getExactLayerCoordinatesRef()
Gets reference to exact layer coordinates.
Definition: location.cpp:105
A basic cell on a CellCache.
Definition: cell.h:136
std::iterator_traits< octet_iterator >::difference_type distance(octet_iterator first, octet_iterator last)
Definition: checked.h:198
CellGrid * getCellGrid() const
Get the Cellgrid.
Definition: layer.cpp:93
void clear(void)
Removes all elements from the priority queue.
const ModelCoordinate getLayerCoordinates() const
Returns the layer coordinates of this cell.
Definition: cell.cpp:515
Zone * getZone()
Returns zone.
Definition: cell.cpp:466
std::vector< double > m_gCosts
A table to hold the costs.
void popElement(void)
Pops the element with the highest priority from the queue.
A 3D Point.
Definition: point.h:205
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.
Definition: map.h:120
const std::string & getCostId()
Returns cost identifier which is used for pathfinding.
Definition: route.cpp:243
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.
Definition: route.cpp:262
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.
Definition: cell.cpp:585
bool empty(void) const
Determines whether the queue is currently empty.
A pq which stores index-value pairs for elements.
Definition: priorityqueue.h:36
double getLayerDistanceTo(const Location &location) const
Gets layer distance to another location.
Definition: location.cpp:180
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.
Definition: cellcache.cpp:310
int32_t getMaxIndex() const
Returns the number of cells on this CellCache.
Definition: cellcache.cpp:845
A Zone is an abstract depiction of a CellCache or of a part of it.
Definition: cellcache.h:50
ModelCoordinate m_mc
target coordinates
Definition: cell.h:89
void calcPath()
Calculates final path.
bool m_foundLast
Indicates if last between target could be achieved.