# Help me with this silly algorithm...

Discussion in 'Game Development (Technical)' started by cliffski, Aug 16, 2004.

1. ### cliffski ModeratorOriginal Member

Joined:
Jul 27, 2004
Messages:
3,897
0
I know it should be easy but im getting old...

Say i have a variable number of objects (at least 1)
and a float value from zero to one

I need to select the object that is the closest match to the float.
so if i have 5 objects and the value is 0.5 I want the 3rd object.
if the value is 0 i want the first object (object 0). if its 1.0f i want the 5th object (object 4)

This needs to work for every value from 0 to 1.

I bet this can be done in 1 line of C++, I just cant concentrate Its not good enough to just cast an int, I need it to be the closest match without rounding in an arbitrary direction.
Cheers!

#1
2. ### patrox Indie Author

Joined:
Jul 27, 2004
Messages:
218
0
probably:

long indexOfObject = (long)(thefloat*(float)(maxObjects-1)) ;

pat.

#2
3. ### cliffski ModeratorOriginal Member

Joined:
Jul 27, 2004
Messages:
3,897
0
doesn't that cast down though? so 0.49 is considered 4 when there are 10?

#3
4. ### Nikster Original Member

Joined:
Jul 27, 2004
Messages:
698
0
you don't need the -1 as if you have 10 objects 1.0 would = 9

#4
5. ### Jim Buck Indie Author

Joined:
Jul 27, 2004
Messages:
1,158
0
Actually, if you want each object to have equal chance of getting picked, you have to "partition" 1.0 into slices of maxObjects. (Otherwise, if you just do simple rounding, the first and last object will have half the chance that the others will.) So:

// this will assume you want zero-based indexing
long indexOfObject = (long)(thefloat*(float)maxObjects);
if(indexOfObject == maxObjects)indexOfObject--;

The above gives every single index equal chance of being chosen *except* for the last value. It will have one more float value that can choose it: 1.0.

As an example, consider the above code on maxObjects of 4:
.00 - .24999 ----> 0
.25 - .49999 ----> 1
.50 - .74999 ----> 2
.75 - .99999 ----> 3
1.0 -------------> 3 (the is because of the if-statement and the reason why the last value will have one more float value that can choose it)

#5
Last edited: Aug 16, 2004
6. ### Nemesis Original Member

Joined:
Jul 27, 2004
Messages:
273
0
Indeed, the solution works for the range 0.0 - 1.0 inclusive, except for 1.0 itself which should be treated as an exception. A simple if/then or wrapping the expression in a max(...) function should do.

I'm not surprised at all you got stuck on this.. I can often handle complex stuff but am befuddled by the simplest ones.. duh!

#6
7. ### svero ModeratorOriginal MemberIndie Author

Joined:
Jul 27, 2004
Messages:
3,392
6
Here's code to find a random integer between max and min... So RandomRange(0,5) will return a random number from 0-5 with uniform probability. So you could do...

item = my_items[RandomRange(0,NUM_ITEMS-1)]

And the bonus is that it's a useful general function to add to your stuff.

Code:
```double RandomProb ()
{
static bSeeded = 0;

if (!bSeeded)
{
srand ((unsigned)time (NULL));
bSeeded = TRUE;
}

double prob = (double)rand () / (double)RAND_MAX;
return prob;
}

INT RandomRange (INT min, INT max)
{
if (max < min)
{
swap (max, min);
}
else if (max == min)
{
return max;
}

//Algorithm requires these asserts
ASSERT (min > INT_MIN / 2);
ASSERT (max < INT_MAX / 2);

//Take NUMBER OF ELEMENTS times random probability.
double dNum = (max - min + 1) * RandomProb ();

//Find largest number that dNum is 'greater than'.
INT range = INT (dNum);

//Unlikey, but can happen that RandomProb returns EXACTLY 1.0000000000000
if (range == max - min + 1)
{
return max;
}

RET_ASSERT (range <= max - min, min);

return min + range;
}
```

#7
Last edited: Aug 17, 2004
8. ### lexaloffle Indie Author

Joined:
Jul 27, 2004
Messages:
207
0
Right. Now we have everything we need to derive a correct answer.

1. patrox: i = t*(n-1)
2. cliffski: i > t*(n-1)
3. Nikster: i = t*n
4. Jim: i = (t==1) ? n-1 : t*n
5. Svero: rand()%n ^_^

If we assume  to be correct, then  must be false, because (n-1) is clearly not equal to n. However,  can't be false because it is usually not the same result as , and svero is usually right. Therefore,  is false. This means that  must be true, because if i != x, then i >x, unless i < x which would be ridiculous. So i == x+y (where x == t*(n-1) and y is a positive number), but we still do not know the value of y. We can see by  that it is sometimes 0 and somtimes 1. Therefore, on average it is 0.5, which gives us the following result:

i = t*(n-1)+0.5

And with casting:

i = (int)(t*(float)(n-1)+0.5);

_

#8
9. ### Jim Buck Indie Author

Joined:
Jul 27, 2004
Messages:
1,158
0
That's not right. For example, in the case of 4 objects, you want 0 - .24999 to map to 0. In your case .24999 becomes 1.24997 (3.0 * .24999 + 0.5).. and when cast as an int becomes 1... not 0 like it should. Any formula that is different from t*n will inherently not give equal chance to all the possible index values.

#9

Joined:
Jul 27, 2004
Messages:
3,897
0

#10
11. ### grimreaper Original Member

Joined:
Jul 27, 2004
Messages:
35
0
Those who dont read "Numerical Recipes in C" are condemned to fsck up...

Dont be tempted to use the following; it uses the low order bytes which dont have enough entropy.

// returns a random integer in the range 1 to maxObjects.
int ClifskisNotVeryRandyNumber( unsigned int maxObjects )
{
return 1+( rand() % maxObjects );
}

// returns a random integer in the range 1 to maxObjects.
int ClifskisRandyNumber( unsigned int maxObjects )
{
return 1+(int) ( maxObjects*rand()/(RAND_MAX+1.0) );
}

// returns a random integer in the range minRange to maxRange.
int ClifskisRandyNumber( unsigned int rangeMin, unsigned int rangeMax )
{
return rangeMin+(int) ( rangeMax*rand()/(RAND_MAX+1.0) );
}

Dont forget to initialize srand somewhere.

BTW, random number generation is much harder than it looks.

grimreaper

PS
Hey Svero: you had to special case RandomProb returning exactly 1 coz you didnt add 1 to RAND_MAX.

#11
12. ### svero ModeratorOriginal MemberIndie Author

Joined:
Jul 27, 2004
Messages:
3,392
6
I guess that's a good trick ... and yet.. 1.0 is a valid probability. Course I suppose there's no particular use for returning a probablity of 1 vs .999999999... in general as it rarely even comes up.

#12
13. ### lexaloffle Indie Author

Joined:
Jul 27, 2004
Messages:
207
0
I was guessing that cliffski doesn't require the ranges of reals mapping to each integer to be the same size. i.e..

Draw a unit line segment. Draw n evenly spaced points along the line such that the 1st one is at 0 and the nth one is at 1. For any given number (t), find the closest point.

i = (int)(t*(float)(n-1)+0.5);

It's n-1 because 11 points will be spaced 0.1 units apart.

This line of code is taken from an animation system were there are n keyframes spread evenly from 0 to 1. When interpolation is turned off, it has to pick the closest frame (i) for a given time (t).

#13
14. ### svero ModeratorOriginal MemberIndie Author

Joined:
Jul 27, 2004
Messages:
3,392
6

okok guys!...

I think cliffski's learned his lesson and from now on will work out his own algorithms - S

#14
15. ### Morphecy Original Member

Joined:
Jul 27, 2004
Messages:
34
0
LOL guys #15