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?

  • \$\begingroup\$ Please explain the downvote. I will accept an answer, as soon as I can try them out \$\endgroup\$ – Iter Ator May 30 '17 at 15:10

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.

  • \$\begingroup\$ This should be done during the development, and not by the game when the player loads the scene, right? \$\endgroup\$ – Vaillancourt May 30 '17 at 12:06
  • \$\begingroup\$ That's basically A* \$\endgroup\$ – liggiorgio May 30 '17 at 12:28
  • 1
    \$\begingroup\$ @liggiorgio no it's a floodfill to discover all the walkable area. A* implies there is a destination and a heuristic. \$\endgroup\$ – ratchet freak May 30 '17 at 12:44
  • \$\begingroup\$ Oh snap, you're right, I confused them \$\endgroup\$ – liggiorgio May 30 '17 at 14:26

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.

  • 1
    \$\begingroup\$ @Iter You can either precompute a navigation mesh or design it by hand/using tools overtop your existing map. This also allows for multiple regions on the same XZ position as you put it. \$\endgroup\$ – Danny Yaroslavski May 30 '17 at 12:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.