Recast / Detour

[Neoptolemus]

Hi there,

I've been working on integrating the recast and detour libraries written by Mikko Mononen into the HPB template, to create a bot whose navigation and pathfinding is powered by it.

The easy part has been done. I've written some code to read a Half-Life BSP, extract all the vertices, triangulate the faces and write the indices to a standard .OBJ file format. It also flips the Y and Z vertices around, and mirrors along the Z axis (as OpenGL, and therefore recast, uses a right-handed coordinate system where Y is up, and -Z is "forward"). It's not perfected yet as it still extracts the geometry for the sky and other redundant surfaces, and the bounding boxes for entities, but these will be stripped out next to leave only "real" geometry.

I've then opened the level up using the RecastDetourDemo application available from the github here.

The results are pretty good, as shown here:




For anyone who is interested in trying it for themselves, I've made a pre-compiled version of the tool available (complete with examples for cs_italy and de_dust), as well as the source for my BSP-OBJ exporter here:

https://dl.dropboxusercontent.com/u/...stDetourCS.zip

The source is not fully drag and drop, you'll need to define your own functions for retrieving the BSP file path and the OBJ destination path, but that should be all.

I'll update this thread as I make progress and I eventually want to release a bot template with the navmesh generation and pathfinding fully integrated.

[The Storm]

Yay, nice work. I didn't knew that navmesh library even exist.
Looking forward to your progress. I wish PMB to see this.

[Neoptolemus]

Originally Posted by The Storm

Yay, nice work. I didn't knew that navmesh library even exist.
Looking forward to your progress. I wish PMB to see this.

It's been around a few years now, but it isn't well known. Epic just integrated it into the latest version of Unreal Engine 4 but otherwise it tends to stay relatively anonymous, probably because it's open source under GPL. The author, Mikko, used to work as a senior AI programmer for Crytek.

Recast is the library used to generate a nav mesh from a triangle soup, and Detour is a separate library for pathfinding. It has some interesting innovations around pathfinding in crowds to avoid "3 stooges syndrome" in doorways and narrow corridors.

You can find a really good high level write-up of how Recast works here:

http://critterai.org/projects/nmgen_study/

It's a Java port of the library but it does a great job of explaining the process.

Ultimately I want to use Recast and Detour as a base, but add my own, Half-Life specific enhancements. I'll keep you posted

[The Storm]

Nice. I'm impatient.

[Neoptolemus]

I managed to get the bot to internally generate a navmesh when the user types a command last night. De_dust takes about 2-3 seconds on my i7.

When I try exporting the generated mesh back out to an OBJ file to check it out however, the indices look a little messed up. It's probably just that I'm reading the data out of the detailed mesh incorrectly so I'll have a look at the Recast documentation and try again. Looks promising though!

EDIT: Yep, Looks like piecing it back together into a triangle mesh is a little more involved. I'll figure it out when I have time. Once I've proven that the mesh generated is viable, I can start thinking about getting the bots moving around the map

[Neoptolemus]

Success! My bot now generates a viable navmesh, here is de_dust:



You'll notice some odd little islands here and there, that's just where I've not quite culled the geometry that is inside the map, but not actually reachable by the player, like on top of pillars and walls etc. It's not really a big deal for the moment since they're disconnect and therefore wouldn't form any part of a path anyway.

Now let's get the bots moving around

[The Storm]

Nice, I remember PMB doing the same steps when he wrote his own implementation to generate navmesh.

[Neoptolemus]

Originally Posted by The Storm

Nice, I remember PMB doing the same steps when he wrote his own implementation to generate navmesh.

Yeah, I wonder if he still keeps an eye on these forums from time to time? I'll have a dig through the archives as well and read up how he built his navmesh, see if there are any useful bits regarding ladders for example.

[The Storm]

I'm not sure. He shows up from time to time about 1 time per 2 years.

[Neoptolemus]

When I have more to show I'll try and get in touch. In the meantime I've been doing a bit of housekeeping and created a menu to generate the navmesh and export the map data into my bots own little directory. This will make debugging easier in the future as I had previously done it all in one process.