FIFE  be64c707dea6b3250bd4355bf5c825d25920087d
singlelayersearch.cpp
Go to the documentation of this file.
1 /***************************************************************************
2  * Copyright (C) 2005-2019 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 "pathfinder/route.h"
36 #include "util/math/fife_math.h"
37 
38 #include "singlelayersearch.h"
39 
40 namespace FIFE {
41  SingleLayerSearch::SingleLayerSearch(Route* route, const int32_t sessionId):
42  RoutePatherSearch(route, sessionId),
43  m_to(route->getEndNode()),
44  m_from(route->getStartNode()),
45  m_cellCache(m_from.getLayer()->getCellCache()),
46  m_startCoordInt(m_cellCache->convertCoordToInt(m_from.getLayerCoordinates())),
47  m_destCoordInt(m_cellCache->convertCoordToInt(m_to.getLayerCoordinates())),
48  m_next(0) {
49 
51  int32_t max_index = m_cellCache->getMaxIndex();
52  m_spt.resize(max_index, -1);
53  m_sf.resize(max_index, -1);
54  m_gCosts.resize(max_index, 0.0);
55  }
56 
58  }
59 
61  if(m_sortedfrontier.empty()) {
64  return;
65  }
66 
69  m_next = topvalue.first;
70  m_spt[m_next] = m_sf[m_next];
71  // found destination
72  if (m_destCoordInt == m_next) {
75  return;
76  }
77 
81  Cell* nextCell = m_cellCache->getCell(nextCoord);
82  if (!nextCell) {
83  return;
84  }
85  int32_t cellZ = nextCell->getLayerCoordinates().z;
86  int32_t maxZ = m_route->getZStepRange();
87  bool zLimited = maxZ != -1;
88  uint8_t blockerThreshold = m_ignoreDynamicBlockers ? 2 : 1;
89  bool limitedArea = m_route->isAreaLimited();
90  const std::vector<Cell*>& adjacents = nextCell->getNeighbors();
91  for (std::vector<Cell*>::const_iterator i = adjacents.begin(); i != adjacents.end(); ++i) {
92  if (*i == NULL) {
93  continue;
94  }
95  if ((*i)->getLayer()->getCellCache() != m_cellCache) {
96  continue;
97  }
98  int32_t adjacentInt = (*i)->getCellId();
99  if (m_sf[adjacentInt] != -1 && m_spt[adjacentInt] != -1) {
100  continue;
101  }
102  if (zLimited && ABS(cellZ-(*i)->getLayerCoordinates().z) > maxZ) {
103  continue;
104  }
105  bool blocker = (*i)->getCellType() > blockerThreshold;
106  ModelCoordinate adjacentCoord = (*i)->getLayerCoordinates();
107  if ((adjacentInt == m_next || blocker) && adjacentInt != m_destCoordInt) {
108  if (!blocker && m_multicell) {
109  continue;
110  } else if (!m_multicell){
111  continue;
112  }
113  }
114  // search if there are blockers which could block multicell object
115  if (m_multicell) {
116  blocker = false;
117  Location currentLoc(nextCell->getLayer());
118  currentLoc.setLayerCoordinates(nextCell->getLayerCoordinates());
119  Location adjacentLoc((*i)->getLayer());
120  adjacentLoc.setLayerCoordinates((*i)->getLayerCoordinates());
121 
122  int32_t rotation = getAngleBetween(currentLoc, adjacentLoc);
123  std::vector<ModelCoordinate> coords = grid->toMultiCoordinates(adjacentLoc.getLayerCoordinates(), m_route->getOccupiedCells(rotation));
124  std::vector<ModelCoordinate>::iterator coord_it = coords.begin();
125  for (; coord_it != coords.end(); ++coord_it) {
126  Cell* cell = m_cellCache->getCell(*coord_it);
127  if (cell) {
128  if (cell->getCellType() > blockerThreshold) {
129  std::vector<Cell*>::iterator bc_it = std::find(m_ignoredBlockers.begin(), m_ignoredBlockers.end(), cell);
130  if (bc_it == m_ignoredBlockers.end()) {
131  blocker = true;
132  break;
133  }
134  }
135  if (limitedArea) {
136  // check if cell is on one of the areas
137  bool sameAreas = false;
138  const std::list<std::string> areas = m_route->getLimitedAreas();
139  std::list<std::string>::const_iterator area_it = areas.begin();
140  for (; area_it != areas.end(); ++area_it) {
141  if (m_cellCache->isCellInArea(*area_it, cell)) {
142  sameAreas = true;
143  break;
144  }
145  }
146  if (!sameAreas) {
147  blocker = true;
148  break;
149  }
150  }
151  } else {
152  blocker = true;
153  break;
154  }
155  }
156  if (blocker) {
157  continue;
158  }
159  } else if (limitedArea) {
160  // check if cell is on one of the areas
161  bool sameAreas = false;
162  const std::list<std::string> areas = m_route->getLimitedAreas();
163  std::list<std::string>::const_iterator area_it = areas.begin();
164  for (; area_it != areas.end(); ++area_it) {
165  if (m_cellCache->isCellInArea(*area_it, *i)) {
166  sameAreas = true;
167  break;
168  }
169  }
170  if (!sameAreas) {
171  continue;
172  }
173  }
174 
175  double gCost = m_gCosts[m_next];
176  if (m_specialCost) {
177  gCost += m_cellCache->getAdjacentCost(adjacentCoord ,nextCoord, m_route->getCostId());
178  } else {
179  gCost += m_cellCache->getAdjacentCost(adjacentCoord ,nextCoord);
180  }
181  double hCost = grid->getHeuristicCost(adjacentCoord, destCoord);
182  if (m_sf[adjacentInt] == -1) {
184  m_gCosts[adjacentInt] = gCost;
185  m_sf[adjacentInt] = m_next;
186  } else if (gCost < m_gCosts[adjacentInt] && m_spt[adjacentInt] == -1) {
187  m_sortedfrontier.changeElementPriority(adjacentInt, gCost + hCost);
188  m_gCosts[adjacentInt] = gCost;
189  m_sf[adjacentInt] = m_next;
190  }
191  }
192  }
193 
195  int32_t current = m_destCoordInt;
196  int32_t end = m_startCoordInt;
197  Path path;
198  Location newnode(m_cellCache->getLayer());
199  // This assures that the agent always steps into the center of the cell.
201  path.push_back(newnode);
202  while(current != end) {
203  if (m_spt[current] < 0 ) {
204  // This is when the size of m_spt can not handle the distance of the location
207  break;
208  }
209  current = m_spt[current];
210  ModelCoordinate currentCoord = m_cellCache->convertIntToCoord(current);
211  newnode.setLayerCoordinates(currentCoord);
212  path.push_front(newnode);
213  }
214  path.front().setExactLayerCoordinates(m_from.getExactLayerCoordinatesRef());
215  m_route->setPath(path);
216  }
217 }
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 m_destCoordInt
The destination coordinate as an int32_t.
PriorityQueue< int32_t, double > m_sortedfrontier
Priority queue to hold nodes on the sf in order.
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
int32_t m_next
The next coordinate to check out.
void setSearchStatus(const SearchStatus status)
Sets the current status of the search.
int32_t getMaxIndex() const
Returns the number of cells on this CellCache.
Definition: cellcache.cpp:843
void setExactLayerCoordinates(const ExactModelCoordinate &coordinates)
Sets precise layer coordinates to this location.
Definition: location.cpp:87
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
bool empty(void) const
Determines whether the queue is currently empty.
Layer * getLayer()
Returns the current layer.
Definition: cell.cpp:335
Location m_from
A location object representing where the search ended.
bool isCellInArea(const std::string &id, Cell *cell)
Returns true if cell is part of the area, otherwise false.
Definition: cellcache.cpp:1491
void setRouteStatus(RouteStatusInfo status)
Sets route status.
Definition: route.cpp:57
Layer * getLayer()
Returns layer.
Definition: cellcache.cpp:800
int32_t m_startCoordInt
The start coordinate as an int32_t.
bool m_specialCost
Indicates if the search should use special costs.
std::vector< int32_t > m_spt
The shortest path tree.
void pushElement(const value_type &element)
Pushes a new element onto the queue.
CellCache * m_cellCache
A pointer to the CellCache.
A basic route.
Definition: route.h:64
const std::list< std::string > getLimitedAreas()
Definition: route.cpp:286
void updateSearch()
Updates the search.
double getAdjacentCost(const ModelCoordinate &adjacent, const ModelCoordinate &next)
Returns cost for movement between these two adjacent coordinates.
Definition: cellcache.cpp:1111
void setPath(const Path &path)
Sets the path for the route.
Definition: route.cpp:163
unsigned char uint8_t
Definition: core.h:38
Location m_to
A location object representing where the search started.
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:704
std::vector< Cell * > m_ignoredBlockers
Blockers from a multi cell object which should be ignored.
CellTypeInfo getCellType()
Returns blocker type.
Definition: cell.cpp:290
bool m_ignoreDynamicBlockers
Indicates if dynamic blockers should be ignored.
bool isAreaLimited()
Definition: route.cpp:277
const ModelCoordinate getLayerCoordinates() const
Returns the layer coordinates of this cell.
Definition: cell.cpp:310
const value_type getPriorityElement(void) const
Retrieves the element with the highest priority.
Definition: priorityqueue.h:99
const std::vector< Cell * > & getNeighbors()
Returns the layer coordinates of this cell.
Definition: cell.cpp:318
ExactModelCoordinate & getExactLayerCoordinatesRef()
Gets reference to exact layer coordinates.
Definition: location.cpp:105
A basic cell on a CellCache.
Definition: cell.h:123
ModelCoordinate convertIntToCoord(const int32_t cell) const
Convertes unique identifier to coordinate.
Definition: cellcache.cpp:838
void calcPath()
Calculates final path.
CellGrid * getCellGrid() const
Get the Cellgrid.
Definition: layer.cpp:93
void popElement(void)
Pops the element with the highest priority from the queue.
A 3D Point.
Definition: point.h:205
RoutePatherSearch using A*.
SingleLayerSearch(Route *route, const int32_t sessionId)
Constructor.
DoublePoint intPt2doublePt(Point pt)
Convert from 2D int32_t point to 2D double point.
Definition: point.h:349
const std::string & getCostId()
Returns cost identifier which is used for pathfinding.
Definition: route.cpp:243
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
ModelCoordinate getLayerCoordinates() const
Gets cell precision layer coordinates set to this location.
Definition: location.cpp:113
bool m_multicell
Indicates if the route is for a multi cell object.
std::vector< int32_t > m_sf
The search frontier.
A pq which stores index-value pairs for elements.
Definition: priorityqueue.h:36
Route * m_route
Pointer to route.
std::vector< double > m_gCosts
A table to hold the costs.