Panda3D
Loading...
Searching...
No Matches
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.
 
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

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.

Constructor & Destructor Documentation

◆ PathFinder()

PathFinder::PathFinder ( NavMesh nav_mesh)

Definition at line 16 of file aiPathFinder.cxx.

◆ ~PathFinder()

PathFinder::~PathFinder ( )

Definition at line 20 of file aiPathFinder.cxx.

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.

Referenced by find_path(), and identify_neighbors().

◆ 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().

Referenced by identify_neighbors().

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

References add_to_olist(), and generate_path().

Referenced by PathFind::path_find(), and 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().

Referenced by find_path().

◆ 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 add_to_olist(), calc_node_score(), and 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().

Member Data Documentation

◆ _closed_list

std::vector<Node*> PathFinder::_closed_list

Definition at line 36 of file aiPathFinder.h.

◆ _dest_node

Node* PathFinder::_dest_node

Definition at line 34 of file aiPathFinder.h.

◆ _grid

NavMesh PathFinder::_grid

Definition at line 38 of file aiPathFinder.h.

◆ _open_list

std::vector<Node*> PathFinder::_open_list

Definition at line 35 of file aiPathFinder.h.

◆ _src_node

Node* PathFinder::_src_node

Definition at line 33 of file aiPathFinder.h.


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