Panda3D
Public Member Functions | Public Attributes | List of all members
PathFinder Class Reference

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

#include "aiPathFinder.h"

Public Member Functions

 PathFinder (NavMesh nav_mesh)
 
void add_to_clist (Node *nd)
 This function adds a node to the closed list. More...
 
void add_to_olist (Node *nd)
 This function adds a node to the open list heap. More...
 
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. More...
 
int calc_heuristic (Node *nd)
 This function calculates the heuristic of the nodes using Manhattan method. More...
 
void calc_node_score (Node *nd)
 This function calculates the score of each node. More...
 
void find_path (Node *src_node, Node *dest_node)
 This function initializes the pathfinding process by accepting the source and destination nodes. More...
 
void generate_path ()
 This function performs the pathfinding process using the A* algorithm. More...
 
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. More...
 
bool is_diagonal_node (Node *nd)
 This function checks if the traversal from a node is diagonal. More...
 
void remove_from_clist (int r, int c)
 This function removes a node from the closed list. More...
 
void remove_from_olist ()
 This function removes a node from the open list. More...
 

Public Attributes

std::vector< Node * > _closed_list
 
Node_dest_node
 
NavMesh _grid
 
std::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 31 of file aiPathFinder.h.

Member Function Documentation

◆ add_to_clist()

void PathFinder::add_to_clist ( Node nd)

This function adds a node to the closed list.

Definition at line 312 of file aiPathFinder.cxx.

Referenced by generate_path().

◆ add_to_olist()

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

◆ calc_cost_frm_src()

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 and vertical traversals have cost = 10.

Definition at line 119 of file aiPathFinder.cxx.

References is_diagonal_node().

Referenced by calc_node_score().

◆ calc_heuristic()

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

Referenced by calc_node_score().

◆ calc_node_score()

void PathFinder::calc_node_score ( Node nd)

This function calculates the score of each node.

Score = Cost + Heuristics.

Definition at line 108 of file aiPathFinder.cxx.

References calc_cost_frm_src(), and calc_heuristic().

◆ find_path()

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

Referenced by PathFind::path_find().

◆ generate_path()

void PathFinder::generate_path ( )

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

It updates the openlist and closelist.

Definition at line 50 of file aiPathFinder.cxx.

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

◆ identify_neighbors()

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

References remove_from_olist().

Referenced by generate_path().

◆ is_diagonal_node()

bool PathFinder::is_diagonal_node ( Node nd)

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

Definition at line 157 of file aiPathFinder.cxx.

Referenced by calc_cost_frm_src().

◆ remove_from_clist()

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

This function removes a node from the closed list.

Definition at line 322 of file aiPathFinder.cxx.

◆ remove_from_olist()

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

Referenced by generate_path(), and identify_neighbors().


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