Thoughts on OpenSteer?

[Yati]

Hi,

I'm interested to know if anyone has used OpenSteer library and what their thoughts are on it.

I'm probably going to use it for a university project, its made by Craig Reynolds so it probably some very solid code.

[duststorm]

It's already pretty old.
Today velocity obstacles and dynamic avoidance algorithms are all the hype.
DetourCrowd of the recastnavigation library is a possible (open source) implementation of such algorithm.

[Mind Calamity]

Why pretty old, I was taking a look at it a few months ago and it managed to impress me quite a bit.

(Keep in mind that my skill and knowledge in AI is little to none, but I'm still interested in a more detailed opinion.)

[duststorm]

It depends on what you need it to do. OpenSteer still has some useful formation types built-in which can be really useful (units move in a fixed formation relative to each other), that would need a custom implementation in newer algorithms.
For vehicle steering it will probably work very well too (or even better, since these RVO algorithms seem to be mostly tailored to people steering).

For having a lot of human agents (like big crowds), velocity obstacle avoidance (detourcrowd uses a variant called RVO) performs much better. It lends itself better to parallelization and divide and conquer approaches, can handle a lot more agents in less time and has better results (it's more precise and avoids more collisions) for human-like characters that try to avoid collisions.
Opensteer like boids type of behaviour can, however, still be implemented on top of velocity obstacle steering to achieve behaviours such as flocking, avoiding, following, ... that opensteer is famous for.

Here you can find a comparison and some information on how it works:
http://gamma.cs.unc.edu/CA/ClearPath.pdf
http://gamma.cs.unc.edu/CA/
http://www.youtube.com/watch?v=Hc6kng5A ... re=related
http://gamma.cs.unc.edu/RVO2/

http://digestingduck.blogspot.be/2009/1 ... -path.html
http://digestingduck.blogspot.be/2009/1 ... hings.html

[Mind Calamity]

AI is an amazing field to study, although I find myself dedicating very little time to it. Thanks for the awesome links and information!

[duststorm]

The game AI community is a pretty specific and dedicated community. There are a few invaluable information sources on the web, however. I can recommend the website http://aigamedev.com/ as a starting point for keeping updated with game AI.

[al2950]

I looked at opensteer a while back and its very interesting to study but I didnt like the design too much so implemented my own system. One book I found very useful regarding AI (at least beginner AI ) is "Programming Game AI by Example" by Mat Buckland

[duststorm]

One book I found very useful regarding AI (at least beginner AI ) is "Programming Game AI by Example" by Mat Buckland

That book is indeed a nice introduction to the field, but you need to take it with a grain of salt. It's written almost 10 years ago, and in that time a lot has changed. So don't take it as gospel or the best solution to your problems, some of the solutions explained in it have been improved a long time ago. It's still very good for gaining insight and base understanding however.

In any case, whatever pathfinding and steering algorithms you use, don't make the mistake of going back to waypoint systems. Use navmeshes!

[Yati]

yes, I have been following your Recast/Detour project. I'm waiting for terrain navMeshes

[jacmoe]

Why wait?
Go to Bitbucket and find OgreRecast, it's there. Terrain navmesh stuff.

As for OpenSteer..

Basically, it's just a demonstration of a concept.
Was probably never meant to be used as-is.

Steering is only useful in very small doses, because it doesn't fit into navmesh navigation and physics very well.

You can use it for boids, though.
Like birds.

Otherwise: don't bother.
Use Recast/Detour.

[duststorm]

I'm waiting for terrain navMeshes

Why wait?
Go to Bitbucket and find OgreRecast, it's there. Terrain navmesh stuff.

He probably means that terrain navmeshes is still in a very early stage, and he's right
But today I made some good progress on the subject!

Use Recast/Detour.

Couldn't agree more!

[Yati]

I've had a look at duststorm's update, nice . I was wondering is it possible to manually make the nav-mesh (in Maya) and use it with terrain? My projects terrain size is minuscule compared to the terrain in duststorm's demo and I know exactly which part should be walk able.

Update:
I think this was a brain fart of a idea, because if I did this then adding gates would not be possable

[duststorm]

I was wondering is it possible to manually make the nav-mesh (in Maya) and use it with terrain?
Update:
I think this was a brain fart of a idea, because if I did this then adding gates would not be possable

I was actually thinking among the same lines too.
In theory it would be possible to manually construct a navmesh and feed it to detourCrowd for navigation, given that you stick to the constraints (such as only convex polygons, obey parameters, ...) of recast. Instead I would first automatically generate a navmesh and then edit it manually where necessary, though. As it would be much faster and I think the results of recast will amaze you (with the right parameters you probably need almost no tweaking). Level editors like that of the Elder Scrolls work that way (also have a look at this video).

However, you would do this with a regular recast single navmesh, or a recast tiled navmesh (not implemented in my demo), but not with detourTileCache. That means no dynamic temporary obstacles. Quick mesh rebuilding per tile would still be possible with tiled navmesh.
The reason why it's not so simple to edit by hand with dtTileCache is that dtTileCache only needs to store almost-finished navmesh tiles, in a state before they are actually a polygonal navmesh (they are compressed heightfields). I haven't looked into this exactly, but maybe it would be possible to edit those by hand too, instead of the actual navmesh (while still not looking too weird for a user). Maybe it's also possible to implement an editor that produces the navmesh, lets you edit it and then reflects those changes back in the compressed heightfield tile. These aspects are as for now unexplored, but deserve serious consideration if recast is going to make it in an editor like ogitor one day (which I seriously hope for).

For doors you can actually mark static polygon areas on the recast navmesh (rcMarkPolyArea) at navmesh build time. In the engine you can then just change the area flag of that specific polygon on the navmesh (eg to walkable or unwalkable). So if your only aim is to have doors (of which you know the locations beforehand) it's possible even with navmesh editing. But arbitrary obstacles at any location will not be possible.

[Yati]

I was actually thinking among the same lines too.

I think you misunderstood me a little bit.

I meant make a mesh of the walk-able areas of the terrain as a mesh, like the dungeon mesh in you demo, then use it to generate the navmesh but not use it for rendering.

But it is true that using recast to generate a nav-mesh would be better so I'm doing that. The results are getting closer & closer to what I need

[duststorm]

I meant make a mesh of the walk-able areas of the terrain as a mesh, like the dungeon mesh in you demo, then use it to generate the navmesh but not use it for rendering.

That's possible, even with temporary obstacles. And you could even support dynamic navmesh rebuilding if you keep your simplified terrain geometry (the one with walkable areas you constructed manually) in memory, and when you need to regenerate a navmesh tile just feed that to recast along with any extra objects you want to add, instead of the real scene geometry.

But simplifying your scene manually to make recast generate the navmesh you want kind of beats the purpose of recast. Its goal was to do high quality automatic navmesh generation.

But I agree that it can be useful to allow a level designer to explicitly mark some areas of the map as "unwalkable". The simplest solution I can imagine is just to put a good old "invisible wall" in your scene. That can also be used by the physics engine to do collision detection and keep your characters from walking into forbidden areas.
If you want an alternative solution, that is what rcMarkConvexArea is for . It allows you to mark convex shaped areas (eg. boxes) and lets you assign custom area flags (for example: water, mud, unwalkable).