Navigation using AABB

[Neoptolemus]

Originally Posted by The Storm

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]

You can make the nodes smaller, put radius around them and the zig-zagging will be fixed.

[Neoptolemus]

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]

What an ugly creature.
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]

Originally Posted by The Storm

What an ugly creature.
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]

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]

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]

I'll be waiting for your progress.

[Neoptolemus]

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]

I'm not big fan of NS but I will watch just for the navigation.