Main Page | Class Hierarchy | Class List | Directories | File List | Class Members | Related Pages

PathFinder Class Reference

#include <pathfinder.h>

List of all members.

Public Types


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
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.

		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
			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
		4) Mark the current node as processed

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.
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:
Generated on Sat Nov 11 10:21:11 2006 for OpenCity by  doxygen 1.4.2