Devilution
Diablo devolved - magic behind the 1996 computer game
|
#include "all.h"
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 | |
DEVILUTION_BEGIN_NAMESPACE 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] = { -1, -1, 1, 1, -1, 0, 1, 0 } |
For iterating over the 8 possible movement directions. More... | |
const char | pathydir [8] = { -1, 1, -1, 1, 0, -1, 0, 1 } |
char | path_directions [9] = { 5, 1, 6, 2, 0, 3, 8, 4, 7 } |
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... | |
Implementation of the path finding algorithms.
Definition in file path.cpp.