Dynamic Obstacles

[Arnaud Jamin]

Hello,

I wonder if Recast could be used to manage many "moving dynamic obstacles" efficiently.
What I mean by "moving dynamic obstacles" is for example a unit in a game like Starcraft.
A unit occupies a small space in the map and usually it cannot be passed through.
Since Recast is based on a navmesh, entities do not occupy a space inside the navmesh.

The attached image describes the different behaviour I need.
I do not have a lot of verticality. My world is mainly flat.

Do you think Recast could still be used for those needs or a grid based pathfind would be more adapted?

I read Mikko's blog and I know he’s working on dynamic avoidance. The last post about that suggested the use of a local grid around the character, which makes me think a grid base pathfind may be more suited.

Thanks !

[Mikko Mononen]

Hi,

Your problem sounds like it could be better solved using grids. Detour
Tile cache allows you to change the topology of the navmesh pretty
quickly, but you may get better results using coarser grids.

You may find Chris Jurney's presentations from GDC inspiring:
http://www.chrisjurney.com/

--mikko

[Arnaud Jamin]

Thanks !

[Drabner]

Hey,
sorry for mild thread necromancy.

I am currently doing some research for an RTS game idea of mine.
Basically, I'd have a LOT (hundreds) of units running around on the
terrain and units of same player should not block each other while
moving or idling, but when doing any action.
And of course, units of opposing players should always block each
other. Then buildings, etc. Basic RTS stuff, just with a larger scale,
think Supreme Commander, maybe.

This thread made me jump to some assumptions, please tell me if those
are correct:
I could implement this by:
1) Using recast only, making different nav meshes for each faction,
each nav mesh being influenced by blocking dynamic units like enemies
or own "active" units. So basically introducing agents as blocking
objects. However, this might end up being pretty heavy on performance,
with all those dynamic objects and multiple nav meshes.
2) Using recast, but putting another system (grids) on top of it, so
the AI would look at the nav meshes as well as the system on top of it
(which includes the masses of units) to find a path.
3) Using another system (grid) only, skipping recast.

Right now, 2 and 3 seem to be the best options to me.
I'd personally prefer 2, since the terrain itself should be dynamic
(changing terrain, plus objects like buildings blocking paths). And
recast already can handle all of that. In a purely grid-based system,
I'd have to do all of the dynamic handling myself.

[Mikko Mononen]

Hi,

If you can prune down the navigation problem to 2D, then I suggest to
go for it! Layers add a lot of complexity. Grid is the easiest data
structure if you are dealing with dynamic obstacles. Check out this
blog, on how to speed up pathfinding on grids:
http://harablog.wordpress.com/
I also recommend into trying to find path for a whole ground and then
resolve paths for individuals based on that.

You may find Roland's work inspiring: http://people.cs.uu.nl/roland/

If you have hundreds of units, then global avoidance methods like
continuum crowds or aggregate dynamics
(http://gamma.cs.unc.edu/DenseCrowds/) are cheaper than trying to
resolve the collisions individually (like RVO). It is hard to say
where the sweet spot is, though.

Always remember that multi-agent navigation is untractable problem.
Whether the agents will reach the goal is just statistics unless you
allow them to pass through each other.

--mikko

[Drabner]

Thanks for the ideas!

I'm not sure if pure 2D would suffice, since I intend to also have
caves and other underground structures in the same the level as
"normal" terrain.
Think of elves running around terrain and then entering a dwarven
complex underground. Mind you, the dwarven complex was built by
another player, so the whole cave is a dynamic change to the level as
well.

Also... I do consider flying units, not sure yet what impact that has
on anything.

> If you have hundreds of units, then global avoidance methods like
> continuum crowds or aggregate dynamics
> (http://gamma.cs.unc.edu/DenseCrowds/) are cheaper than trying to
> resolve the collisions individually (like RVO). It is hard to say
> where the sweet spot is, though.

Yeah, I've definitely not chosen the easiest topic here.

> Always remember that multi-agent navigation is untractable problem.
> Whether the agents will reach the goal is just statistics unless you
> allow them to pass through each other.
>

Definitely. "Reaching the goal" is as relative as it can be in an RTS
game.
Sometimes the goal may be the 200th place in the queue of people
wanting to reach it, too ;)
Hmm... "Queue standing 3000 - The Game"...