FIFE
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
singlelayersearch.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 "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  const std::vector<Cell*>& adjacents = nextCell->getNeighbors();
89  for (std::vector<Cell*>::const_iterator i = adjacents.begin(); i != adjacents.end(); ++i) {
90  if (*i == NULL) {
91  continue;
92  }
93  if ((*i)->getLayer()->getCellCache() != m_cellCache) {
94  continue;
95  }
96  int32_t adjacentInt = (*i)->getCellId();
97  if (m_sf[adjacentInt] != -1 && m_spt[adjacentInt] != -1) {
98  continue;
99  }
100  if (zLimited && ABS(cellZ-(*i)->getLayerCoordinates().z) > maxZ) {
101  continue;
102  }
103  bool blocker = (*i)->getCellType() != CTYPE_NO_BLOCKER;
104  ModelCoordinate adjacentCoord = (*i)->getLayerCoordinates();
105  if ((adjacentInt == m_next || blocker) && adjacentInt != m_destCoordInt) {
106  if (!blocker && m_multicell) {
107  continue;
108  } else if (!m_multicell){
109  continue;
110  }
111  }
112  // search if there are blockers which could block multicell object
113  if (m_multicell) {
114  blocker = false;
115  Location currentLoc(nextCell->getLayer());
116  currentLoc.setLayerCoordinates(nextCell->getLayerCoordinates());
117  Location adjacentLoc((*i)->getLayer());
118  adjacentLoc.setLayerCoordinates((*i)->getLayerCoordinates());
119 
120  int32_t rotation = getAngleBetween(currentLoc, adjacentLoc);
121  std::vector<ModelCoordinate> coords = grid-> toMultiCoordinates(adjacentLoc.getLayerCoordinates(), m_route->getOccupiedCells(rotation));
122  std::vector<ModelCoordinate>::iterator coord_it = coords.begin();
123  for (; coord_it != coords.end(); ++coord_it) {
124  Cell* cell = m_cellCache->getCell(*coord_it);
125  if (cell) {
126  if (cell->getCellType() != CTYPE_NO_BLOCKER) {
127  std::vector<Cell*>::iterator bc_it = std::find(m_ignoredBlockers.begin(), m_ignoredBlockers.end(), cell);
128  if (bc_it == m_ignoredBlockers.end()) {
129  blocker = true;
130  break;
131  }
132  }
133  }
134  }
135  if (blocker) {
136  continue;
137  }
138  }
139 
140  if (m_route->isAreaLimited()) {
141  // check if cell is on one of the areas
142  bool sameAreas = false;
143  const std::list<std::string> areas = m_route->getLimitedAreas();
144  std::list<std::string>::const_iterator area_it = areas.begin();
145  for (; area_it != areas.end(); ++area_it) {
146  if (m_cellCache->isCellInArea(*area_it, *i)) {
147  sameAreas = true;
148  break;
149  }
150  }
151  if (!sameAreas) {
152  continue;
153  }
154  }
155 
156  double gCost = m_gCosts[m_next];
157  if (m_specialCost) {
158  gCost += m_cellCache->getAdjacentCost(adjacentCoord ,nextCoord, m_route->getCostId());
159  } else {
160  gCost += m_cellCache->getAdjacentCost(adjacentCoord ,nextCoord);
161  }
162  double hCost = grid->getHeuristicCost(adjacentCoord, destCoord);
163  if (m_sf[adjacentInt] == -1) {
165  m_gCosts[adjacentInt] = gCost;
166  m_sf[adjacentInt] = m_next;
167  } else if (gCost < m_gCosts[adjacentInt] && m_spt[adjacentInt] == -1) {
168  m_sortedfrontier.changeElementPriority(adjacentInt, gCost + hCost);
169  m_gCosts[adjacentInt] = gCost;
170  m_sf[adjacentInt] = m_next;
171  }
172  }
173  }
174 
176  int32_t current = m_destCoordInt;
177  int32_t end = m_startCoordInt;
178  Path path;
179  Location newnode(m_cellCache->getLayer());
180  // This assures that the agent always steps into the center of the cell.
182  path.push_back(newnode);
183  while(current != end) {
184  if (m_spt[current] < 0 ) {
185  // This is when the size of m_spt can not handle the distance of the location
188  break;
189  }
190  current = m_spt[current];
191  ModelCoordinate currentCoord = m_cellCache->convertIntToCoord(current);
192  newnode.setLayerCoordinates(currentCoord);
193  path.push_front(newnode);
194  }
195  path.front().setExactLayerCoordinates(m_from.getExactLayerCoordinatesRef());
196  m_route->setPath(path);
197  }
198 }
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 &quot;cell precise&quot; 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.
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:40
int32_t getZStepRange()
Returns z-step range from object.
Definition: route.cpp:268
Layer * getLayer()
Returns the current layer.
Definition: cell.cpp:521
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:1488
void setRouteStatus(RouteStatusInfo status)
Sets route status.
Definition: route.cpp:55
Layer * getLayer()
Returns layer.
Definition: cellcache.cpp:802
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.
ModelCoordinate getLayerCoordinates() const
Gets cell precision layer coordinates set to this location.
Definition: location.cpp:113
A basic route.
Definition: route.h:64
const value_type getPriorityElement(void) const
Retrieves the element with the highest priority.
Definition: priorityqueue.h:99
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
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:1108
void setPath(const Path &path)
Sets the path for the route.
Definition: route.cpp:161
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:706
std::vector< Cell * > m_ignoredBlockers
Blockers from a multi cell object which should be ignored.
CellTypeInfo getCellType()
Returns blocker type.
Definition: cell.cpp:476
bool isAreaLimited()
Definition: route.cpp:275
const std::vector< Cell * > & getNeighbors()
Returns the layer coordinates of this cell.
Definition: cell.cpp:504
ExactModelCoordinate & getExactLayerCoordinatesRef()
Gets reference to exact layer coordinates.
Definition: location.cpp:105
A basic cell on a CellCache.
Definition: cell.h:136
CellGrid * getCellGrid() const
Get the Cellgrid.
Definition: layer.cpp:92
void calcPath()
Calculates final path.
const ModelCoordinate getLayerCoordinates() const
Returns the layer coordinates of this cell.
Definition: cell.cpp:496
void popElement(void)
Pops the element with the highest priority from the queue.
A 3D Point.
Definition: point.h:202
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:344
const std::string & getCostId()
Returns cost identifier which is used for pathfinding.
Definition: route.cpp:241
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
bool m_multicell
Indicates if the route is for a multi cell object.
std::vector< int32_t > m_sf
The search frontier.
bool empty(void) const
Determines whether the queue is currently empty.
A pq which stores index-value pairs for elements.
Definition: priorityqueue.h:36
Route * m_route
Pointer to route.
int32_t getMaxIndex() const
Returns the number of cells on this CellCache.
Definition: cellcache.cpp:845
std::vector< double > m_gCosts
A table to hold the costs.