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:

https://dl.dropboxusercontent.com/u/...Route_dust.png


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.

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.

Re: Recast / Detour
 

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

Re: Recast / Detour
 

Nice. I'm impatient. :)

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

Re: Recast / Detour
 

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

https://dl.dropboxusercontent.com/u/...st_navmesh.png

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

Re: Recast / Detour
 

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

Re: Recast / Detour
 

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.

Re: Recast / Detour
 

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

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.

Re: Recast / Detour
 

SUCCESS!

http://youtu.be/6uFuxnBJfCE

The bot is successfully running around the map. At the moment he just picks random points to visit, and there seems to be an issue with bots sometimes choosing inaccessible areas and just humping the walls (this is probably a consequence of my earlier screenshot with the disconnected islands), but otherwise, as you can see, their movement is pretty smooth.

I want to abstract out some of the movement code to make it easier to order the bot around, and have recovery systems in case the bot falls off a ledge and needs to recalculate etc.

Re: Recast / Detour
 

cool :)

btw, are you the author of libtess2? I've been using libtess2 in an Android car navigation system for previous company and it works pretty good (no more awkward callbacks with the original GLU tesselator) :)

Re: Recast / Detour
 

I believe libtess2 is also authored by Mikko Memononen, the same as recast and detour. Luckily, triangulating a Half-Life BSP is a trivial task so I could write my own solution, as I'd rather not include too many third party libraries other than the pathfinding.

Right now I'm writing some code to parse the entities in the BSP, as I'm currently discarding func_wall entities which is not ideal since it means the bots get stuck on fences and railings, the APC in cs_office etc. Will have more updates soon!

Re: Recast / Detour
 

Very very nice progress. I'm impressed! :)

Re: Recast / Detour
 

I've finished the code to parse entities, so the navmesh generation now takes func_wall entities into consideration. This means bots now avoid the APC in cs_office and other decorative objects that obstruct movement.

I noticed however that the fence in cs_militia is still not being included, which means that it's not a BSP brush entity or a func_wall. Does anyone know what else it might be?

EDIT: Ok so it's a func_illusionary. I assume this is to create the actual chain fence effect and allow bullets to pass through, but what is actually blocking movement? It can't be a BSP brush as I already factor those in. I don't want to include func_illusionary entities either as that will make the bots think they can't pass through, for example, the curtains in cs_747. The mystery deepens...

Re: Recast / Detour
 

Check if the func_illusionary have the FL_WORLDBRUSH flag. :)

Re: Recast / Detour
 

Hmm that's going to be a little tricky as the flag appears to be set in the edict_t, but navmesh generation happens before that, reading the vertices and entity data directly from the BSP. At this point there is no flag for the entity, just a classname, origin, some rendering info and a pointer into the models array for its bounding box (which is what I read out).

I may need to read in func_illusionary entities, then use off-mesh connections to basically rejoin the broken paths for illusionary objects that allow movement (such as the curtains in cs_747).

Bah!

EDIT: On second thoughts, the engine must know to set that flag from the BSP data so I just need to figure out how it determines whether to set it or not. Time to hit the HLSDK!

Re: Recast / Detour
 

Are you sure of that? I think that in the BSP data you should have flag like SOLID_BSP or something. From what I see the engine does not set this flag but the HLSDK itself, so it should be read directly from the BSP.

Edit: Also from this old post of PMB - http://forums.bots-united.com/showthread.php?t=1226 he says that the mappers are responsible for the flag, so a little bit of research will be good. Just dump out the entity properties out of the BSP data - one from cs_747 and one from cs_militia and compare them to see what makes them solid. :)

Re: Recast / Detour
 

Yeah, the entities section is all ASCII so you can open it up, scroll to that bit and take a look. However, it may be that the flag is set in the model reference. In fact, thinking more about it, that would make more sense anyway. I'll take a look tonight.

In the meantime I've decoupled the bot's movement from their view, so they can strafe, run backwards while looking at something. I have made it so that running backwards is less accurate (so they're more likely to miss the door and run into the wall when not looking where they're going).

I need to figure out a way to stop Detour from hugging corners so tight, as bots often get caught on geometry. Are HL collisions done with boxes or cylinders? I wonder if that's the issue.

Re: Recast / Detour
 

Hi,
Half-life does not handle collision the same way than Quake.
It is POINT based, and move computations -like traces- are at least partly performed in hull-specific clip-bsp trees , which are basically pre-computed "hull-based inflated " worlds ( called "configuration spaces" in robot path planning; see zhlt code for details).
If the way recast computes contours away from walls is different than the bsp builder inflation/bevelling method, it may be closer in some occasions; to me, all this is the most obvious explanation for your bots unexpectedly bumping into the visible world.
I hope this helps.

Re: Recast / Detour
 

Hey SamPlay, thanks for the heads up.

Recast assumes the agent is represented as a cylinder, so the borders of the navmesh it generates will always have a gap from the wall the same size as the agent radius. My guess here is that Half-Life's collision detection results in characters having a different shape, which causes the bots to catch on geometry that wouldn't happen with a collision cylinder.

The simplest method here will be to give the bots some additional obstacle avoidance to compensate for this, as increasing the agent radius in recast will prevent the catching but may result in narrow corridors being considered impassible when they're not.

I'm taking a break now from movement to work on other areas, I'm putting together a proper frustrum-based visibility cone for bots for accurate sight. Then I can think about having the bots actually fight.

Re: Recast / Detour
 

"The devil is in details..."
Hi again,
I understood you are now "coding in other directions", but for sake of completeness...
1. Recast uses cylinder along walls, but apparently not around corners, where it introduces its own bevelling.
Half-life uses axis aligned boxes around corners, but I do not remember if they change for cylinders ( tweak!) along walls or not.
I suspect that, except for the side effect of bot dynamics generating overshoots on turns, your bots will always bump into corners.
2. The allowed distance from walls depends on the "standing"/"ducking" status in maps like de_aztec, where there are several walls tilted towards the ground ( the bot "head" does not hit at the same distance).
3. As regards what can block move in a map, I would look
- at "Immortal BLG" posts on this site ( maybe).
- at Xash3d ( half-life tweaked to a quake-like engine) code, where AFAIK it rebuilds/expands the bsp to be all inclusive.

Re: Recast / Detour
 

Hi again SamPlay,

Thanks for the further input. I'm still learning the intricacies of both Recast and the Half-Life internals, so this kind of advice is always appreciated :)

I think you're right that bots will always generally catch on corners, even as a player I still sometimes misjudge a corner and am momentarily blocked. I think it's a symptom of Half-Life's collision detection. I think the trick here will be two-fold:

1) Create a second pass after calling recast's findStraightPath to further adjust the positioning of the nodes. An average path will usually only contain around 12 points, though if it's a complex, weaving path it can be more (for example a spiral staircase), but we're still talking about small numbers. This would make it computationally inexpensive to check the distances of each point to the nearest wall and, if necessary, move them away a bit. Perhaps I can override the findNearestWall recast function to retrieve the location and normal of ALL hit walls and use it to place the node somewhere in the middle, so bots aim for the centre of a doorway rather than trying to cut tight around the doorframe

2) Give the bots their own way of detecting if they've caught on something and to adjust their position accordingly. It should be fairly straight forward to get the normal of the collision and "bounce" them off slightly to get them around the corner. Perhaps work out a compromise between the normal of the collision and the oritentation of the point they're trying to get to, to have them "slide" along the wall instead of trying to run into it

With regards to sloped walls, that should (in theory) be covered by recast's use of heightfields, though it is still possible that at points where the headspace is very close to the player height (e.g. 71 units, where player height is 72 units), the accuracy of the heightfield may not be enough. Reducing the cell height during voxelisation would help alleviate this problem, at the expense of longer navmesh generation times (though given this is a one-off process, it's probably not a big deal).

I'll continue working on movement of course as it's easily the most important aspect of the AI, so I'll take a look at Immortal BLG and Xash when I have a chance.

Re: Recast / Detour
 

Been working on improving the bot's ability to unstick themselves, but it's still a work in progress.

At the moment I've been experimenting with the idea of doing a trace from the bot's origin to their target. If it reaches then carry on, but if it hits something it runs the following calculation to work out which way to move to unblock its path:

- Get the cross product of the hit surface normal (to create a tangent line parallel to the wall)
- If the dot product of the tangent line and the target is negative, then multiply by -1 to get a line that is parallel to the wall, but also in the direction of the destination
- Move in that direction

https://dl.dropboxusercontent.com/u/...0Avoidance.png

If the obstacle is another player then the bot treats it as a cylinder (i.e the hit surface normal is directly back towards the bot).

It works fairly well, but needs a lot of tweaking. The main problem is when the bot's origin has a clear line of sight but their left or right side doesn't. I'll add extra traces to handle that.

Re: Recast / Detour
 

Ok, looks like I was over-complicating matters. All I had to do was have a trace on one side and a trace on the other, and then strafe left or right depending on whether one was blocked. If they're both blocked then I just recalculate the path.

Seems to work just fine now, even for awkward passages like the doors in de_dust2 :P Just need better avoidance of other players now.

Re: Recast / Detour
 

A new video of the improved movement system. Now includes senses to avoid walls and give themselves a little space to handle corners rather than trying to cut them tight and end up catching on them. It's still not perfect, but we're getting there!

https://youtu.be/DtC2k6wxFJ4

Re: Recast / Detour
 

Nice progress. Btw you can try to watch the official CS bot(Condition Zero) that also uses navmesh. They are pretty good in avoiding other players and corners.

Re: Recast / Detour
 

So quick update. Further tweaks to the code now has the bot running flawlessly around cs_italy for a good 15 minutes, never getting stuck. It even was able to fix itself when it was going up the large stairs towards the wine cellar, missed them and accidently started running up the ledge on the other side of the railings instead. It stopped, went back and tried again.

I then tried the bot on de_chateau and it immediately got caught on a simple corner and got stuck. D'oh!

I've implemented a new check. If the bot's next waypoint is no longer directly reachable, it first looks to see if a point a few units to the left or right of the point is accessible, and if it is, then it inserts that new point into the path. Failing that, it tries a point to the bot's left or right and sees if that point can reach the waypoint. Like so:

https://dl.dropboxusercontent.com/u/...edirection.png

It doesn't work flawlessly, but it seems to happen often and usually succeeds. I've also added flags to points saying whether or not it's compulsory or if the bot can skip it if the next point in the path is directly reachable. These "helper" points are always compulsory of course.

Re: Recast / Detour
 

Well I think that perhaps you should not generally hit the wall and then recalculate path. The bot should not hit the wall at all. :)

Re: Recast / Detour
 

True, the bot should not, but there are a moments where it loses line of sight with the destination point.

The main reason for this is that I'm going for a more "natural" movement type, where the bot can only move in the 8 cardinal directions as a human player would (depending on whether the forward/backward/left/right keys are pressed), so it can't move directly to a point unless it is looking at it, or it happens to align exactly on one of those points.

I think also part of the problem is simply how tight recast hugs corners when generating paths, which means even a slight deviation from the straight line could cause the point to disappear behind a corner.

Either way, I'm taking the kitchen sink approach to getting the bots running smoothly, then I'll simplify after and find the key processes that work the best.

Re: Recast / Detour
 

When a human that already had played the map wants to go somewhere, he knows exactly how to go there without the need to always directly see the target path.

I often even walk with aiming at some direction but moving to a completely different one that often is complicated - corners with stairs. :)

Re: Recast / Detour
 

Sorry, I think I didn't explain my last post properly :) The bot already can look in any direction and still move towards the waypoint, but it is limited only to the 8 cardinal directions (i.e. forwards, backwards, left, right or diagonally). That means that if the destination point is orientated on a narrow angle, it may end up moving to a position where the intended destination is no longer reachable, like so:

https://dl.dropboxusercontent.com/u/...20Movement.png

The yellow line is the exact direction the bot needs to move in, and the dotted line is the route the bot will take since in CS 1.6 you can't move in that direction unless you're rotated in the right way.

To combat this problem, the bot can insert a new waypoint next to the intended one which IS still reachable to compensate for this occurrence.

Hope this clears it up!

In other news, I've started working on off-mesh connections, which will allow for ladder movement, running off ledges and jumping. Funnily enough, the ladders will probably be the easier part since it's trivial to retrieve the ladder position and size and place connections at the top and bottom. Jumping and running off ledges is harder as it will require modifying the recast and detour library.

Re: Recast / Detour
 

Okay, now I got your point correctly. :)

However isn't it possible when the bot wants to move at target waypoint you to do the best path calculations in advance and insert additional waypoits between if needed? This way the bot will not even consider getting close to the wall.

Re: Recast / Detour
 

I must say, awesome reading! Really impressive work.
Keep us updated :)

Re: Recast / Detour
 

Thanks atomen!

I've started implementing ladders. My code now extracts the func_ladder brush and uses it to place waypoints at the top and bottom and hook it up to the navmesh.

In principle this works, the bot tries to climb the ladder, but despite looking upwards at the top and trying to move forwards, the bot just stays frozen at the foot of the ladder.

Am I missing something? I've confirmed that the bot is trying to move forwards, and they're looking upwards, but they just stay stuck on the ladder. My LookAt function looks like this:

Re: Recast / Detour
 

Could you check when the bot is on the ladder if the movetype is MOVETYPE_FLY?
Also I see in EPB that there is special code that handles ladder approaching

Re: Recast / Detour
 

Yeah I took a look at that bit of code. From what I can see though it simply checks if the bot is about to go down a ladder and slows down to ensure it doesn't go flying off the edge.

I added a bit of code which draws the direction in which the bot wants to move if the movetype == MOVETYPE_FLY. This is the result:


https://dl.dropboxusercontent.com/u/...uck_ladder.png


The red line is the bot's path, the yellow line is the direction the bot wants to move. The bot is looking at the top of the ladder (which is invisible, but it definitely works as I can climb it fine) and is trying to move forward (as shown by the yellow line). I have commented out all of the movement code so that all the bot is trying to do is move towards the next point in the path (so no trying to check if the point is reachable, no pushing away from walls etc.)

There must be something missing because the bot is frozen at the foot of the ladder, no movement at all. It's as if the moment the movetype becomes MOVETYPE_FLY, the bot is completely unable to move. It can't even move sideways.

Re: Recast / Detour
 

Ok, just for the test could you set the 5th argument of the RunPlayerMove function - "upmove" to the max moving speed as soon as the bot movetype become MOVETYPE_FLY? Lets see what happens then.

Also it almost seems like there could be something wrong again with the msecval. Could you try one of the alternative methods that I had described earlier?

And lastly it may sounds a bit rubbish but are you sure that you are still calling RunPlayerMove when the bot hit the ladder? :)

Re: Recast / Detour
 

I think this is because RunPlayerMove receives view angles instead of move angles, which should be oriented same as red line (upwards)...

To traverse ladder:
1) pEdict->v.movetype == MOVETYPE_FLY
2) bot move angles which receives to RunPlayerMove should direct at top of ladder
3) bot forwardSpeed != 0.0
So from this point I think that you have missed something from this...

Sorry for bad english...

Re: Recast / Detour
 

@Immortal_BLG Yep you are totally correct, how I overlooked that...