|
Devilution
Diablo devolved - magic behind the 1996 computer game
|
Go to the source code of this file.
Functions | |
| int | FindPath (BOOL(*PosOk)(int, int, int), int PosOkArg, int sx, int sy, int dx, int dy, char *path) |
| find the shortest path from (sx,sy) to (dx,dy), using PosOk(PosOkArg,x,y) to check that each step is a valid position. More... | |
| int | path_get_h_cost (int sx, int sy, int dx, int dy) |
| heuristic, estimated cost from (sx,sy) to (dx,dy) More... | |
| int | path_check_equal (PATHNODE *pPath, int dx, int dy) |
| return 2 if pPath is horizontally/vertically aligned with (dx,dy), else 3 More... | |
| PATHNODE * | GetNextPath () |
| get the next node on the A* frontier to explore (estimated to be closest to the goal), mark it as visited, and return it More... | |
| BOOL | path_solid_pieces (PATHNODE *pPath, int dx, int dy) |
| check if stepping from pPath to (dx,dy) cuts a corner. More... | |
| BOOL | path_get_path (BOOL(*PosOk)(int, int, int), int PosOkArg, PATHNODE *pPath, int x, int y) |
| perform a single step of A* bread-first search by trying to step in every possible direction from pPath with goal (x,y). More... | |
| BOOL | path_parent_path (PATHNODE *pPath, int dx, int dy, int sx, int sy) |
| add a step from pPath to (dx,dy), return 1 if successful, and update the frontier/visited nodes accordingly More... | |
| PATHNODE * | path_get_node1 (int dx, int dy) |
| return a node for (dx,dy) on the frontier, or NULL if not found More... | |
| PATHNODE * | path_get_node2 (int dx, int dy) |
| return a node for (dx,dy) if it was visited, or NULL if not found More... | |
| void | path_next_node (PATHNODE *pPath) |
| insert pPath into the frontier (keeping the frontier sorted by total distance) More... | |
| void | path_set_coords (PATHNODE *pPath) |
| update all path costs using depth-first search starting at pPath More... | |
| void | path_push_active_step (PATHNODE *pPath) |
| push pPath onto the pnode_tblptr stack More... | |
| PATHNODE * | path_pop_active_step () |
| pop and return a node from the pnode_tblptr stack More... | |
| PATHNODE * | path_new_step () |
| zero one of the preallocated nodes and return a pointer to it, or NULL if none are available More... | |
Variables | |
| PATHNODE | path_nodes [MAXPATHNODES] |
| Notes visisted by the path finding algorithm. More... | |
| int | gdwCurPathStep |
| size of the pnode_tblptr stack More... | |
| int | gdwCurNodes |
| the number of in-use nodes in path_nodes More... | |
| int | pnode_vals [MAX_PATH_LENGTH] |
| for reconstructing the path after the A* search is done. More... | |
| PATHNODE * | pnode_ptr |
| A linked list of all visited nodes. More... | |
| PATHNODE * | pnode_tblptr [MAXPATHNODES] |
| A stack for recursively searching nodes. More... | |
| PATHNODE * | path_2_nodes |
| A linked list of the A* frontier, sorted by distance. More... | |
| PATHNODE | path_unusednodes [MAXPATHNODES] |
| const char | pathxdir [8] |
| For iterating over the 8 possible movement directions. More... | |
| const char | pathydir [8] |
| char | path_directions [9] |
| each step direction is assigned a number like this: dx -1 0 1 +--— -1|5 1 6 dy 0|2 0 3 1|8 4 7 More... | |
Interface of the path finding algorithms.
Definition in file path.h.
1.8.17