| 366 | } |
| 367 | |
| 368 | int FindPath(tl::function_ref<bool(Point)> posOk, Point startPosition, Point destinationPosition, int8_t path[MaxPathLength]) |
| 369 | { |
| 370 | /** |
| 371 | * for reconstructing the path after the A* search is done. The longest |
| 372 | * possible path is actually 24 steps, even though we can fit 25 |
| 373 | */ |
| 374 | static int8_t pnodeVals[MaxPathLength]; |
| 375 | |
| 376 | // clear all nodes, create root nodes for the visited/frontier linked lists |
| 377 | gdwCurNodes = 0; |
| 378 | Path2Nodes = &PathNodes[NewStep()]; |
| 379 | VisitedNodes = &PathNodes[NewStep()]; |
| 380 | gdwCurPathStep = 0; |
| 381 | const uint16_t pathStartIndex = NewStep(); |
| 382 | PathNode &pathStart = PathNodes[pathStartIndex]; |
| 383 | pathStart.x = static_cast<int16_t>(startPosition.x); |
| 384 | pathStart.y = static_cast<int16_t>(startPosition.y); |
| 385 | pathStart.f = pathStart.h + pathStart.g; |
| 386 | pathStart.h = GetHeuristicCost(startPosition, destinationPosition); |
| 387 | pathStart.g = 0; |
| 388 | Path2Nodes->nextNodeIndex = pathStartIndex; |
| 389 | // A* search until we find (dx,dy) or fail |
| 390 | uint16_t nextNodeIndex; |
| 391 | while ((nextNodeIndex = GetNextPath()) != PathNode::InvalidIndex) { |
| 392 | // reached the end, success! |
| 393 | if (PathNodes[nextNodeIndex].position() == destinationPosition) { |
| 394 | const PathNode *current = &PathNodes[nextNodeIndex]; |
| 395 | size_t pathLength = 0; |
| 396 | while (current->parentIndex != PathNode::InvalidIndex) { |
| 397 | if (pathLength >= MaxPathLength) |
| 398 | break; |
| 399 | pnodeVals[pathLength++] = GetPathDirection(PathNodes[current->parentIndex].position(), current->position()); |
| 400 | current = &PathNodes[current->parentIndex]; |
| 401 | } |
| 402 | if (pathLength != MaxPathLength) { |
| 403 | size_t i; |
| 404 | for (i = 0; i < pathLength; i++) |
| 405 | path[i] = pnodeVals[pathLength - i - 1]; |
| 406 | return static_cast<int>(i); |
| 407 | } |
| 408 | return 0; |
| 409 | } |
| 410 | // ran out of nodes, abort! |
| 411 | if (!GetPath(posOk, nextNodeIndex, destinationPosition)) |
| 412 | return 0; |
| 413 | } |
| 414 | // frontier is empty, no path! |
| 415 | return 0; |
| 416 | } |
| 417 | |
| 418 | bool path_solid_pieces(Point startPosition, Point destinationPosition) |
| 419 | { |