Public Member Functions | Protected Member Functions | Protected Attributes

sp::tool::PathGraph Class Reference
[Pathfinding]

#include <spToolPathFinder.hpp>

List of all members.

Public Member Functions

 PathGraph ()
virtual ~PathGraph ()
PathNodeaddNode (const dim::vector3df &Position, void *Data=0)
void removeNode (PathNode *Node)
 Removes the spcified PathNode object.
void clearNodeList ()
 Clears the whole path node list.
PathEdgeaddEdge (PathNode *From, PathNode *To, bool Adjusted=false)
void removeEdge (PathEdge *Edge)
 Removes the specified PathEdge object.
void clearEdgeList ()
 Clears the whole path edge list.
void createGrid (const dim::vector3df &From, const dim::vector3df &To, const dim::vector3di &Steps, const std::vector< bool > &Bitmap=std::vector< bool >(), bool DiagonalEdges=true)
virtual std::list< PathNode * > findPath (PathNode *From, PathNode *To)
 Trys to find a path from the specified start node to the target node through this path graph.
virtual bool findPath (PathNode *From, PathNode *To, std::list< PathNode * > &Path)
virtual std::list< PathNode * > findPath (const dim::vector3df &From, const dim::vector3df &To)
 Uses the other "findPath" function but uses the nearest PathNode objects from the specified global positions .
virtual bool findPath (const dim::vector3df &From, const dim::vector3df &To, std::list< PathNode * > &Path)
 Uses the other "findPath" function but uses the nearest PathNode objects from the specified global positions .
bool foundPath () const
 Returns true if the last searched path has been found. Otherwise false and no path has been found.
const std::list< PathNode * > & getNodeList () const
 Returns the node list.
const std::list< PathEdge * > & getEdgeList () const
 Returns the edge list.

Protected Member Functions

bool nextStep ()
PathNodegetNextNode ()
void addNodeToQueue (PathNode *Node, PathNode *Predecessor, const f32 WayCosts)
void constructPath (std::list< PathNode * > &Path, PathNode *NextNode)

Protected Attributes

std::list< PathNode * > NodeList_
std::list< PathEdge * > EdgeList_
std::list< PathNode * > NodeQueue_
std::map< PathNode *, bool > ClosedMap_
PathNodeStartNode_
PathNodeTargetNode_
bool isSolved_

Detailed Description

PathGraph objects represent a graph for path finding. The "A* Algorithm" is used for fast path finding.


Constructor & Destructor Documentation

sp::tool::PathGraph::PathGraph (  ) 
virtual sp::tool::PathGraph::~PathGraph (  )  [virtual]

Member Function Documentation

PathEdge* sp::tool::PathGraph::addEdge ( PathNode From,
PathNode To,
bool  Adjusted = false 
)

Adds a new edge to the graph. Each edge represents a connection between two nodes.

Parameters:
From,: Specifies the start PathNode object.
To,: Specifies the target PathNode object.
Adjusted,: Specifies whether the edge is to be adjusted or not. By default false which means the connection goes in both forwards and backwards directions.
Returns:
Pointer to the new PathEdge object. If the "From" and "To" parameters as invalid (null pointer) the return value is 0 (null).
PathNode* sp::tool::PathGraph::addNode ( const dim::vector3df Position,
void *  Data = 0 
)

Adds a new node to the graph. Each node represents a point in the scene.

Parameters:
Position,: Specifies the global position in the scene.
Data,: Specifies any kind of data linked to the new node object.
Returns:
Pointer to the new PathNode object.
void sp::tool::PathGraph::addNodeToQueue ( PathNode Node,
PathNode Predecessor,
const f32  WayCosts 
) [protected]
void sp::tool::PathGraph::clearEdgeList (  ) 

Clears the whole path edge list.

void sp::tool::PathGraph::clearNodeList (  ) 

Clears the whole path node list.

void sp::tool::PathGraph::constructPath ( std::list< PathNode * > &  Path,
PathNode NextNode 
) [protected]
void sp::tool::PathGraph::createGrid ( const dim::vector3df From,
const dim::vector3df To,
const dim::vector3di Steps,
const std::vector< bool > &  Bitmap = std::vector< bool >(),
bool  DiagonalEdges = true 
)

Creats a grid of nodes connected with edges.

Parameters:
From,: Specifies the global start position of the grid.
To,: Specifies the global target position of the grid.
Steps,: Specifies the count of nodes between the axels. e.g. if you want a grid of 10x10x1 nodes (a plane) set this parameter to (10, 10, 1).
Bitmap,: Specifies the array of enabled nodes. The array needs to be in the following order: [ Z*Steps.Z*Steps.Y + Y*Steps.Y + X ] where X, Y and Z is in the range [0, Steps.X/ Y/ Z]. By default empty array which means that the grid will be created completely.
DiagonalEdges,: Specifies whether diagonal edge connections are to be enabled or not.
Note:
Edges will also automatically created for each direct neighbor of each node. i.e. if you have a 2D grid (a plane) nearly each node (not these at the border) will have 8 neighbors.
virtual std::list<PathNode*> sp::tool::PathGraph::findPath ( PathNode From,
PathNode To 
) [virtual]

Trys to find a path from the specified start node to the target node through this path graph.

virtual bool sp::tool::PathGraph::findPath ( const dim::vector3df From,
const dim::vector3df To,
std::list< PathNode * > &  Path 
) [virtual]

Uses the other "findPath" function but uses the nearest PathNode objects from the specified global positions .

virtual bool sp::tool::PathGraph::findPath ( PathNode From,
PathNode To,
std::list< PathNode * > &  Path 
) [virtual]

Trys to find a path from the specified start node to the target node through this path graph.

Parameters:
From,: Specifies the start PathNode object.
To,: Specifies the target PathNode object.
Returns:
List with all nodes which form the path. If no path has been found the list is empty.
virtual std::list<PathNode*> sp::tool::PathGraph::findPath ( const dim::vector3df From,
const dim::vector3df To 
) [virtual]

Uses the other "findPath" function but uses the nearest PathNode objects from the specified global positions .

bool sp::tool::PathGraph::foundPath (  )  const [inline]

Returns true if the last searched path has been found. Otherwise false and no path has been found.

const std::list<PathEdge*>& sp::tool::PathGraph::getEdgeList (  )  const [inline]

Returns the edge list.

PathNode* sp::tool::PathGraph::getNextNode (  )  [protected]
const std::list<PathNode*>& sp::tool::PathGraph::getNodeList (  )  const [inline]

Returns the node list.

bool sp::tool::PathGraph::nextStep (  )  [protected]
void sp::tool::PathGraph::removeEdge ( PathEdge Edge  ) 

Removes the specified PathEdge object.

void sp::tool::PathGraph::removeNode ( PathNode Node  ) 

Removes the spcified PathNode object.


Member Data Documentation

std::map<PathNode*, bool> sp::tool::PathGraph::ClosedMap_ [protected]
std::list<PathEdge*> sp::tool::PathGraph::EdgeList_ [protected]
std::list<PathNode*> sp::tool::PathGraph::NodeList_ [protected]
std::list<PathNode*> sp::tool::PathGraph::NodeQueue_ [protected]

The documentation for this class was generated from the following file:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines