.:: Bots United ::.  
filebase forums discord server github wiki web
cubebot epodbot fritzbot gravebot grogbot hpbbot ivpbot jkbotti joebot
meanmod podbotmm racc rcbot realbot sandbot shrikebot soulfathermaps 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
Optimizing waypoint graph using an Octree
Old
  (#1)
Akz
Creator of GrogBot
 
Akz's Avatar
 
Status: Offline
Posts: 91
Join Date: Jan 2004
Default Optimizing waypoint graph using an Octree - 13-02-2005

Got this idea earlier today and decided to share it with you others.

Let's say we've got a really big CS map loaded and waypointed. There's 1500 waypoints in total. (This is just an example after all!) You've got 16 bots running around the map. Every bot loops through the waypoint list to find the nearest waypoint twice per second. With some basic maths, You'll find out that it equals 48 000 loops per second in total. With 60 fps, its 800 loops per frame in average.

For those of you who don't know what an Octree is,
An octree is a tree data-structure. Think about it this way, a cube (the root) is divided into 8 smaller cubes (children), each of these smaller cubes are then divided again into 8 smaller cubes (if specific conditions haven't been met), and again, and again...

Now, how to use that in practice?

To find out how large the root cube should be, loop through the list of waypoints, and find the one with the farthest X, Y or Z value from the origin (0,0,0). Let's say we have a map with three waypoints placed, A at (3200, 2011, -2511), B at (231, -3854, -459) and C at (2564, 1056, 6). Now, after looping through the waypoints and comparing their X, Y and Z positions to the origin, you'll find out that the largest value found was 3854. The root cube should be 3854x3854x3854.

I'll demonstrate the Octree process for waypoints with a few simple drawings:


This picture represents a 2-dimensional waypointed map. The 2D form of Octree is called Quadtree by the way. The blue dots are marking the waypoints. Remember to save pointers to the waypoints inside for every node you create. We want to have no more than 5 waypoints per one Octree (or in this case, Quadtree) node. Consider this pic as the root node. Is there more than 5 waypoints in it? Yes, divide...


Is there more than 5 waypoints in the upper-left node? Yes, let's divide again... I'll call the upper-left node A from this on.


Is there more than 5 waypoints in the upper-left node of A? No, we're done with it, move to the next child, it's okay as well, the next one too. In the last one, there's 8 waypoints in it, divide.


Now loop through the children just like as we did for A. Upper-left: 2 waypoints, upper-right: 1 waypoint, lower-left: 1 waypoint, lower-right: 4 waypoints. We're done! No more division needed here. Move up in the tree.

We're done with A:s children now as well, move up in the tree.

Now we're working on the root's children. The upper-left node (A) is ready, move to the next one. There's 3 waypoints in it, no division needed, next one is ok, so is the last one. Move up in the tree.

Ahh, we're back on the root node, job done! Save the data to your waypoint file for example. Well, how is it meant to be used then? Let me show ya.


The red dot is the player and the green circle is the radius we're searching the nearest waypoint from. We'll start from the root node, is the radius inside the root node? Yes. Move down in the tree.

Is the radius inside the root's 1st child node? Yes. Move down in the tree. I'll call the root's 1st child node A from this on.

Is the radius inside A's 1st child node? No. Is the radius inside A's 2nd child node? No. Is the radius inside A's 3rd child node? Yes. This node has no children to loop through, so let's loop through the waypoint pointers stored in the node. One of the waypoints is inside the circle (or colliding it, whatever). Store the waypoint pointer to a linked list or something for later access. And here we go again! Is the radius inside A's 4th child node? Yes. The node has children, move down in the tree. I'll call A's 4th child node A4 from this on.

Is the radius inside A4's 1st child node? Yes. No children to loop through. Loop through the waypoints checking if they're inside the radius and store the pointers to the list for later access. Is the radius inside A4's 2nd child node? No. Is the radius inside A4's 3rd child node? Yes. Do the same as in A's 1st child. Is the radius inside A4's 4th child node? Yes. Do the same as in A's 1st child. We're done with A4, move up in the tree.

We're done with A's children now as well. Move up in the tree.

We're done with the 1st child. Is the radius inside root's 2nd child? No. Is the radius inside root's 3rd child? Yes. Oh my god, you know what to do already right? Loop through the waypoints checking if they're in the radius and saving the pointers to our list if so. Is the radius inside root's 4th child? No. Move up in the list. Root node reached. We're done!

Thank god it's over. I feel tired, maybe I shouldn't have explained the whole looping process

The CPU power saved in that example is minimal due to the small number of waypoints, but in large areas the difference may be noticable. Also notice that my example was using a Quadtree, which only has 2*2=4 children per node (2-dimensional). When writing your 3-dimensional Octree implementation, your nodes will always have 2*2*2=8 children (or none). In your real implementation, you should also define a minimum size for your nodes to avoid cases like continous dividing due to a large soup of waypoints placed on each other somewhere.

Tell me what you think, is it a crazy idea or not and please don't blame me if it's old information or something


GrogBot - A bot for Pirates, Vikings and Knights HL modification.

http://grogbot.bots-united.com

Last edited by Akz; 13-02-2005 at 12:33..
  
Reply With Quote
Re: Optimizing waypoint graph using an Octree
Old
  (#2)
Cheeseh
[rcbot]
 
Cheeseh's Avatar
 
Status: Offline
Posts: 361
Join Date: Dec 2003
Location: China
Default Re: Optimizing waypoint graph using an Octree - 13-02-2005

I've thought of it before but it's difficult to implement and not the best way to get the nearest waypoint. What if there are no nearby waypoints (or none visible) in the current child node of a bot where the child above has the nearest waypoint or a reachable waypoint? These nodes are split up at congruent postitions not related to the maps complexity. Well reading the "check radius inside node" how more complex will it get? Finding the nearest waypoint may require finding the child/node above/below/left to/right to it on the diagram (may require a more sophisticated data structure)

I use a 3d hash table where it splits all waypoints again into congrent slices but it's easy to find the outer blocks of a chosen block, its just [x-1][y][z] then [x+1][y][z] then [x][y+1][z] etc etc (three simple for loops)

i'm not saying it's impossible for quadtree's just more complex than it may seem, especially for a 3d quadtree that you may want for waypoints.

Here's a really crap mspaint example to show the problem that was breifly mentioned, its a bit artificial but shows the problem.

-B is the bot
-blue dots are waypoints
-red line is the map
Attached Thumbnails
Click image for larger version

Name:	botquadtree.jpg
Views:	389
Size:	7.1 KB
ID:	614  

Last edited by Cheeseh; 13-02-2005 at 14:23..
  
Reply With Quote
Re: Optimizing waypoint graph using an Octree
Old
  (#3)
@$3.1415rin
Council Member, Author of JoeBOT
 
@$3.1415rin's Avatar
 
Status: Offline
Posts: 1,381
Join Date: Nov 2003
Location: Germany
Default Re: Optimizing waypoint graph using an Octree - 13-02-2005

i'm also using a hashtable, but only 2d, because you dont have too much diversity on the z axis for most maps. when a nearest waypoint is searched, the nearest bucket and all it's neighbours are searched, if nothing can be found, the old 'stupid' routine is called. but that shouldnt be the case too often, because when a player isnt near to a waypoint, a waypoint is added automatically.

An octtree would certainly be another good solution, but hashing was easier for me, because I didnt knew how to get the neighbouring buckets there fast (havnt worked much on it though), when i'm at a border of a big volume, i.e. the neighbour would be in quite another part of the tree, and we have to go down the tree because, I simply didnt like the idea of searching the other 'half' of the terrain.


  
Reply With Quote
Re: Optimizing waypoint graph using an Octree
Old
  (#4)
Akz
Creator of GrogBot
 
Akz's Avatar
 
Status: Offline
Posts: 91
Join Date: Jan 2004
Default Re: Optimizing waypoint graph using an Octree - 13-02-2005

Oh, never used hash tables before. Got to do some googling. Thanks for the tip!


GrogBot - A bot for Pirates, Vikings and Knights HL modification.

http://grogbot.bots-united.com
  
Reply With Quote
Re: Optimizing waypoint graph using an Octree
Old
  (#5)
Pierre-Marie Baty
Roi de France
 
Pierre-Marie Baty's Avatar
 
Status: Offline
Posts: 5,049
Join Date: Nov 2003
Location: 46°43'60N 0°43'0W 0.187A
Default Re: Optimizing waypoint graph using an Octree - 13-02-2005

Yes, this quadtree/octree concept seems to be quite a fashionable idea in the game AI developers' world, but I side with Cheeseh, it might not be desirable to need that level of complexity to limit the number of waypoints to search from. Personally I use a 2D hashtable to store my walkfaces, like Cheeseh again. If I want to expand from a given [x][y] I look successively in [x-1][y-1], [x-1][y], [x-1][y+1], [x][y+1], [x+1][y+1], [x+1][y], [x+1][y-1], [x][y-1] (i.e. I circle around the slot) which in total leads me to only 9 slots to search into.

However Akz's explanation of the octree screams out for a wiki article ASAP



RACC home - Bots-United: beer, babies & bots (especially the latter)
"Learn to think by yourself, else others will do it for you."
  
Reply With Quote
Re: Optimizing waypoint graph using an Octree
Old
  (#6)
Akz
Creator of GrogBot
 
Akz's Avatar
 
Status: Offline
Posts: 91
Join Date: Jan 2004
Default Re: Optimizing waypoint graph using an Octree - 13-02-2005

I'm pretty sure I understand how hash tables work now (Wow, that's simple!), though I'm going to continue the research on making octrees useful in bots too.

Quote:
Originally Posted by Pierre-Marie Baty
However Akz's explanation of the octree screams out for a wiki article ASAP
Uhmm, is everyone able to contribute to the wiki? I could write a few pathfinding articles or something there.


GrogBot - A bot for Pirates, Vikings and Knights HL modification.

http://grogbot.bots-united.com
  
Reply With Quote
Re: Optimizing waypoint graph using an Octree
Old
  (#7)
sfx1999
Member
 
sfx1999's Avatar
 
Status: Offline
Posts: 534
Join Date: Jan 2004
Location: Pittsburgh, PA, USA
Default Re: Optimizing waypoint graph using an Octree - 13-02-2005

You could just use the BSP tree built into the map. Hell, the engine probably has functions to help you with this.


sfx1999.postcount++
  
Reply With Quote
Re: Optimizing waypoint graph using an Octree
Old
  (#8)
@$3.1415rin
Council Member, Author of JoeBOT
 
@$3.1415rin's Avatar
 
Status: Offline
Posts: 1,381
Join Date: Nov 2003
Location: Germany
Default Re: Optimizing waypoint graph using an Octree - 13-02-2005

had a similar idea when reading this thread :

pmb, why dont you use the bsp tree determining the nearest walkface ? since you are not doing strange stuff like tub as far as I know, and the walkfaces are directly linked to the bsp data, so why not use that fast dotproduct search ?


  
Reply With Quote
Re: Optimizing waypoint graph using an Octree
Old
  (#9)
sfx1999
Member
 
sfx1999's Avatar
 
Status: Offline
Posts: 534
Join Date: Jan 2004
Location: Pittsburgh, PA, USA
Default Re: Optimizing waypoint graph using an Octree - 13-02-2005

I tried to get PMB to use an actual BSP tree for his walkmesh, but he said it was to much math.


sfx1999.postcount++
  
Reply With Quote
Re: Optimizing waypoint graph using an Octree
Old
  (#10)
Pierre-Marie Baty
Roi de France
 
Pierre-Marie Baty's Avatar
 
Status: Offline
Posts: 5,049
Join Date: Nov 2003
Location: 46°43'60N 0°43'0W 0.187A
Default Re: Optimizing waypoint graph using an Octree - 13-02-2005

I will not use the BSP tree because I want my bot to be portable. So far I only use the BSP data to build the list of polygons. Once this is done, everything else works independently from the engine.



RACC home - Bots-United: beer, babies & bots (especially the latter)
"Learn to think by yourself, else others will do it for you."
  
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 - 2024, Jelsoft Enterprises Ltd.
vBulletin Skin developed by: vBStyles.com