FIFE
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
multilayersearch.cpp
Go to the documentation of this file.
1 /***************************************************************************
2  * Copyright (C) 2005-2013 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  const std::vector<Cell*>& adjacents = nextCell->getNeighbors();
186  if (adjacents.empty()) {
187  return;
188  }
189  for (std::vector<Cell*>::const_iterator i = adjacents.begin(); i != adjacents.end(); ++i) {
190  if (*i == NULL) {
191  continue;
192  }
193  if ((*i)->getLayer()->getCellCache() != m_currentCache) {
194  continue;
195  }
196  int32_t adjacentInt = (*i)->getCellId();
197  if (m_sf[adjacentInt] != -1 && m_spt[adjacentInt] != -1) {
198  continue;
199  }
200  if (zLimited && ABS(cellZ-(*i)->getLayerCoordinates().z) > maxZ) {
201  continue;
202  }
203  bool blocker = (*i)->getCellType() != CTYPE_NO_BLOCKER;
204  ModelCoordinate adjacentCoord = (*i)->getLayerCoordinates();
205  if ((adjacentInt == m_next || blocker) && adjacentInt != m_destCoordInt) {
206  if (blocker && m_multicell) {
207  std::vector<Cell*>::iterator bc_it = std::find(m_ignoredBlockers.begin(), m_ignoredBlockers.end(), *i);
208  if (bc_it == m_ignoredBlockers.end()) {
209  continue;
210  }
211  } else {
212  continue;
213  }
214  }
215  // search if there are blockers which could block multicell object
216  if (m_multicell) {
217  blocker = false;
218  Location currentLoc(nextCell->getLayer());
219  currentLoc.setLayerCoordinates(nextCell->getLayerCoordinates());
220  Location adjacentLoc((*i)->getLayer());
221  adjacentLoc.setLayerCoordinates((*i)->getLayerCoordinates());
222 
223  int32_t rotation = getAngleBetween(currentLoc, adjacentLoc);
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) {
227  Cell* cell = m_currentCache->getCell(*coord_it);
228  if (cell) {
229  if (cell->getCellType() != CTYPE_NO_BLOCKER) {
230  std::vector<Cell*>::iterator bc_it = std::find(m_ignoredBlockers.begin(), m_ignoredBlockers.end(), cell);
231  if (bc_it == m_ignoredBlockers.end()) {
232  blocker = true;
233  break;
234  }
235  }
236  }
237  }
238  if (blocker) {
239  continue;
240  }
241  }
242 
243  if (m_route->isAreaLimited()) {
244  // check if cell is on one of the areas
245  bool sameAreas = false;
246  const std::list<std::string> areas = m_route->getLimitedAreas();
247  std::list<std::string>::const_iterator area_it = areas.begin();
248  for (; area_it != areas.end(); ++area_it) {
249  if (m_currentCache->isCellInArea(*area_it, *i)) {
250  sameAreas = true;
251  break;
252  }
253  }
254  if (!sameAreas) {
255  continue;
256  }
257  }
258 
259  double gCost = m_gCosts[m_next];
260  if (m_specialCost) {
261  gCost += m_currentCache->getAdjacentCost(adjacentCoord ,nextCoord, m_route->getCostId());
262  } else {
263  gCost += m_currentCache->getAdjacentCost(adjacentCoord ,nextCoord);
264  }
265  double hCost = grid->getHeuristicCost(adjacentCoord, destCoord);
266  if (m_sf[adjacentInt] == -1) {
268  m_gCosts[adjacentInt] = gCost;
269  m_sf[adjacentInt] = m_next;
270  } else if (gCost < m_gCosts[adjacentInt] && m_spt[adjacentInt] == -1) {
271  m_sortedFrontier.changeElementPriority(adjacentInt, gCost + hCost);
272  m_gCosts[adjacentInt] = gCost;
273  m_sf[adjacentInt] = m_next;
274  }
275  }
276  }
277 
279  int32_t current = m_lastDestCoordInt;
280  int32_t end = m_lastStartCoordInt;
281  Location newnode(m_currentCache->getLayer());
282  Path path;
283  // This assures that the agent always steps into the center of the target cell.
285  path.push_back(newnode);
286  while(current != end) {
287  if (m_spt[current] < 0 ) {
288  // This is when the size of m_spt can not handle the distance of the location
291  break;
292  }
293  current = m_spt[current];
294  newnode.setLayerCoordinates(m_currentCache->convertIntToCoord(current));
295  path.push_front(newnode);
296  }
297  // set exact start coordinates
298  if (m_path.empty()) {
299  path.front().setExactLayerCoordinates(m_from.getExactLayerCoordinatesRef());
300  }
301  m_path.insert(m_path.end(), path.begin(), path.end());
302  }
303 
305  int32_t current = m_lastDestCoordInt;
306  int32_t end = m_lastStartCoordInt;
307  Location newnode(m_currentCache->getLayer());
308  Path path;
309  // This assures that the agent always steps into the center of the target cell.
310  newnode.setLayerCoordinates(
311  m_currentCache->getCell(m_currentCache->convertIntToCoord(current))->getLayerCoordinates());
312  path.push_back(newnode);
313  while(current != end) {
314  if (m_spt[current] < 0 ) {
315  // This is when the size of m_spt can not handle the distance of the location
318  break;
319  }
320  current = m_spt[current];
321  newnode.setLayerCoordinates(m_currentCache->convertIntToCoord(current));
322  path.push_front(newnode);
323  }
324  m_path.insert(m_path.end(), path.begin(), path.end());
326  }
327 
329  std::vector<Cell*> cells = m_startCache->getTransitionCells(m_endCache->getLayer());
330  if (!cells.empty()) {
331  Location loc;
332  Cell* cell = NULL;
333  // find nearest portal (air-line distance)
334  for (std::vector<Cell*>::iterator it = cells.begin(); it != cells.end(); ++it) {
335  if ((*it)->getZone() != m_startZone) {
336  continue;
337  }
338  TransitionInfo* trans = (*it)->getTransition();
339  Cell* transTarget = trans->m_layer->getCellCache()->getCell(trans->m_mc);
340  if (transTarget->getZone() != m_endZone) {
341  continue;
342  }
343  if (!cell) {
344  loc.setLayer((*it)->getLayer());
345  loc.setLayerCoordinates((*it)->getLayerCoordinates());
346  cell = *it;
347  continue;
348  }
349  Location temp((*it)->getLayer());
350  temp.setLayerCoordinates((*it)->getLayerCoordinates());
351  Location loc1(cell->getTransition()->m_layer);
352  loc1.setLayerCoordinates(cell->getTransition()->m_mc);
353  Location loc2((*it)->getTransition()->m_layer);
354  loc2.setLayerCoordinates((*it)->getTransition()->m_mc);
355 
356  double temp_distance = temp.getLayerDistanceTo(m_from) + loc2.getLayerDistanceTo(m_to);
357  double current_distance = loc.getLayerDistanceTo(m_from) + loc1.getLayerDistanceTo(m_to);
358  if (current_distance > temp_distance) {
359  loc = temp;
360  cell = *it;
361  }
362  }
363  if (cell) {
364  m_betweenTargets.push_back(cell);
365  }
366  }
367  }
368 
370  // in case no transition is there then return
371  std::vector<Cell*> endTransCells;
372  std::vector<Cell*> tmpTransCells = m_endCache->getTransitionCells();
373  std::vector<Cell*>::iterator tcell_it = tmpTransCells.begin();
374  for (; tcell_it != tmpTransCells.end(); ++tcell_it) {
375  Zone* zone = (*tcell_it)->getZone();
376  if (zone == m_endZone) {
377  endTransCells.push_back(*tcell_it);
378  }
379  }
380  if (endTransCells.empty()) {
381  return;
382  }
383  // in case no transition is there then return
384  std::vector<Cell*> startTransCells;
385  tmpTransCells = m_startCache->getTransitionCells();
386  tcell_it = tmpTransCells.begin();
387  for (; tcell_it != tmpTransCells.end(); ++tcell_it) {
388  Zone* zone = (*tcell_it)->getZone();
389  if (zone == m_startZone) {
390  startTransCells.push_back(*tcell_it);
391  }
392  }
393  if (startTransCells.empty()) {
394  return;
395  }
396 
397  // fetch zones
398  std::vector<Zone*> zones;
399  const std::list<Layer*>& allLayers = m_from.getLayer()->getMap()->getLayers();
400  std::list<Layer*>::const_iterator lay_it = allLayers.begin();
401  for (; lay_it != allLayers.end(); ++lay_it) {
402  CellCache* cache = (*lay_it)->getCellCache();
403  if (cache) {
404  const std::vector<Zone*>& tmp_zones = cache->getZones();
405  zones.insert(zones.end(), tmp_zones.begin(), tmp_zones.end());
406  }
407  }
408 
409  // sort zones by iterator distance
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) {
413  // pseudo distance
414  int32_t distance = std::distance(zones.begin(), zit);
415  zoneDistanceMap.insert(std::pair<Zone*, int32_t>(*zit, distance));
416  distanceZoneMap.insert(std::pair<int32_t, Zone*>(distance, *zit));
417  }
418  // start zone
419  int32_t startZone = zoneDistanceMap.find(m_startZone)->second;
420  // target zone
421  int32_t targetZone = zoneDistanceMap.find(m_endZone)->second;
422  // Priority queue to sort zones
423  PriorityQueue<int32_t, double> sortedfrontier;
424  // add start zone
425  sortedfrontier.pushElement(PriorityQueue<int32_t, double>::value_type(startZone, 0.0));
426  // max size zones
427  int32_t max_index = zones.size();
428  // shortest tree
429  std::vector<int32_t> spt(max_index, -1);
430  // search frontier
431  std::vector<int32_t> sf(max_index, -1);
432  // costs
433  std::vector<double> costs(max_index, 0.0);
434  int32_t next = 0;
435  bool found = false;
436  while (!found) {
437  if (sortedfrontier.empty()) {
438  break;
439  }
441  sortedfrontier.popElement();
442  next = topvalue.first;
443  spt[next] = sf[next];
444  // found destination zone
445  if (targetZone == next) {
446  found = true;
447  break;
448  }
449  Zone* nextZone = distanceZoneMap.find(next)->second;
450  // look in zone for tranistions
451  std::vector<Cell*> transCells = nextZone->getTransitionCells();
452  if (transCells.empty()) {
453  continue;
454  }
455  std::vector<Cell*>::iterator cell_it = transCells.begin();
456  for (; cell_it != transCells.end(); ++cell_it) {
457  // transition info
458  TransitionInfo* trans = (*cell_it)->getTransition();
459  // target transition cache
460  CellCache* transCache = trans->m_layer->getCellCache();
461  // target transition cell
462  Cell* transCelle = transCache->getCell(trans->m_mc);
463  // next zone as int
464  int32_t nextInt = zoneDistanceMap.find(transCelle->getZone())->second;
465  if (nextInt == next && nextInt != targetZone) {
466  continue;
467  }
468  // iterator distance as cost
469  double cost = costs[next] + static_cast<double>(ABS(nextInt-startZone));
470  if (sf[nextInt] == -1) {
471  sortedfrontier.pushElement(PriorityQueue<int32_t, double>::value_type(nextInt, cost));
472  costs[nextInt] = cost;
473  sf[nextInt] = next;
474  } else if (cost < costs[nextInt] && spt[nextInt] == -1) {
475  sortedfrontier.changeElementPriority(nextInt, cost);
476  costs[nextInt] = cost;
477  sf[nextInt] = next;
478  }
479  }
480  }
481  // startZone to endZone could be solved
482  if (found) {
483  // fetch sorted zones
484  int32_t current = targetZone;
485  int32_t end = startZone;
486 
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 ) {
492  return;
493  }
494  current = spt[current];
495  tempZone = distanceZoneMap.find(current)->second;
496  betweenZones.push_front(tempZone);
497  }
498  // so here we fetch the transistions
499  Location lastLoc = m_from;
500  for (std::list<Zone*>::iterator lit = betweenZones.begin(); lit != betweenZones.end(); ++lit) {
501  ++lit;
502  if (lit == betweenZones.end()) {
503  break;
504  }
505  Zone* nextZone = *lit;
506  --lit;
507  Zone* currentZone = *lit;
508  std::vector<Cell*> tempCells = currentZone->getTransitionCells();
509  if (tempCells.empty()) {
510  continue;
511  }
512 
513  Cell* transCell = NULL;
514  double nextCost = 0.0;
515  Location newLoc = lastLoc;
516  for (std::vector<Cell*>::iterator cit = tempCells.begin(); cit != tempCells.end(); ++cit) {
517  Cell* nextCell = *cit;
518  TransitionInfo* nextTrans = nextCell->getTransition();
519  Cell* transTargetCell = nextTrans->m_layer->getCellCache()->getCell(nextTrans->m_mc);
520  // skip wrong transitions
521  if (nextZone != transTargetCell->getZone()) {
522  continue;
523  }
524  // nearest transistion (air-line distance)
525  Location tmpLoc((*cit)->getLayer());
526  tmpLoc.setLayerCoordinates((*cit)->getLayerCoordinates());
527  double locCost = lastLoc.getLayerDistanceTo(tmpLoc);
528  if (!transCell || locCost < nextCost) {
529  nextCost = locCost;
530  transCell = *cit;
531  newLoc.setLayer(transTargetCell->getLayer());
532  newLoc.setLayerCoordinates(transTargetCell->getLayerCoordinates());
533  }
534  }
535  // found valid transition cell
536  if (transCell) {
537  m_betweenTargets.push_back(transCell);
538  lastLoc = newLoc;
539  }
540  }
541  }
542  }
543 }
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:88
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 &quot;cell precise&quot; 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:40
int32_t getZStepRange()
Returns z-step range from object.
Definition: route.cpp:268
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:136
Layer * getLayer()
Returns the current layer.
Definition: cell.cpp:521
bool isCellInArea(const std::string &id, Cell *cell)
Returns true if cell is part of the area, otherwise false.
Definition: cellcache.cpp:1488
void setRouteStatus(RouteStatusInfo status)
Sets route status.
Definition: route.cpp:55
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:453
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:1279
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:284
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:1108
void setPath(const Path &path)
Sets the path for the route.
Definition: route.cpp:161
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:468
std::vector< Cell * > m_ignoredBlockers
Blockers from a multi cell object which should be ignored.
CellTypeInfo getCellType()
Returns blocker type.
Definition: cell.cpp:476
std::vector< Cell * > getTransitionCells(Layer *layer=NULL)
Returns transistion cells of this CellCache.
Definition: cellcache.cpp:1240
void searchBetweenTargetsMap()
Fetch targets from map.
bool isAreaLimited()
Definition: route.cpp:275
const std::vector< Cell * > & getNeighbors()
Returns the layer coordinates of this cell.
Definition: cell.cpp:504
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:187
CellGrid * getCellGrid() const
Get the Cellgrid.
Definition: layer.cpp:92
void clear(void)
Removes all elements from the priority queue.
const ModelCoordinate getLayerCoordinates() const
Returns the layer coordinates of this cell.
Definition: cell.cpp:496
Zone * getZone()
Returns zone.
Definition: cell.cpp:447
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:202
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:119
const std::string & getCostId()
Returns cost identifier which is used for pathfinding.
Definition: route.cpp:241
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:260
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:566
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.