OgreCrowd: a crowd component for Ogre using Recast/Detour

[Yati]

Yes, I uncommented the line like you said, the InputGeom was a fair bit away from the main terrain.

I set the offsets to 0 and it lines up wrong up a nav-mesh was generated in areas where they overlapped.

thanks!
Looking forward to next commit

[duststorm]

It's committed.

The reason why it's lined up wrong is because the offset of terrain page is never 0 when terrain center is set to 0. Instead it's -pageSize/2.

[duststorm]

I had some nice screens that I wanted to share with you guys.
Nothing really new, but I was putting together a technical test project to test some techniques in Ogre and I found the mesh to be an interesting demonstration of recast.

screenshot07162012_234542092_s.jpg

screenshot07162012_234125099_s.jpg

screenshot07162012_234845964_s.jpg

I'm using the recast wrappers in this demo and you might be happy to hear that integrating navmesh generation into the demo only took about 10 lines of code (most of which are setting proper parameters).

[jacmoe]

Holy shit, that looks great!

[duststorm]

Holy shit, that looks great!

Thanks
I'm using the shadow code I just managed to botch together together with terrain (bstone was an incredible help).
The main star is a wonderful model from arteria3D I just got my hands on. I bought it mainly because it had some interesting pathfinding features, so I could try recast on something that actually looks nice
The tree can be downloaded for free from turbosquid, but you will have to do a little work to get it exported to ogre.

I'm in a sharing mood I created a wiki article today about integrating Berkelium into Ogre and I'm thinking of documenting my findings concerning RTSS shadows and terrain on the wiki too.

[duststorm]

When browsing the source code of PagedGeometry I learned an interesting technique that could be used for building navmesh pages (or tiles) too.
It determines the amount of updates per time period by anticipating the camera move speed.
From the code comments:

//Calculate cache speeds based on camera speed. This is important to keep the cache
//process running smooth, because if the cache can't keep up with the camera, the
//immediately visible pages will be forced to load instantly, which can cause
//noticeable and sudden stuttering. The cache system results in smoother performance
//because it smooths the loading tasks out across multiple frames. For example,
//instead of loading 10+ blocks every 2 seconds, the cache would load 1 block every
//200 milliseconds.

Read the details here: http://code.google.com/p/ogre-paged/sou ... 7b5ae2#528

I thought I'd just write it down here as a note to self and maybe others.

Of course, this technique might only really be useful when processing is inlined in the render loop. When processing happens in a separate thread the best strategy might still be "process as much as possible of everything I need". Just some food for thought.

[bstone]

Nicely done!

[duststorm]

A quick heads-up to inform you that this project is not dead yet

I've been working on a more high-level crowd manager to make it possible to render large crowds in big scenes.
The key to making this happen is paging the crowd. With that I mean only loading crowd agents in areas that are close to the camera, ea that can be seen.
This is much like the technique used in games as GTA or Assassin's Creed.

I still have to decide the final architecture, but the goal is to make the crowd manager a separate component that can be instantiated around the existing recast components, to allow maximal flexibility and make it an optional component. I also intend to make its behaviour customizable by means of strategy classes that can be plugged in.

Enough rant, these are some screens of the very first working demo:

screenshot09032012_234918255.jpg

screenshot09032012_234943409.jpg

The screens are minimalistic and small-scale, but a good way to test and debug the system.
It also works well with more agents

screenshot09042012_000851099.jpg

The demo currently pages agents in 9 tiles around the camera position. This number can be increased, with a 25 tiles 5x5 grid being the next option up (how the amount of tiles and border cells goes up is an interesting formula ). The number of border tiles (tiles on the outer border of the paged area) is an important metric because it's there that new agents get added if the camera moves and the area slides to a new set of tiles.
Agents that walk out of the paged area will also be put in a new random location within one of the border tiles.
The idea is to make agents appear and dissappear as far away from the camera as possible, there where the viewer is least likely to notice it (an improvement on this technique could be to only shuffle things around outside of the camera view frustum).

So, there you go. What do you think? Suggestions, comments, experience you want to share, feature requests? Let me hear them!

My current roadmap is as follows:
- Make crowd distributions configurable (currently only uniform distribution per tile)
- Add the notion of spawn portals (this is a way to control distribution, by means of a population density property)
- Incorporate a waypointing system to control the flow of traffic (instead of aimless wandering around)
- Add interaction triggers with activation conditions like in behaviour trees. Eg. a bench trigger, when an agent walks by, there is a 20% chance that it will sit down, things like mutual exclusion (only one agent can enter), or queueing of multiple agents. This is a great way to add interaction to your world. This can be expanded with things like drawing money from ATM machines, buying something at market stalls, entering doors, looking through shop windows or interaction with other agents such as stopping and engaging in a conversation. Global action triggers are also possible, for example stopping and answering a cell phone call. Finally it should be possible to add action triggers dynamically, for example an explosion or gunshots should alert all agents in the vicinity, making them switch to panic mode and flee the scene. Other agents could be alerted when they see others fleeing, and flee as well, ...
- Not really crowd paging specific: add convenience functions to prune navmesh polygons not reachable from any waypoint to avoid spawning of agents in unreachable areas or imprison them in confined spaces (so that you don't need to edit out the unreachable parts manually).
- Apply instancing and hardware skinning to animated characters
- Scale the demo, make it more interesting
- Pair crowd paging with navmesh paging on large terrains (integration with the new paging terrain)

I'm first working on features I need immediately in one of my own applications. Then there is room for improvement after the deadline

[Alexiss]

Nice work !

I've got one question, might be silly : are "teleportation portals" supported ? For instance, if a specific area instantly teleport the user in another otherwise unreachable area, will it be recognized and used by the navigation algorithm ?

[duststorm]

are "teleportation portals" supported ?

As a matter of fact, yes.
Recast has the concept of off-mesh connections which allows you to create things like "jump links". They have the limitation, however, that they can only connect one tile to one of its neighbouring tiles, not to arbitrary tiles.
So you might want to implement teleporting using a higher-level technique.

Off-mesh connections are supported by the detour pathfinder, and therefore my Ogre recast wrappers support it.
I have not implemented anything using off-mesh connections in the demo or the wrapper however, as I didn't immediately need them. Patches are always welcome

[saejox]

i am following this via github rss, i thought you stop working on it.
i am glad to see you at work again

[duststorm]

Yeah, I ran a bit behind on updating the github version. It has been a few commits behind the bitbucket repo for a while. That's fixed now.

Update: I decided a new name would do this project more justice, therefore I renamed it officially to OgreCrowd! Please update your bookmarks as the repository names have changed.
I also went for an MIT license.

[drwbns]

Very cool work as usual duststorm. I'm glad it's still progressing.

[Mind Calamity]

Update: I decided a new name would do this project more justice, therefore I renamed it officially to OgreCrowd! Please update your bookmarks as the repository names have changed.
I also went for an MIT license.

Finally decided to give it a proper name, eh ? I like it!

I haven't really been following lately, but I'm wondering (and don't really have the time to look through the code right now), are you abstracting it bit by bit ? I mean from first glance it still seems like the demo application you had a while ago. (By this, I mean judging by the name, it should be a component, rather than just a demo like before )

[duststorm]

are you abstracting it bit by bit ? I mean from first glance it still seems like the demo application you had a while ago. (By this, I mean judging by the name, it should be a component, rather than just a demo like before )

Yes. The goal is to make it separate components that can be combined for higher-level functionality.
Eg, OgreRecast wraps the navmesh, you can build it directly, or instantiate OgreDetourTileCache and let the tilecache build the navmesh in OgreRecast.
OgreRecast also wraps simple Detour pathfind methods, and allows to find (random) points on the navmesh.

Instead of using these pathfinding methods directly you can make use of steering agents. For agents it's almost the same situation:
OgreDetourCrowd manages navigating agents. The agents are loosely coupled to my Character class (which is an easier way to manage an agent), but you could easily roll your own.
The latest addition is going to be a CrowdInstanceManager, which will manage Character instances and will make use of OgreDetourCrowd.
All these components are made to look much like components such as Caelum or PagedGeometry.


I'm trying to apply this strategy also to the demos. Now there are three demo applications, adhering the Ogre SampleApplication framework. They are compiled into one executable where OgreRecast.cfg determines which of the three will be instantiated in the main() method (maybe I'll change that in the future to make it compile three separate executables).
Those three are:
- OgreRecastApplication: the first demo in the dungeon map
- OgreRecastTerrainApplication: almost same thing, but on terrain. Some things dropped that made less sense, some things added. Inherits from the former app and reuses a lot.
- OgreRecastPagedCrowdApplication: the latest demo, built from ground up. But the fact that I need a minimal amount of code proves that the Recast wrapper components I built are useful.
The third is very much still in early development, and I have yet to move code from the application into a separate component. This will happen when the API stabilizes.

To get basic recast functionality working in your own app, using the OgreCrowd wrappers, you really don't need much. As a rough guess, 20 lines of code would probably suffice!
To illustrate this (and provide a good getting-started point) I will probably create a fourth minimal example (something you could put on a wiki tutorial, for example). This is basically what the first demo application was in the beginning, but since it has gotten quite some features to showcase.

As the codebase progresses I will clean it up further. For example I intend to organize all component-related classes in their own namespace, while sample applications can remain in the default namespace.
Recastnavigation core stuff can be wrapped in its own namespace too, to separate Ogre wrappers from recast core.
Additionally I have to work on proper CMake scripts, compile the components as a separate library and separate them from the sample apps. And I will move the Samples in their own folder to organize the source files better.


Does that satisfy your requirements for calling it a component?

[duststorm]

Thanks for the useful comment.
I have now separated the applications from the component (sample applications are in Samples now).
I still have to fix the vcproj next time I boot windows, and CMake and lib build will be for sometime in the future.

[saejox]

i was about 2 months behind, decided to upgrade.
Here are some problems/requests i found:

Code: Select all

src\ogredetourtilecache.cpp(650) : error C4716: 'OgreDetourTileCache::isWithinBounds' : must return a value

you forgot to return

PATHDATA m_PathStore[MAX_PATHSLOT]; is protected. I am using this directly. I have moved it to public. Or is there an alternative way to get pathdata?

Code: Select all

#include "include/OgreRecastNavmeshPruner.h" 

should be "include/OgreRecastNavmeshPruner.h"

Code: Select all

#include <Terrain/OgreTerrain.h>
#include <Terrain/OgreTerrainGroup.h>

you seem to have included terrain in inputgeometry builder.
I dont think many people use terrain, like myself. I removed the terrain parts, but it would be great if you could make the terrain optional.
Also OgrePaging is now requirement as well it seems.

since i access PATHDATA directly i need some kinda confirmation that path actually exists or not.
PATHDATA doesnt have constructor, if it did i could look if path exists or not by looking at MaxVertex == 0.
just something to consider.


edit:
there is also a nasty crash

Code: Select all

if(m_ctx) 
   delete m_ctx;

you forgot to nulify, caused quite a grief for me.

additionally, there isnt a destructor for OgreRecast.
Restarting recast in mid game is not very easy because of that.

====

Moving to new version was quite easy, took only 15 mins.
I can say writing this post took longer
Keep up the good work!

Thanks.

[duststorm]

Thanks for detailing the fixes.
Looks like I dropped a few stitches there I'll fix them soon.

[duststorm]

It took me a while but I made the time to consider saejox' fixes.

Code: Select all

src\ogredetourtilecache.cpp(650) : error C4716: 'OgreDetourTileCache::isWithinBounds' : must return a value

fixed
apparently my gcc at current setup doesn't warn me about that

PATHDATA m_PathStore[MAX_PATHSLOT]; is protected. I am using this directly. I have moved it to public. Or is there an alternative way to get pathdata?

You're right. As I quickly shifted focus to using OgreCrowd for managing paths and agents, I forgot to add those convenience functions.
I added OgreRecast::getPath(int pathSlot) and OgreRecast::getTarget(int pathSlot) methods.
I wasn't exactly sure whether to return just a list of Ogre::Vector3's or just return the PATHDATA object (which is a nice Struct Of Arrays). It's a tradeoff between ease of use of API and safety against unwanted modifications and speed. For now I went for the easy to use one.

Code: Select all

#include "include/OgreRecastNavmeshPruner.h" 

should be "include/OgreRecastNavmeshPruner.h"

Yeah, I fear my include statements are a little inconsistent in places. Not sure whether all is fine now, but I'll go through all of them thorougly soon.

you seem to have included terrain in inputgeometry builder.
... but it would be great if you could make the terrain optional.

Good point! I had assumed that the new terrain component was generally accepted as the standard by now, but since it is a component you're right at not including it by default. I'll probably create an OgreTerrainInputGeom specialization to separate it from regular InputGeom.

i need some kinda confirmation that path actually exists or not.
PATHDATA doesnt have constructor, if it did i could look if path exists or not by looking at MaxVertex == 0.

getPath(pathSlot) now solves that problem for you. It returns an empty list when no path is defined. If you still use PATHDATA directly I made sure that MaxVertex and target are inited to 0 in the DetourCrowd constructor.

there is also a nasty crash

Code: Select all

if(m_ctx) 
   delete m_ctx;

you forgot to nulify

Fixed.

I am aware that I haven't payed much attention to proper destructors yet. This is something I will have to fix to move this thing from just a demo to a useable component.
I'll make work of it. (I hope soon! )


I think most of your remarks are fixed now, I have not tested extensively, though. (I don't have much spare time at the moment) Let me know when something's broken.
I still have to try it out on windows and update the project file (still awaiting when I finally do a CMake setup)

Another idea I might incorporate is make typedefs for std::vectors of certain types, like the Ogre API does.

[fixtone]

Hi duststorm,

Excellent work with OgreCrowd is impressive!!!

I wanted to say that I have a bug in the demo Rescast Ogre Terrain.

The problem is when i press the letter H to place house on terrain.

The error occurs:

Class OgreDetourTileCache, function rasterizeTileLayers in line rc.triareas = new unsigned char[chunkyMesh->maxTrisPerChunk];

Some ideas might be going .....

I thank you very much and sorry for my English

[duststorm]

Seems like maxTrisPerChunk is uninitialized, and it looks like the whole chunky tri mesh has not been created.
I haven't been able to reproduce the problem myself, but I might have to test it on windows.

Is this a deterministic bug or does it only happen sometimes?

[fixtone]

Hello,

Sorry I don't tell you execute on windows.

It's a deterministic bug and the problem always happens.

Thanks

[duststorm]

Back with a little update on the project, I integrated the new instancing with the crowd paging demo.
I've committed a few experiments I've done with the crowd instancing component to bitbucket. It's still in early stages, and progress is slow due to time restrictions, but none the less I've made a teaser movie.


There's still some things not working optimally. What bothers me most is some agents that stand still forever, but i'll dig a little deeper into that issue soon.

I haven't had the time to re-test the windows build, because at the moment I don't have a windows dev machine setup, sorry for that, please be a little more patient.
I wonder whether I should keep my non-stable experiments on a separate branch in the repo, and commit to main only what is (kind of) stable. I didn't consider this earlier because I considered the entire thing in alpha stage, but maybe now there is a need for this. Any input on this?

If you are looking for 'more stable' releases, there is a beta1 tag which corresponds to the windows demo that is available for download.

[Alexiss]

Nice to see you keep improving OgreCrowd, this could become a major plugin.
Kudos, and keep up the good work.

[fixtone]

Hi!

I found the bug of chunky tri mesh from triangles, OgreRecastTerrain in Windows.

The original code is:

Code: Select all

// Create partial input geom only for the tiles we want to rebuild
InputGeom geom = InputGeom(bb, mTerrainGroup, mNavmeshEnts);

// Rebuild tiles that touch inputGeom bounding box
mDetourTileCache->buildTiles(&geom);

I solve the bug:

Code: Select all

// Create partial input geom only for the tiles we want to rebuild
InputGeom* geom = new InputGeom(bb, mTerrainGroup, mNavmeshEnts);

// Rebuild tiles that touch inputGeom bounding box
mDetourTileCache->buildTiles(geom);

To build Tiles i need the pointer of InputGeom because used the values of struct rcChunkyTriMesh *m_chunkyMesh.

Thanks.