# Pathfinding on 7 oceans

This topic is 2140 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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

##### Share on other sites
I suggest perusing the AI forum. There was a recent post there with a link to a fantastic Gamasutra article all about pathfinding.

Off the top of my head I would recommend this:
1. Break the world map into a grid, like a globe, with nodes at every intersection of latitudinal and longitudinal lines.
2. Every node should know how to get to the 4 nodes attached to it.
3. Calculate the closest node to your destination.
4. Calculate the closest node to your origin.
5. Calculate a path from the origin node to the destination node.
6. Use A* to get your ship to the origin node.
7. Use A* to get your ship from the destination node to the actual destination.

The trick here is that steps 1 & 2 can be be precomputed at compile time. I believe this is called a navmesh. Also I am assuming there is just open water between any two points and no land masses. Introducing intervening land masses will complicate step 5 slightly but not by much. It will be up to you find the optimum size of the grid.

##### Share on other sites

Hi,

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

##### Share on other sites

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.

##### Share on other sites
I was thinking about multiple heirarchy nav meshes after I posted. This is a good idea and would probably be how I solved the problem. The trick is to make each grid align with the next finer grid so that every node knows not only the 4 peer nodes attached to it but also the node it is sitting on top of in the next finer graph. Additionally you need to check when it is time to use the finer grained graph. I would do this as a fifth test where you are basically testing to see if it is better to stay at the current node instead of moving to the next node. An example of the implementation I would use:

Assume a line of points numbered from 0 to 1000. I would create two graphs, one with every point evenly divisible by 100 (0, 100, 200,...) and one with every point that is evenly divisible by 10 (0, 10, ... 100, 110,...). You can see that the two graphs intersect at every one of the coarser grained graph's nodes. Now lets say I am standing at point 0 and want to move to point 240. I would start in the coarser grained graph and move to point 100 then to point 200. I can then see that I stay closer to my goal by staying at point 200 then by moving to 300 which would overshoot it. I then switch to the fine grained graph and I'm already standing at one of its nodes (200) so I then move to 210, 220, 230, and finally 240. Tada! I get cake :)

I hope this made sense.

##### Share on other sites

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.

##### Share on other sites

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

##### Share on other sites
Why a grid? A graph with the ports as nodes, since ships go from port to port and not "anywhere in the world", and the allowed direct routes without stops as edges, is going to have only a few hundred nodes at most, easily processed with A*; exact coordinates along routes can be precomputed (72% of the way from Marseille to Ajaccio you are at xx'xx'' east yy'yy'' north). If you need routes from/to the middle of the sea, a compact precomputed data structure can contain the sea region from which each port can be reached; this gives the set of arcs to add when adding a sea location to the navigation graph as an extra node.

• 18
• 29
• 11
• 23
• 16