.:: Bots United ::. - View Single Post

Neoptolemus · **Navigation using AABB -** 10-03-2017

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!

	(#1)
Neoptolemus Member Status: Offline Posts: 93 Join Date: Apr 2012	Navigation using AABB - 10-03-2017 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!