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