OgreCrowd: a crowd component for Ogre using Recast/Detour

A place to show off your latest screenshots and for people to comment on them. Only start a new thread here if you have some nice images to show off!
Post Reply
User avatar
duststorm
Minaton
Posts: 921
Joined: Sat Jul 31, 2010 6:29 pm
Location: Belgium
x 80
Contact:

Re: DetourCrowd and Recast in Ogre demo (update)

Post by duststorm »

I have added another feature to the demo!
Steering your own agent
Steering your own agent
screenshot06022012_032429722_small.jpg (50.92 KiB) Viewed 13245 times
Now there is a "Steer agent" mode that allows you to control an agent yourself using the keyboard.
Doing this, the other people in the crowd will still avoid your character, and you will not be able to walk out of the navmesh (eg. walk into walls).
At the moment there is however no complete control, as you ask the detourCrowd steering planner to move in a certain direction. It is not always certain that your character will walk in exactly that direction if there are a lot of other agents blocking the way. You also get the effect of your character following a wall sideways if you run into a wall, which is actually quite nice.

Here is the obligatory video:


This is a showcase of a new feature that got added very recently to recastnavigation (being able to request custom velocities for agents).

Interestingly, using detourCrowd in a more realistic scenario like this shows some interesting details and some areas that could be improved. For example, jitter in agent steering is a lot more noticeable with human agents that always face the velocity direction than with cylinders.
I would still have to add tweaks to the animation system and for example add smooth turning when changing direction.
However, having such a crude and simple demo is very interesting for seeing the exact features of the library, and what might need some tweaking when used in a poject.

So, this new demo has been integrated with the latest svn version of the recastnavigation code. I had to do a few minor changes as the DetourCrowd API changed a bit. I also did a few more cleanups.


As a quick reminder, these are the controls:
ENTER Switch between demo modes
LMB Place end marker for first agent and others (depending on mode)
RMB Place begin marker of first agent (only in simple mode)
SPACE Add new agent at position of cursor (cursor must be on navmesh, doesn't work in steer mode)
W,A,S,D Steer camera
W Walk forward in steering mode
Mouse Rotate camera, rotate agent in steer mode
Developer @ MakeHuman.org
User avatar
duststorm
Minaton
Posts: 921
Joined: Sat Jul 31, 2010 6:29 pm
Location: Belgium
x 80
Contact:

Re: DetourCrowd and Recast in Ogre demo (update)

Post by duststorm »

Another small update:

I extended the code a bit so it can build navmeshes from a list of entities.
The demo now shows an obstacle in the form of a pot. It's a separate mesh from the dungeon map.
Obstacles limit the walkable part of the navmesh
Obstacles limit the walkable part of the navmesh
screenshot06052012_145711659.jpg (147.9 KiB) Viewed 13201 times
Demo with multiple obstacles
Demo with multiple obstacles
screenshot06052012_215834470.jpg (124.07 KiB) Viewed 13177 times
I also fixed a bug that prevented a navmesh from more than two meshes to be built.


I plan to experiment with some other controllable agent behaviour too. I plan to try to use a dynamic obstacle instead of an agent in the crowd for a controllable character, so that other agents still try to avoid it, but the player has complete control over his character.
Developer @ MakeHuman.org
User avatar
duststorm
Minaton
Posts: 921
Joined: Sat Jul 31, 2010 6:29 pm
Location: Belgium
x 80
Contact:

Re: DetourCrowd and Recast in Ogre demo (update)

Post by duststorm »

Today I found a little time to do some additional fixes and added a feature where the navmesh and other recast debug drawing can be enabled or disabled.
This adds the following item to the controls explanation:
V toggle hide/show navmesh and recast visual debugging

Other than that I have updated the included recast libs again, keeping them in sync with the latest upstream release.

I think that by now I've exploited most of the features that the combination recast/detour/detourCrowd has on offer.
I'm interested in adding temporary and dynamic obstacles in the mix, but for this I will need to drag in a new dependency: detourTileCache, which allows for caching navmesh pages in order to create navmeshes for very large scenes efficiently. Pages can be loaded in when they are needed while other parts of the navmesh can be swapped out. Also pathfinding works on one navmesh locally, but can reference other pages in the higher hierarchy, making the pathfinding problem more localized which increases the scalability of the system.
Other than allowing for very large navmeshes, the tileCache also has the feature that it allows to quickly build and rebuild navmeshes with extra obstacles added. Those can be added or removed at runtime and the process is fairly quick.

I think dynamic obstacles with dtTileCache will be the subject of my next experiments. I think that I will be starting a new demo project, though, as I believe the current one would become a bit bloated and hard to understand otherwise. I think I will go for a second demo application that borrows as much from the first as possible, trying to reuse objects from the first demo and adding new ones where necessary.
I intend to demo doors in a level using temporary obstacles (unless temporary disabling navmesh segments is really better in this case) and I want to experiment with a variant of the agent steering demo mode, but instead of letting the player steer an agent, placing a dynamic obstacle on the player position. This will allow complete player control (without the steering being corrected by the crowd steering) but will still make other agents avoid collisions with the player. I wonder whether it will be fast enough, though, as this would mean adding and removing temporary obstacles to the navmesh every frame.

Additionally, when I have my first detourTileCache demo done, I might demo how the tilecache can work together with a terrain that consists of multiple pages. In light of the current GSoC of terrain paging, a matching navmesh paging might be an interesting subject.
Last edited by duststorm on Thu Jun 07, 2012 10:13 am, edited 1 time in total.
Developer @ MakeHuman.org
User avatar
jacmoe
OGRE Retired Moderator
OGRE Retired Moderator
Posts: 20570
Joined: Thu Jan 22, 2004 10:13 am
Location: Denmark
x 179
Contact:

Re: DetourCrowd and Recast in Ogre demo (update)

Post by jacmoe »

It's quite a job just to keep up with all this awesomeness! :)
This has to be the coolest project I've ever followed on Bitbucket/Github/Whatever.
Huge thumbs up from here.

This project deserves to be linked to from the Recastnavigation project page IMO.
/* Less noise. More signal. */
Ogitor Scenebuilder - powered by Ogre, presented by Qt, fueled by Passion.
OgreAddons - the Ogre code suppository.
User avatar
Xplodwild
Goblin
Posts: 231
Joined: Thu Feb 12, 2009 3:49 pm
Location: France
x 13
Contact:

Re: DetourCrowd and Recast in Ogre demo (update)

Post by Xplodwild »

Any plans to add Terrain navmesh generation? :-)
I can donate some bucks to speed this up ;)
User avatar
duststorm
Minaton
Posts: 921
Joined: Sat Jul 31, 2010 6:29 pm
Location: Belgium
x 80
Contact:

Re: DetourCrowd and Recast in Ogre demo (update)

Post by duststorm »

I will get to this after I have the tilecached navmesh system down.
If you need a shortcut, Paul Wilson already did recast navigation on ogre terrain a while ago:
http://www.ogre3d.org/forums/viewtopic.php?f=11&t=57487
http://paulwilsonleveldesign.carbonmade ... /3971271#3

My demo project still needs the code to transform the terrain vertices to a format that recast understands. For this I will probably borrow heavily from what paul wilson did in his sample.
Developer @ MakeHuman.org
User avatar
saejox
Goblin
Posts: 260
Joined: Tue Oct 25, 2011 1:07 am
x 36

Re: DetourCrowd and Recast in Ogre demo (update)

Post by saejox »

i started using recast after seeing how easy to integrate it to my existing levels.
awesome work.

i have a little question, as i understand it Recast assumes walkable area is in +Y direction.
I dug around a little and found that i cant change this without touching Recast source.

should i convert coordinates to my playable plane dynamically? (e.g Vector3 RecastToGameCoord(Vector3 ))
or rotate it in building phase? (i dont really know how to do this)

any ideas?

thank you, great work.
Nimet - Advanced Ogre3D Mesh/dotScene Viewer
asPEEK - Remote Angelscript debugger with html interface
ogreHTML - HTML5 user interfaces in Ogre
User avatar
duststorm
Minaton
Posts: 921
Joined: Sat Jul 31, 2010 6:29 pm
Location: Belgium
x 80
Contact:

Re: DetourCrowd and Recast in Ogre demo (update)

Post by duststorm »

Ogre uses the same default of y is up.
But if you want to use a custom axis system you might get by by simple swapping around the vector components in the inputGeom generation phase.
So, assuming that you are using a coordinate system with z is up, use this mapping:

Code: Select all

recastInputVect.x = yourAppVect.x;
recastInputVect.y = yourAppVect.z;
recastInputVect.z = yourAppVect.y;
You might have to add a - sign where necessary.

In the inputGeom building phase, this means changing the order or the "verts" array. It contains vertices like this:

Code: Select all

verts = {x0, y0, z0, x1, y1, z1, ..., xn, yn, zn}
so the length of verts is three times the amount of vertices in your scene.
You can just modify it to swap the positions of z and y components with each other. That way you are only modifying the ogre wrapper code for recast, not the recast libraries themselves.

Additionally, if you do this, you will also have to transform recast coordinates back and forth to your scene coordinates in the same way, for example with a RecastToGameCoord function.
You will have to do this everytime you give a position to recast/detour (for example setting a target and position for an agent) and when updating the positions of agents in your scene.
As well as the debug drawing function that draws the navmesh in the scene, where you will have to do the same y-z remapping.
It's a fairly easy transformation and you don't need to modify the recastnavigation code.

For your reference, all my own code, including the Ogre wrappers for the recast library are in the include/ and src/ folders.
include/Recast, include/Detour, include/DetourCrowd etc. are the original unmodified recastnavigation libraries.
Well, to be completely honest I have to admit I modified the locations of the includes in some of the headers a bit, because I'm using a different folder organization. But that's all that's modified.
You can see what changes I made from the original recastnavigation code if you look at the "patchRecastnavigationSvn.patch" file. It's what I use to get a new version of recast in my project.
It's used by the "updateRecastnavigationSvn.sh" bash script.
Developer @ MakeHuman.org
User avatar
duststorm
Minaton
Posts: 921
Joined: Sat Jul 31, 2010 6:29 pm
Location: Belgium
x 80
Contact:

Re: DetourCrowd and Recast in Ogre demo (update)

Post by duststorm »

Time for some update! :)

I managed to get navmesh building with DetourTileCache working.
The advantage of navmeshes built and maintained by dtTileCache is that you can add and remove obstacles to them at runtime. Now the demo allows you to place and remove temporary obstacles, which are basically cylinders with specified radius and height. (only available when dtTileCache navmesh building is enabled)

You might have noticed that the navmesh is a little different now. It has a little more segments than the single navmesh construction, and this has a small negative effect on steering quality (apparently it works better with a little larger polygons). Maybe with some tweaking of the dtTileCache params that I can get things to improve.

Temporary obstacles are really fast. In fact there is no noticeable delay when adding or removing them.
DtTileCache also allows you to set other dynamic obstacles than cylinders, using convex polygons that you can add to the navmesh. I will test this in the future.

The controls for the demo are as follows (I'll repeat the full list for convenience):
BACKSPACE Place a temporary obstacle at cursor position (only with dtTileCache navmesh building enabled)
DELETE Remove temporary obstacle that cursor currently points to (only with dtTileCache navmesh building enabled)
ENTER Switch between demo modes
LMB Place end marker for first agent and others (depending on mode)
RMB Place begin marker of first agent (only in simple mode)
SPACE Add new agent at position of cursor (cursor must be on navmesh, doesn't work in steer mode)
W,A,S,D Steer camera
W Walk forward in steering mode
Mouse Rotate camera, rotate agent in steer mode
V toggle hide/show navmesh and recast visual debugging

Here is a video of temporary obstacles in action:
[youtube]yhtVBguU1NI[/youtube]
Notice how agents stop when their path is blocked and start moving again when they find a new route to their target. :)

The version of the demo shown in the video is now available in the code repo. You can switch back to the old simple navmesh construction by setting OgreRecastApplication::SINGLE_NAVMESH to true. In fact any feature from older demos is still available. To get back to the cylinder agents, set OgreRecastApplication::HUMAN_CHARACTERS to false. Similarly, to remove the pots (static obstacles) from the scene, set OgreRecastApplication::OBSTACLES to false.


Next up:
Now that I have temporary obstacles working, I want to create a second agent steering demo that uses a temp obstacle for the player instead of a crowd agent, giving complete control over the character by the user.
Though I still find it a bit unfortunate that by doing this I won't have a velocity obstacle.
A similar approach is discussed in the comments of this blog post:
http://digestingduck.blogspot.be/2010/0 ... acles.html

Experiment with convex obstacles. This will be good for doing doors and having non-cylindrical obstacles, like square boxes or more complex shapes.

Generating a navmesh from a terrain tile.
Last edited by duststorm on Sun Jun 10, 2012 9:47 am, edited 1 time in total.
Developer @ MakeHuman.org
User avatar
jacmoe
OGRE Retired Moderator
OGRE Retired Moderator
Posts: 20570
Joined: Thu Jan 22, 2004 10:13 am
Location: Denmark
x 179
Contact:

Re: DetourCrowd and Recast in Ogre demo (update)

Post by jacmoe »

You are truly spoiling us! :D

How would this fit into hierarchical path planning?
Would that be more efficient for huge areas, like paged terrain?
Or, does it matter?
/* Less noise. More signal. */
Ogitor Scenebuilder - powered by Ogre, presented by Qt, fueled by Passion.
OgreAddons - the Ogre code suppository.
User avatar
duststorm
Minaton
Posts: 921
Joined: Sat Jul 31, 2010 6:29 pm
Location: Belgium
x 80
Contact:

Re: DetourCrowd and Recast in Ogre demo (update)

Post by duststorm »

jacmoe wrote:How would this fit into hierarchical path planning?
Would that be more efficient for huge areas, like paged terrain?
Or, does it matter?
Good questions. Ones I've been rethinking yesterday too.
Reading some notes on mikko's blog (the creator of recast) about hierarchical pathfinding, I believe dtTileCache can handle this.

The intermediate data in tilecache could well be used for the purpose of compactly storing parts of the navmesh that are not currently used, as they are more compact than a 3D navmesh (and are compressed using fastLZ). One could store a large grid of tilecaches in a hierarchical navmesh manager, and generate the 4 navmesh pages it currently needs. The rest of them could be stored in ram or be streamed in when needed.
Here you can read about how much memory is saved using dtTileCache: http://digestingduck.blogspot.be/2010/0 ... acles.html
Some interesting reads that mention using dtTileCache for very large nav grids:
http://digestingduck.blogspot.be/2011/0 ... r-win.html
http://groups.google.com/group/recastna ... 80bc?pli=1

I will have to do some more digging and reading. A lot has been written about recastnavigation, and the author has a wonderfully instructive blog and is very helpful on his mailing list. The problem is that a lot of information needs to be puzzled together from different locations. Especially once you get into newer recast features than the original ones.


Maybe this streaming and loading can be done at the time the terrain paging component is doing its streaming. This makes a good case for requesting callbacks from the GSoC terrain paging component.
Developer @ MakeHuman.org
ShortBus
Gnoblar
Posts: 8
Joined: Sun Jun 10, 2012 7:36 pm

Re: DetourCrowd and Recast in Ogre demo (update)

Post by ShortBus »

I second that opinion: This is by far the most interesting addon project I've seen around these days. Good work, duststorm and thanks for your effort in integration such a brilliant library into Ogre, I really appreciate that. I got three questions I'd like to ask, I hope you don't go any trouble helping me out a bit here:

One thing I stumbled across while trying to implement your code: Is there any possibility of finding the nearest point on the navigation mesh to a given vector in the scene? I noticed there is an adjustment feature inside the functions for settings the target, but that doesn't seem to exists for setPosition() of a given agent. Due to that I always end up with a totally messed up vector like 0.0, 0.0, -2323732498237.0 when inserting agents into the scene ... or am I just doing something totally wrong here?

Also, I'm not sure if it's a good idea to estimate the agents used by detour as entities. Wouldn't it be better to calculate them using scene nodes? This way we would be able to use any kind of node, such as manualobjects and terrain instead of entities.

And this leads me to my last concern so far: How do you plan to integrate ogres terrain system into your code? I'm not quite sure, but I think I remember there has been a heightfield feature implemented in recast/detour. I guess this would be an interesting thing to investigate. Do you have any idea when this feature will be implented? I'm thinking about a workaround right now, but maybe you're still on it?

Again: Great work, thank you so much for this promising piece of code!
User avatar
duststorm
Minaton
Posts: 921
Joined: Sat Jul 31, 2010 6:29 pm
Location: Belgium
x 80
Contact:

Re: DetourCrowd and Recast in Ogre demo (update)

Post by duststorm »

ShortBus wrote:Is there any possibility of finding the nearest point on the navigation mesh to a given vector in the scene?
Yes, that's possible. The sample that comes with recastnavigation does it.

Look for the file CrowdTool.cpp (in the original recastnavigation code, from http://code.google.com/p/recastnavigation/)
the function CrowdToolState::setMoveTarget(p, adjust) does more or less what you want.
In particular the navquery->findNearestPoly(p, ext, filter, &m_targetRef, m_targetPos) function does exactly this.

Good point on that one, I will make a wrapper function for it in OgreRecast.


Oh, and thanks for the positive responses :)
At the moment it's not really an addon project, more like a demo and reusable tutorial on how to integrate it :)
Last edited by duststorm on Sun Jun 10, 2012 9:00 pm, edited 1 time in total.
Developer @ MakeHuman.org
User avatar
duststorm
Minaton
Posts: 921
Joined: Sat Jul 31, 2010 6:29 pm
Location: Belgium
x 80
Contact:

Re: DetourCrowd and Recast in Ogre demo (update)

Post by duststorm »

I have added a bool OgreRecast::findNearestPointOnNavmesh(Ogre::Vector3 position, Ogre::Vector3 result) function.

To test it out in the demo set the OgreRecastApplication::RAYCAST_SCENE variable to true. Clicking the dungeon mesh anywhere (for example on the arcs, or the walls) will put the begin/end markers on the position nearest to the navmesh.
The findNearestPoint function uses a bounds property that determines the maximum distance the point can be from the navmesh for it still to find a result (look at the implementation of the function).
Developer @ MakeHuman.org
ShortBus
Gnoblar
Posts: 8
Joined: Sun Jun 10, 2012 7:36 pm

Re: DetourCrowd and Recast in Ogre demo (update)

Post by ShortBus »

Ah, thank you very much. I had just finished writing my own, but never mind, I'm using your method from now on.

Just tested it out and everything works expected. One more thing: There is a method updateDestination() n your Character base class. You may want to use the function you just implemented there again in order to allow the detection of a higher variety of possible navmesh points. When not using this, dtCrowd will only search for valid positions within a range of roughly twice the agents extents which is fine for wall and near obstacle detection, but not for querying a (user selected) random point on the navigation mesh.

// EDIT: Just forgot this: Is it possibly to modify the navigation mesh once it has been built? I'm thinking about elevators or any kind of dynamic surface that would need to be taken into account when calculating the path. Maybe you got any thoughts about that? Thanks again :-)
User avatar
duststorm
Minaton
Posts: 921
Joined: Sat Jul 31, 2010 6:29 pm
Location: Belgium
x 80
Contact:

Re: DetourCrowd and Recast in Ogre demo (update)

Post by duststorm »

ShortBus wrote:There is a method updateDestination() in your Character base class. You may want to use the function you just implemented there again in order to allow the detection of a higher variety of possible navmesh points.
You probably mean setPosition() and updateDestination()? You're right, it could be a bit more defensive and use findNearestPointInNavmesh().
updatePosition() is a protected method, so it is protected from external manipulation. Also it just copies the position from the detourCrowd agent, which should be on the navmesh by definition.

I just went ahead and added this.
ShortBus wrote:Is it possibly to modify the navigation mesh once it has been built?
With DetourTileCache, yes it is :)
The demo now offers two different methods of building a navmesh. The first one is a simple static single navmesh.
Recently I added dtTileCache navmesh building (you can test it by setting OgreRecastApplication::SINGLE_NAVMESH to false). It's currently the default setting of the code in the repo, and it's what makes temporary obstacles possible.
The trick is that because your navmesh is divided in tiles you can quickly rebuild a single tile that changed. This is what happens in this demo: http://www.youtube.com/watch?v=WzFJMvE0L60
Developer @ MakeHuman.org
User avatar
duststorm
Minaton
Posts: 921
Joined: Sat Jul 31, 2010 6:29 pm
Location: Belgium
x 80
Contact:

Re: DetourCrowd and Recast in Ogre demo (update)

Post by duststorm »

Another small update before I go to bed.

I finished my experiment with manually steering a character (from keyboard input) by placing a temp obstacle on its current position, instead of binding it to an agent. This makes you able to directly control the character (the classic way) instead of requesting a velocity from the agent controlling the character, which could alter or completely deny your request, giving a limited feel of control.

The disadvantage is that the player is no longer a velocity obstacle, so other agents will not anticipate the direction you're moving in.

You can push other characters around, fright train style. Which you either might or might not want, but I guess this is where a physics engine comes into play.

This demo is enabled by setting TEMP_OBSTACLE_STEERING to true (enabled by default in latest version of the code) and it replaces the older agent steering example. You can tell the difference by looking at the top left info box on screen. If it says "Steer agent" it's the old sample, if it says "Steer obstacle" it's this experiment.

I didn't have time to make a video yet, maybe later :).

Oh, and I also changed the viewport bg color to dark grey. The black was hiding the cursor. Just a small detail.
Developer @ MakeHuman.org
ShortBus
Gnoblar
Posts: 8
Joined: Sun Jun 10, 2012 7:36 pm

Re: DetourCrowd and Recast in Ogre demo (update)

Post by ShortBus »

I have not been able to test your latest additions so far, will get into that later. Anyway, I have made some impressions of your code and it seems to work pretty well for me. Yesterday I had some success on implementing it into my own game and it turned out that your Ogre bindings are handy and well documented. You did a good job on hiding the awkward mesh conversion and initialization code needed for recast and wrapped it into a nice and easy to use meta structure. I would suggest keeping it that way, but make some small adjustments. For example, the AnimatableCharacter class was a bit too specialized to suit my needs, whilst its super class Character misses some basic functionality in my opinion.

So i started out deriving a new class from Character (i called it Agent) and implemented some extensions, such as cached parameter modifications of a detour crowd object. In my case I needed it to be able to modify the agents speed and acceleration dynamically. I also created an AgentManager which keeps track of the agents and thus provides a generic interface for mass update of all registered agents. I won't hesitate to contribute this if you like, but I'd thought that maybe there needs to be some discussion about how such things should be implemented to reflect a consensual concept.
User avatar
duststorm
Minaton
Posts: 921
Joined: Sat Jul 31, 2010 6:29 pm
Location: Belgium
x 80
Contact:

Re: DetourCrowd and Recast in Ogre demo (update)

Post by duststorm »

ShortBus wrote:the AnimatableCharacter class was a bit too specialized to suit my needs, whilst its super class Character misses some basic functionality in my opinion.
Suggestions are welcome :)
Indeed I wanted to keep the demo code fairly basic so it's quickly understood. That's why some things about the demo application might look hackish (don't think my approach of referencing entities by their name in the scene is a good idea! ;)). Sometimes I just chose not to add in an extra manager class. The focus is on the integration with recast, and to demo the features as compactly as possible.
I put a lot of todos here and there in the code for things that need cleaning up and application specific things that need to be dragged out of the wrappers.
ShortBus wrote:i started out deriving a new class from Character (i called it Agent) and implemented some extensions, such as cached parameter modifications of a detour crowd object. In my case I needed it to be able to modify the agents speed and acceleration dynamically. I also created an AgentManager which keeps track of the agents and thus provides a generic interface for mass update of all registered agents. I won't hesitate to contribute this if you like, but I'd thought that maybe there needs to be some discussion about how such things should be implemented to reflect a consensual concept.
I'm certainly interested in your opinion! Maybe you can provide some more details on what you did.
If you want to share code you could maybe put up a bitbucket fork, so I can have a look for comparison. That way we could easily pull in new things.

A small update before I go to bed:
After a few issues I managed to get basic convex shape obstacles working.
recast_convexObstacles_1_small.jpg
recast_convexObstacles_1_small.jpg (32.95 KiB) Viewed 12756 times
recast_convexObstacles_3_small.jpg
recast_convexObstacles_3_small.jpg (57.05 KiB) Viewed 12756 times
recast_convexObstacles_2_small.jpg
recast_convexObstacles_2_small.jpg (27.25 KiB) Viewed 12756 times
As the screenshots show, I added cube shaped boxes that can be added and removed at runtime to the navmesh just like temporary obstacles. The affected tiles of the navmesh are rebuilt, which happens fairly quickly because the tiles are fairly small (one color is a tile area).

There's still some stuff missing: the convex hull creation from geometry does not work with too many vertices and I need to fix the convex hull offset algorithm, because the convex hulls need to be offset with the size of the agent ratio, or agents still walk through the borders of objects.

This is in fact an interesting point of thought: does it need to be able to build convex hulls from complex objects? Or can we expect artists to create adequate simplifications for the meshes so they can be efficiently used as obstacles. How do physics engines handle this problem (As I believe they have a similar process in creating convex hulls)?

The inputGeom objects that store the geometry of obstacles only supports static stuff at the moment, I want to make a dynamicInputGeom class that you can apply transformations to. Additionally I think I will create an Obstacle class much like the Character, that can be given transformation commands and can be updated using update(tick). In the obstacle class I can handle the updating of the navmesh for temporary obstacle placement, so I can remove that from the main demo class.
With recent modifications a lot of cleanup todo's have been placed about everywhere in the code. So there's still work to get it the way I want :)

For those that want to have doors: convex obstacles are ideal for marking a door. In fact the convex obstacles do not necessarily have to be a regular obstacle. They can also be used to mark areas of the navmesh with a specific flag, for example: water, or grass, ... This can be used to give different weights to the pathfinding algorithm, or to filter out areas for certain types of agents (eg. those that cannot swim).

Once I have dynamic inputGeom classes, I can also experiment with dynamic objects that can be walkable. While obstacles can only remove parts from the navmesh, introducing a new piece of geometry (eg. putting a plank over a gap) can also introduce new paths. I want to experiment with that too.
Developer @ MakeHuman.org
User avatar
duststorm
Minaton
Posts: 921
Joined: Sat Jul 31, 2010 6:29 pm
Location: Belgium
x 80
Contact:

Re: DetourCrowd and Recast in Ogre demo (update)

Post by duststorm »

This afternoon during a break I played a bit with the demo and recorded a video.

And because a video tells so much more:

It shows the workings of dynamic convex obstacles.
I also demo the alternative "character in the crowd steering demo", which is what you would probably want to use in a game that gives you direct control over the playable character. Notice how I can push other characters around and how I have complete control over it.

You can notice in the video that there is still some trouble with the offset convex meshes of boxes (they become almost triangle-shaped, making agents walk through part of the box). That is something I have yet to fix some time.


I played around a bit to see how the detourCrowd agents deal with paths that become cut off or that reopen. The result looks pretty nice.

It looks like it works as well as this technique
Developer @ MakeHuman.org
drwbns
Orc Shaman
Posts: 788
Joined: Mon Jan 18, 2010 6:06 pm
Location: Costa Mesa, California
x 24

Re: DetourCrowd and Recast in Ogre demo (update)

Post by drwbns »

Maybe you should have the agents wander if there's a blocked path, it might look a little better. But great job so far, I hope you can really expand this further
User avatar
duststorm
Minaton
Posts: 921
Joined: Sat Jul 31, 2010 6:29 pm
Location: Belgium
x 80
Contact:

Re: DetourCrowd and Recast in Ogre demo (update)

Post by duststorm »

drwbns wrote:Maybe you should have the agents wander if there's a blocked path, it might look a little better.
That is something you can add to your AI and is specific to a certain application.
Pathfinding is a low-level AI function, that is controlled by a higher level AI behaviour that has a concept of goals and sets destinations for the agent.
I'm not going to include such behaviour in this demo since I only want to create a general presentation of what is possible with recast.
This also makes it more clear how detourCrowd agents react if complete paths to a target cannot be found (they will go to a location as close to the target as possible).
Developer @ MakeHuman.org
User avatar
Zonder
Ogre Magi
Posts: 1168
Joined: Mon Aug 04, 2008 7:51 pm
Location: Manchester - England
x 73

Re: DetourCrowd and Recast in Ogre demo (update)

Post by Zonder »

Got to say I am loving these updates keep up the excellent work :)
There are 10 types of people in the world: Those who understand binary, and those who don't...
User avatar
duststorm
Minaton
Posts: 921
Joined: Sat Jul 31, 2010 6:29 pm
Location: Belgium
x 80
Contact:

Re: DetourCrowd and Recast in Ogre demo (update)

Post by duststorm »

Thanks for the positive comments, I love hearing your feedback. :)

I tested another feature that tiled navmeshes allow: supporting dynamic scenes by rebuilding affected tiles.
The difference with the dynamic obstacles from before is that these objects can also add new walkable areas, where obstacles can only block paths.
Walkway created by stacking pallets in the scene
Walkway created by stacking pallets in the scene
recast_walkway.jpg (130.54 KiB) Viewed 12635 times
recast_walkway2.jpg
recast_walkway2.jpg (107.15 KiB) Viewed 12635 times

Rebuilding the navmesh tiles is somewhat heavier than placing a temporary obstacle, though. But I think it's mainly the unoptimized way in which I transform most of the scene into recast format again and feed it to detour to build a new tile. Optimizing that could make a big difference.
What I need is an efficient way to get the triangles from the scene that overlap the bounding box of the navmesh tile, transform them in world-space coordinates and feed them to the tile building algorithm.

Anyway, as usual I created a little video of me having fun with it. (it's really fun to play around with) :)


As you can see I'm stacking pallets until they form walkways. What is interesting about this is that recast can handle the fact that the pallets are full of holes (I'm just using the original pallet geometry, I'm not feeding a bounding box object or convex hull or anything. No tricks with transparent planes either, it's the original WoodenPallet.mesh from the ogre samples).
How the navmesh building is affected by obstacles is influenced a lot by the recast parameters you specify. Such as maximum error, resolution, the max height that agents can step on (in this case the wooden pallet should not be higher than that value, or the character cannot step onto it).

You can try it out yourself too, by getting the latest source from the repo.

The added controls are:
K Add a walkable wooden pallet at cursor position
I Remove walkable wooden pallet at cursor position
Developer @ MakeHuman.org
User avatar
duststorm
Minaton
Posts: 921
Joined: Sat Jul 31, 2010 6:29 pm
Location: Belgium
x 80
Contact:

Re: DetourCrowd and Recast in Ogre demo (update)

Post by duststorm »

Not much new today, except for a quick bugfix. Convex shaped obstacles (eg. the wooden crates) should be a bit better now.

One other pick to show that it's also possible to create isolated islands.
It's also possible to create navmesh islands with new geometry, like on the top of this stack
It's also possible to create navmesh islands with new geometry, like on the top of this stack
recast_stack_small.jpg (75.37 KiB) Viewed 12610 times
That makes the only item left on my short-ter TODO list is:
- Generate navmesh from terrain tiles

This should be done farily quick since I can reuse a lot from Paul Wilson's example.


I already have created functions for (re-)building separate tiles on the navmesh, so in theory paged navmesh streaming should already be possible. Once I create a terrain demo (I will create a separate demo for this) I can showcase how one would implement the streaming feature.
I hope I can integrate it with the GSoc terrain paging after this summer, too ;) I hope you prepare some callbacks when terrain page loading happens, kuxv, so I can bring in navmesh loading at those points. ;)

And then there is some old plain boring cleanup and documenting work left to be done ;)
Developer @ MakeHuman.org
Post Reply