OgreCrowd: a crowd component for Ogre using Recast/Detour

[duststorm]

UPDATE 15: Update your bookmarks. Now that this has become much more than just a simple demo I decided to give it a proper name. Introducing: OgreCrowd. The bitbucket and github repo names have changed, and I've added an MIT license.

UPDATE 14: I did the first steps in realizing paging and instancing of crowds in larger scenes. A video is now also available.

UPDATE 13: Some work done on generic terrain integration (instead of fixed for one tile). You can now change terrain generation parameters for the demo in the OgreRecast.cfg file.

UPDATE 12: API documentation updated and windows binary package available! You can try out all demo features by changing the config in the OgreRecast.cfg file (for example switching from terrain demo to dungeon demo).

UPDATE 11: Made some good progress with terrain navmeshes. Cellsize is now much lower allowing better navmesh resolution. Also I demonstrate how to build only a selection of navmesh tiles from the whole terrain. That along with a lot of smaller features adds and fixes and improvements.

UPDATE 10: Some early progress on generating navmeshes from terrain. There's still some problems to tackle, though.

UPDATE 9: Extended the demo with an example of how to create a door. It's just a suggestion of a way to do it, not gospel.

UPDATE 8: Added dynamic walkable objects to the demo.

UPDATE 7: Convex temporary obstacles (and thus support for doors) is coming along nicely. There are still some issues with building the convex hulls for the obstacles, though.

UPDATE 6: Small update: added a test for steering a character that places temp obstacles and is not bound to an agent.

UPDATE 5: Added DtTileCache navmesh building and temporary obstacles.

UPDATE 4: Added navmesh building from more than one mesh.

UPDATE 3: The demo now also contains a mode where you can control an agent manually using the keyboard!

UPDATE 2: I updated the demo and gave it some real people.

UPDATE: To satisfy everyone I also created a mercurial repo. Both repos will be kept in sync, feel free to issue pull requests for improvements

The recast navigation library is not new to the Ogre community, although it has lost some popularity since it was first introduced on this forum some two years ago. Luckily the creator, Mikko Mononen, hasn't stayed still and during this time this already great library has grown and became even more amazing. The library is still being developed very actively. With this demo I intend to depart where mkultra333 left off with his simple Ogre+Recast integration demo and reintroduce a bare bones example of how to integrate the library in Ogre.
In the meanwhile I slipped in a showcase of one of the greatest new features.

Introducing: DetourCrowd!
This component is built on top of Detour, which handles pathfinding on a navmesh generated dynamically from your level geometry by Recast (each of these components are useable independently). DetourCrowd offers what the library was still missing: local independent steering of agents within a crowd. This involves steering towards a destination and avoiding others, or periodically stepping out of the way to let others pass while standing still.

I'm really excited about the performance and the quality of the steering approach, which is using an RVO algorithm (Reciprocal Velocity Obstacles). Simply put, individual agents plan their movement by anticipating the projected velocity vectors of others and neighbours come to a concensus about pathplanning.
The system uses a request queue to handle path calculations requested by agents, and allows specifying a maximum number of calculations per tick so you can set upper limits for finishing preparation of a frame in your application loop.

As I said the purpose of my demo was to create a minimal example to get you started quickly. It's single threaded (in practice you probably want to run detourCrowd in a separate thread) and contains minimal modifications from the tutorial framework application. I was able to cut a lot of corners by reusing snippets from the forum and referring to mkultra333 and Paul Wilson's previous Ogre+Recast demos.

Where does this demo fit in then? Well, firstly I'm using DetourCrowd for steering, while previously people resorted to implementing classic opensteer-style steering behaviour. I'm not an expert on these matters, but reading up on it I learned some advantages of RVO, like steering appears to be less jittery, more convincing and smooth steering, even in very crowded areas. Paul Wilson's application contained Ogre::Mesh to recast conversion, but it was a rather large project if you were just looking at a "getting started" guide, while mkultra333 serialized his own map format to recast.
This demo is a result of my recent personal experiments with recastnavigation, but I decided to share it with anyone who's interested. I hope to respark interest in this library within the Ogre community. Maybe this finally gives birth to a tutorial in the wiki. (something I was planning to do, but given that I still didn't take the time to put my berkelium snippet on there I make no promises)

Enough talking, let's have a look at some images!

Sorry about the stuttering in the video, it's because I was recording. The video is not great, it's better if you try it out yourself.

This video shows the three scenarios in the demo:

• Simple navigation: Left clicking places the destination marker, right clicking places begin marker. A change in the path lead to redrawing a new path, upon which the light blue agent restarts navigating from the begin to end marker.
  Additional agents can be added by pressing SPACE and will navigate towards the set destination as well.
• Wandering crowds: all dark blue agents wander off independently to random positions avoiding each other. The light blue agent can be controlled freely by the user.
• Chase: the dark blue agents chase the light blue agent like zombies chasing human meat. The user can move the light blue agent freely. Beware not to get overrun by too many of them!

Pressing ENTER swaps between the three scenarios

I've put the code public for anyone who's interested, but it's still a bit rough and hacky in some areas. I hope to clean that up soon.
Here it is: https://github.com/duststorm/OgreCrowd

The license is MIT, but note that some of the code is not originally mine (Ogre, recastnavigation, borrowed from mkultra333 and Paul Wilson). Thanks to all these fine people out there the licenses are all pretty liberal.
Suggestions for improvements, bug reports and fixes, as well as further experiments are welcome.

It should work on all platforms, though I've only tested it on Ubuntu linux at this time. It's made with Ogre 1.7.3 but I hope it also works with 1.8
I've included a qtcreator project file so it can be built using qmake(-qt4). A VS project should be easy to make, the demo is based on the example framework. (if someone wants to donate a VS project file, please do)

Some directions for future work:

• Apart from choosing a destination, at this time you cannot interactively control an agent within the crowd. (eg. having direct control over its velocity vector)
  This is an often suggested feature for DetourCrowd and is on the developer's TODO list. This would bridge the gap between player input handling, physics engine and detourCrowd.
  (see here: http://groups.google.com/group/recastna ... e110f026ea , here: http://code.google.com/p/recastnavigati ... ail?id=163 , here: http://groups.google.com/group/recastna ... c86233e67f and here: http://code.google.com/p/recastnavigati ... ail?id=163 )
• The random walk demo is implemented very inefficiently. For each agent it samples a random point on the navmesh (an algorithm which Mikko says is a bit heavy on CPU). It's just a quick experiment of how wandering crowds could work and there are a lot of easy improvements, such as caching calculated random points and re-assigning them to other agents.
• DetourCrowd should operate in a separate thread or even on multiple separate threads.
• Creating nav meshes from Ogre::Terrain
• Additional AI and steering behaviour? Callbacks to a higher level task-based AI system? Also author of the project Mikko Mononen is interested in researching this further.
• Dynamic retrieval of level properties from the navmesh, such as cover locations, climb-able or jumpable locations, ...
• Replacing the cylinders with animated characters, with their own character controllers.
• Handling dynamic levels, subdividing the navmesh in sectors which can be loaded and unloaded.
• Loading and unloading crowds based on camera location.

For more information about Recast and Detour, have a look at these sources:
Project webpage: http://code.google.com/p/recastnavigation/
Project's blog: http://digestingduck.blogspot.com/
Detailed presentation of how Recast works: http://digestingduck.blogspot.com/2010/ ... -past.html
Browse API online: http://www.stevefsp.org/projects/rcndoc/prod/index.html

Other topics on this forum:
http://www.ogre3d.org/forums/viewtopic.php?f=16&t=52455
http://www.ogre3d.org/forums/viewtopic.php?f=5&t=62079
http://www.ogre3d.org/forums/viewtopic.php?f=11&t=57487

[mkultra333]

This looks great. I use recast/detour in my project, but didn't work out crowd control. One problem I had is that I let Bullet physics handle my monsters bumping into each other, and into walls and stuff, rather than having them as kinematic (non-physics) objects, but Crowd control didn't like you to mess with the agent positions yourself because it messed up all its working, so the constant feedback from the physics would have messed things up. So at the moment my monsters tend to bump into each other a lot and pile up in choke points. Maybe I could use the crowd control as sort of "ghost" agents that act as guides for the real physical monsters rather then really controlling them.

How does DetourCrowd react if you have to force changes on where exactly particular agents are, mid path?

[duststorm]

(...)but Crowd control didn't like you to mess with the agent positions yourself because it messed up all its working (...)
How does DetourCrowd react if you have to force changes on where exactly particular agents are, mid path?

I think that's everyone's biggest grief with it at the moment.

I already mentioned some mailinglist discussions in my initial post that deal with this. The short summary that at the moment the library doesn't support it yet, but it is considered a must to add it.
The author's own words on it:

Issue 163 (http://code.google.com/p/recastnavigati ... ail?id=163)
is there to remind me to fix this. The idea is to have a way to set a
velocity which controls the agent, instead of setting a target.
Unfortunately I don't have an ETA when this will be done. But I'm
currently (slowly) working on DetourCrowd related issues.

I believe being able to set a velocity is all you need for integrating physics, player input and recast navigation.
The one constraint which you will probably have to stick to is that whatever position you move an agent to, it has to stay within the navmesh. But I think clipping positions to navmesh is something most people can live with.

I'm not fully sure but I think you don't have to place an entity on another position very often (setPosition). However, in the demo I am doing this already. When, in simple navigation mode, you place a new begin or end marker the light blue agent restarts at the begin marker. I do this by removing its agent from the crowd, and re-adding a new one at the wanted position. Of course, this requires detourCrowd to calculate a new path and velocity towards the destination.

One interesting remark is that a user on the recast mailinglist has already shared a patch for manually setting velocities. (here it is: http://groups.google.com/group/recastna ... t=4&view=1) It adds a requestMoveVelocity method allowing to request a velocity for an agent yourself. It doesnt work with offmesh connections yet, however.
I haven't tried this out yet but I believe I will soon.

For those who can wait, I believe a proper patch will be applied to the library not before too long.

[Mind Calamity]

Oh finally someone decided to tackle the problem of pathfinding put it in out (my) beloved OgreAppWizard-like project. I'll check this demo out and try to work out how to implement Detour on my own. Thanks a lot, duststorm!

[duststorm]

The code still needs to be cleaned up some, but I think it's pretty clear.
If you're having a look at the code, start from createScene() in OgreRecastApplication.cpp
One important thing I need to change is letting it take multiple Ogre::Meshes to create a navmesh from (now it's only one, because the map is a single entity), but that's just a small change.

I made another video because I didn't like the quality of the first one
[youtube]veZIqHTcBFk[/youtube]
This one's about the behaviour I'm currently most interested in, simulating a crowd like achieved in Assasin's Creed and such.
For my purposes I don't immediately need physics integration or player control, but they are interesting to investigate none the less.

[Mind Calamity]

Hi, duststorm I created my own repository for keeping my own version which I plan to simplify and make a utility class out of. For now I've removed some dependencies and fixed some minor errors which prevented me from compiling the demo.

You can find the repository here:

https://bitbucket.org/MindCalamity/ogrerecastdemo/

Also important to mention is that I converted the project into a Visual Studio solution and removed the dependency on Qt as the demo didn't utilize Qt for anything but the build process.

[jacmoe]

I might fork the fork and add a CMake script ...

Duststorm: Awesome work here!
Perfect timing too.

[duststorm]

Thanks on the input.
Hmm, yes, I might have left in a lot of messy stuff because I bootstrapped my project by copying the project file from one of my other projects. The qt dependencies should definitely not be in there.
EDIT: I think the qt dependencies probably got in because the qtcreator project importer for visual studio added them. I just use qtcreator because I'm used to it and like working with it, even when I'm not using qt libs.

I'll have a look at your git repos and pull in all improvements.

As for the structure of wrapper classes, I'm also still thinking about how to structure everything nicely. For now I made a class bridging between Ogre and Recast, and one for Detour(Crowd). I think it's best to keep those two separate, as their functionalities are separate and they could be used independently. (you could, for example, generate your navmesh in a content production tool, maybe even edit it by hand, save it as an .obj or something and then load it in your application without dynamically generating it)

[Mind Calamity]

I might fork the fork and add a CMake script ...

Duststorm: Awesome work here!
Perfect timing too.

Beat 'ya to it

And a link for convenience: https://bitbucket.org/MindCalamity/ogrerecastdemo/

I should probably update the README file soon. Also tested and working with OGRE 1.8 (I haven't updated my build in a month or two though).

For those who don't like CMake or have problems using it, you can still clone the repository at the previous revision and use the supplied Visual Studio projects.

Also, jacmoe feel free to make the script better as this is actually my first time using CMake, and I basically just adapted the wiki quickstart package to work with this project.

[jacmoe]

Great!

BTW: QtCreator can use CMakeLists.txt as a project file directly.
At least the Linux version.
Haven't tried the Windows version in quite some time, so I don't know if they fixed CMake based projects there.

And: the repo is Mercurial - muhaha.
Not git.

[Mind Calamity]

Yeah I like Mercurial more than Git, mainly because I find TortoiseHg a bit easier to use and I'm just more comfortable with it as a lot of OGRE-related projects seem to use it.

Yes, I just tried it with Qt Creator 2.3.0 and Qt 4.7.4 and it worked fine aside from only including and building the debug configuration.

[duststorm]

I tend to prefer git a little more, guess I'm an inode guy too. But the bias is not that large
Unfortunately going back and forth between mercurial and git is not the easiest of things, but it is possible so I'll see what I can do.

[duststorm]

Actually it's quite easy to do

To keep everyone happy, I've created a mercurial repo on bitbucket:
https://bitbucket.org/duststorm01/ogrerecastdemo
so now we can exchange patches

I will keep both git and hg repo in sync with each other.


I'd like to pull in some of your changes MindCalamity, but since it's not a fork I don't know whether it's possible.

[duststorm]

Another update.
If you are interested in how Recast works to create a navigation mesh, have a look at CritterAI's NMGen
http://www.critterai.org/nmgen_study

It's an implementation of recast in java, but heavily documented and layd out more clearly (and OO) for educational purposes. The purpose of the author was to research and learn from recast himself, which he did by making NMGen.
You can find a wonderfully detailed article of the full workings of recast here:
http://www.critterai.org/book/export/html/2

While NMGen is easier to understand, it is a lot slower than recast and is not optimised enough for production use. It's for learning only.

[Herb]

duststorm: thanks for sharing this! It's been on my list to revisit Recast, but haven't had the time to get everything out of it that I needed. This will really get me going on this again. The DetourCrowd control looks like a really good option for RTS projects moving multiple units around.

[duststorm]

For RTS it's ready to use as is. And it would work perfectly for it.
As you can see in the demo, agents move precisely to the position you click on if they can. When standing still, they will remain in the same position but can temporarily make a step out of the way to make room for another agent to pass, after which they will return to their original position. There's not a lot of jittering in the steering and avoidance.

It's only if you want your input controller or physics to set velocities to agents that you will need to make changes to DetourCrowd. A waypoint system will work fine out of the box.

[Slappy]

It looks really great!

I will have a try, nice job, thanks!

[duststorm]

I received a PM from member rnc that might be interesting to others too.

He asked how to handle multiple characters in a scene instead of cylinder meshes.
Characters are not fed to recast as meshes. A character in detour is always as simple as a cylinder (with a specific height and radius). It doesn't support more complex shapes (in 99% of the cases this probably not needed anyway).
So the only thing you would do is create an agent in detourcrowd for each character entity and set the height and radius of their cylinders accordingly. DetourCrowd also doesn't handle multiple sizes of characters, since it creates the navmesh specifically for agents of a certain size, so you need to set one size for all. For people this would be pretty reasonable.

Also, I mentioned to him in reply that at the moment my example only loads one mesh for creating a nevmesh of. I'm planning to add support for multiple meshes in the future, which is not that hard to do.

[duststorm]

I had some time to expand my demo a bit.

screenshot05292012_173249384.jpg

screenshot05292012_173305244.jpg

What I did was use MakeHuman to create a character that I exported to Ogre. Using the mocap retargeting tools I made a walking animation from CMU mocap data.
This is mainly a test or proof of concept, but I really like the result.
There are some visible issues with texturing and some faces that were left out. This is mainly because I automatically generated 2 LODS using OgreXMLConverter. It would probably better to create LOD meshes by hand.
At the moment there is only one mesh, but there is some good variety in textures.

The debug drawing can be enabled or disabled, as can be seen in this shot.

screenshot05292012_173136060.jpg

I'm still cleaning up the code but I will update the demo source code soon. I'm not exactly sure how I will do it, as I want to keep the old demo too. I will probably add a switch so you can choose which demo to run.

And finally, here is a video to see it in action:


I still have a lot to fix and tweak to make it look better. For example, there is no idle animation, and the mesh will just go in T-pose when idle. Maybe the animation can be improved too. It's still a bit jittery in some situations, ...
I also want to add a behaviour tree and make characters interact with their environment.
Next up will probably be updating to Ogre 1.8 and making use of RTShader system. Then I will add hardware skinning and per-pixel lighting.
Lots of things to do...

[jacmoe]

Really, really cool!

[mkultra333]

Hey, that's great. If you make the license nice, so people can use the meshes and animations straight away for anything, then this will be a good jump start for a lot of projects.

I'd maybe not get too carried away with the shaders and stuff though, it might make it harder for people to integrate into their projects if they already have their own shader setup.

[duststorm]

The model (at the moment it's only just one) will probably be in the demo, but the more interesting thing is that you can use MakeHuman and Blender quite easily to create your own characters.
It will probably become quite boring really quick to always see the same people

I'm thinking about creating a tutorial explaining the character creation process.

To help in creating ready usable characters we are working at creating a library of clothes, hairstyles and proxy meshes for MakeHuman. I hope in the future to add an animation library.


Speaking of license, what is generally considered acceptable for a license of art files? Is CC that allows derivates, but with attribution for example, good?


About the shaders: I agree I should not do anything fancy with those. But I believe enabling hardware skinning in the demo will have its use, as you will probably want to do that when animating lots of characters.

[mkultra333]

I like CC0 myself. No attribution, do what you like.

But then again, I try to avoid even that. Legally, art assets are often subject to "Moral rights" that can't be signed away. So an artist might take offence at the way you've used a piece of his art, and take you to court, even if he said it was copyright free for any use. Bit of a pain, so I avoid using other people's art even when CC0.

So a quick guide to Make Human might be the better option anyway. I use it myself.

[duststorm]

Legally, art assets are often subject to "Moral rights" that can't be signed away. So an artist might take offence at the way you've used a piece of his art, and take you to court, even if he said it was copyright free for any use. Bit of a pain, so I avoid using other people's art even when CC0.

So a quick guide to Make Human might be the better option anyway. I use it myself.

I'll announce it on these forums when I have the guide ready. It's on my agenda

Of course, you could go as far as arguing that the same goes for the artistic assets that are in Makehuman, such as the basemesh which is used or the items such as clothing or hair or textures applied to it.
In practice it is meant to be used for this, so it would be a bit backward to shy away from it for these reasons.

I also believe that almost any project will probably want to modify these characters at least a little bit, to personalize and differentiate the project. The strength in applications such as makehuman lies in allowing everyone to create realistic humans as a starting point, without the need to be a highly skilled artist.
That being said, I too like the fact of having some art assets available for quick prototyping.

[duststorm]

I have committed the current version of the demo to bitbucket and github.
Still have to make work of adding a CMake setup though.

Next up will be updating the recastnavigation library to the latest svn version, which will add manual setting of velocities for agents. This might also be a little thanks to forum member Captain_Deathbeard who resparked interest in this feature on the mailing list.
This update will require a bit of work though as the API for DetourCrowd has changed a little. I will probably add an extra demo mode that allows you to steer an agent to demonstrate the new feature.
There's other plans like adding in some other behaviour and interaction with the environment (eg. with a pluggable behaviour tree system), but that will probably go into a separate demo. (I want to keep the pathfinding demo simple)

As always, I'll keep you up to date when I have something new.