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?
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).
P.S. We don’t quite have A* working 100% yet which is why i’m lurking on this form.
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.
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!
This is an extremely old thread, however I believe this is relevant to anyone looking to do ship navigation even now. I just wanted to share an alternative solution for anyone that wants to use navmeshes instead.
Instead of utilizing a large grid graph which has poor performance unless you give up massive amounts of resolution, you can instead utilize a navmesh recast graph.
- Create a plane with a collider (no need for a mesh renderer) that acts as your pathfinding layer.
- Set up your pathfinder navmesh recast graph to rasterize only colliders and disable rasterize meshes.
- Set your Max Slope to 0 to make sure the mesh is only rendered on your flat plane, and set Walkable Height to a large value to prevent the navmesh from generating under your terrain and make sure the navmesh only spawns under open sky.
- Assign your pathfinding layer plane to a unique layer i.e. Pathfinding and in the unity Layer Collision Matrix (Edit → Project Settings → Physics → Layer Collision Matrix) disable collisions between all layers you don’t want to collide with the new Pathfinding layer.
You can easily adjust the resolution of this to work on larger worlds, or even adapt it to use ProceduralGraphMover if you have an exceedingly large world or do not require global pathfinding outside of the player range.
Hope this helps anyone looking into this