🔒 Locked

Better runtime efficiency

Started by bballmitch Apr 27, 2006 at 6:58 PM 3 replies 500+ views

Original Post

Apr 27, 2006 at 6:58 PM

Ok, So I have this block of code that I will explain:


if(keys[VK_CONTROL])
       {
           double x = getRandomNumber(-60,60), z = getRandomNumber(-60,60);
           while( x > (player1->getX() - 10) && x < (player1->getX() + 10) )
           {
                  x = getRandomNumber(-60, 60);
           }
           while( z > (player1->getZ() - 10) && z < (player1->getZ() + 10) )
           {
                  z = getRandomNumber(-60, 60);
           }
           zom.init( x , 0, z, 100);
       }

What happens is if you press ctrl, then two random numbers are gotten between -60, and 60. It keeps setting x to a new random number if that number is within a 10 unit radius of player1. Same for Z. Then my Bad_Guy object (zom) is initialized with the correct coordinates. The problem with this is that it may take a time to find these numbers. What happens is it usually takes 1-2 seconds to get these numbers correct, which slows down my program. Is there a better way to do this that will take much less time? BTW, getRandomNumber() works 100% like it should.

Palidine

200

Palidine

Apr 27, 2006 at 7:14 PM

If I'm reading it right, you basically want an offset between 10-60 units away from the player's position in either the positive or negative direction:

so:

//get the random offsetz = getRandomNumber(10,60);//50% of the time it's negativeif ( getRandomNumber( 0, 100 ) >= 50 ){    z *= -1;}//add the offset to the player position to get the actual positionz += player1->getZ();

the code is the same for the X axis, just replace all the z with x

-me

Numsgil

110

Numsgil

Apr 27, 2006 at 7:39 PM

It seems to me you're using the manhattan distance away from the player (that is, travel along the axis).

If you're interested in how to do it with a circle so it's not quite so blocky, here's what I do:

double distance = getRandomNumber(10, 60);double angle = rnd() * 2 * PI; //pick an angle between 0 and 2 PI//assumes that rnd() returns values between [0, 1).  You could also do://double angle = getRandomNumber(1, 1256) / 200;//to provide a fairly good range of 1256 different angles.zom.init( distance * cos(angle) , 0, distance * sin(angle), 100);

NotAYakk

Apr 27, 2006 at 7:48 PM

Or:

// represents the valuesstruct Interval {  double start;  double end;  Interval(double start_, double end_):start(start_), end(end_) {};};struct IntervalLength { double operator()(Interval i,...)const{return i.end-i.start;};};struct LengthTotaler {  struct Helper {    double length;    Helper(double l):length(l){};    Helper(Interval i):length(IntervalLength()(i)){};  };  int operator()(Helper l, Helper r) {return l.length+r.length;};};// exception list iterators must be sorted and non-overlapping.template<typename iterator >int RandomExcept( Interval range, std::pair<iterator, iterator> except ) {  int except_total = std::accumulate(except.first, except.last, 0., LengthTotaler);  double total_range = IntervalLength()(range) - except_total;  double random_value = getRandomNumber(total_range);  double retval = random_value + range.start;  {for (iterator i = except.first; i != except.second; ++i) {    if (retval >= i.start) {      if (retval <= i.end) {        retval+= IntervalLength()(*i);      } else {        break;      }    }  }}  return retval;}int test() {  Interval total_range = Interval(-60., 60.);  Interval excluded_range = Interval(-10, 10);  typedef std::pair<Interval*, Interval*> IntervalRange;  IntervalRange excluded = IntervalRange(&excluded_range, &excluded_range+1);  return RandomExcept( total_range, excluded );}

That may work. It basically places all of the "brains" of Palidine's response into code.

Althought, I don't see how what you wrote could take multiple seconds.

If your random number is truely uniform, there is a 83% chance that you'll pass your tests on the first try. Or a 68% chance you'll pass both tests.

The chance that you'll loop more than a handful of times is amazingly small. Which seems to tell me that either
a> Something in that code you wrote is amazingly slow, or
b> getRandomNumber isn't generating numbers that are very random.

Might I ask what happens when you do:

int i;for(i = 0; i < 1000; ++i) {  double d = getRandomNumber(-60, 60);}printf("0x%08x\n", i);

How long does it take?

Edit: removed printf from inner loop

[Edited by - NotAYakk on May 1, 2006 12:48:54 PM]

Numsgil

110

Numsgil

Apr 28, 2006 at 10:18 AM

If he's doing it multiple times a second it could take a while. Or doing something similar within getRandomNumber.

What does getRandomNumber look like? I know it's somewhat difficult to get such a function to return the start and end values with equal probability to the rest of the function, I might be able to help you with yours if it's being quite slow.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.