Navigation using AABB

[SamPlay]

hi!
Here is what I am working on:
I separated the bot movement issue in 2:

1. planned navigation( to move from any point to any other point):
I started by adding a "nav along segment" process to the widespread
"nav towards waypoint" one to strongly tie the bot to the line joining 2 waypoints,
but I finally opted as core process for a more efficient/human like "nav around corners", where waypoints are
replaced by corners retrieved from map geometry: the bot move straight tangentially to a sequence of
circles (with a sign for the turn): the equations are very simple trigo.

2.short distance unexpected moves ( dodging bullets, a grenade, hand to hand fighting moves
, avoid friendly player/ neutral moving obstacle): I felt here that the key was to know to what extent one
could decide upon moves w/o caring about the world fixed obstacles: this is obtained by computing expansions
of each bsptree leaf to maximum size convex ( overlapping ) cells as a set of bounding planes: any straight move
is safe within such a cell.

3.Different move angles constraint often show up at the same time: I have devised a way to combine/mix them
( basically, each angle requirement is converted in a desirability index curve on a 360 degree span; mix is
performed on those curves. Heavy but works really great.)

I am using for both systems data generation the "configuration space", as it is available in the
form of clipping trees in hl bsp files; this allows to half-solve the issue of the bot bumping into the world.

I plan to use a bsptree of my own that generalizes "config space" for any hull size to expand 1. and 2.
but I am for now fighting with far too high pre-processing computation times on real maps.

hope this helps

[Neoptolemus]

Hi SamPlay, that sounds really interesting actually.

The "nav along segment" bit sounds similar to what I have currently implemented for my bot. It generates a set of waypoints using the sector-based system I developed and it judges how far it is from the line connecting two waypoints and adjusts movement accordingly. The jittery movement seen in my previous videos was largely down to the bots being too strict about sticking to the line.

I'm not sure I've heard of a navigation system being expressed in terms of corners. How do you generate the corner markers (is it entirely automatic from BSP data, or does it require human intervention?), and how are they linked together so a bot knows it can reach point A directly from point B?

Would be interested to see a video of the results

[SamPlay]

hi again,
some answers...
1. "nav along segment": Associated with a velocity controller and a state of the art waypoint nav controller, you can get extremely tight trajectory control w/o jitter ( like almost instantaneous 90 deg turn).

2. "nav around points/corners": this one I invented; my code does not cover all cases yet, but it already works in my simple maps.
2. Data generation: fully automatic, that is the whole point for me;
2.1. I use "configuration space(s)": I coded tools to build/expand them from half-life1 bspfile or my own simple test-map format.
2.2. Corner-Points: for each edge shared by a walkable face and a non-walkable one: rotate around a fixed vertex from one face to
the next sharing an edge until 360 degrees or another such edge is met; a corner point exists if the covered angle is more than 180 degrees
( steps and the like actually make it fairly more complicated).
If you use world data, the corner-point lies on a world edge and the turn radius should at least be the bot hull circumcirle radius;
If you use configuration space, the c-point is already away from obstacles and the radius is just a 'safety/comfort' margin.
2.3. Connections: c-points should be connected for nav...
- if one can reach the other by a 'constant-yaw' move ( in configuration space),
- if they are reciprocally 'silhouetting' ( else the segment cannot be part of a shortest path).
In my own simple-3d worlds where 2d projection does not loose info, I project on 2d and use a 2d bsptree based method, adding checks for 'silhouetting'.
This was good enough to get data to run and check my nav control laws.
In the general case, my preferred solution - still in the works - = is for now :split the 3d world into piece-wise '2d-projectable' sub worlds, use the 2d approach and recombine.

3. video: I do not have any; what ( free!) software should be used?

[Neoptolemus]

For video recording I use Fraps. The free version gives you 30 seconds of footage. I then use VLC player to compress it to an AVI and then I chuck it on YouTube. It's not great quality but it works for me! If you want to record a video longer than 30 seconds, you can record multiple 30-second clips and then stitch them together using VLC.

I look forward to seeing more of your system in action, it sounds really unique!

[SamPlay]

hi,
I am currently re-coding to be able to find connections in full-3d, so i will look into fraps but I cannot shoot anything right now ; when? depends on what you'd rather see - tell me ...
1. my bot navigating in a real counter-strike session: not anytime soon, as
I think it is still my old 'nav along segment' which is implemented.
2. my extremely crude 3d engine-like 'every-day' ai-test-bed ( top-view+ little first person view), with a aabox-bot having dynamics of half-life (from pm_move.cpp!)
In effect, 'corner-nav' does not look much different from the usual 'homing';
the trajectories are more efficient, hence more human-like, but you are still stuck with one of the issue with homing that 'nav along segment' solves: the sharper and fastest the turn, the more the bot deviates 'outside' the turn without caring to re-align with the expected path segment.

[Neoptolemus]

Not to worry SamPlay, I'm looking forward to seeing what it looks like when it's ready

It's been a while since I posted any progress, so here is a video of the bot with the new jumping behaviour. I did some optimisations so that now building the jump connections only adds on ~10% to the navigation build time as opposed to quadrupling it

https://youtu.be/BXIQ781caug

The bot determines if it is likely to miss a jump, either because it is moving too slowly or is approaching the jump at the wrong angle, and takes a step back to give itself more of a run up. It needs refinement but seems to work pretty well at the moment.

The new system of navigation is (kind of) in, with the bot dynamically navigating through sectors instead of having a static route generated for it. This also allows it to better understand the space around it and therefore avoid hugging walls like it was doing previously.

[The Storm]

Looks good.

[Neoptolemus]

I'm still working on getting steering behaviour nice and reliable. The bot still sometimes gets stuck in places it shouldn't, but I should have some decent footage up soon.

I created an obstacle course for the bot to test more demanding movement, and got a nice surprise from it when I let the bot run through it. I had created a narrow walkway suspended over a water tunnel, similar to the screenshot I showed a while ago. The idea was that the bot would drop off the walkway into the water, swim through the tunnel and climb out at the other end, climb a couple of ladders and get to the destination.

Instead, the cheeky bastard dropped off the walkway, landed on the RIM of the water tunnel, carefully walked around the edge and then jumped directly from there to the destination, bypassing the water tunnel and ladders. That was really cool, but unfortunately it was also cheating, so I had to shoot him.

[Neoptolemus]

Alright, a new video!

https://youtu.be/TnEqo4cyPlI

This is using the obstacle course I built which is specifically designed to test tricky navigation, including:

- Narrow passages
- Vents
- Duck-jumping (for obstacles too high for regular jumps)
- Swimming
- Dropping
- Jumping
- Climbing ladders
- Dealing with breakables that are in the way

As you can see, the movement is a lot better with less hugging of walls. There is still some polish needed:

- Bot sometimes inexplicably freezes while climbing ladders and can't progress any further (this only seems to happen when the framerate drops to 30 for recording, weird)
- Bot sometimes still misses easy jumps, need to tweak it so they don't aim to land right on the edge of their target...
- If I tell the bot to go back after reaching the end of the course, for some reason he refuses to duck under one of the bars. No idea why this is since it's the same height as before...

[The Storm]

Much better although the bot seems a bit nervous before jump.

Two things I can suggest about the framerate.

1. First record a demo, then while playing the demo start to do the actual recording.
2. About the issue in general - it sounds like something wrong with the calculation of the msec value.