Public Member Functions | Public Attributes
PathFinder Class Reference

This class implements pathfinding using A* algorithm. More...

#include "aiPathFinder.h"

List of all members.

Public Member Functions

 PathFinder (NavMesh nav_mesh)
void add_to_clist (Node *nd)
 This function adds a node to the closed list.
void add_to_olist (Node *nd)
 This function adds a node to the open list heap.
int calc_cost_frm_src (Node *nd)
 This function calculates the cost of each node by finding out the number of node traversals required to reach the source node.
int calc_heuristic (Node *nd)
 This function calculates the heuristic of the nodes using Manhattan method.
void calc_node_score (Node *nd)
 This function calculates the score of each node.
void find_path (Node *src_node, Node *dest_node)
 This function initializes the pathfinding process by accepting the source and destination nodes.
void generate_path ()
 This function performs the pathfinding process using the A* algorithm.
void identify_neighbors (Node *nd)
 This function traverses through the 8 neigbors of the parent node and then adds the neighbors to the _open_list based on A* criteria.
bool is_diagonal_node (Node *nd)
 This function checks if the traversal from a node is diagonal.
void remove_from_clist (int r, int c)
 This function removes a node from the closed list.
void remove_from_olist ()
 This function removes a node from the open list.

Public Attributes

vector< Node * > _closed_list
Node * _dest_node
NavMesh _grid
vector< Node * > _open_list
Node * _src_node

Detailed 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 36 of file aiPathFinder.h.

Member Function Documentation

void PathFinder::add_to_clist ( Node *  nd)

This function adds a node to the closed list.

Definition at line 350 of file aiPathFinder.cxx.

Referenced by generate_path().

void PathFinder::add_to_olist ( Node *  nd)

This function adds a node to the open list heap.

A binay heap is maintained to improve the search.

Definition at line 210 of file aiPathFinder.cxx.

Referenced by find_path(), and identify_neighbors().

int PathFinder::calc_cost_frm_src ( Node *  nd)

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 141 of file aiPathFinder.cxx.

References is_diagonal_node().

Referenced by calc_node_score().

int PathFinder::calc_heuristic ( Node *  nd)

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 172 of file aiPathFinder.cxx.

Referenced by calc_node_score().

void PathFinder::calc_node_score ( Node *  nd)

This function calculates the score of each node.

Score = Cost + Heuristics.

Definition at line 125 of file aiPathFinder.cxx.

References calc_cost_frm_src(), and calc_heuristic().

Referenced by identify_neighbors().

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

This function initializes the pathfinding process by accepting the source and destination nodes.

It then calls the generate_path().

Definition at line 33 of file aiPathFinder.cxx.

References add_to_olist(), and generate_path().

Referenced by PathFind::path_find().

void PathFinder::generate_path ( )

This function performs the pathfinding process using the A* algorithm.

It updates the openlist and closelist.

Definition at line 59 of file aiPathFinder.cxx.

References add_to_clist(), identify_neighbors(), and remove_from_olist().

Referenced by find_path().

void PathFinder::identify_neighbors ( Node *  nd)

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 98 of file aiPathFinder.cxx.

References add_to_olist(), calc_node_score(), and remove_from_olist().

Referenced by generate_path().

bool PathFinder::is_diagonal_node ( Node *  nd)

This function checks if the traversal from a node is diagonal.

Definition at line 187 of file aiPathFinder.cxx.

Referenced by calc_cost_frm_src().

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

This function removes a node from the closed list.

Definition at line 364 of file aiPathFinder.cxx.

void PathFinder::remove_from_olist ( )

This function removes a node from the open list.

During the removal the binary heap is maintained.

Definition at line 256 of file aiPathFinder.cxx.

Referenced by generate_path(), and identify_neighbors().

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