Recast / Detour

[Neoptolemus]

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.

[SamPlay]

"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.

[Neoptolemus]

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.

[Neoptolemus]

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



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.

[Neoptolemus]

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 Just need better avoidance of other players now.

[Neoptolemus]

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

[The Storm]

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.

[Neoptolemus]

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:



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.

[The Storm]

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.

[Neoptolemus]

Originally Posted by The Storm

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.

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.