* @brief add a step from pPath to (dx,dy), return 1 if successful, and update the frontier/visited nodes accordingly * * @return TRUE if step successfully added, FALSE if we ran out of nodes to use */
| 194 | * @return TRUE if step successfully added, FALSE if we ran out of nodes to use |
| 195 | */ |
| 196 | BOOL path_parent_path(PATHNODE *pPath, int dx, int dy, int sx, int sy) |
| 197 | { |
| 198 | int next_g; |
| 199 | PATHNODE *dxdy; |
| 200 | int i; |
| 201 | |
| 202 | next_g = pPath->g + path_check_equal(pPath, dx, dy); |
| 203 | |
| 204 | // 3 cases to consider |
| 205 | // case 1: (dx,dy) is already on the frontier |
| 206 | dxdy = path_get_node1(dx, dy); |
| 207 | if (dxdy != NULL) { |
| 208 | for (i = 0; i < 8; i++) { |
| 209 | if (pPath->Child[i] == NULL) |
| 210 | break; |
| 211 | } |
| 212 | pPath->Child[i] = dxdy; |
| 213 | if (next_g < dxdy->g) { |
| 214 | if (path_solid_pieces(pPath, dx, dy)) { |
| 215 | // we'll explore it later, just update |
| 216 | dxdy->Parent = pPath; |
| 217 | dxdy->g = next_g; |
| 218 | dxdy->f = next_g + dxdy->h; |
| 219 | } |
| 220 | } |
| 221 | } else { |
| 222 | // case 2: (dx,dy) was already visited |
| 223 | dxdy = path_get_node2(dx, dy); |
| 224 | if (dxdy != NULL) { |
| 225 | for (i = 0; i < 8; i++) { |
| 226 | if (pPath->Child[i] == NULL) |
| 227 | break; |
| 228 | } |
| 229 | pPath->Child[i] = dxdy; |
| 230 | if (next_g < dxdy->g && path_solid_pieces(pPath, dx, dy)) { |
| 231 | // update the node |
| 232 | dxdy->Parent = pPath; |
| 233 | dxdy->g = next_g; |
| 234 | dxdy->f = next_g + dxdy->h; |
| 235 | // already explored, so re-update others starting from that node |
| 236 | path_set_coords(dxdy); |
| 237 | } |
| 238 | } else { |
| 239 | // case 3: (dx,dy) is totally new |
| 240 | dxdy = path_new_step(); |
| 241 | if (dxdy == NULL) |
| 242 | return FALSE; |
| 243 | dxdy->Parent = pPath; |
| 244 | dxdy->g = next_g; |
| 245 | dxdy->h = path_get_h_cost(dx, dy, sx, sy); |
| 246 | dxdy->f = next_g + dxdy->h; |
| 247 | dxdy->x = dx; |
| 248 | dxdy->y = dy; |
| 249 | // add it to the frontier |
| 250 | path_next_node(dxdy); |
| 251 | |
| 252 | for (i = 0; i < 8; i++) { |
| 253 | if (pPath->Child[i] == NULL) |
no test coverage detected