.:: Bots United ::.

.:: Bots United ::. (http://forums.bots-united.com/index.php)
-   General Bot Coding (http://forums.bots-united.com/forumdisplay.php?f=24)
-   -   Recast / Detour (http://forums.bots-united.com/showthread.php?t=9985)

Neoptolemus 20-06-2015 23:52

Recast / Detour
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:


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 21-06-2015 21:02

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

Neoptolemus 22-06-2015 08:01

Re: Recast / Detour

Originally Posted by The Storm (Post 66180)
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:


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 :thumbsup:

The Storm 22-06-2015 19:05

Re: Recast / Detour
Nice. I'm impatient. :)

Neoptolemus 23-06-2015 11:27

Re: Recast / Detour
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 26-06-2015 22:21

Re: Recast / Detour
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 27-06-2015 15:50

Re: Recast / Detour
Nice, I remember PMB doing the same steps when he wrote his own implementation to generate navmesh. :)

Neoptolemus 27-06-2015 18:16

Re: Recast / Detour

Originally Posted by The Storm (Post 66188)
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 27-06-2015 19:17

Re: Recast / Detour
I'm not sure. He shows up from time to time about 1 time per 2 years. :D

Neoptolemus 29-06-2015 12:04

Re: Recast / Detour
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.

All times are GMT +2. The time now is 04:11.

Powered by vBulletin® Version 3.8.2
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.