* find the shortest path from (sx,sy) to (dx,dy), using PosOk(PosOkArg,x,y) to * check that each step is a valid position. Store the step directions (see * path_directions) in path, which must have room for 24 steps */
| 42 | * path_directions) in path, which must have room for 24 steps |
| 43 | */ |
| 44 | int FindPath(BOOL (*PosOk)(int, int, int), int PosOkArg, int sx, int sy, int dx, int dy, char *path) |
| 45 | { |
| 46 | PATHNODE *path_start, *next_node, *current; |
| 47 | int path_length, i; |
| 48 | |
| 49 | // clear all nodes, create root nodes for the visited/frontier linked lists |
| 50 | gdwCurNodes = 0; |
| 51 | path_2_nodes = path_new_step(); |
| 52 | pnode_ptr = path_new_step(); |
| 53 | gdwCurPathStep = 0; |
| 54 | path_start = path_new_step(); |
| 55 | path_start->g = 0; |
| 56 | path_start->h = path_get_h_cost(sx, sy, dx, dy); |
| 57 | path_start->x = sx; |
| 58 | path_start->f = path_start->h + path_start->g; |
| 59 | path_start->y = sy; |
| 60 | path_2_nodes->NextNode = path_start; |
| 61 | // A* search until we find (dx,dy) or fail |
| 62 | while ((next_node = GetNextPath())) { |
| 63 | // reached the end, success! |
| 64 | if (next_node->x == dx && next_node->y == dy) |
| 65 | { |
| 66 | current = next_node; |
| 67 | path_length = 0; |
| 68 | while (current->Parent) { |
| 69 | if (path_length >= MAX_PATH_LENGTH) |
| 70 | break; |
| 71 | pnode_vals[path_length++] = path_directions[3 * (current->y - current->Parent->y) - current->Parent->x + 4 + current->x]; |
| 72 | current = current->Parent; |
| 73 | } |
| 74 | if (path_length != MAX_PATH_LENGTH) { |
| 75 | for (i = 0; i < path_length; i++) |
| 76 | path[i] = pnode_vals[path_length - i - 1]; |
| 77 | return i; |
| 78 | } |
| 79 | return 0; |
| 80 | } |
| 81 | // ran out of nodes, abort! |
| 82 | if (!path_get_path(PosOk, PosOkArg, next_node, dx, dy)) |
| 83 | return 0; |
| 84 | } |
| 85 | // frontier is empty, no path! |
| 86 | return 0; |
| 87 | } |
| 88 | |
| 89 | /** |
| 90 | * @brief heuristic, estimated cost from (sx,sy) to (dx,dy) |
no test coverage detected