Navigation using AABB

[Neoptolemus]

Hi all,

After a little while away I'm back.

I spent some time playing with the Recast/Detour library to see if there was a reliable way to handle things like climbing ladders, jumping over/onto obstacles and so on, but I couldn't really find a decent way of handling it. Most of my attempts occasionally worked and usually didn't.

Also, because I want to write a proper, unified bot for Natural Selection that can play either side and even as the commander, the navmesh solution as it stood was woefully inadequate for the fact that you have so many different movement profiles, including classes with the ability to fly and climb walls/walk on ceilings.

Eventually I decided to go back to the drawing board, dispense with fancy workarounds and just do something cruder but more flexible. What I've come up with so far is a navigation system based on axis-aligned bounding boxes (AABB).

The idea is to process the map to generate a series of irregular-sized boxes along a grid which has units around 10 HL units big. It does this by voxelising the map into 10x10x10 cubes so it looks like a Minecraft world, then expanding each cube as much as possible. This is an example of what it looks like in cs_assault. The white lines show you the boundaries of each box, and each box also has a height associated with it so the AI knows if it can fit in by walking, crouching or not at all:



Once the boxes are generated, I can then work out connection details telling the AI how to get from box A to box B (e.g. do I have to jump, can I walk between them, do I have to crouch or climb a ladder etc). Then the flexibility becomes simple, if the height difference between the box I'm currently in and the next box is greater than my step height, but less than my maximum jump height then I jump up to get there. If it's too high to jump but I can climb walls then I'll run up the wall to get there and so on.

The results have actually been pretty good, I did some testing on cs_militia which has some tricky and interesting movements to perform. Here is my pathfinding trying to get onto the roof of the house from the front yard:



As you can see it correctly determines it can climb the ladder and then jump off from the top onto the roof (Mauve means climb a ladder, yellow means jump and red means drop down). Now here is the AI getting back down:



In this case it decided to drop down from the roof into the room overlooking the yard, then jump out of the window. Now here is the AI trying to get into the attic space from the back yard:



And in de_dust2, here it has figured out it can get in through the small hole in the wall by the bomb site (blue by the way means crouch):



So far it seems to be working well, though there's still quite a bit to do:

* Currently there is no post-processing of the AABBs that are generated to further consolidate and optimise, so the numbers can be quite high. In some of the large and more complex natural selection maps the count can reach almost 12k. This translates to a 0.25-0.5s calculation time for a worst-case scenario path find (i.e. a failed path find between two points on opposite sides of the map). This is to be expected since I'm sacrificing pre-calculation for greater flexibility, but this can be significantly improved still

* The pathfinding uses a basic A* system with no post-processing, which is why you can see some inefficient, blocky movement patterns

* The pathfinding doesn't yet take the width of a player into account, so it will happily send them through gaps which are too narrow to move through

* It also hugs the edges of surfaces a bit too closely. As you can see in the first Militia screenshot it is climbing the very edge of the ladder

However so far it seems promising. It correctly allows skulks to climb up walls and into vents, and lerks can fly up onto high ledges.

This system in theory should also make dynamic geometry fairly simple to implement since boxes can be moved around, or even generated on the fly (total time to generate 12k boxes and all their connections for a large, complex HL map takes around 0.25s).

Anyway, just thought I'd drop by and share my progress so far, hopefully I can turn this into a viable navigation method for HL-based maps!

[lokkdokk]

wanna to see it on new bot, huh

[The Storm]

Nice work, yeah!

[tschumann]

Nice work. Looking forward to seeing it in action.

[Neoptolemus]

It won't be ready to use in-game for a little while yet. The test application I'm using in the screenshots is ideal as it gives me a very easy way to visualise the paths generated, so I won't migrate the code into the bot proper until I'm satisfied with general path finding and can start work on steering. Can't wait to show off a video of skulks charging around a map though

[Neoptolemus]

Quick update: I have solved the problem of narrow gaps and fixed some irritating edge cases with ladders not being detected properly. I've also modified wall climbing so it actually checks that there is solid wall to climb up (so skulks don't try to climb up thin air to get to suspended walkways or floating platforms). It's really starting to look good.

Next up is swimming, which will require a little bit of logic but nothing too different from what walkable areas do.

Finally, tweaking the path so the AI doesn't insist on walking right on the edge of ledges. The voxelisation process doesn't follow the geometry 100%, so there are cases where a walkable area will slightly overhang the actual level geometry, which is why we want to avoid the edges.

I'll be putting the code up on Github for the bot once I've migrated the navigation code over from the testing tool I'm using, so I'll be sure to link you guys to it once it's up. Screenshots coming soon!

[The Storm]

Very nice! I'm excited to see it in action.

[Neoptolemus]

Success! Swimming is now in. I created my own little obstacle course to see if the pathfinding could figure out how to get there, and it caused some weird crashes with free() which never happened in any other map. That's now fixed.

Here are the results:

1) AI jumps up some crates, runs along the overhanging beam and then jumps down into the tank of water. It is smart enough to know that it can fall from a much greater height into water than it would if it was landing on solid ground




2) It swims to the bottom of the tank, then swims through the tunnel and up the other end




3) Finally it climbs out of the water, jumps into the vent and reaches the destination!




Remember that this is not using ANY waypoints or human hints. It is 100% calculated using just the geometry it extracts from the BSP file. I'm genuinely surprised how effective it seems to be.

There are a couple of outstanding things to work on:

1) Avoid hugging the edges too closely
2) Path smoothing to avoid unnecessary "kinks" in the route it takes
3) Create connections between non-adjacent sectors (to handle jumping over gaps, flying etc)

I will probably look at handling 1 and 2 in the testing tool, and when I'm happy I will migrate the code to the bot itself and start actually seeing the pathfinding in action

[The Storm]

Lol, I'm really impressed! I can also propose one more step
4) Make engine independent API so that much more FPS's can benefit from your hard work.

[Neoptolemus]

Originally Posted by The Storm

Lol, I'm really impressed! I can also propose one more step
4) Make engine independent API so that much more FPS's can benefit from your hard work.

In fact it is engine independent. The main process acts on a triangle soup, basically just vertices and indices like an OBJ file, though of course I have a pre-processing step to extract the triangles from the BSP in my implementation. To make it work for another engine you would only need to create a bespoke process to generate a series of triangles from the level data.

The main issue to overcome would be to simplify the map enough to avoid generating too many sectors. Half-Life maps are quite blocky and tend to be axis-aligned, but modern maps use much more detailed meshes which can be at any angle which could result in huge numbers of sectors. It would be worth experimenting with though

I have started integrating my pathfinding system into the bot now as I want to see how it performs in practice, but I've been delayed slightly by a change in jobs. I was doing development on my work laptop which I've had to return but I'm hoping to get another from my new workplace. Hopefully I can have a video in the next few days!