Automatic navigation meshes

[Guessmyname]

http://www.moddb.com/games/overgrowth/n ... ion-meshes

Not so much a feature request as 'something people might find interesting'. Of note:

the lead AI programmer for Crysis (Mikko Mononen) recently released an open-source navigation mesh library called Recast, along with a companion pathfinding library called Detour. You can find the Google Code project here.

Don't know how adaptable this is to an RTS engine, but still interesting.

[Argh]

It's quite applicable to an RTS- a grid could be built, then edited in-game, to allow for 3D navigation of actors in a scene, for example (the engine I'm working with atm supports this). Such techniques lead to better navigation of characters, a lower CPU load (paths from A-->B can be stored, so no costly re-calculations), the arbitrary shapes allow for odd shapes, areas can be set 'off limits' very easily, etc., etc.

[Guessmyname]

How well would it work with deforming terrain though?

[Argh]

It isn't really designed for that... like, IDK, 90% of the other smart things people are doing to solve these kinds of problems. Terrain deformation's a very expensive novelty.

[Guessmyname]

Hmm. If we had that ROAM map mesh optimiser whatsit implemented, I wonder if using that to make the nav mesh would be viable... though that wouldn't take into account features or buildings etc etc... :/

[Argh]

A nav-mesh may only be used with things you can't destroy. It'd be great for cities where buildings can be destroyed, but leave impassible rubble and other things of that sort- the illusion can be maintained fairly easily.

Or, as I alluded to earlier, nav-mesh squares could have different states, and switching from passable to impassible and vice-versa would be possible.

[Pxtl]

I'd be more excited about this if Spring weren't already so committed to landscape-based terrain - it seems like it would be fantastic for an RTS game that allows more complex topology, like one that had bridges or even full underground quake-style maps.

[Guessmyname]

I'd be more excited about this if Spring weren't already so committed to landscape-based terrain - it seems like it would be fantastic for an RTS game that allows more complex topology, like one that had bridges or even full underground quake-style maps.

Bridges would most likely be a model anyway, wouldn't they?

[Hobo Joe]

New pathfinding would be very good for spring, that's my biggest gripe with it at the moment, it's slow and it makes units take really stupid paths so often, not to mention it doesn't support moving across things that aren't part of the map itself.


The one thing I thought was good about SupCom2 was the pathfinding, it'd be amazing if we could get something like that, though I know that few if any of the developers have the skill to do something like that, much less the inclination.

[jK]

Using a FPS mesh navigation AI in a RTS would be just a big fail:
1. those AIs calculate waypoints, which will cause units/agents to walk always on the same paths, something what you really don't want in a RTS
2. it even cause more problems with groups/hordes

The non-plus ultra for RTSs is just A* and that's what Spring is using.
Sure there are many extensions for it to optimize group behavior, one is heatmapping which is already integrated, but broken in <=81. In 82+ it will work, still it's not perfect yet.

[Hobo Joe]

one is heatmapping which is already integrated, but broken in <=81. In 82+ it will work, still it's not perfect yet.

This sounds really interesting, can you elaborate?

[Kloot]

Heat-mapping means each unit leaves a decaying trail of heat on the map along its path that is avoided by other units, with the effect of spreading out large groups (resulting in less congestion, etc).

And yes, navigation meshes are not very suited to heightmap-based engines.

though I know that few if any of the developers have the skill to do something like that

OT, but how would you even know what our skillsets are?

[Das Bruce]

It's a ploy.

[Guessmyname]

Fair enough. Just thought I'd chuck it out there; it looked interesting and everyone complains about the pathfinder, thus...

[Argh]

1. The engine I'm doing something with atm doesn't have these supposed problems with local steering jK insists are inevitable. That is handled in a different way.

2. There's no doubt that for global pathing, it picks the optimal path, which can lead to congestion in a sector. That is one of the downfalls of this kind of system if that isn't taken into account, but the game engine I'm dealing with doesn't consider it a problem for various reasons.

That doesn't mean there aren't reasonable solutions. Congestion could be handled by tracking sector membership and denying a local steering decision to continue moving along a path if a sector ahead of the actor is too congested. If sectors aren't absurdly small, then it should both perform reasonably well if performed only once a second or so, or better yet load-balanced across all actors over that period.

In fact, it should actually work quite a bit better than heatmapping simply due to a lower sector count and because of fewer required sector tests, and improvements in local steering code (i.e., adopting the raytest model of avoidance or similar, once every tenth of a second / actor) could make up the difference, along with perhaps a weighting variable for Really Big and Really Small stuff to determine congestion levels or even do some basic projective analysis.

In fact, the biggest problem would be handling immobile actors gracefully, I suspect, but I can already tell that nobody's actually interested in being open-minded.

[aegis]

Heat-mapping means each unit leaves a decaying trail of heat on the map along its path that is avoided by other units, with the effect of spreading out large groups (resulting in less congestion, etc).

the university's crowd continuum idea creates heat in front of units, so two units are less likely to collide

[JohannesH]

Oh I thought the fixed heatmap pathing was already in... Then I must ask though, how much do you feel units will spread in a way you don't want them to, when microing similarly as you do now? How should one change the way you order units around? How easy is it to make units clump together when needed.

And if it's felt it's unwanted change for some game can it be disabled for that game and still benefit from future fixes to pathfinding?

[Argh]

The heatmap was designed to be disable-able, and IIRC, not enabled by default.

[jK]

No, heatmapping can't be disabled, you only can change the modifiers, so it won't take into account for pathing (still it will be computed).

and here a visualization why it is broken in <=81


you also see that it isn't perfect in 82+ either: gollie has the same trace width as a pw, the velocity isn't taken into account, nor is the turnrate, ...

[Argh]

No, heatmapping can't be disabled, you only can change the modifiers, so it won't take into account for pathing (still it will be computed).

Eh... I thought when imbazcek put that in, the default was to not take it into account. Anyhow, I agree that the way it's working there is less than ideal.

And why is it projecting heat so far ahead of the actors? If that's trying to avoid future congestion, then it should probably use a wider projection...