Response Curves - Behavioral Mathematics for Game AI - page 314

S EARCH O PTIMIZATION
Because we are using the edge values to search for the chosen bucket, we don't nec-
essarily have to have the buckets sorted by size. However, we can optimize searches
through having our buckets sorted by size. This method works very well when there
are many buckets of widely disparate sizes. We can construct an example of when
this optimization is useful by using a quadratic distribution such as:
If we use this formula over the x range of 0 to 30, we find that the probabilities
( y ) of any given x range from 100 to 10. That gives us a large difference in bucket
sizes. This is even more apparent when we realize that the final edge of these 31
buckets will be at 2155. The first bucket ( x = 0) has a 4.6% chance of being picked.
On the other end of the spectrum the last bucket has only a 0.5% chance.
The important factor to address, however, is the starting point of our “divide
and conquer� approach. The purpose of guessing the midpoint is to reduce the
amount of space left to search regardless of whether our guess was high or low. By
starting with the middle bucket, we are reducing the number of buckets on each
side of our guess to a joint minimum. No matter which way we missed (too high or
too low), we know that we have reduced the remaining buckets to search as low as
we can.
In the above examples, we started at the middle bucket found by using the
formula:
iGuess = iLow + ( ( iHigh - iLow ) / 2 );
Applied to this example, our initial index would be 15 (Figure 12.5). Upon a
little examination, however, we find that the edge of bucket 14 is 1399. That means
that almost 65% of the data is below what we calculated as the midpoint of the vec-
tor. That also tells us that, if our initial guess of 15 is incorrect, we are going to be
moving left more often than right . If that is the case, we would want to optimize for
quicker searches on the side of the vector that we are going to be landing in more
often.
By changing our initial guess to the bucket that is in the middle of the possible
choices rather than the middle bucket, we can achieve better results. That is, rather
than selecting the middle bucket, we want to select the bucket at the point where we
know the ball will fall half the time on one side and half the time on the other side.
We can do this by determining a theoretical bucket edge that is half the value of the
farthest edge.