16 #include "aiPathFinder.h"
18 PathFinder::PathFinder(NavMesh nav_mesh) {
22 PathFinder::~PathFinder() {
35 _dest_node = dest_node;
40 _dummy_node->_status = _dummy_node->open;
41 _dummy_node->_score = -1;
42 _open_list.push_back(_dummy_node);
62 while(_open_list.size() > 1) {
66 Node* nxt_node = _open_list[1];
68 if(nxt_node->_grid_x == _dest_node->_grid_x &&
69 nxt_node->_grid_y == _dest_node->_grid_y) {
86 cout<<
"DESTINATION NOT REACHABLE MATE!"<<endl;
102 for(
int i = 0; i < 8; ++i) {
103 if(parent_node->_neighbours[i] != NULL) {
104 if(parent_node->_neighbours[i]->_status == parent_node->_neighbours[i]->neutral
105 && parent_node->_neighbours[i]->_type ==
true) {
107 parent_node->_neighbours[i]->_prv_node = parent_node;
128 nd->_score = nd->_cost + nd->_heuristic;
143 Node *start_node = nd;
144 while(start_node->_prv_node != _src_node) {
151 start_node = start_node->_prv_node;
173 int row_diff = abs(_dest_node->_grid_x - nd->_grid_x);
174 int col_diff = abs(_dest_node->_grid_y - nd->_grid_y);
176 int heuristic = 10 * (row_diff + col_diff);
189 float row_diff = nd->_grid_x - nd->_prv_node->_grid_x;
190 float col_diff = nd->_grid_y - nd->_prv_node->_grid_y;
193 if(row_diff == 0 || col_diff == 0) {
212 Node *child_node, *parent_node;
213 int child_idx, parent_idx;
216 nd->_status = nd->open;
218 _open_list.push_back(nd);
224 child_idx = _open_list.size() - 1;
225 parent_idx = child_idx / 2;
226 child_node = _open_list[child_idx];
227 parent_node = _open_list[parent_idx];
231 while(_open_list[child_idx]->_score <= _open_list[parent_idx]->_score) {
233 _open_list[parent_idx] = child_node;
234 _open_list[child_idx] = parent_node;
237 child_idx = parent_idx;
238 parent_idx = child_idx / 2;
241 child_node = _open_list[child_idx];
242 parent_node = _open_list[parent_idx];
258 Node *child_node, *child_node_1, *child_node_2;
259 int child_idx, child_idx_1, child_idx_2;
263 _open_list.erase(_open_list.begin() + 1);
265 if(_open_list.size() > 1) {
267 Node *temp_node = _open_list[_open_list.size() - 1];
270 for(
int i = _open_list.size() - 1; i > 1; --i) {
271 _open_list[i] = _open_list[i - 1];
275 _open_list[1] = temp_node;
282 if((k * 2 + 1) < _open_list.size()) {
285 child_idx_2 = k * 2 + 1;
286 child_node_1 = _open_list[child_idx_1];
287 child_node_2 = _open_list[child_idx_2];
289 if(_open_list[child_idx_1]->_score < _open_list[child_idx_2]->_score) {
290 if(_open_list[k]->_score > _open_list[child_idx_1]->_score) {
292 _open_list[child_idx_1] = _open_list[k];
293 _open_list[k] = child_node_1;
303 if(_open_list[k]->_score > _open_list[child_idx_2]->_score) {
305 _open_list[child_idx_2] = _open_list[k];
306 _open_list[k] = child_node_2;
316 else if((k * 2) < _open_list.size()) {
319 child_node = _open_list[child_idx];
321 if(_open_list[k]->_score > _open_list[child_idx]->_score) {
323 _open_list[child_idx] = _open_list[k];
324 _open_list[k] = child_node;
352 nd->_status = nd->close;
354 _closed_list.push_back(nd);
365 for(
unsigned int i = 0; i < _closed_list.size(); ++i) {
366 if(_closed_list[i]->_grid_x == r && _closed_list[i]->_grid_y == c) {
367 _closed_list.erase(_closed_list.begin() + i);
382 Node* find_in_mesh(NavMesh nav_mesh,
LVecBase3 pos,
int grid_size) {
383 int size = grid_size;
387 for(
int i = 0; i < size; ++i) {
388 for(
int j = 0; j < size; ++j) {
389 if(nav_mesh[i][j] != NULL && nav_mesh[i][j]->contains(x, y)) {
390 return(nav_mesh[i][j]);
This is the base class for all three-component vectors and points.
void generate_path()
This function performs the pathfinding process using the A* algorithm.
This class is used to assign the nodes on the mesh.
void add_to_clist(Node *nd)
This function adds a node to the closed list.
bool is_diagonal_node(Node *nd)
This function checks if the traversal from a node is diagonal.
void remove_from_olist()
This function removes a node from the open list.
void find_path(Node *src_node, Node *dest_node)
This function initializes the pathfinding process by accepting the source and destination nodes...
void identify_neighbors(Node *nd)
This function traverses through the 8 neigbors of the parent node and then adds the neighbors to the ...
void calc_node_score(Node *nd)
This function calculates the score of each node.
void add_to_olist(Node *nd)
This function adds a node to the open list heap.
void remove_from_clist(int r, int c)
This function removes a node from the closed list.
int calc_heuristic(Node *nd)
This function calculates the heuristic of the nodes using Manhattan method.
int calc_cost_frm_src(Node *nd)
This function calculates the cost of each node by finding out the number of node traversals required ...