Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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

share|improve this question
2  
Blakey87 is obviously beginning game development, if you are going to cast a vote to close, write a comment as to why, don't just vote to close because it is easy. –  AttackingHobo Jun 23 '11 at 23:13
1  
@AttackingHobo you are 100% correct and thanks, I come from a web based background (PHP), and this is my first time at trying to create a game, never used objective C before so everything is new to me, I dont normally ask for help but I thought why not –  blakey87 Jun 24 '11 at 7:56
1  
@AttackingHobo I voted to close because the question basically asks for a way to get a random value between a given min and max, which is really trivial, as long as you figure out how to get a random value on your system (which is not the question). I think beginners questions are ok, but there's got to be a threshold. Also all the answers given don't provide a solution in plain Objective-C, so no real help there (assuming the OP is really totally new to Objective-C) –  bummzack Jun 24 '11 at 10:33
1  
@bummzack: Generating a good random value between two numbers is actually something I see people do wrong very often; usually their results are either biased, or unnecessarily slow. –  user744 Jun 24 '11 at 18:12
2  
@bummzack: There are two problems and you're conflating them - first, generating good random numbers. That's really hard. Second, generating good random numbers between two given values. That's not really hard, but people still screw it up a lot. (Duck's answer is biased, CaseyB's answer confuses noise and randomness, MrXee's answer is unbiased but unnecessarily slow.) –  user744 Jun 25 '11 at 12:26
show 15 more comments

6 Answers 6

up vote -3 down vote accepted

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

share|improve this answer
    
I don't understand why this was chosen as the accepted answer. Why do you generate two random values? Also your ys1 (which is the start position of the new block) can become bigger or smaller than ye1 (it can even end up with the same size). Your example does something... but it doesn't position a block randomly, so that it's reachable by the player. –  bummzack Jun 24 '11 at 14:53
2  
@Gajet this seems incredibly complicated for what is a very simple idea..and your use of variable names is very confusing. I don't understand it. –  The Communist Duck Jun 24 '11 at 16:50
2  
Use variables that are descriptive, not cryptic. –  AttackingHobo Jun 24 '11 at 17:03
1  
"Always code as if the guy who ends up maintaining your code will be a violent psychopath who knows where you live." — Martin Golding –  Keeblebrox Jun 24 '11 at 17:11
1  
@Gajet, please check the revision history. It seems there was an edit collision and you might want to roll back the text, at least, to my version. –  mmyers Jun 27 '11 at 21:22
show 6 more comments

@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;
}
share|improve this answer
    
hope you understand what my answer were (and why it was accepted) now. –  Ali.S Jun 26 '11 at 20:54
add comment

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;

share|improve this answer
1  
random() % m produces non-uniform results. For a game it probably doesn't matter too much; on the other hand for a game the system rand()/random() functions may not be acceptable, and as long as you're going to deal with that you might as well do this part right too. –  user744 Jun 24 '11 at 18:30
1  
Since the OP is asking for Objective-C I'd suggest arc4random as the random function. –  bummzack Jun 24 '11 at 21:35
1  
-1 I think OP wanted both a random height off the ground AND a random block-height. Even if he didn't, this will not work - it will always produce a value between g and 2*g + jumpHeight. And even if you fixed it to be say what I assume you meant (m = previousBlockHeight + jumpHeight), it would still produce unsatisfying results - it would be heavily biased towards generating blocks near the ground, meaning the character would rarely be near the top of the screen. –  BlueRaja - Danny Pflughoeft Jun 24 '11 at 22:35
add comment

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. 232-1).

share|improve this answer
add comment

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.

share|improve this answer
    
Same problem as @Communist Duck's answer, will generate blocks that are heavily biased towards the bottom of the screen - being near the top of the screen would be rare, especially if playerJumpHeight is small. –  BlueRaja - Danny Pflughoeft Jun 24 '11 at 23:09
    
@BlueRaja-DannyPtflughoeft: he has some value for his height min value. it makes his answer diffrent from the one CommunistDuck gave and more similar to mine. just by changeing heightMin in each cycle he will get out of hook. –  Ali.S Jun 26 '11 at 20:28
add comment

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.

share|improve this answer
    
I don't think it is. It doesn't account for jumping accessibility at all. –  The Communist Duck Jun 23 '11 at 21:12
    
It gives you a value from 0.0 - 1.0 that varies in a nice distribution. All you need to do is map that so that 0.0 is 0.0 and 1.0 is your max height! –  CaseyB Jun 23 '11 at 21:48
1  
so does random(), but this person is obviously confused about how to do it. –  AttackingHobo Jun 23 '11 at 23:09
    
Perlin noise is a continuous, and thereby very non-random, distribution. All we need here is a random number between two values. –  user744 Jun 24 '11 at 18:31
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.