#include <aiPathFinder.h>
Public Member Functions | |
void | identify_neighbors (Node *nd) |
int | calc_cost_frm_src (Node *nd) |
int | calc_heuristic (Node *nd) |
void | calc_node_score (Node *nd) |
bool | is_diagonal_node (Node *nd) |
void | add_to_olist (Node *nd) |
void | remove_from_olist () |
void | add_to_clist (Node *nd) |
void | remove_from_clist (int r, int c) |
void | generate_path () |
void | find_path (Node *src_node, Node *dest_node) |
PathFinder (NavMesh nav_mesh) | |
~PathFinder () | |
Public Attributes | |
Node * | _src_node |
Node * | _dest_node |
vector< Node * > | _open_list |
vector< Node * > | _closed_list |
NavMesh | _grid |
Class : PathFinder 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 35 of file aiPathFinder.h.
PathFinder::PathFinder | ( | NavMesh | nav_mesh | ) |
Filename : aiPathFinder.cxx Created by : Deepak, John, Navin Date : 10 Nov 09
PANDA3D SOFTWARE Copyright(c) Carnegie Mellon University. All rights reserved.
All use of this software is subjest to the terms of the revised BSD license. You should have received a copy of this license along with this source code in a file named "LICENSE"
Definition at line 17 of file aiPathFinder.cxx.
PathFinder::~PathFinder | ( | ) |
Definition at line 21 of file aiPathFinder.cxx.
void PathFinder::add_to_clist | ( | Node * | nd | ) |
Function : add_to_clist Description : This function adds a node to the closed list.
Definition at line 349 of file aiPathFinder.cxx.
void PathFinder::add_to_olist | ( | Node * | nd | ) |
Function : add_to_olist Description : This function adds a node to the open list heap. A binay heap is maintained to improve the search.
Definition at line 209 of file aiPathFinder.cxx.
int PathFinder::calc_cost_frm_src | ( | Node * | nd | ) |
Function : calc_cost_frm_src Description : 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 140 of file aiPathFinder.cxx.
int PathFinder::calc_heuristic | ( | Node * | nd | ) |
Function : calc_heuristic Description : 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 171 of file aiPathFinder.cxx.
void PathFinder::calc_node_score | ( | Node * | nd | ) |
Function : calc_node_score Description : This function calculates the score of each node. Score = Cost + Heuristics.
Definition at line 124 of file aiPathFinder.cxx.
Function : find_path Description : This function initializes the pathfinding process by accepting the source and destination nodes. It then calls the generate_path().
Definition at line 32 of file aiPathFinder.cxx.
void PathFinder::generate_path | ( | ) |
Function : generate_path Description : This function performs the pathfinding process using the A* algorithm. It updates the openlist and closelist.
Definition at line 58 of file aiPathFinder.cxx.
void PathFinder::identify_neighbors | ( | Node * | parent_node | ) |
Function : identify_neighbors Description : 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 97 of file aiPathFinder.cxx.
bool PathFinder::is_diagonal_node | ( | Node * | nd | ) |
Function : is_diagonal_node Description : This function checks if the traversal from a node is diagonal.
Definition at line 186 of file aiPathFinder.cxx.
void PathFinder::remove_from_clist | ( | int | r, | |
int | c | |||
) |
Function : remove_from_clist Description : This function removes a node from the closed list.
Definition at line 363 of file aiPathFinder.cxx.
void PathFinder::remove_from_olist | ( | ) |
Function : remove_from_olist Description : This function removes a node from the open list. During the removal the binary heap is maintained.
Definition at line 255 of file aiPathFinder.cxx.
vector<Node*> PathFinder::_closed_list |
Definition at line 40 of file aiPathFinder.h.
Definition at line 38 of file aiPathFinder.h.
Definition at line 42 of file aiPathFinder.h.
vector<Node*> PathFinder::_open_list |
Definition at line 39 of file aiPathFinder.h.
Definition at line 37 of file aiPathFinder.h.