Game Development Reference
In-Depth Information
USHORT NumberToConsider = mvTargets.size() * 0.25;
BuildEdges( NumberToConsider );
// USHORT i = rand() % ( NumberToConsider - 1 ); // <— The old way
USHORT Guess = rand() % ( mvTargets[NumberToConsider - 1].Edge );
USHORT i = GetResult( Guess, NumberToConsider );
mpCurrentTarget = mvTargets[i].pDude;
mpCurrentWeapon = mvTargets[i].pWeapon;
}
Notice that, for comparison purposes, we have left in the original method for
determining the index of the target to select (commented out). In that method, we
selected a random index between 0 and the last record we were considering
(
NumberToConsider - 1
). Instead, rather than generating a random index, we
generate a random
guess
between 0 and the edge of the last bucket (in our example,
81). We then need to find out into which bucket the random guess falls. We do this
by passing it into
GetResult()
.
Our implementation of
GetResult()
here is similar to the one that we originally
used in Chapter 12. The implementation is the same “divide and conquer� binary
search. The only difference is that we have included a parameter,
NumBuckets
, to
state how many of the buckets we are searching.
USHORT CAgent::GetResult( USHORT Target, USHORT NumBuckets )
{
// Bucket indexes
USHORT iHigh = NumBuckets;
USHORT iLow = 0;
USHORT iGuess;
bool found = false;
while ( !found ) {
// Guess is halfway between the low and high indexes
iGuess = iLow + ( ( iHigh - iLow ) / 2 );
