Devilution
Diablo devolved - magic behind the 1996 computer game
|
Go to the documentation of this file.
18 int FindPath(BOOL (*PosOk)(
int,
int,
int),
int PosOkArg,
int sx,
int sy,
int dx,
int dy,
char *path);
PATHNODE * pnode_tblptr[MAXPATHNODES]
A stack for recursively searching nodes.
int gdwCurPathStep
size of the pnode_tblptr stack
PATHNODE * GetNextPath()
get the next node on the A* frontier to explore (estimated to be closest to the goal),...
void path_next_node(PATHNODE *pPath)
insert pPath into the frontier (keeping the frontier sorted by total distance)
BOOL path_solid_pieces(PATHNODE *pPath, int dx, int dy)
check if stepping from pPath to (dx,dy) cuts a corner.
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 pPa...
int path_get_h_cost(int sx, int sy, int dx, int dy)
heuristic, estimated cost from (sx,sy) to (dx,dy)
void path_push_active_step(PATHNODE *pPath)
push pPath onto the pnode_tblptr stack
PATHNODE * path_pop_active_step()
pop and return a node from the pnode_tblptr stack
int pnode_vals[MAX_PATH_LENGTH]
for reconstructing the path after the A* search is done.
void path_set_coords(PATHNODE *pPath)
update all path costs using depth-first search starting at pPath
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
const char pathxdir[8]
For iterating over the 8 possible movement directions.
PATHNODE path_unusednodes[MAXPATHNODES]
PATHNODE * path_get_node2(int dx, int dy)
return a node for (dx,dy) if it was visited, or NULL if not found
PATHNODE * path_new_step()
zero one of the preallocated nodes and return a pointer to it, or NULL if none are available
PATHNODE * pnode_ptr
A linked list of all visited nodes.
PATHNODE * path_get_node1(int dx, int dy)
return a node for (dx,dy) on the frontier, or NULL if not found
int path_check_equal(PATHNODE *pPath, int dx, int dy)
return 2 if pPath is horizontally/vertically aligned with (dx,dy), else 3
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 ...
PATHNODE * path_2_nodes
A linked list of the A* frontier, sorted by distance.
int gdwCurNodes
the number of in-use nodes in path_nodes
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 accor...
PATHNODE path_nodes[MAXPATHNODES]
Notes visisted by the path finding algorithm.