Help me with this silly algorithm...

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

  1. cliffski

    Moderator Original Member

    Joined:
    Jul 27, 2004
    Messages:
    3,897
    Likes Received:
    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!
     
  2. patrox

    Indie Author

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

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

    pat.
     
  3. cliffski

    Moderator Original Member

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

    Original Member

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

    Indie Author

    Joined:
    Jul 27, 2004
    Messages:
    1,158
    Likes Received:
    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 Jim Buck, Aug 16, 2004
    Last edited: Aug 16, 2004
  6. Nemesis

    Original Member

    Joined:
    Jul 27, 2004
    Messages:
    273
    Likes Received:
    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!
     
  7. svero

    Moderator Original Member Indie Author

    Joined:
    Jul 27, 2004
    Messages:
    3,392
    Likes Received:
    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 svero, Aug 17, 2004
    Last edited: Aug 17, 2004
  8. lexaloffle

    Indie Author

    Joined:
    Jul 27, 2004
    Messages:
    207
    Likes Received:
    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 [1] to be correct, then [3] must be false, because (n-1) is clearly not equal to n. However, [3] can't be false because it is usually not the same result as [5], and svero is usually right. Therefore, [1] is false. This means that [2] 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 [4] 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);


    _
     
  9. Jim Buck

    Indie Author

    Joined:
    Jul 27, 2004
    Messages:
    1,158
    Likes Received:
    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.
     
  10. cliffski

    Moderator Original Member

    Joined:
    Jul 27, 2004
    Messages:
    3,897
    Likes Received:
    0
    my head hurts
     
  11. grimreaper

    Original Member

    Joined:
    Jul 27, 2004
    Messages:
    35
    Likes Received:
    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 );
    }

    Instead use:

    // 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.
     
  12. svero

    Moderator Original Member Indie Author

    Joined:
    Jul 27, 2004
    Messages:
    3,392
    Likes Received:
    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.
     
  13. lexaloffle

    Indie Author

    Joined:
    Jul 27, 2004
    Messages:
    207
    Likes Received:
    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);

    This is just patrox's answer with +0.5 to adjust for rounding.

    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).
     
  14. svero

    Moderator Original Member Indie Author

    Joined:
    Jul 27, 2004
    Messages:
    3,392
    Likes Received:
    6
    This thread is hilarious!

    okok guys!...

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

    - S
     
  15. Morphecy

    Original Member

    Joined:
    Jul 27, 2004
    Messages:
    34
    Likes Received:
    0

Share This Page

  • About Indie Gamer

    When the original Dexterity Forums closed in 2004, Indie Gamer was born and a diverse community has grown out of a passion for creating great games. Here you will find over 10 years of in-depth discussion on game design, the business of game development, and marketing/sales. Indie Gamer also provides a friendly place to meet up with other Developers, Artists, Composers and Writers.
  • Buy us a beer!

    Indie Gamer is delicately held together by a single poor bastard who thankfully gets help from various community volunteers. If you frequent this site or have found value in something you've learned here, help keep the site running by donating a few dollars (for beer of course)!

    Sure, I'll Buy You a Beer