NavMesh baking and dynamic entities?

[beo6]

Hello everyone.

 

Since i get further and further quite nicely with my small RTS Project i have another question which is depending on performance.

 

 

I have units in a realtime strategy game. these can drive/walk around a terrain and buildings can be build by the player.

 

The first calculation of the navmes of the terrain with no entity on it took a couple of minutes in the editor.

First i tried to recalculate the navmesh when an entity reached its destination ingame. However that freezed the game for a very long time completely.

 

using the method SetNavigationMode(true) does nothing for entities that didn't got baked into the navmesh in the first place. The character controllers just bump into each another.

 

 

Is there anything i do wrong? Or is there a better way for pathfinding?

 

Maybe i should overwrite the destination when the controller encounters an obstacle and try to move around it manually?

 

 

Thanks for any idea, suggestion etc.

[YouGroove]

Your units must start in the Navmesh when they become active and use Navigation methods i think.

[beo6]

I don't really understand what you mean.

My units are always inside the Navmesh.

 

When i keep the GoToPosition function always running both units move around each other.

 

But:

1) i am not sure how the performance will go when there are many units with pathfinding always active.

 

2) it looks bad when a soldier moves near a tank where the tank is standing still and as soon as the soldier comes near the tank the tank also starts moving to make space for the soldier.

 

3) that would not work for buildings since these will not have a character controller and they should not move.

[beo6]

// small push.

 

Anyone already knows more?

 

I can't believe that we need to regenerate the complete navmesh which takes a long long time,

just when we dynamically add one obstacle in the level.

[AggrorJorn]

Why would you need to recalculate the entire navmesh once a person reaches its destination? I would only recalc the navmesh once you have placed a building.

 

I haven't tried it yet, but instead of recalculating the entire navmesh for a terrain, it might be possible to 'add' a new region to the navmesh. Not sure if there is a build in solution for this.

 

Secondly: If you are using character controllers (thus physics) for movement, consider using position translation. Have a look at this topic:

http://www.leadwerks.com/werkspace/topic/7958-navigation-without-physics/

 

Thirdly: Although there is some movement behaviour build in, it is difficult to have a solution that does exactly what you need and is finetuned to your needs. You would need to build in your own steering behaviours for your units.

 

 

Edit*

I am not seeing any official API calls to make alterations to the existing navmesh. The navmesh system that leadwerks uses (recast) does have this functionality, but there isn't a nice mapping via the Leadwerks API. Would love to see this though.

Edited February 18, 2014 by Aggror

[beo6]

Hello Aggror and thank you for your reply.

 

since i currently have no building functionality i tested with my existing units and they collided badly with the baked navmesh.

 

recreating the navmesh when a building is build also takes a very long time. (several minutes) so even this case is highly unusable since it pauses the whole game.

Changing the existing navmesh would be the best option i think.

 

The units i have already move nicely over the terrain so i don't think i need so much fine tuning.

 

I remember your mentioned thread about navigation without physics. However they talk about using the path data directly. If i would do that and move the entity with translate i would end up having the same issue and navigating around obstacles on my own.

Also i would have to wait for the standard LE 3.1 version so i can access the navpath from code since it is not accessible from LUA.

 

 

I think only flying units will not use the character controller and navmesh since they would not have issues flying over mountains or other obstacles.

 

 

So. +100 for having the possibility to change only small parts of the navmesh. (as long as that does not pause the game for minutes of course)

[YouGroove]

Also i would have to wait for the standard LE 3.1 version so i can access the navpath from code since it is not accessible from LUA.

 

Yep that's sad for Lua.

[Tim Shea]

I think buildings (and dynamic obstacles which do not themselves navigate) are intended to use the Prop collision type. Props should not affect the NavMesh, but they are dynamically handled when generating paths (at least, this is my understanding).

 

I also would love to see the navmesh and character controller fleshed out (or even just exposed so they can be overridden) but given what you have to work with I think your best option is to manually avoid assigning destinations inside dynamic obstacles, and then just use the baked navmesh.

 

Collisions between units are always an issue with A* pathfinding. You can google for some interesting solutions, e.g. crowd steering, but it isn't something that can really be addressed in the pathfinding algorithm itself.

[Josh]

What I found is that recalculating chunks of the navmesh was too slow when terrain was involved. What is really needed is a separation between static and dynamic geometry, so the static data can be cached and then the dynamic geometry laid on top.

 

Leadwerks internally already uses a tiled approach, so we're halfway there.

[DudeAwesome]

I would draw a radius for every Building and every Unit and would detect collisions to avoid this. Or just use aabb

[AggrorJorn]

What is really needed is a separation between static and dynamic geometry,

What is the definition of 'dynamic geometry' here? Geometry that gets placed by the gamer (eg a building in an rts game) or props that move due to physics (like crates, barrels.)

[tournamentdan]

I would draw a radius for every Building and every Unit and would detect collisions to avoid this. Or just use aabb

 

I agree. This is a fairly common practice in AI engines. Instead of updating the nav mesh they create what they call AI mesh. They use multiple raycasts that are parented to the character controller. With those raycasts you can detect the AI mesh and use it for cover nodes or even nonpathable walking space. For objects that are going to move. You can parent the AI mesh to a object like your building or crate or barrel. This can be done with physics mesh also but not all areas of the map will have a physics mesh.

 

I will be using this technique so cars and pedestrians can tell the difference between a side walk and street. That way I only use one nav mesh for both.

 

Check out this video for some ideas.