.:: Bots United ::.  
filebase forums irc server wiki web
cubebot epodbot fritzbot gravebot grogbot hpbbot ivpbot jkbotti joebot
meanmod podbotmm racc rcbot realbot sandbot shrikebot soulfathermaps waypoints yapb

Go Back   .:: Bots United ::. > Developer's Farm > General Bot Coding
General Bot Coding See what a pain it is to get those little mechs shooting around

Reply
 
Thread Tools
Recast / Detour
Old
  (#1)
Neoptolemus
Member
 
Status: Offline
Posts: 92
Join Date: Apr 2012
Default Recast / Detour - 21-06-2015

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.

Last edited by Neoptolemus; 21-06-2015 at 01:56..
   
Reply With Quote
Re: Recast / Detour
Old
  (#2)
The Storm
Council Member / E[POD]bot developer
 
The Storm's Avatar
 
Status: Offline
Posts: 1,566
Join Date: Jul 2004
Location: Bulgaria
Default Re: Recast / Detour - 21-06-2015

Yay, nice work. I didn't knew that navmesh library even exist.
Looking forward to your progress. I wish PMB to see this.
   
Reply With Quote
Re: Recast / Detour
Old
  (#3)
Neoptolemus
Member
 
Status: Offline
Posts: 92
Join Date: Apr 2012
Default Re: Recast / Detour - 22-06-2015

Quote:
Originally Posted by The Storm View Post
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
   
Reply With Quote
Re: Recast / Detour
Old
  (#4)
The Storm
Council Member / E[POD]bot developer
 
The Storm's Avatar
 
Status: Offline
Posts: 1,566
Join Date: Jul 2004
Location: Bulgaria
Default Re: Recast / Detour - 22-06-2015

Nice. I'm impatient.
   
Reply With Quote
Re: Recast / Detour
Old
  (#5)
Neoptolemus
Member
 
Status: Offline
Posts: 92
Join Date: Apr 2012
Default Re: Recast / Detour - 23-06-2015

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

Last edited by Neoptolemus; 23-06-2015 at 14:40..
   
Reply With Quote
Re: Recast / Detour
Old
  (#6)
Neoptolemus
Member
 
Status: Offline
Posts: 92
Join Date: Apr 2012
Default Re: Recast / Detour - 26-06-2015

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
   
Reply With Quote
Re: Recast / Detour
Old
  (#7)
The Storm
Council Member / E[POD]bot developer
 
The Storm's Avatar
 
Status: Offline
Posts: 1,566
Join Date: Jul 2004
Location: Bulgaria
Default Re: Recast / Detour - 27-06-2015

Nice, I remember PMB doing the same steps when he wrote his own implementation to generate navmesh.
   
Reply With Quote
Re: Recast / Detour
Old
  (#8)
Neoptolemus
Member
 
Status: Offline
Posts: 92
Join Date: Apr 2012
Default Re: Recast / Detour - 27-06-2015

Quote:
Originally Posted by The Storm View Post
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.
   
Reply With Quote
Re: Recast / Detour
Old
  (#9)
The Storm
Council Member / E[POD]bot developer
 
The Storm's Avatar
 
Status: Offline
Posts: 1,566
Join Date: Jul 2004
Location: Bulgaria
Default Re: Recast / Detour - 27-06-2015

I'm not sure. He shows up from time to time about 1 time per 2 years.
   
Reply With Quote
Re: Recast / Detour
Old
  (#10)
Neoptolemus
Member
 
Status: Offline
Posts: 92
Join Date: Apr 2012
Default Re: Recast / Detour - 29-06-2015

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.
   
Reply With Quote
Reply


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump



Powered by vBulletin® Version 3.8.2
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
vBulletin Skin developed by: vBStyles.com