One thing I am struggling with is how to implement smart Ai to hunt an agent in 3D.

Say a shark against a fish, or a spaceship vs a spaceship.

Issues I have currently:

Obviously using a navmesh or a grid is literally impossible due to it being a 3D volume, its just no chance of traditional pathfinding solution due to memory/performance issues.

Steering behaviours:

Well they are kind've dumb, suppose a fish is behind some rocks, how does the shark know whether it can go through a cave (and fit through) to take a short cut, or go around the rocks to get the fish without a pathfinder…I can check if the agent can fit through its immediate next position with some physics checks, but a seeking behaviour won't then try to go around the rock when that option is not on the cards.

What are good solutions here for 3D volume pathfinding?

My immediate thought is you can just implement A-star using cubes surrounding the player in lieu of squares. Create appropriate sized cubes around your player and use A* to determine which cube to head to next.

in terms of obstructions you could either explicitly mark certain cubes as impassible or on the fly check a volume with a boxcast or some equivalent for a collider and exclude it from the search.

Warframe did something here, AFAIK using a volume grid:

https://www.gdcvault.com/play/1022016/Getting-off-the-NavMesh-Navigating​

It would be also possible to generate convex polyhedra, and the faces become path segments so path finding algorithms work as usual, and number of nodes remains small. A similar problem is generating portals or Potential Visible Set data, which dates back to games like Quake. But that's very difficult to automate with current day detail levels. (First related paper i've found: https://www.gri.msstate.edu/publications/docs/2002/10/4852prash01.pdf)

CelticSir said:
Well they are kind've dumb, suppose a fish is behind some rocks, how does the shark know whether it can go through a cave (and fit through) to take a short cut, or go around the rocks to get the fish without a pathfinder…I can check if the agent can fit through its immediate next position with some physics checks, but a seeking behaviour won't then try to go around the rock when that option is not on the cards.

This does not sound dumb to me at all but natural. I don't think living creatures use a form of path finding, other then memorizing some paths which have been learned. If the shark follows the fish, then notices it won't fit through a narrow passage of rocks, he might just stop, seek a random way around the obstacle, and he might miss to catch up the fish. It's natural, but to avoid dumb looking behavior we need to model some natural motion planning / obstacle avoiding, which surely is harder to get right than following some path. But because 3D means risk of performance issues i'd try that option first, eventually.

This is something I have thought about a bit. If you make your terrain using an octree of voxels combined with either marching cubes, dual contouring or some similar algorithm, 3D pathing should come naturally since space is already divided up nicely. At that point you can just use any standard pathfinding algorithm and search voxels with no sign changes in them. Accounting for different sized creatures might be a bit more tricky but it should still be doable by checking your creature bounding object with multiple voxels. Again an octree will help with that.

A* works just fine in “3D” because it doesn't care. You have a function which tests adjacent nodes in your map for fitness, so just pass it nodes up, down, and all directions into the fifth dimension if you like. As long as you code the fitness test to examine all movable nodes on your map it will find a path just fine.

So Maybe your problem is how to work the nodes into your map? Form cubes as wristshot0 suggests.

So instead of your map being in a 2D array, put it in a 3D array where the third index is “depth”.

Each record in the array points to extra data for the map like move cost (zero if you can't move), type of terrain in the cube etc.

The problem with cubes is just how many there would need to be in 3D the map is huge. we're talking about a graph of n^3 which is painfully slow. Even a map of 50 by 50 by 50 units becomes 125,000 nodes. It's not doable.

CelticSir said:

The problem with cubes is just how many there would need to be in 3D the map is huge. we're talking about a graph of n^3 which is painfully slow. Even a map of 50 by 50 by 50 units becomes 125,000 nodes. It's not doable.

Not necessarily. Fist you are not checking every cube. Second In a proper octree you will have empty space represented by a few large cubes. My test world is 800km in diameter with a half meter resolution and with LOD it fits into 2 gig.

@Gnollrunner

Gnollrunner said:

CelticSir said:

The problem with cubes is just how many there would need to be in 3D the map is huge. we're talking about a graph of n^3 which is painfully slow. Even a map of 50 by 50 by 50 units becomes 125,000 nodes. It's not doable.

Not necessarily. Fist you are not checking every cube. Second In a proper octree you will have empty space represented by a few large cubes. My test world is 800km in diameter with a half meter resolution and with LOD it fits into 2 gig.

Hmm every example I find to learn quad/octree people use tiny points rather than objects with a 2d/3d bounds when they setup the structure, which is a pain because it then doesn't cover situations where the object overlaps two regions.

@undefined With marching cubes nothing crosses cube boundaries. The main downside is you need to use an advanced form of it if you want terrain with sharp corners.