PathFinder Class Reference

#include <aiPathFinder.h>

Collaboration diagram for PathFinder:
Collaboration graph
[legend]

List of all members.

Public Member Functions

void identify_neighbors (Node *nd)
int calc_cost_frm_src (Node *nd)
int calc_heuristic (Node *nd)
void calc_node_score (Node *nd)
bool is_diagonal_node (Node *nd)
void add_to_olist (Node *nd)
void remove_from_olist ()
void add_to_clist (Node *nd)
void remove_from_clist (int r, int c)
void generate_path ()
void find_path (Node *src_node, Node *dest_node)
 PathFinder (NavMesh nav_mesh)
 ~PathFinder ()

Public Attributes

Node_src_node
Node_dest_node
vector< Node * > _open_list
vector< Node * > _closed_list
NavMesh _grid

Detailed Description

Class : PathFinder Description : This class implements pathfinding using A* algorithm. It also uses a Binary Heap search to search the open list. The heuristics are calculated using the manhattan method.

Definition at line 35 of file aiPathFinder.h.


Constructor & Destructor Documentation

PathFinder::PathFinder ( NavMesh  nav_mesh  ) 

Filename : aiPathFinder.cxx Created by : Deepak, John, Navin Date : 10 Nov 09

PANDA3D SOFTWARE Copyright(c) Carnegie Mellon University. All rights reserved.

All use of this software is subjest to the terms of the revised BSD license. You should have received a copy of this license along with this source code in a file named "LICENSE"

Definition at line 17 of file aiPathFinder.cxx.

PathFinder::~PathFinder (  ) 

Definition at line 21 of file aiPathFinder.cxx.


Member Function Documentation

void PathFinder::add_to_clist ( Node nd  ) 

Function : add_to_clist Description : This function adds a node to the closed list.

Definition at line 349 of file aiPathFinder.cxx.

Here is the caller graph for this function:

void PathFinder::add_to_olist ( Node nd  ) 

Function : add_to_olist Description : This function adds a node to the open list heap. A binay heap is maintained to improve the search.

Definition at line 209 of file aiPathFinder.cxx.

Here is the caller graph for this function:

int PathFinder::calc_cost_frm_src ( Node nd  ) 

Function : calc_cost_frm_src Description : This function calculates the cost of each node by finding out the number of node traversals required to reach the source node. Diagonal traversals have cost = 14. Horizontal / Vertical traversals have cost = 10.

Definition at line 140 of file aiPathFinder.cxx.

Here is the call graph for this function:

Here is the caller graph for this function:

int PathFinder::calc_heuristic ( Node nd  ) 

Function : calc_heuristic Description : This function calculates the heuristic of the nodes using Manhattan method. All it does is predict the number of node traversals required to reach the target node. No diagonal traversals are allowed in this technique.

Definition at line 171 of file aiPathFinder.cxx.

Here is the caller graph for this function:

void PathFinder::calc_node_score ( Node nd  ) 

Function : calc_node_score Description : This function calculates the score of each node. Score = Cost + Heuristics.

Definition at line 124 of file aiPathFinder.cxx.

Here is the call graph for this function:

Here is the caller graph for this function:

void PathFinder::find_path ( Node src_node,
Node dest_node 
)

Function : find_path Description : This function initializes the pathfinding process by accepting the source and destination nodes. It then calls the generate_path().

Definition at line 32 of file aiPathFinder.cxx.

Here is the call graph for this function:

Here is the caller graph for this function:

void PathFinder::generate_path (  ) 

Function : generate_path Description : This function performs the pathfinding process using the A* algorithm. It updates the openlist and closelist.

Definition at line 58 of file aiPathFinder.cxx.

Here is the call graph for this function:

Here is the caller graph for this function:

void PathFinder::identify_neighbors ( Node parent_node  ) 

Function : identify_neighbors Description : This function traverses through the 8 neigbors of the parent node and then adds the neighbors to the _open_list based on A* criteria.

Definition at line 97 of file aiPathFinder.cxx.

Here is the call graph for this function:

Here is the caller graph for this function:

bool PathFinder::is_diagonal_node ( Node nd  ) 

Function : is_diagonal_node Description : This function checks if the traversal from a node is diagonal.

Definition at line 186 of file aiPathFinder.cxx.

Here is the caller graph for this function:

void PathFinder::remove_from_clist ( int  r,
int  c 
)

Function : remove_from_clist Description : This function removes a node from the closed list.

Definition at line 363 of file aiPathFinder.cxx.

void PathFinder::remove_from_olist (  ) 

Function : remove_from_olist Description : This function removes a node from the open list. During the removal the binary heap is maintained.

Definition at line 255 of file aiPathFinder.cxx.

Here is the caller graph for this function:


Member Data Documentation

Definition at line 40 of file aiPathFinder.h.

Definition at line 38 of file aiPathFinder.h.

Definition at line 42 of file aiPathFinder.h.

Definition at line 39 of file aiPathFinder.h.

Definition at line 37 of file aiPathFinder.h.


The documentation for this class was generated from the following files:
 All Classes Files Functions Variables Typedefs Enumerations Enumerator

Generated on Tue Dec 8 01:13:31 2009 for Pandai by  doxygen 1.6.1