http://en.wikipedia.org/wiki/Binary_search
I implemented a kind of binary search in the path portion of my sprite system today. Binary searches are FAST! You should know how they work in case you ever need to find a certain value, or the value closest to a certain value in a sorted list!
The way a binary search works is simple. You look at the item in the middle of the list, and if your value is less than that, you continue your search on the right half of the remiaining list. Otherwise you continue your search on the left half of the remaining list.
In my path system, I have a segmented line, with points at various X and Y positions. In path space, each of these points is a certain distance from the start of the path, in increasing order. My task was to find the point which is closest to a desired path space X position, without going over.
My first approach was to simply iterate through the list of points, incrementing a distance accumulator, until I went over my desired value. At that point I knew I'd found the start of the segment in which the X position I'd specified lies.
This was however quite slow when dealing with paths with anywhere between 400-2000 points, while moving 50 spheres along it, and doing 20 physics steps each frame, each requiring each sphere's position in screen space to be calculated multiple times! Ouch!
How slow? Well let's say the framerate dropped to 30, just from all those path caclulations.
So I decided to optimize that code with a binary tree, and optimize it did! Now I convert my path list to an array when I update the path, and then when I need to transform points from path space to global space I do a special binary search on that list, where at each step instead of simply checking to see if the value is less than or greater than the current value, I also check to see if the next value in the array is greater than the desired value if the current value is less than the desired value. This is neccessary because I'm not looking for specific values that I know are in the array, I'm looking for the nearest value which is less than the desired value, because that indicates the point which is at the start of whichever segment of the path the desired point actually lies within.
Anyway, doing it this way, the speedup is tremendous. According to my own calculations, the worst case search would have to look at just 8 points in a list of 256 points, and just 16 in a list of 65536 points! But that's the worse case. According to the Wikipedia article, the search takes O log N, and that means that searching a list of 256 points, in the average case, only 2 or 3 points will need to be examined to find the correct point on the path! Because I'm looking at the next point in the path because I'm doing a "fuzzy" search my cost is probably 2x this, but still, that's incredibly fast, and you might find it heard to beleive until you try "dividing" the path in half and half again to find the worst case for a specific number of points yourself. :-)
The only drawback of this sort of search is the list bust be SORTED, and sorting a list every time you want to find a point, and converting it to an array every time you want to find a point is not going to give you any speed improvement. So this algorithm works best on lists which don't change that often relative to the number of times you actually need to find point in the list. In my case, you may never change the path once creating it once, and thousands of searches will be done on that list of points, so this algorithm is perfect for my needs.
You might also want to look up Binary Tree, which is a way of doing these sorts of searches directly on a linked list. I didn't use the binary tree cause it is a lot more complicated to set up and to adjust on the fly and there would be no real increase in speed over the setup I'm using.
Btw, there are functions in the code archives for doing binary searches, though I didn't think to look there before coding my own and mine was a special "fuzzy" case anyway. :-)
|
