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