How are walkable regions determined, and movements handled on a 3D map?

Question

I've created a 3D scene with both indoor and outdoor parts. The outdoor part has bridges and caves also.

How is it possible to handle player movements on it?

My intuition is: To determine the walkable regions, I could create a large grid. If the normal under the segment is not too steep, then it is walkable. If the difference between the heights of two neighboring segments in not large, then the player can move between them.

My solution is far from optimal. It would consume a lot of memory, and it can't handle situations, when there are multiple walkable regions on the same XZ position (for example a bridge over a valley)

How to manage movements effectively? How is it solved in game engines like Unreal or Unity?

Answer 1

You spawn a bot in a known accessible location and then tell it to move a little bit in a few directions (the 8 cardinal and half-cardinals is usually enough) from that spot.

If it didn't hit anything you teleport the bot to those new locations and repeat. Add a nearness filter to previously explored points so you don't over-sample.

if it did hit something then you can probe in that general direction to discover the boundaries If you find 2 edge points nearby each other you can try and move through the middle of it.

Here is an article detailing on how you can achieve that.

Note that this method assumes the player cannot jump. If he can then you need to add jumps to the probes.

Answer 2

I think you are on the right track. One possibility to create a walkable area is to create a navigation mesh.
They can be created automatically and on good resource how it can be done can be found here.
They also make pathfinding for bots/AI pretty easy but as you said use up some memory.

As you guessed you can create this navigation mesh basically by getting the normal of triangles and depending on the angle determine if the area is walkable, if yes you can create a duplicate triangle and add it to the navigation mesh. Each vertice of the triangle acts as navigation node. Depending on the player or other agents the pathfinding can apply different rules for pathfinding as size of the agent.
When generating the navigation meshes there are many parameters you can change to modify it to your needs. One big benefit is that jumping between navigation meshes can be handled as well. You can create on multi purpose navigation mesh or many meshes with specific criteria as it suits your needs better.