Hi,
for my game, I would like to make a pathfinding algorithm, that computes the shortest route for a ship between any two points on the world. Already, I have a simple A* algorithm but it is too slow for very long, complicated distances. What could be the best solution? Your answer would be so much appreciated.
Salut,
Laetitia
Hi,
many thanks for your reply.
What I have at the moment is fairly similar. But in fact, using A* for step 5, with a graph that has 3600x1800 nodes (ie 0.1 deg resolution). But if I go from the Pacific to the Mediterranean, this takes almost forever. Therefore, I was thinking about ways of hierarchical algorithms. Ie first a solution on a very coarse grid, then refine. But I don't know whether such algorithms exist? Also, I'd like to use visibility connections, because I think that's is a more perfect way of finding a route. Ie ships travel on great circles to the next visible point on the route - if that makes sense. Also, I will check the thread you suggested.
Merci beaucoup,
Michael
The complex solution to this type of problem as alluded to is to implement a hierarchy within the structure of the pathfinding so that A* doesn't search through that many nodes. If you take the globe and partition it into a lower resolution polar grid, and then associate each of the high detail nodes into those 'buckets', you can create a hierarchy for the pathfinder that will dramatically reduce the complexity of calculating the path.
As an alternative, depending on your requirements, for that many nodes, it would only be about 25MB to store a lookup table for pathfinding, if the pathfinding requirements don't need to include dynamic weighting. If weighting needs to change dynamically it gets complex with having to update the lookup table.
As another alternative. If the goal node changes infrequently, or especially if there are many units moving to shared destinations, it might be faster and easier to implement if you flood fill from the destination node to generate an influence map that the ships can simply follow the decreasing weighted edges until they reach the destination. I've experimented with good results of essentially pathfinding on influence maps like this by flooding weight values. Since the flood isn't so branch and condition heavy as a full path query, building and updating the layers are actually very fast and cache friendly, and once you have the influence map, pathfinding is just a lookup and a follow into the best weighted neighbor.
Hi,
many thanks for your replies. I think they make complete sense, but will have to think about them for a bit, then implement.
Many thanks,
L.
Your grids are too big, you need to reduce their sizes or make smaller runs. It is faster to break the A* to small portions, because for big runs you search bigger and bigger areas (even with the euclidian distance constraint, it will still scale pretty fast with huge graphs).
Think that realistically the ship wouldn't go straight from one point to another of the world, it would stop on some ports or military forts for repairs and to get more supplies (such as food and water). You could calculate the distance to ports then to other ports and create a dynamic algorithm, very similar to A* to determine the best route.
Off-topic: Out of curiosity I created a 3600x1800 random map for my A* to solve, it took 4.449775 seconds o.O
