Panda3D
|
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 | |
vector< Node * > | _closed_list |
Node * | _dest_node |
NavMesh | _grid |
vector< Node * > | _open_list |
Node * | _src_node |
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.
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().
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().