7
\$\begingroup\$

Let's say I already have an A* algorithm.

How can I handle the cases when the goal cannot be reached, and still attempt to get there?

For instance on the following example:

tile map Notice the amazing GIMP skills!

The yellow unit needs to reach the green spot, but it's on island and can't actually reach it.

Yet, on a typical RTS, the unit will try to go as close as possible.

My problem is that I don't know how to tell A* that the closest tile to the goal is the square near the sea.

How can I have this partial pathfinding? Is A* still a good choice?

\$\endgroup\$
  • \$\begingroup\$ I think RTS just find the nearest point outside of the terrain and calculate the path to that instead of doing partial path-finding. \$\endgroup\$ – API-Beast Aug 30 '14 at 23:16
  • \$\begingroup\$ @API-Beast So 1. do they still do pathfinding to know the goal is not reachable and 2. how do you find the nearest point? \$\endgroup\$ – Pierre Arlaud Aug 30 '14 at 23:55
  • \$\begingroup\$ No, it's not that the goal not reachable, it's that the point you clicked on is "solid", e.g. it blocks unit movement. RTS tend to not have any unreachable targets. \$\endgroup\$ – API-Beast Aug 30 '14 at 23:58
  • \$\begingroup\$ You dont need to modify anything. Just remember the closest point you ever been to. The A* will attempt to find the path and will fail for you example, but that doesnt mean it will not first establish the path you drawn, you only have to remember path to the closest point the A* ever been to. \$\endgroup\$ – wondra Aug 31 '14 at 12:19
  • 1
    \$\begingroup\$ Never checked it actually, be sure to share if it work in practice. (this was just logical assumption on how A* work). \$\endgroup\$ – wondra Aug 31 '14 at 22:31
3
\$\begingroup\$

In theory, you dont need to modify anything. Just remember the closest point you ever been to. The A* will attempt to find the path and will fail for you example, but that doesnt mean it will not first establish the path you drawn, you only have to remember path to the closest point the A* ever been to.

\$\endgroup\$
  • \$\begingroup\$ A* performs badly - its worst case in fact - if the destination is unreachable, because it will visit all contiguous nodes. I think some modification will at least help? \$\endgroup\$ – congusbongus Sep 1 '14 at 2:22
  • 3
    \$\begingroup\$ The problem is that unless you exhaust A* you do not know that your end point is unreachable. If you make compromises with limiting how A* works you will end up spending way more time fixing cases when "why did that path just fail?" happens. \$\endgroup\$ – Patrick Hughes Sep 1 '14 at 2:31
  • \$\begingroup\$ @PatrickHughes congusbongus might have a point. Often, RTS engines have an imperfect pathfinding algorithm, which fails to find the shortest path (and barely follows a heuristic) if the shortest path is too complicated. \$\endgroup\$ – Pierre Arlaud Sep 1 '14 at 7:31
  • \$\begingroup\$ Just get the code working, then if it is too slow, PROFILE it. Don't let people get you stuck in the mud because something MIGHT be too slow. Just get it working and move on from there to the next most important thing - which probably isn't improving the performance of this algorithm. \$\endgroup\$ – xaxxon Sep 8 '16 at 9:06
0
\$\begingroup\$

Using A* alone (and going to the closest searched point) is ok for small maps, but it will perform badly if the map is larger. If the target is unreachable, A* will search the entire reachable space before figuring out that the target is unreachable. This may involve lots of search points, and can be very slow. In this situation, A* has no advantage over algorithms like Dijkstra.

For a more efficient solution, you need three parts:

  • Find all the groups of mutually-unreachable regions
  • Find the closest reachable position
  • Pathfind to this position

The first step can be pre-calculated so you can cheaply find whether your destination is reachable. Flood-fill (a.k.a. BFS) will suffice.

The second will typically be Dijkstra or a similar looking algorithm. You can even pre-calculate it (for each unreachable position, search for the closest reachable position and save it before the game starts).

You can then use A* for the third step.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.