Optimizing waypoint graph using an Octree
 

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:

http://grogbot.bots-united.com/img/octree1.jpg
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...

http://grogbot.bots-united.com/img/octree2.jpg
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.

http://grogbot.bots-united.com/img/octree3.jpg
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.

http://grogbot.bots-united.com/img/octree4.jpg
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.

http://grogbot.bots-united.com/img/octree5.jpg
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 :D

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

Re: Optimizing waypoint graph using an Octree
 

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

Re: Optimizing waypoint graph using an Octree
 

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.

Re: Optimizing waypoint graph using an Octree
 

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

Re: Optimizing waypoint graph using an Octree
 

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

Re: Optimizing waypoint graph using an Octree
 

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. 8)

Uhmm, is everyone able to contribute to the wiki? I could write a few pathfinding articles or something there.

Re: Optimizing waypoint graph using an Octree
 

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

Re: Optimizing waypoint graph using an Octree
 

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 ?

Re: Optimizing waypoint graph using an Octree
 

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

Re: Optimizing waypoint graph using an Octree
 

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.