Recast - Open Source Alternative to PathEngine

[jacmoe]

You're right, I'm sorry.

Just give us a fine screen shot of the Recast demo running on your machine, and you'll be totally and utterly forgiven!

[nikki]

Tadaa!



(trying to fix the resolution so it runs on one monitor)

[memoni]

Only the demo has SDL dependancy, the rest of the toolkit only has dependancy to std libs.

Looking at the picture, there are some weird polys, so the linux port needs a little more love. I have had several patches and the problems are well known. I hope to support linux better in future releases. It will be always a little behind, since dont have linux dev box.

[memoni]

Nikki, If you change:

const int top = (int)s->next ? (int)s->next->smin : MAX_HEIGHT;

to

const int top = s->next ? (int)s->next->smin : MAX_HEIGHT;

Does it work on 64bit? That first int cast is a bug. And nope, I'm not assuming everyone runs on 32bit system, I just cannot test on 64bit system

[nikki]

Nikki, If you change:

const int top = (int)s->next ? (int)s->next->smin : MAX_HEIGHT;

to

const int top = s->next ? (int)s->next->smin : MAX_HEIGHT;

Does it work on 64bit? That first int cast is a bug.

Yup, it works. I think I found that cast in a few other files.

And nope, I'm not assuming everyone runs on 32bit system, I just cannot test on 64bit system

Ok.

[jacmoe]

Looking at the picture, there are some weird polys, so the linux port needs a little more love.

I think it's the missing qsort rearing it's ugly face?

I have had several patches and the problems are well known. I hope to support linux better in future releases. It will be always a little behind, since dont have linux dev box.

That's one of the advantages of open source.
I am sure that people on all platforms will contribute. This is only the beginning.

[memoni]

Nikki, I think the same cast bug is in the same file three of four times (cut'n'paste ftw). Is there other places you found?

Jacmoe, yes, its the qsort. I wonder if I should reimplement the sort instead of trying to figure out good compiler defines for each platform.

Also if someone knows how to get the dimensions of a single monitor, and not the whole desktop under SDL, I'd be interested to know

[ppClarity]

Jacmoe, yes, its the qsort. I wonder if I should reimplement the sort instead of trying to figure out good compiler defines for each platform.

Maybe http://www.cplusplus.com/reference/algorithm/sort/ ?

[jacmoe]

Well, that's STL - I haven't seen STL in use in the Recast project.
So I guess that's out of the question.

[jacmoe]

I found CrissCross:
http://code.google.com/p/crisscross/
Looks like a decent low weight cross platform utility library.
Is New BSD License MIT compatible?

<edit>
It has sorting algos, quicksort being one of them, which is why I'm mentioning it here.

http://www.koders.com/cpp/fid67A82F0449 ... 3Asort#L24
http://www.koders.com/cpp/fid551F710CE5 ... even%22#L7
</edit>

[memoni]

I implemented simple replacement for qsort_r yesterday, so that is solved now. Many other cross platform fixes done too (i.e. fixed the gotos).

[jacmoe]

Great - looking forward to test it once it's committed.

[xadhoom]

Hi memoni!

Nice too see you around here in the Ogre forum. I want to give Recast a try and will invite one of our internships to use it for our pathfinding related things.
The project looks pretty good! Thanks for the Demo, too!

xad

[KungFooMasta]

Wow, this is great! I've read through the main.cpp in the demo, and while I don't understand the majority of it, my one comment is that I kind of wish the code was a little more C++ like (ie using namespaces and having classes, OOP). Staying C is likely for performance reasons I'm guessing.

I was trying to figure out how the library is used from a high level perspective. Do we have to register each "level geometry" with recast, and at some point tell recast to process everything? In our app we took an approach based off the gamasutra article "GDC 2002: Polygon Soup for the Programmer's Soul: 3D Pathfinding", and the screenshots from http://code.google.com/p/recastnavigation/ remind me of the algorithm described there.

Can this library be used to generate multiple "PathMaps", as we call it in our implementation? Basically I want to have different navigation depending on the size of the characters.

[Wolfmanfx]

It is possible to export the resulting paths as xml or something like that because it would be great to use navmesh/navgraph with my own path algos.

[nikki]

Nikki, I think the same cast bug is in the same file three of four times (cut'n'paste ftw). Is there other places you found?

It was there in just one other file I think.

[memoni]

I don't think C++ would be any speed concern. I'm no just big fan of namespaces and OOP just for the sake of it. The library started initially as more functional programming style, and the whole process is just series of function calls really, so I did not see any point trying to force it more OOP than that.

The technique really close to the one described by David Miles in his GDC06 talk (google for david miles polygon soup).

To get started take a look at one of the samples for example:
http://code.google.com/p/recastnavigati ... Simple.cpp
Scroll to bool Sample_StatMeshSimple::handleBuild() and you'll see how to build the navmesh.

If you want to export the navmesh as an xml, feel free to adjust any of the examples. The debug draw functions and dtCreateNavMeshData are good starting points to learn how to use the data. The toolkit is build so that you have access to every intermediate data there is, and they should be pretty easily accesible too. For example the compact heightfield (walkable surface extracted from voxels) could be already used for pathfinding.

I write blog about Recast too, if you're interested using Recast, take a look at it. I try to post some thoughts how things are build there.
http://digestingduck.blogspot.com/

[KungFooMasta]

Thanks memoni! I found the power point presentation, very useful! I will probably use the ideas presented there in the next version of our pathing system. One thing that I've been thinking about is how the voxelizing process starts. What I currently do is treat the area as a 2d grid, and raycast downwards at each 'cell', to see where the character would be able to stand. The problem with this is that overlapping walkable areas wouldn't work with this raycast style solution. Do you initially have some 'start point', and from there spiral outwards to detect traversable cells?

[memoni]

Raycast sampling suffers from aliasing errors. That is, it will miss some tiny or otherwise unaligned features in your input geometry. To get the best results you should use conservative voxelisation.

The way Recast recast does voxelization is that, it first calculates a bounding rectangle of triangle and the clips the triangle to each column the triangles touches. Then the min and max of the resulting polygon is calculated and the result is rounded to the vertical voxel resolution.

The voxelization result is RLE encoded to allow quickly loop up of neighbour free space as well as to save memory. That way it is also possible to have higher resoution in vertical dimension which is important for avoiding aliasing when checking if a character can move to neighbour cell.

I have found to it is faster to create the voxelization by rasterizing the triangles rather than "querying" (box test or raycast) your world. YMMV.

[koirat]

I just wanted to ask if it is possible to export navmesh from recast.
But since the creator shown himself I also want to congratulate him his achievement.

[Ident]

i tried this out and the program is very solid and intuitive, love it

however, i didn't really understand it's full purpose yet as i m not familiar with how such path engines work:
Can this be used in runtime for generating paths for characters or is this rather for being used in advance to make pathpoints for characters in level design?

Would appreciate an answer as I'm a little confused and the stuff about it and the readme file just confused me more on this matter

[koirat]

The program itself is just presenting some technology. You are not able to save any data by default until you do it by yourself. Application consists of two parts one is to generate navigation mesh, and second is to find the shortest path from one point to another.
Usually you want to generate navmesh at design time, you want to know if everything is done correctly, sometimes you need to fix some glitches manually.
Basically navigation mesh is a group of regions that your actors are able to walk and find paths.
{to tell you the truth I'm a little surprised that creator did not support some exporting methods}
You can see here navmesh made with one of those default levels, made with default settings. It's imported into blender. (you have to write exporter by yourself, I used *.obj format, same as recas input format)

[jacmoe]

That's fine if you know your level is going to be totally static.
I'd probably just use the navmesh directly, because it allows me to rebuild the navmesh should the level geometry change.
And it allows me to page navmeshes as well.
Maybe a cached navmesh on disk, but I'd keep the Recast navmesh format because that's what Detour uses.

[Ident]

okay, thx koirat,- i guess this is not what i m looking for then, altho it's a really awesome application

[nikki]

If you just have some small moving objects but a generally static level, how about a pathfinding algorithm using recast navmeshes for the 'general path', and a steering algorithm for actually following it?