A* Multiple paths to goal

[roland]

Hey,
I have a problem with my pathfinding for bots - they will only choose the shortest path. I however do not want to use Dijkstra’s due to the amount of possible paths in the map being too large. (I’m searching from one side of the map to the other).

Here’s my example image, start point on the left, goal on the right. Blue are walls / unwalkable.

http://storm2d.net/misc/astar/initial.png

Right now the bots will take this path only:

http://storm2d.net/misc/astar/optimum.png

I want the bots to choose all “intelligent” routes to the goal, eg. take the shortest path along any possible route.
Here’s some examples:

http://storm2d.net/misc/astar/a.png

http://storm2d.net/misc/astar/b.png

http://storm2d.net/misc/astar/c.png

http://storm2d.net/misc/astar/d.png

http://storm2d.net/misc/astar/e.png

http://storm2d.net/misc/astar/f.png

I added some more tiles to show bad paths - There’s no point for bots to do this, humans wouldn’t.

http://storm2d.net/misc/astar/bad_a.png

http://storm2d.net/misc/astar/bad_b.png

Can you guys give me any ideas on how I could do this? I need to somehow determine options for routes, then I can make each bot choose one at random when they spawn.

I was thinking of having a list of paths from the bot’s position to the goal. Firstly I add the shortest path,
then having a loop, finding paths that have to be “different” from the paths that are currently in the list. I would do this by checking the number of nodes that are the same in the current path to any of the paths already in the list. So at least X nodes have to be different in each path. Once I can’t find a path that has X nodes different, I’ll stop. But I don’t know how I can cut out the “stupid” paths where they go around in circles or something, because some stupid paths can be shorter than the longer routes. Will Dijkstra’s be required for this? It needs to be fast enough to calculate for each bot multiple times in their life (eg. if they get knocked off their path then they will have to find a new one)

Thanks,
roland

[moogie]

Maybe I am getting confused, but there is only one shortest path for the images you have provided. Do you want instead to have multiple semi-optimal paths?

[micecd]

Solution, use 2 paths and then combine them.

Split up the 2 points A -> B into A -> B -> C

Pick a point on the grid from random points between 0-width for x and 0-height for y for walkable points.

Then, apply the pathfinding for AB then the pathfinding for BC, and then combine the path points.

[JVallius]

Hey, interesting problem!

I thought something like this:

http://dl.dropbox.com/s/un474r0m5yoiflv/pathfinding.png

A1…B4 are waypoints. First, place waypoints like showing in the picture. Calculate the first path from Start to A1, A2 or A3. From there, calculate a path to B1, B2, B3 or B4, and from there to the End.

You can place waypoints manually or code a simple loop.

Hope this helps.

[Orangy_Tang]

Here’s an idea:

Rather than passable/impassable for your tiles, have a ‘cost’ associated with moving through them. Impassable are +infinity, and initially all passable tiles start with cost 0. Then:

1. Find the most optimal path considering the costs with regular A*
2. Store that path as a possible path
3. For every tile that the path touches, increase the cost of traversing that tile.
4. Repeat until you have ‘enough’ paths.

This effectively means that every path after than the first, it’s ‘harder’ to take the same route as an existing path. Note that you don’t set the tiles to impassable, as you still want the tiles to be used if there’s no other option (like the tile immediately right of your green start square).

[JVallius]

@Orangy Tang

This sounds good, much better than mine!

[roland]

Thanks for your comments

@moogie

Maybe I am getting confused, but there is only one shortest path for the images you have provided. Do you want instead to have multiple semi-optimal paths?

Yeah exactly.

@JVallius

Hey, interesting problem!

I thought something like this:

http://dl.dropbox.com/s/un474r0m5yoiflv/pathfinding.png

A1…B4 are waypoints. First, place waypoints like showing in the picture. Calculate the first path from Start to A1, A2 or A3. From there, calculate a path to B1, B2, B3 or B4, and from there to the End.

You can place waypoints manually or code a simple loop.

Hope this helps.

I like this idea - I didn’t think of that. Although I’d have to figure out how to place the waypoints on my maps, which are quite more complex than this - I need a solution for any possible map made and this might be difficult.

@Orangy Tang

Here’s an idea:

Rather than passable/impassable for your tiles, have a ‘cost’ associated with moving through them. Impassable are +infinity, and initially all passable tiles start with cost 0. Then:

1. Find the most optimal path considering the costs with regular A*
2. Store that path as a possible path
3. For every tile that the path touches, increase the cost of traversing that tile.
4. Repeat until you have ‘enough’ paths.

This effectively means that every path after than the first, it’s ‘harder’ to take the same route as an existing path. Note that you don’t set the tiles to impassable, as you still want the tiles to be used if there’s no other option (like the tile immediately right of your green start square).

Cool. I think I’ll try this. Some routes are much “taller” than 1 tile as in my example map so I’ll have to make the cost increase for the neighbours around the node as well - but only neighbours that are accessable by the node (can raycast between them without hitting any blocks)
Thanks

[pjt33]

I like Orangy Tang’s idea a lot, but I’m going to throw a second idea into the ring, in case you’re keen enough to try testing various ideas and see how effective they are. In short: meet in the middle.

This idea takes a parameter E (for excess) which indicates how much worse than optimal you’re willing to accept. First find the optimal path length, L. Then, reusing the data structures you’ve already built up, extend into a breadth-first search of all nodes reachable from your start point in no more than EL/2 and with heuristic estimate no worse than EL/2. Now do a similar BFS from the end point. The intersection of the reachable points gives you paths of length no more than EL, and for each node in the intersection the path you get is the optimal path through that node.

The main downsides are that the two BFS will expand quite a lot more nodes than the original A*, and that you need to deduplicate. However, you’ll probably need to do that with Orangy Tang’s answer too unless you have a good heuristic for how much penalty to apply to each existing path, so without careful analysis or profiling it’s hard to say which is faster.

[roland]

I took Orangy Tang’s solution - I need to improve the heuristic a bit but it will work well. I will probably search for 4-5 paths and choose one at random, only 4-5x slower than always choosing the fastest path, which I can deal with.

Ingame Screenshot: