Random Position between ranges

Question

Does anyone have a good algorithm for generating a random y position for spawning a block, which takes into account a minimum and maximum height, allowing player to to jump on the block.

Blocks will continually be spawned, so the player must always be able to jump onto the next block, bearing in mind the minimum position which would be the ground, and the maximum which would the players jump height bearing in mind the ceiling

Answer 1

You just have to generate some boundaries for the blocks you are going to make, maybe due to the last block or other limitations in your game; for example, if your game has some level of ground, no block should start below ground level. Having those parameters set, it's really easy to create a random number which has all the features you required.

In your game example: imagine a block starting at NewStartPositionY and ending at NewEndPositionY. We know GroundLevel is the ground height (you consider it as zero) and CeilingLevel is the ceiling height. A character might jump at most MaxJump units. Some other parameters might be PlayerHeight, which is the height of the character, and LastStartPositionY and LastEndPositionY which define the last block, and let's take MinimumBlockSize as the minimum size of platform. Knowing all these values you can set your boundaries :

// to initialize boundaries
NewStartPositionY = GroundLevel;
NewEndPositionT = min (LastEndPositionY + MaxJump,  CeilingLevel - PlayerHeight)
// to set actual random value
NewStartPositionY = random (NewEndPositionY - NewStartPositionY - MinimumBlockSize)
NewEndPositionY = random (NewEndPositionY - NewStartPositionY - MinimumBlockSize) + NewStartPositionY + MinimumBlockSize;

---

Edit:

Here is what the above code actually does; I just expanded it since it seems to cause many a headache! (It just needs more variables and does more operations but the result is the same.)

// -- first we define what are the boundaries of generated blocks 
// it's obvious that no block can be under the ground level
MinimumBoundaryY = GroundLevel;
// we need to make sure player can jump over the new level
// and at the same time we have to make sure player can go over it
// and not hit the ceiling so we choose the minimum value from them both
MaximumBoundaryY = min(lastEndPositionY + maxJump, CeilingLevel - PlayerHeight)
// --now initialize startPosition of the Block
// we want the block to at least have `MinimumBlockSize` height
// so the start position should be somewhere between `minimumBoundaryY`
// and `MaximumBoundaryY - MinimumBlockSize`
StartYRange = MaximumBoundaryY - MinimumBoundaryY - minimumBlockSize;
// and now we a random value we assign the actual value of new StartPosition
newStartPositionY = random() % StartYRange + MinimumBlockSize;
// --now as the last part we have to calculate endPosition of the new block
// again we first calculate the range for endPosition value.
// note that end position should always be somewhere between
// `beginPositionY + MinimumBlockHeight` and `maximumBlockHeight` so the range well be
EndYRange = MaximumBoundaryY - newStartPositionY - MinimumBlockHeight;
// in the end just set the EndPosition of the Block, we now it's variation range
// and we know it's the minimum valid value is `beginPositionY + MinimumBlockheight`
NewEndPositionY = random() % EndYRange + newStartPositionY + MinimumBlockHeight;

Hope this second piece of code helps you all understand what my code does! (and change your downvotes to upvotes :D).

Answer 2

@Gajet's answer is impossible to follow (so I'm not even convinced it will work), and what I think @The Communist Duck meant his solution to be...

block_y = ground_y + random() % (previousBlock_y + playerJumpHeight)

...will be heavily biased towards creating blocks with y-values centered around ground_y + playerJumpHeight.

The easiest way to produce more satisfying results would be, rather than generate a height between ground_y and previousBlock_y + playerJumpHeight, generate a random value between previousBlock_y - playerJumpHeight and previousBlock_y + playerJumpHeight.

Of course, since we want to take ground_y and maxBlockHeight into consideration also, we really want to find a random value between max(ground_y, previousBlock_y - playerJumpHeight) and min(maxBlockHeight, previousBlock_y + playerJumpHeight). This will skew our distribution a bit (biased towards the center of the screen), but not enough to be noticeable.

The simplest way to do this would be

//delta_y is a random number between -/+ playerJumpHeight
min_y = max(ground_y, previousBlock_y - playerJumpHeight)
max_y = min(maxBlockHeight, previousBlock_y + playerJumpHeight)
range_y = max_y - min_y
block_y = random() % range_y + min_y

If you then want the block to have a random height as well, just generate a random number between ground_y and block_y to be the height.

---

[Edit] There is a way to have a probability of jumping down by any amount, while still giving the player equal probability of being anywhere on the screen at any given point.

Thanks to Didier Piau on the math forums for figuring this out. The full explanation is complex, so I'll leave it out; the curious can visit that page, from which I generalized this algorithm. The algorithm itself is actually pretty simple, though.

int getNextBlockHeight()
{
    int playingFieldHeight = screen_y - ground_y;
    int canonicalBlockMaxHeight = playingFieldHeight - playerHeight;
    int nextBlockMaxHeight = min(currentBlockHeight + playerJumpHeight, canonicalBlockMaxHeight);

    //Let's divide the screen vertically into chunks of size playerJumpHeight.
    //This code makes it so that each chunk is approximately twice as likely as being chosen
    //as the previous chunk
    float canonicalHeightRatio = (float)canonicalBlockMaxHeight / playerJumpHeight;
    float nextHeightRatio = (float)nextBlockMaxHeight / playerJumpHeight;

    //The following looks complicated, but really it just ensures that the minimum is 0, the maximum is
    //nextBlockMaxHeight, and everything in between is mapped logarithmically
    float randomMin = pow(2, -canonicalHeightRatio);
    float randomMax = pow(2, nextHeightRatio-canonicalHeightRatio);
    float randomVal = randFloat(randomMin, randomMax);
    float randomHeightRatio = log2(randVal)+canonicalHeightRatio;
    return (int)(randomHeightRatio*playerJumpHeight) + ground_y;
}

//Return the log-base-2 of a number
const float log_of_2 = log(2);
float log2(float value)
{
    return log(value) / log_of_2;
}

//Generates a random floating-point number between min and max
float randFloat(float min, float max)
{
    float randomNormalized = (float)rand()/RAND_MAX; //Between 0.0 and 1.0
    return randomNormalized*(max-min) + min;
}

Answer 3

Generate a random y value between a ground y value g and a max height m. m is simply g+character jump height.

I don't know how Obj-C's random works, but usually you'll want something like:

block_y = (random() % m) + g;

Answer 4

Coincidentally, I wrote a random number generator in Objective-C a few weeks ago to help teach myself the language.

If you're using it, you can generate numbers between two values using the following messages on the Random class:

/* Inclusive low to exclusive high. */
- (int32_t)uniformIntFrom:(int32_t)low to:(int32_t)high;
- (uint32_t)uniformUnsignedFrom:(uint32_t)low to:(uint32_t)high;

/* Inclusive low to inclusive high. */
- (float)uniformFloatFrom:(float)low to:(float)high;
- (double)uniformDoubleFrom:(double)low to:(double)high;

/* Inclusive 0 to exclusive 1. */
- (float)uniformFloat;
- (double)uniformDouble;

If you are curious about how to generate a good random number between two values, this is the main portion of the source code for it:

uint32_t range = high - low;
uint32_t reject;
uint32_t n;

if (range < 2)
    return low;

/* Trick borrowed from OpenBSD's arc4random_uniform. Figure out
 * the size of the bias given the requested range, and throw away
 * numbers within the biased range.
 */

if (range > 0x80000000)
    reject = 1 + ~range;
else
    reject = ((max - (range * 2)) + 1) % range;

do {
    n = [engine next];
} while (n < reject);
return low + (n % range);

Where [engine next] gives me a number between 0 and max (which is usually UINT_MAX, i.e. 2³²-1).

Answer 5

Not sure how this translates in Obj-C but here's my version for C++. You want to normalize your random value before turning it into a specific range so the rand() stays uniform.

float randomHeight( float heightMin, float heightMax )
{
    float normRand = rand() / (float) RAND_MAX;
    float range = normRand * (heightMax - heightMin);
    return range + heightMin;
}

Note that rand() returns values from 0 to RAND_MAX so if you can find the equivalent in Obj-C, you can just replace these values with yours.

Answer 6

It sounds like what you want is just a 1D string of Perlin Noise. This is a very well documented problem and there are several examples available on the internet.