.:: Bots United ::.

.:: Bots United ::. (http://forums.bots-united.com/index.php)
-   General Bot Coding (http://forums.bots-united.com/forumdisplay.php?f=24)
-   -   Navigation using AABB (http://forums.bots-united.com/showthread.php?t=10049)

Neoptolemus 10-03-2017 14:35

Navigation using AABB
 
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:

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

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:

https://dl.dropboxusercontent.com/u/..._Onto_Roof.PNG

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:

https://dl.dropboxusercontent.com/u/...f_To_Floor.PNG

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:

https://dl.dropboxusercontent.com/u/...ugh_Window.PNG

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

https://dl.dropboxusercontent.com/u/...st2_Hole_1.PNG

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 10-03-2017 22:04

Re: Navigation using AABB
 
wanna to see it on new bot, huh

The Storm 10-03-2017 23:57

Re: Navigation using AABB
 
Nice work, yeah! :)

tschumann 11-03-2017 04:54

Re: Navigation using AABB
 
Nice work. Looking forward to seeing it in action.

Neoptolemus 11-03-2017 08:49

Re: Navigation using AABB
 
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 15-03-2017 00:41

Re: Navigation using AABB
 
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 15-03-2017 22:56

Re: Navigation using AABB
 
Very nice! I'm excited to see it in action. :)

Neoptolemus 21-03-2017 12:29

Re: Navigation using AABB
 
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

https://dl.dropboxusercontent.com/u/88069272/Swim_1.PNG


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

https://dl.dropboxusercontent.com/u/88069272/Swim_2.PNG


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

https://dl.dropboxusercontent.com/u/88069272/Swim_3.PNG


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 24-03-2017 21:39

Re: Navigation using AABB
 
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 26-03-2017 03:06

Re: Navigation using AABB
 
Quote:

Originally Posted by The Storm (Post 66736)
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!

The Storm 26-03-2017 03:12

Re: Navigation using AABB
 
Nice. I'll be waiting to see the bot in action. :)

Neoptolemus 09-04-2017 08:35

Re: Navigation using AABB
 
Quick update: I'm still going, but my new company didn't issue me with any kit, so I'm having to share the family laptop which my wife and kids also use. I did a lot of my coding on the train to work, but obviously I can't take the laptop with me at the moment.

I have been trying to port the code over to HL proper, but I'm getting crashes even though the code is identical, which is weird. Just trying to debug :)

The Storm 09-04-2017 16:31

Re: Navigation using AABB
 
Easy fix, just buy one more laptop. :P

Neoptolemus 16-04-2017 01:54

Re: Navigation using AABB
 
Right I'm finally up and running with a new setup, so I am back in action :sorcerer:

The pathfinding solution is now working in the bot itself, so I am trying to get some footage of the bots running around, however the path nodes hug the walls too tightly at the moment so the bots end up getting caught on corners.

It's been a little while since I worked with this, so for some reason I am having some trouble getting basic things like forward/right/up vectors for traces. In the old version of my bot I was calculating the forward direction from the bot's current origin to the next point in the path, but right now I just want the forward vector to be the direction the bot is looking in.

From memory, there is a function called UTIL_MakeVectors which takes view angles (such as pEdict->v.angles) then populates the v_forward, v_right and v_up vectors into gpGlobals. However, attempting to include this produces an unresolved external symbol error even though the IDE identifies it correctly.

Is there a better way to just get the Vector of a player's current view angle? I searched online and only found functions like AngleVectors which don't exist, and no code examples online on how to create my own :(

EDIT: I figured it out. I just created a wrapper function to call g_engfuncs.pfnAngleVectors :) Hopefully I can get the bots running reasonably smoothly now, though I will still need to spend some time fixing the path finding so it doesn't hug walls and corners so tight. Perhaps some kind of "erosion" like Recast uses to shrink the navmesh away from walls and edges.

The Storm 19-04-2017 23:40

Re: Navigation using AABB
 
From very long time I've also wasn't digging in bot movement/looking code so I can't really point out a solution, but if you have trouble compiling some function I will be glad to help. :)

Neoptolemus 20-04-2017 23:43

Re: Navigation using AABB
 
Quote:

Originally Posted by The Storm (Post 66750)
From very long time I've also wasn't digging in bot movement/looking code so I can't really point out a solution, but if you have trouble compiling some function I will be glad to help. :)

Thanks!

I've had a new problem crop up which has me completely stumped: the bots can't crouch any more! I had it working great, the bots were able to climb ladders, crouch into vents etc, and then suddenly they stopped crouching. Now they sort of start walking but remain standing up.

To try and debug the issue, I commented out all code and just set the bot's forward speed to pEdict->v.maxspeed and pEdict->v.button |= IN_DUCK. The bots just start walking. What the hell?!

EDIT: Never mind, no idea how I fixed it but it works now. I really need to abstract some of this stuff and hide it somewhere safe so I don't keep accidentally breaking it.

Neoptolemus 21-04-2017 13:06

Re: Navigation using AABB
 
I've finally got the bots running around in-game. Still need to do a lot of tweaking of the core pathfinding process as it still hugs the walls too tight in many cases, and as you can see the path generated is still a little drunk and weaves around a bit.

However it's surprisingly effective. I'm still working with CS 1.6 because the maps are less complex than the Natural Selection ones so the bots don't get caught up on the geometry quite so much.

https://youtu.be/Xey8cQBcG7Y

The Storm 21-04-2017 13:19

Re: Navigation using AABB
 
Looks pretty neat. Good job. :)

Neoptolemus 21-04-2017 18:45

Re: Navigation using AABB
 
Additional bonus video of the bot running around cs_militia. I'm really pleased with how smoothly it handles ladders. Asides from the boxy pathfinding, the movement is really smooth.

In this video it manages to go from the CT spawn area, eventually landing on top of the side gate between the front and back yards of the house.

https://youtu.be/VAg_5DGod7k

By the way, the bot got stuck once he was on top of the gate, I think I set the max fall distance a little too low so he thought he couldn't jump down :P

The Storm 21-04-2017 22:16

Re: Navigation using AABB
 
It's funny to see how the bot looks down when is reaching a connection, I had the same issue with E[POD]bot long time ago. :}

Btw, you should add some radius to the path so the bot will move smoothly and if the place is too small just set the radius to zero. The Podbot based bots have code when you are using the autowaypointing option each waypoint is placed with as some radius depending on the place. In this way if you have multiple bots following the connection the chances to collide are much smaller and the movement will look more smooth. :)

Neoptolemus 21-04-2017 23:53

Re: Navigation using AABB
 
Quote:

Originally Posted by The Storm (Post 66755)
It's funny to see how the bot looks down when is reaching a connection, I had the same issue with E[POD]bot long time ago. :}

Btw, you should add some radius to the path so the bot will move smoothly and if the place is too small just set the radius to zero. The Podbot based bots have code when you are using the autowaypointing option each waypoint is placed with as some radius depending on the place. In this way if you have multiple bots following the connection the chances to collide are much smaller and the movement will look more smooth. :)

Hah, yeah the looking down is just because the movement code is really primitive right now. The logic is basically that if the bot has a path to follow then set forward speed to max and look at the next node in the path, which are placed near the floor.

I have already re-integrated my previous code which makes the bot look as far along the path as possible, so if they are climbing some stairs they will look at the top of the stairs for example, and it now uses strafing to make a much more natural type of movement.

The radius idea is interesting, one idea I want to investigate later is subdividing sectors when a moving object (e.g. a player) moves through it, thus allowing them to be included in pathfinding calculations. That's waaaay down the line right now though.

Going to look at smoothing out the paths now so there's less zig-zagging involved.

The Storm 22-04-2017 00:38

Re: Navigation using AABB
 
You can make the nodes smaller, put radius around them and the zig-zagging will be fixed. :)

Neoptolemus 01-05-2017 01:48

Re: Navigation using AABB
 
I have fixed up the zig-zagging a little bit by smoothing the path, and I have done some work on steering. I have also added some post-processing of the path once it's generated to make the path easier to follow. For example, drops (red path lines) no longer go straight down, and the bottom of ladder paths are placed further away so the bot doesn't accidentally get caught on the sides of climbable surfaces.

I have also modified the way the bot detects obstacles to strafe around them to take wall-climbing into consideration, so a bot can still strafe to avoid obstacles even when running vertically up a wall.

Below is a video of a Skulk bot navigating ns_tanith. There are some issues to work out still (you can see the bot get a little stuck here and there), but for the most part the bot seems pretty solid in getting from A to B, and it will take any path available. Still plenty of work to do though! The main thing is that the bot almost never gets completely stuck, it usually unsticks itself within a few seconds, so for the most part they are nimble enough to potentially provide a challenge.

https://youtu.be/K5hHk_AC2SM

The Storm 01-05-2017 15:22

Re: Navigation using AABB
 
What an ugly creature. :D
Btw the bot is still only using the shortest path possible without considering the whole block area that can lead him the the final destination. What algorithm are you using for path finding?

Neoptolemus 01-05-2017 16:34

Re: Navigation using AABB
 
Quote:

Originally Posted by The Storm (Post 66760)
What an ugly creature. :D
Btw the bot is still only using the shortest path possible without considering the whole block area that can lead him the the final destination. What algorithm are you using for path finding?

You're right, at the moment the bot is using just basic A*, with some weighting used for crouching, jumping etc, so it is always taking the shortest route from A to B right now. This is on the to-do list as it means right now every bot that wants to go to the same place will basically form a conga line.

How do you encourage the Podbots to mix up their routes? I'm thinking of having path finding configurable so you can set an urgency: the higher the urgency the closer they will stick to the shortest route. However, I need to come up with a decision making process that still takes logical paths to a destination without taking pointless detours (I intend to set up a separate process for random patrols, if the bot hasn't got any particular goals).

The other thing I need to do is optimise: on a complex NS map, finding a path that crosses the entire map takes around 2 seconds on a second generation i3 CPU, on an old laptop from 2010. Splitting pathfinding into separate threads will stop it interfering with the main game, but I want to get it down to less than a second. I'm not too concerned right now as I have done NO optimisation at all yet, so there is loads of room for improvement.

The Storm 01-05-2017 17:09

Re: Navigation using AABB
 
Podbots are also using A* but with some improvements. All distinct possible routes are calculated and the bot choose one of them based on route danger points and a bit of randomness. Danger points are increased for a route when a bot is killed during going thought it. The higher they are the lower the chances are the bot will choose that path again. With each round the danger points are automatically lowered, so the bot will be less predictable and will again choose the more danger path.

All that data is saved in .exp(experience) files so the more you play a map the better. :)

EDIT: When something requires emergency(like planted bomb) the bot will always choose the shortest path.

Neoptolemus 01-05-2017 18:58

Re: Navigation using AABB
 
Ok that's what I hope to implement, though right now I need to do some optimisation. ns_tanith generated 17k sectors, so when doing pathfinding it is literally performing A* against 17k potential nodes. For shorter paths it's ok, but as mentioned a path across the entire map could take 2-3 seconds, so evaluating multiple routes is out of the question until I've implemented a culling system to cut it down significantly.

Right now I want to absolutely nail the pathfinding and steer behaviour, then I'll look to make it more efficient. More videos to come soon :)

The Storm 02-05-2017 00:52

Re: Navigation using AABB
 
I'll be waiting for your progress. :)

Neoptolemus 16-05-2017 23:14

Re: Navigation using AABB
 
Quick update: I have now got marine bots responding to orders given by the commander, and I've set up individual movement profiles for the marines and all alien classes, so they will all traverse the maps based on their own capabilities (marines will take the stairs, skulks will just climb up the wall etc.).

Will have a new video soon :)

The Storm 16-05-2017 23:26

Re: Navigation using AABB
 
I'm not big fan of NS but I will watch just for the navigation. :)

Neoptolemus 18-05-2017 08:16

Re: Navigation using AABB
 
Ok :-) I'll post some decent footage tonight of them in action. I was quite pleased when a marine missed his jump and fell down behind some railings. He crouched and made his way through some vents, jumped over another set of railings to get back on the path and quickly reached his destination :)

Neoptolemus 26-05-2017 17:17

Re: Navigation using AABB
 
https://youtu.be/bl4BsC7cvhM

A new update. I have been working hard on perfecting the steering behaviours and I think I've got it pretty solid. Bots now rarely get stuck, and if they do they can usually get out of it pretty quickly. Here you can see the skulk handling more complex paths without a hitch. The way it handles vents in particular is really slick.

The movement is still a little wobbly in places, this is partly because the bot tries to stick more closely to the precise route. It does this by checking its distance from the path and if it's too high, it corrects and moves closer to it. I am being quite strict right now to avoid the bot getting caught on obstacles when navigating narrow passages, but some more tweaking will find the right balance :)

Next up, I want to handle button-operated doors. This will require adding a "detour" feature, so you can calculate a path and then, if it crosses a button-operated door, add a detour to where the button is. This hopefully will not be too difficult!

The Storm 27-05-2017 01:15

Re: Navigation using AABB
 
Little "wobbly" is really mildly said at least from what I saw on the video. The bot is moving like a cyborg with a stick. :D

No offense, but I think you should perfect the movement before starting to play with buttons. :)

Neoptolemus 27-05-2017 17:33

Re: Navigation using AABB
 
Bah :( you're right. I think I've spent too much time tweaking it so I stopped noticing how bad it looked. I'll get there ;)

Neoptolemus 12-06-2017 23:11

Re: Navigation using AABB
 
A progress update. I have made some tweaks to the movement code so the bot is better at determining if it is straying from the path and how strictly it needs to do so. This has fixed a lot of the jittery movement seen in the previous video.

I have also done some work on auxiliary functions which will be important later, such as being able to trace a line through navigation sectors for things like reachability. This will be needed for important additions like anti-aliasing on paths to further smooth them and have the bot move in a more human-like manner with fewer 90-degree "kinks" in the route taken.

Off the back of this, I have added new jump connections to allow the bot to determine if it can reach a distant position more directly by jumping. This ultimately allows it to jump over gaps and take shortcuts it would otherwise have to walk the long way to reach. Here is an example of it in action:

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


And here is another example in cs_italy:

https://dl.dropboxusercontent.com/u/...ctionItaly.PNG


It is not quite fit for purpose yet as the bots are not smart enough to figure out that they need to have the correct forward momentum before attempting a jump. If they are approaching a jump from the wrong angle they'll just leap off in that direction, usually missing the jump miserably. This wasn't a problem when the only jumping was up onto a crate or step, but when leaping across a gap of course it matters.

The Storm 13-06-2017 00:30

Re: Navigation using AABB
 
Nice work. About the jumping all the Podbot derivatives including the original Podbot do have hardcoded the best jump technique that is possible to have and this way they always get to the right spot. If you want you can checkout some of their code about that.

Neoptolemus 13-06-2017 00:39

Re: Navigation using AABB
 
Yes I remember the Podbots were really accurate with their jumps. I'll take a look for certain :)

I seem to remember in earlier version of Podbots (circa 2004 when I used to play them all the time) that they could do inhuman acrobatics by running in one direction and immediately leaping at full speed in a different direction without having to stop and take a run-up. Did this get sorted or was it left as it was? Apologies if this was never the case, my memory is a little hazy given it was 13 years ago (ouch!).

The Storm 13-06-2017 01:08

Re: Navigation using AABB
 
Well, I also don't remember. :D

SamPlay 19-06-2017 23:25

Re: Navigation using AABB
 
hi!
I am working on navigation system too, though with a different approach, so I am following this thread with interest.

I coded a bot from Podbot in the past;
As regards Podbot, as far as I remember, bot jumps were recorded from actual player jumps; the velocity at jump start is stored with the jump start navigation point; when the bot triggers the jump, the bot code forces its velocity to the stored one, which
- generates irrealistic ( violent ) direction changes if the bot direction does not match the player one at the time of recording.
- provides the right vertical and horizontal velocity components for a successful jump, though the bot velocity just before the forced setting might not have been appropriate ( this showed as irrealistic 'kicks' sometimes).
Hope this helps.

Neoptolemus 20-06-2017 23:30

Re: Navigation using AABB
 
Quote:

Originally Posted by SamPlay (Post 66809)
hi!
I am working on navigation system too, though with a different approach, so I am following this thread with interest.

I coded a bot from Podbot in the past;
As regards Podbot, as far as I remember, bot jumps were recorded from actual player jumps; the velocity at jump start is stored with the jump start navigation point; when the bot triggers the jump, the bot code forces its velocity to the stored one, which
- generates irrealistic ( violent ) direction changes if the bot direction does not match the player one at the time of recording.
- provides the right vertical and horizontal velocity components for a successful jump, though the bot velocity just before the forced setting might not have been appropriate ( this showed as irrealistic 'kicks' sometimes).
Hope this helps.

Hi SamPlay, thanks for the clarification. Now you mention the recorded jumps I do remember reading about those in some patch notes years ago, and it sounds like my memory of unrealistic velocity changes during jumps was correct.

I would be interested to hear about your navigation system if you're ready to share any details. Mine seems to work well in practice but it needs a lot of optimisation as it is quite inefficient in terms of the number of sectors generated and so on right now. Then again this machine is so old that even Half-Life struggles to run sometimes (seriously, switching on the flashlight sometimes drops the frame rate below 20!). I think it's starting to fail since it's a 2009 i3 (2nd generation) and should have no problem with HL at all.

In the meantime, I am experimenting with a different navigation approach whereby instead of generating a fixed set of waypoints from the sector system, it instead returns the sectors themselves and the bot navigates through them dynamically.

This has some advantages because the bot maintains spatial awareness, so dynamic obstacles such as moving platforms or other players can be taken into account on-the-fly without having to regenerate sections of the path. It also means its easier for the bot to determine if and how it can get back on the path if it falls, misses a jump or gets knocked around.

Will hopefully have some good results soon :)


All times are GMT +2. The time now is 09:22.

Powered by vBulletin® Version 3.8.2
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.