.:: Bots United ::.  
filebase forums irc server wiki web
cubebot epodbot fritzbot gravebot grogbot hpbbot ivpbot jkbotti joebot
meanmod podbotmm racc rcbot realbot sandbot shrikebot soulfathermaps waypoints yapb

Go Back   .:: Bots United ::. > Developer's Farm > General Bot Coding
General Bot Coding See what a pain it is to get those little mechs shooting around

Reply
 
Thread Tools
Re: Navigation using AABB
Old
  (#21)
Neoptolemus
Member
 
Status: Offline
Posts: 81
Join Date: Apr 2012
Default Re: Navigation using AABB - 21-04-2017

Quote:
Originally Posted by The Storm View Post
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.
   
Reply With Quote
Re: Navigation using AABB
Old
  (#22)
The Storm
Council Member / E[POD]bot developer
 
The Storm's Avatar
 
Status: Offline
Posts: 1,552
Join Date: Jul 2004
Location: Bulgaria
Default Re: Navigation using AABB - 21-04-2017

You can make the nodes smaller, put radius around them and the zig-zagging will be fixed.
   
Reply With Quote
Re: Navigation using AABB
Old
  (#23)
Neoptolemus
Member
 
Status: Offline
Posts: 81
Join Date: Apr 2012
Default Re: Navigation using AABB - 4 Weeks Ago

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

Last edited by Neoptolemus; 4 Weeks Ago at 01:00..
   
Reply With Quote
Re: Navigation using AABB
Old
  (#24)
The Storm
Council Member / E[POD]bot developer
 
The Storm's Avatar
 
Status: Offline
Posts: 1,552
Join Date: Jul 2004
Location: Bulgaria
Default Re: Navigation using AABB - 4 Weeks Ago

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?
   
Reply With Quote
Re: Navigation using AABB
Old
  (#25)
Neoptolemus
Member
 
Status: Offline
Posts: 81
Join Date: Apr 2012
Default Re: Navigation using AABB - 4 Weeks Ago

Quote:
Originally Posted by The Storm View Post
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.
   
Reply With Quote
Re: Navigation using AABB
Old
  (#26)
The Storm
Council Member / E[POD]bot developer
 
The Storm's Avatar
 
Status: Offline
Posts: 1,552
Join Date: Jul 2004
Location: Bulgaria
Default Re: Navigation using AABB - 4 Weeks Ago

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.
   
Reply With Quote
Re: Navigation using AABB
Old
  (#27)
Neoptolemus
Member
 
Status: Offline
Posts: 81
Join Date: Apr 2012
Default Re: Navigation using AABB - 4 Weeks Ago

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
   
Reply With Quote
Re: Navigation using AABB
Old
  (#28)
The Storm
Council Member / E[POD]bot developer
 
The Storm's Avatar
 
Status: Offline
Posts: 1,552
Join Date: Jul 2004
Location: Bulgaria
Default Re: Navigation using AABB - 4 Weeks Ago

I'll be waiting for your progress.
   
Reply With Quote
Re: Navigation using AABB
Old
  (#29)
Neoptolemus
Member
 
Status: Offline
Posts: 81
Join Date: Apr 2012
Default Re: Navigation using AABB - 1 Week Ago

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
   
Reply With Quote
Re: Navigation using AABB
Old
  (#30)
The Storm
Council Member / E[POD]bot developer
 
The Storm's Avatar
 
Status: Offline
Posts: 1,552
Join Date: Jul 2004
Location: Bulgaria
Default Re: Navigation using AABB - 1 Week Ago

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


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump



Powered by vBulletin® Version 3.8.2
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
vBulletin Skin developed by: vBStyles.com