PathFinder Class Reference

#include <pathfinder.h>

List of all members.

Public Types
enum	PATH_TYPE { OC_DISTANCE, OC_TRAFFIC }
Public Member Functions
	PathFinder (SDL_mutex *const mutex, BuildingLayer *const pblayer, Map *const map, const uint &rcuiCityWidth, const uint &rcuiCityHeight)
const bool	findShortestPath (const uint &rcuiW1, const uint &rcuiH1, const uint &rcuiW2, const uint &rcuiH2, std::vector< Destination > &rvdest, const PATH_TYPE &enumType, uint uiMaxLength=0xFFFFFFFF)
Private Attributes
SDL_mutex *	pmutex
BuildingLayer *	pbuildlayer
Map *	pmap
uint	uiWidth
	The city's width.
uint	uiHeight
	The city's height.

---

Detailed Description

This class implements few famous algorithms in path finding problems

Definition at line 43 of file pathfinder.h.

---

Member Function Documentation

const bool PathFinder::findShortestPath (  const uint &  rcuiW1, const uint &  rcuiH1, const uint &  rcuiW2, const uint &  rcuiH2, std::vector< Destination > &  rvdest, const PATH_TYPE &  enumType, uint  uiMaxLength = 0xFFFFFFFF )

Find the shortest path given the OpenCity W1, H1 and W2, H2 coordinates. The algorithm is adapted from the famous DIJKSTRA algorithm. Algorithm 1) Initialize all the OC_ROAD structures 2) Insert the starting point to the "processing" list 3) WHILE the processing list is not empty and not boolFound DO 3a)Sort the processing list 3b)Pop the node with the minimum length (and not marked) 3c)IF the node is the arrival point THEN boolFound = TRUE FI 3d)FOR each neighbour OC_ROAD DO newLength = the length of the current node + the traffic of this neighbour; IF newLength is < to the length of the neighbour THEN i)the length of the neighbour is = newLength ii)father of the neighbour is = this node iii)insert the neighbour to the processing list FI DONE 4) Mark the current node as processed Parameters: rcuiW1,rcuiH1,rcuiW2,rcuiH2  = must be the valid OC W,H coordinates and there must be PathStructure at the designated W1,H1 and W2, H2 coordinates rvdest  = the vector which contains the path requested if it exists enumType  = do we look for shortest path in term of distance or traffic ? uiMaxLength  = limit the number of loops in the algorithm to uiMaxLength. It means that the maximum length of the returned path is uiMaxLength units long. And the most important thing is that the returned path may _not_ be the optimal path. Returns: false IF error, true otherwise Definition at line 209 of file pathfinder.cpp. References Destination::_eDir, Destination::_iHMax, Destination::_iHMin, Destination::_ubTraffic, Destination::_uiL, Destination::_uiTime, Destination::_uiW, Structure::GetCode(), Destination::GetDir(), PathStructure::GetLength(), BuildingLayer::GetLinearStructure(), Layer::GetMaxLinear(), Map::GetSquareMaxHeight(), Map::GetSquareMinHeight(), BuildingLayer::GetStructure(), PathStructure::GetTraffic(), PathFinderNode::iFatherLinear, PathFinderNode::iOwnLinear, Structure::IsSet(), PathFinderNode::ppath, Structure::Set(), PathStructure::SetLength(), PathFinderNode::uiEvaluation, uiWidth, and Structure::Unset(). Referenced by Environment::findShortestPath().

---

The documentation for this class was generated from the following files:

• pathfinder.h
• pathfinder.cpp

---