6
\$\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\$
8
  • \$\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, 2014 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\$ Aug 30, 2014 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, 2014 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, 2014 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, 2014 at 22:31

2 Answers 2

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\$
4
  • \$\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\$ Sep 1, 2014 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\$ Sep 1, 2014 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\$ Sep 1, 2014 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, 2016 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\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .