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
aguru
Goblin
Posts: 236
Joined: Tue Feb 26, 2008 5:48 pm
x 3

Re: DetourCrowd and Recast in Ogre demo (update)

Post by aguru »

This is all very, very cool work. Thanks, duststorm!
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 »

I was planning to integrate Recast/Detour into Ogitor - so I am extra appreciative of your work Duststorm. :P

No, seriously: this is one of the coolest projects to happen in a long, long time. :)
/* 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 »

Thanks for the positive feedback.

What recast funtionality would you want to offer in Ogitor? I assume automatically generating navmeshes from parameters set in the GUI and editing navmeshes manually?

I still have to add serialize/deserialize functions to my code, but that will probably come. I think it's advisable to use the same format as the recast demo, so the code can just be borrowed from there, and you could also use the recast demo to visualize your created nav meshes.

Being able to load pre-computed navmeshes stored in a file would be required for a proper streaming setup anyway.
If people use ogitor only to tweak the navmesh generation parameters visually (and not edit the navmesh polygons by hand), they have the choice of either saving out the navmesh to a file or to generate it dynamically in code (which would be necessary if you want dynamically changing environments anyway).

Ogitor would have to be able to save out two types of things:
navmesh config parameters (could go in the scene xml) -- required
navmesh tile files (as separate files just like terrain, probably) -- optional


Either detourTileCache or recast could be used to generate the navmeshes, but I recommend detourTileCache. It's more complicated, and needs a little more memory at runtime, but it allows to save navmesh tiles to file more efficiently and offers tiling that could fit well with paged terrain. Also it allows the user to add temporary obstacles or regenerate individual tiles in his application.
Developer @ MakeHuman.org
crancran
Greenskin
Posts: 138
Joined: Wed May 05, 2010 3:36 pm
x 6

Re: DetourCrowd and Recast in Ogre demo (update)

Post by crancran »

I've been following your work Duststorm and I must give kudos. I'm certainly interested in the Terrain demo you have planned. We integrated it with Terrain ourselves but we aren't using any paging functionality at present, so this will be a nice gem to see how it all flushes out in the end.
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 »

crancran wrote:I've been following your work Duststorm and I must give kudos. I'm certainly interested in the Terrain demo you have planned. We integrated it with Terrain ourselves but we aren't using any paging functionality at present, so this will be a nice gem to see how it all flushes out in the end.
Thanks. Getting tiled navmesh building to work (with dtTileCache) is quite complicated, so I hope I've made something that can be reused by others. In fact, I believe I found the biggest challenge to understand how the dtTileCache works and how it fits in the navmesh creation process.

To clarify a bit more : There are 3 different approaches to creating navmeshes with recast.
- simple recast navmesh (first demo in recast called "Single navmesh")
- a little harder: tiled navmesh (second demo, called "tiled mesh")
- the most complicated: using detourTileCache (the third demo called "temp obstacles")

The first and third approach are included in my demo. (and all new work is based on dtTileCache)

The first two use recast to create a navmesh, with the second this navmesh creation is divided in separate tiles (axis aligned and with fixed size)

detourTileCache stores per tile of the actual navmesh a compressed dtTile in memory. This is the data for that tile somewhere in a phase between raw input geometry and the output navmesh, where a navmesh can be created from it very quickly (it stores a compressed voxel heightfield). The advantage of storing the compressed heightfield and not the final navmesh is that it allows you to easily and quickly add and remove temporary obstacles to the navmesh, without having to rebuild the tile completely from input geometry.
For a lot of streaming purposes (except if you want to add extra walkable geometry at runtime) it is a good solution to store the compressed heightfields for each tile, and load those in the tilecache when needed so that a navmesh tile can be generated.

The tilecache allows you to easily and quickly swap in and out compressed tiles and it will rebuild the correct tile in the navmesh for it. One disadvantage is that it consumes a little more memory, as for each tile in the navmesh that is loaded, there is also a compressed heightfield tile in the memory. But the memory consumption is very moderate.


One extra note:
For temp obstacles one does not need to rebuild a tile from input geometry, one can just quickly add an obstacle to the compressed heightfield and recalculate a navmesh tile in mileseconds. Currently this only applies to the temp obstacles demo with cylinders. While it is possible to also implement this for convex shapes, I did not do this yet (as it is not implemented in recast yet). So the current version of the demo (with CONVEX_OBXTACLES=true) that adds boxes and pots as obstacles actually rebuilds the tile completely from input geometry (inefficient, I know). This will have to be fixed in the future.

However, for adding something like the pallets, that can actually introduce new walkable areas (and not just cut out parts of the navmesh) one needs to rebuild the full tile from input geometry. This means: delete the compressed heightfield tile from the dtTileCache, rebuild a new compressed tile from input geom, then rebuild a navmesh tile from that compressed tile.
There is no other way around that. That also means you cannot use navmeshes modified by hand with this approach, as you need to regenerate from input geometry automatically.

Of course, this full navmesh rebuilding is a rather extreme case. I think in most situations temporary obstacles will be enough. For anything like doors or temporarily sealed-off locations, or things like rubble or fallen objects blocking paths, adding cylindrical or convex temporary obstacles that block a certain path is enough.
Developer @ MakeHuman.org
User avatar
DavlexDesign
Orc
Posts: 400
Joined: Thu Apr 23, 2009 7:23 am
Location: Australia
x 19
Contact:

Re: DetourCrowd and Recast in Ogre demo (update)

Post by DavlexDesign »

G'day duststorm,

I have to say, I've been watching this thread since it started, seeing how viable something like this might actually be for the planet wide stuff I'm working on.
I can see agreat use for it, inside ships as you fly around the solar systems, maintaining your ship and defending your cargo against would be perpetrators, AI NPCs and PCs that teleport into your ship. I can also see it being usefull for artist controlled / created areas, building interiors, and terrain blocks created by artists. It would be interesting to see how it goes on very very open terrain. I would probably have to go the way of a procedural navmesh, so I'm very interested in what limitations you find.

At the moment, my terrain mesh holds the navicabillity inside it's procedural cache per Control Point Vertex (CPV), I'm wondering if maybe I can hook the mesh generator to build directly from that procedural cache, because my ROAMTree mesh for an entire planet never excedes 65535 control points, maybe I could incorporate it for general terrain roaming too, for NPC's and such.

Kudos to you for your efforts so far mate.

Alex
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 »

The ROAM engine is indeed a very interesting case for implementing recast in.

The biggest challenge would probably be getting the right geometry in recast, and maybe transferring everything to a useable coordinate system.
Recast just expects triangles (an array of floats and an array of indexes, without any restrictions on order or amount, plain and simple), if you can feed those from your engine into recast you're set.

Teleportation is not problem, you can remove agents and re-add them at any position in the navmesh. It's what I'm doing in my demo too if you change the start position of the agent.
The only limitation of recast is that it needs a single axis to be the gravity vector (by default that's y), it cannot cope with 3D navigation without gravity in space for example. But if you want to add pathing for space vessels, you could probably do with a much simple path finder (like: a straight line) with local steering, there are not that many obstacles in space ;). You might even be able to reuse the dtRoundedCorner to calculate smooth corners for your paths.

I'm not sure how your engine deals with terrain up close, but due to this gravity limitation it will not be possible to generate a navmesh around a globe. Only on top of it (provided the downward angle is not too steep, parameters for recast are tweakable of course). If your aim is to only generate navmeshes when the camera is closer to the terrain (which might be sensible) you just need to make sure the coordinate system of the geometry you feed to recast uses y=up.

From the results I've seen recast produce, I feel that it produces very accurate nav meshes. Therefore, especially if you are generating massive environments, I feel you should always try to go for automatically generated navmeshes.
Different types of terrain are not really a problem, both indoor and outdoor, as long as you tweak the navmesh generation parameters properly.

EDIT: To give you an idea what recast can produce from terrain meshes, I asked google for some illustrations.
http://cotdp.com/wp-content/uploads/201 ... Abbey1.png
http://blog.wolfire.com/2010/05/Automat ... ion-meshes
http://www.garagegames.com/community/blogs/view/21710
http://www.garagegames.com/community/blogs/view/21647
http://1.bp.blogspot.com/_-u6ZJlBFOL0/T ... ed_chf.png
http://www.ownedcore.com/forums/world-o ... ation.html
http://www.garagegames.com/community/fo ... ad/83665/2
http://2.bp.blogspot.com/_-u6ZJlBFOL0/S ... ile_04.jpg
http://4.bp.blogspot.com/_-u6ZJlBFOL0/S ... ile_03.jpg
http://imageshack.us/photo/my-images/51 ... stout.jpg/
http://www.crystalspace3d.org/blog/leon ... _navmeshes
http://udn.epicgames.com/Three/Developm ... tml#ReCast
It's a long list, I know. I couldn't resist ;)

The recast algorithm is incredibly stable and achieves remarkable results, even on very complex meshes.
If you want to try it out on your terrain, if you are able to export some of it as a .obj file you can load it in the recast demo (the original one that comes with recastnavigation, I mean) application and experiment with the settings to see the result yourself.

Something else I want to mention, while searching I found this excellent description of the recast parameters:
http://www.critterai.org/nmgen_settings
It explains the impact of most parameters very well with clear images.
In general, the critterAI website contains lots of invaluable information that can help you understand recast better.
Developer @ MakeHuman.org
User avatar
DavlexDesign
Orc
Posts: 400
Joined: Thu Apr 23, 2009 7:23 am
Location: Australia
x 19
Contact:

Re: DetourCrowd and Recast in Ogre demo (update)

Post by DavlexDesign »

G'day duststorm,

Thanks for the great info in that reply, made me think allot about how we could integrate this.
duststorm wrote: The biggest challenge would probably be getting the right geometry in recast, and maybe transferring everything to a useable coordinate system.
Recast just expects triangles (an array of floats and an array of indexes, without any restrictions on order or amount, plain and simple), if you can feed those from your engine into recast you're set.
Very simple really, the mesh generated by my Hybrid ROAM is just that, a list of triangles and indexes, which are offset from a central point of the page the triangles are part of, and the pages are offset from the face of the unit cube they belong to, all I would have to do is transform them to Y UP only, based on player position and UP vector on the surface of the celestial body in question, and depending on the size of the body, doing that really doesn't change the shape of the immediate terrain much anyway, because it already looks flat. On smaller bodies, like Super Mario Galaxy type sizes (small asteroids, or chunks of destroyed moons and stuff), then that would need to be done differently I suppose, because the curvature is really quite evident, and the gravity vectors change with every step taken. Still, A fix could be made for that anyway I suppose, just because it creates a flat mesh, doesn't mean it can't be transformed to fit back over the original model the same way as going the other way.
duststorm wrote:it cannot cope with 3D navigation without gravity in space for example
That's really not an issue, internal ship gravity will be Y Up anyway, so that will be like a normal internal building scenario, When the internal gravity is disrupted, then that will be different, but still, I have that covered with an internal portal region thingy, so 3D travel for AI will be possible, I just haven't catered for obstacles inside them yet.

As for space flight, I don't want recast for that, I have my own stuff for dealing with flight paths and stuff, so it will really mainly be used for internal building navigation on or in space ships, space stations, mining facilities, outposts and any other internal foot walking and also driving stuff maybe (way too many to list).

I can see that it can handle terrain quite easily, that's a good thing, because I would need it to handle small zones around the player, so that's a good thing.

My only worry is, that with the dynamic nature of the ROAM algorithm, there is allot of updating going on, to the visible mesh, and at the moment I am not caching intermediate vertices, the only spot where the mesh is at it's highest resolution is at the players position, and stuff does get discarded quite often, and rebuilt, to conserve memory.

Something that needs 1 gig just to render terrain and nothing else is useless in my opinion, when it comes to consoles and stuff like that, that's more than most consoles have in total for ram to use, including the GPU, mine uses 300 mb All up (including Ogre and its dependencies), with approximately 80 mb of that for the terrain and all its data at the moment, and even that, in my opinion, is too much just for terrain alone, I know I have a ton of other stuff built into the mesh data for allot of other things, but even If I culled all that out, I would probably still chew up about 30 mb for the entire active planet.

I'm still working on all of this, to see if I can make it truly multi-device compatible.

Alex
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 would try multi threading the navmesh build process, and maybe even allocate 2 threads to recast.
One is the regular detour navigation thread that does pathfinding and steering.
The other prepares and builds navmeshes (compressed tiles) that, one finished, can be passed to the main detour thread and added into the navmesh.
The rest of the recast process needs to happen within one thread as it's not built to be thread safe.

Given the vast amount of landscape and the procedural aspect, you will have no choice but to generate the navmesh on the fly each time. I would also only generate the navmesh for the parts you see (unless you can make an accurate prediction on where the camera will move next). I would also only pass in the geometry with the detail that is currently visible (being rendered) and build a navmesh using that. You might want to set different navmesh generation parameters for the different detail LODs however.

Building navmeshes is quite fast, and certainly if you multi thread it so it does not disturb the render thread. Just make it build the navmesh asynchronously and start using it as soon as it's been built.


You could probably generate a navmesh for small spherical planets by projecting the surface onto a flat surface, but there are some potential issues with this approach.
If the projection does not result in uniform distances (like what a mercator projection does) the resulting navmesh will make characters walk slower near the poles than in the middle of the planet.
I believe you need to choose an "equivalent" projection, that makes all areas on the map have the same relative size. You can find an overview of such techniques here: http://nl.wikipedia.org/wiki/Oppervlaktegetrouw (sorry for the non-english, but I didn't find such an overview in english. You can change the language to english after clicking any of the links).

Additionally, the areas at the edges of the map will have to be connected to the other side. You might be able to do this using off-mesh connections.

Another idea I was thinking about: maybe it can be done much simpler. Creating navmeshes for full spheres is probably only an issue for very small planets. In this case, you could wonder whether it's still useful to have a navmesh for pathplanning, as the distances that can be traveled will be very small. If the paths that can be followed on those planets are fairly simple (eg. only avoid mountains and seas) maybe you can navigate directly towards the destination and only use local steering to avoid the obstacles.

When planets become a little larger, you can generate separate navmeshes for a flat tile on the planet, for which you can apply a small fix to make the y always point upwards. Different tiles from one planet can be connected together so that they form a flat projection of the planet's terrain.
Developer @ MakeHuman.org
User avatar
DavlexDesign
Orc
Posts: 400
Joined: Thu Apr 23, 2009 7:23 am
Location: Australia
x 19
Contact:

Re: DetourCrowd and Recast in Ogre demo (update)

Post by DavlexDesign »

G'day duststorm,

Thank's again for the info, much appreciated.
duststorm wrote:You could probably generate a navmesh for small spherical planets by projecting the surface onto a flat surface, but there are some potential issues with this approach.
If the projection does not result in uniform distances (like what a mercator projection does) the resulting navmesh will make characters walk slower near the poles than in the middle of the planet.
This isn't a problem really, (My Mesh at the poles), as you can see, I don't have the same problems of converging mesh even when addressing Polar coordinate based texture mappings, so height maps from these types of data sources, shouldn't be a problem anyway, because my mesh structure is not bound to them, I work with a slightly modified unit sphere projection system, six faces of the unit cube, diced up into many pieces, all pretty close to the same size.

Generating a navmesh nearly every frame could be an issue though, even if generating only for the immediate area, as my immediate area can be quite large. Especially from mountain tops, any type of telescopic view would really mean I would need a navmesh out to a pretty far distance, several 10s of kms at least, on the flat, 1 - 2 km's would be fine I suppose, but then same thing happens for looking at mountains in the distance, as mountains can be seen for vast distances, and once again, telescopic sight stuff would come into play once again, not to mention orbital spy cam viewing. I suppose one way for me to deal with this stuff is use my original idea, and use what I have in the mesh data already, and really only use the navmesh stuff for geometry based internal areas, as it seems to have a very slick ability to generate clean mesh from geometry.

Alex
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 »

DavlexDesign wrote:any type of telescopic view would really mean I would need a navmesh out to a pretty far distance, several 10s of kms at least
Not necessarily. You only have to generate a navmesh in that case if the distance detail is so high that you will see people or vehicles from 10s of kms away. I don't think that's very realistic.
Also, the size of that terrain does not matter. It shouldn't matter that you have to generate a navmesh for 10 square km of terrain, if that terrain only contains, say, 100 polygons. It's the detail (number of polys) of the mesh that will determine how costly generating the navmesh is. Pretty far terrain will probably be pretty low detail, or at least can be reduced to it.

As I suggested, even if you have to generate navmeshes every frame, offload this process to a separate thread, time slice it, make it asynchronous to the rendering. And cache already made tiles as long as memory allows.
Make it asynchronous in a way that you do not wait for a navmesh to be generated, ever. If the navmesh comes in late, that's too bad (but should not be a major disadvantage). In practice this will probably mean you had shown a terrain for a few seconds, and in that time there was no navmesh ready.
DetourCrowd in fact does the same thing with its pathplanning. If you assign a large crowd of agents a destination, they will replan their paths individually, but the crowd manager has a maximum number of pathfinds it will do in one tick.
If there are too many pathfind requests, some agents will just have to wait a few frames before they start moving. In practice this is almost never a problem, and can even make your agents look less robotic.

In your case that would just mean that agents possibly cannot pathplan for the first second that a new terrain is shown, because there is no navmesh yet. If the navmesh comes in late, which would mean that the new terrain was only shown to the spectator for a split second, that's too bad. I think in that second he wouldn't even have had the chance to notice whether units were moving or not.
Developer @ MakeHuman.org
User avatar
DavlexDesign
Orc
Posts: 400
Joined: Thu Apr 23, 2009 7:23 am
Location: Australia
x 19
Contact:

Re: DetourCrowd and Recast in Ogre demo (update)

Post by DavlexDesign »

G'day again duststorm,

All those points are very valid.
I do the same with my terrain anyway, just by the nature of ROAM, the updating of mesh data is time sliced, a limit of triangles generated per frame, and also a limit on a per page basis, so I can get more than 1 page updated in a time slice, so I have several pages that don't need much updating go through in one hit, and other more detailed in another frame maybe.

I will look into this a bit more, thank's for the info ONCE AGAIN !!!!

Very much appreciated.

Alex
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 »

DavlexDesign wrote:I will look into this a bit more, thank's for the info ONCE AGAIN !!!!
No problem, I find it a very interesting problem to think about.


In the meanwhile I have a little update to show you guys:
Added door to demo
Added door to demo
open_closed_working.jpg (99.11 KiB) Viewed 33461 times
This serves to demo how you could achieve doors with dtTileCache.
A door is simply a convex polygon obstacle created from the bounding box of the door (but can be of a more complex shape of course). The convex obstacle is added to the navmesh if the door closes. If it opens the obstacle is removed.



This feature is added to the demo and available in the repo.

As for the instructions:
O Opens or closes the gate


Unfortunately, I'm plagued with a non-deterministic bug that sometimes makes the door have no effect on the navmesh. I've been debugging the cause of it but it is kind of a hard problem. The fact that it's nondeterministic (it happens sometimes, but most of the times it works as it should) makes it even harder. I have found some clues as to where to look, however. But I have a suspicion I have to look at the internals of recast for the cause, not in my own code.
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 »

duststorm wrote:Unfortunately, I'm plagued with a non-deterministic bug that sometimes makes the door have no effect on the navmesh. ...
I fixed the bug! :)
And of course it was my own stupid fault ;) I forgot to assign an area flag to the convex volume (in this case the flag for "unwalkable"), leaving it uninitialized and thus resulting in random behaviour. Funnily enough, the solution just hit me while I was doing something else ;)

Maybe this helps someone with the same issue in the future. If you mark an area with the "walkable" flag in a navmesh polygon that is already walkable, it will (of course) have no effect.
Developer @ MakeHuman.org
ScreenOfDeath
Kobold
Posts: 36
Joined: Wed Feb 01, 2012 2:38 pm
Location: Germany
x 2

Re: DetourCrowd and Recast in Ogre demo (update)

Post by ScreenOfDeath »

Hi !

This is my first post here, and I want to say >>Hello<< to everyone here.

Some infos about my person: (Summary)
Im 22 years old and came from Germany, i´m going to study IT in September.
Im programming since I was 13 years old with a few languages but there was to many limitations. ( Basic -> QBasic -> "Html" -> Purebasic -> BlitzBasic -> C# -> C++ )
So I decided to learn C++ and coded some small projects in Irrlicht, ( since last year ) but Irrlicht didnt satisfied me.
To find alternatives, I took a look into game engines ( Neo Axis, Esenthel, UDK, Crytek ) , but I must say I didnt like them all.
Its much better to code everything you need, because you are learning much more than use a game framework.
Last year I found finally Ogre ( found it before, but I didnt liked the own format ) but nowadyas I must say that this engine is the best choice if somebody want to code seriously games.
I have some good experience with PhysX ( native, not thru a wrapper like NxOgre ) and also lerned how to animate and design in Blender.

So far to my person :D


-> My reason to write here is that I followed your thread a while ago, and I must say you did a great job!

I want to add recast in my new project too, but I´m far away to doing it, I have other things to code.
So, I read in this thread that someone should make an VS Solution file, and so far nobody did it yet, so I decided to make it.

( The source code is the newest avaiable, download it for 2 hours )
So there are some bugs in the source, thus I cant compile it. ( uint was´nt known before, so I changed it to UINT, and add a return to one function, other small changes )

This bundel includes the (almost) original source + ressource packet from duststorm, I added the Visual Studio Solution (2010) , dlls and the .exe and cfg to it, so you just can download it, test it or compile it out of the box. ( Should work :D)
( Take a look into the README.txt )
Its only for the lazy people who cant create a solution with cmake - or people like me which doesnt like that system.


Link: http://depositfiles.com/files/98sjr6oh6 ( 22.45 mb )

So, I hope someone could use it to test this great demo from duststorm.

( English isn´t my native language, but I hope you could understand it :D )


Regards,

ScreenOfDeath
ScreenOfDeath
Kobold
Posts: 36
Joined: Wed Feb 01, 2012 2:38 pm
Location: Germany
x 2

Re: DetourCrowd and Recast in Ogre demo (update)

Post by ScreenOfDeath »

Hi,

my very first post isnt shown yet, because I added a link.

That post will be visible in a few hours I guess.

I made a Visual Studio Solution (2010) for your project, because nobody did it yet.

Again, I must say you did a great job here !

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

Hey ScreenOfDeath, welcome to the community.
Thanks for the project file. Regarding it, I believe Mind Calamity did one too a while back, but replaced it for a CMake setup. I didn't get to doing a CMake setup myself yet (I need to change it a bit to work with my original folder structure, but have just not gotten to actually working on it).
Cmake is the easiest to support multiple architectures and development systems, as it would become a bit much to create project files for all SDKs and (more importantly) keep them up to date.

I do like the idea of packaging a quickly useable .exe distribution. This would allow people to quickly try it out without having to compile it all from source. Feel free to create one, I can probably put it for download somewhere on the repo. :)

What I also wonder: did you have to modify any of the source code to make it compile (I believe the readme states something like that)? If so, could you indicate what you had to change, so maybe I could fix it in the original version. I haven't tested this on windows yet, so I'm only assuming that it works for now. :)
Last edited by duststorm on Tue Jun 26, 2012 1:40 am, edited 2 times 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 »

Also, I want to show the progress I've made this weekend.
I managed to get a basic terrain demo working. Some teasers:
Navmesh on terrain
Navmesh on terrain
screenshot06252012_211129282.jpg.jpg (81.99 KiB) Viewed 33320 times
Tiled navmesh on terrain
Tiled navmesh on terrain
screenshot06252012_211221213.jpg.jpg (128.75 KiB) Viewed 33320 times
Coarser navmesh
Coarser navmesh
screenshot06242012_175417691.jpg.jpg (92.51 KiB) Viewed 33320 times
As you can see I've experimented with the settings to generate some coarser and finer navmeshes.
I haven't been able to come up with something that I'm satisfied with, however. And at the moment I have a lot of questions how to exactly to approach this.

For example, the terrain mesh is pretty large. It's one tile generated exactly like in the terrain tutorial. I believe it is about 3000x3000 units in size and it has about 0.5 million triangles (if I'm not mistaken), which is quite a lot.
So I've been thinking maybe I should use a reduced LOD for building a navmesh from.

I've been fiddling a lot with the navmesh build parameters for some time but didn't find anything that really fit well, and then I got tired of messing with it.

The more I thought about it, the more questions came to mind:
How exactly does the navmesh have to look? Cover almost the entire terrain (is a navmesh really still useful in this case?)
Or be very strict about walkability (the user has to erode pretty flat walkable areas for the characters to walk, such as roads and flat fields). That being said, maybe the random noise terrain generated from the heightmap of the tutorial is not the best input for a navmesh. On the other hand, it would be nice if it worked with arbitrary and procedurally generated terrain.
Also what would be a good character size in relation to the terrain? At the moment characters are about 2.5 high, relative to the 3000x3000 units of the terrain page.

I believe at the moment recast doesn't really handle the proportions of the terrain mesh very well. So I think I will either have to cut the terrain page up in smaller parts, feed recast a reduced level of terrain polygons, or figure out the magic parameters that make it work.
The best results I've gotten up till now was with hacking away at recast parameters. The results I ended up with were either: very few navmesh polygons, a lot of polygons, but all on separate height layers and not connected, or very connected layers, but kind of ignoring steepness of slopes except for some really exceptional cases.
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 decided to spoil you guys with a few more amusing shots I made while playing with the demo :)
Distant travelers
Distant travelers
screenshot06252012_174930733.jpg.jpg (48.57 KiB) Viewed 33320 times
An exodus
An exodus
screenshot06252012_103230016.jpg.jpg (69.14 KiB) Viewed 33320 times
They're just so tiny!
They're just so tiny!
screenshot06252012_175226289.jpg.jpg (65.79 KiB) Viewed 33320 times
I find it quite amusing to see these tiny tiny people wander around aimlessly in that giant terrain. It makes the terrain look really huge in comparison.

I added a function to serialize the recast input mesh to a .obj file so it can be tested in the demo that comes with recast, which makes it easy to test parameters.
Unfortunately in its current state I'm not even able to build a navmesh from the terrain .obj within the official recast demo (the parameters of the GUI can't be set higher, especially cellSize is a problem).


You can try out the demo yourself if you want. I added a config file to the demo for choosing parameters, so you don't need to recompile after changing defines in code anymore. Just modify OgreRecast.cfg
By default, terrain demo is disabled and the familiar dungeon demo is shown. Set terrain to true in the cfg file to check out terrain.
The terrain demo is all still a bit crude, but it mostly works ;) The controls are mostly the same as the original demo.
Developer @ MakeHuman.org
User avatar
Mind Calamity
Ogre Magi
Posts: 1255
Joined: Sat Dec 25, 2010 2:55 pm
Location: Macedonia
x 81

Re: DetourCrowd and Recast in Ogre demo (update)

Post by Mind Calamity »

Very nice progress, duststorm! :)

I'm wondering, how do you read the terrain data ? Directly from the heightmap, or using some other method ?
BitBucket username changed to iboshkov (from MindCalamity)
Do you need help? What have you tried?
- xavier
---------------------
HkOgre - a Havok Integration for OGRE | Simple SSAO | My Blog | My YouTube | My DeviantArt
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 »

One though I had is that your going to need a way for the terrain scale to be specified but maybe presume 1 point = 1 meter as you don't know if 10 point change in the terrain is a small bump or a mountain :)
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 »

Mind Calamity wrote:I'm wondering, how do you read the terrain data ? Directly from the heightmap, or using some other method ?
I extract the vertices and triangle information from the pages in the terrainGroup, much like how I load the vertices of regular entities (sort of a getMeshInformation for terrain pages). All that functionality is in the InputGeom (RecastInputGeom) class.

Basically it takes all vertices, and transforms their coordinates in world space coordinates, and then feeds them to recast. The methods for getting the entity and terrain triangles are pretty much the same that Paul Wilson used, and in turn, those that he uses are pretty much the same snippets that are floating around on the forums or the wiki. (eg for doing polygon level ray intersections)
I believe it takes the higest resolution triangles from the terrain, so maybe I can pick a lower LOD level there.


As for Zonder's remark, yes when I get navmeshes on one terrain page properly working I intend to expand it for multiple terrain pages, swapping in navmeshes when needed along with swapped in terrain.
I would love to hear your input on how you use terrain, eg what are the terrain page sizes you use (for example in a paging setup), and how the navmeshes should look like (their detail, how far they should be produced from the camera, etc)
You can also easily vary the relation between character size and terrain size, either by modifying the terrain parameters, or by setting the ogreRecast agent height and radius. The recast wrappers and Character class are created in that they all follow the agent size parameters. I did notice that my animation scaling depending on agent size does not really work when I set agent height to 10, though ;)

Maybe I don't need to generate a navmesh for the full terrain all at once, but only load a cirkle of pages around the camera position, much like this technology demonstrates:
http://www.youtube.com/watch?v=NAUIUNjuVHg (it's shown at about 2 minutes in the movie).
By the way, that video gives some nice ideas about how recast could be integrated into an editor like ogitor.
Developer @ MakeHuman.org
User avatar
Mind Calamity
Ogre Magi
Posts: 1255
Joined: Sat Dec 25, 2010 2:55 pm
Location: Macedonia
x 81

Re: DetourCrowd and Recast in Ogre demo (update)

Post by Mind Calamity »

You wouldn't mind sharing that class, would you ? I really need to know how to read the terrain data from OGRE right now, and I haven't found any existing up-to-date threads. :)
BitBucket username changed to iboshkov (from MindCalamity)
Do you need help? What have you tried?
- xavier
---------------------
HkOgre - a Havok Integration for OGRE | Simple SSAO | My Blog | My YouTube | My DeviantArt
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 »

Mind Calamity wrote:You wouldn't mind sharing that class, would you ?
It's in the repo.
Like I said, have a look at the RecastInputGeom.cpp file.
The method (constructor) is called:

Code: Select all

InputGeom::Inputgeom(TerrainGroup *tg, std::vector<Entity*> ents)
The only thing you might need to adapt (and that is not yet properly done in my code) is find out the proper transformation for transforming the terrain verts in world space coordinates (they use a coordinate system local to the terrain page).
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 »

No real updates, but I did make a video recording of what the terrain demo looks like at the moment:
[youtube]V5kbEYxXs08[/youtube]

I asked around about my issue on the recast mailing list and gained some valuable insights. I think I know how I can improve the situation. Stay tuned ;)
Developer @ MakeHuman.org
Post Reply