Support Forum

Pathfinding on ocean

Hi,

I have been trying to implement pathfinding on a large ocean game (like sid mieres but 3d) and I have been playing around with the Recast graph due to the size of the world and needing to move ships from port to port as well as avoiding each other.

I am yet to create a smooth workable AI using this system and I would just like to ask if anyone has created something like this using this asset and if you had any pointers or suggestions on what may work the best.

Currently using the Recast graph due to world size and I am able to limit the walkable area’s to everything below a certain height, which matches with the islands being non-walkable quite nicely. The issue is that the terrain (sea floor) is not flat across the entire ocean and so the path’s that are calculated often translate into ‘wonky’ or strange pathing by the ship on the surface of the water.

I actually think there may be a simpler way to do this and I may be over complicating it as the vast majority of the game world is ‘walkable’ and they only really need to not be moveable when terrain is above a certain Y value. (perhaps the navmesh needs to be applied to a flat plane on the ocean surface?)

Or perhaps I am not understanding how to use the recast graph correctly. Would anybody have any suggestions or pointers or further reading topics on how to best achieve this?

Many thanks,

Stephen.

I think your plan to use Navmesh for the ocean surface is a good one. Is your world spherical or flat? We are working on a spherical world and have separate Navmeshes for water and land (so that the boat do not traverse the land and land vehicles do not traverse the water).

Jacob

P.S. We don’t quite have A* working 100% yet which is why i’m lurking on this form.

Hi Jacob,

World is flat so a fake ocean mesh plane might work rather than the terrain. I’ll be doing some more testing this weekend to see if I can achieve something that works well for ocean movement.

I’ll update this thread.

Thanks,

Ste

Just to provide an update:

I’ve been working on a system that will work best for my needs and I have finally got something that seems to work nicely for my use case (large open world ocean with ships and some islands)

I ended up using a grid graph with a large node size (No need for lots of nodes as almost all areas are walkable except the islands).

My logic basically first checks the target location I have clicked on the ocean surface and then creates a linecast between my ship and target. If the linecast intersects with ‘terrain’ then I know there is an island in my path and I then instruct the ship to use the grid graph for pathfinding (to route around the island)

If there is no intersecting terrain (clear line if sight), I then check the depth by spawning my own ‘depth’ nodes along the linecast (they just have a basic bool and raycast dowards to check depth to sea floor). If all come back as valid then I simply ignore using any A* pathfinding and move ship to target.

This seems to work really nicely and as my islands are fairly spread out most of the time there is no use of the grid graph.

I will be tweaking this further for optimisations and refining ship movement around intricate islands but it performs well.

Also whilst testing and researching, I read quite a bit on pathfinding theory and found this site excellent at gaining a deeper understanding on the topic: https://www.redblobgames.com/pathfinding/tower-defense/

There is also this page from the same guy and he talks about ‘wraparound maps’ which I saw and thought might point you in the right direction for a spherical world: http://theory.stanford.edu/~amitp/GameProgramming/MapRepresentations.html#wraparound-maps

From the page:

If your world is spherical or toroidal, then objects can “wrap” around from one end of the map to the other. The shortest path could lie in any direction, so all directions must be explored. If using a grid, you can adapt the heuristic to consider wrapping around. Instead of abs(x1 - x2) you can use min(abs(x1 - x2), (x1+mapsize) - x2, (x2+mapsize) - x1) . This will take the min of three options: either staying on the map without wrapping, wrapping when x1 is on the left side, or wrapping when x2 is on the left side. You’d do the same for each axis that wraps. Essentially you calculate the heuristic assuming that the map is adjacent to copies of itself.

Anyway hope this helps!

Ste