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 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 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.
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