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