Random placement

[katchow]

Ok, hope this doesn't sound stupid...

 

Let's say you want a game to start w/ an enemy placed at a random position, how do you make sure it falls within the playfield (160x100)? If I understand correctly, the "rand" number is 1-255, any way to keep within a certain range? Also, how do you keep your moveable sprite confined to the playable screen? I was just going to draw a playfield box w/ collision detection, but I rather not take up the space.

 

any help is appreciated

[RevEng]

The question isn't stupid at all!

 

In a normal programming environment, you'd just do something like val=(rand*160)/255

 

Since multiplication or division by a non-power of 2 is insanely expensive on a 6507 you have to kludge it...

 

1. You can test if the result is greater than your max, and regen the random number. The problem with this is you are intoducing random delays into your code.

 

2. Add it together in parts that are powers of 2. Ie. For for a max value out of 160 use 128+32, temp1=rand/2, temp2=rand/8, val=temp1+temp2

 

3. Create a lookup table that converts the range from 0-255 to 0-159 or whatever. IMO this is a waste of ROM space, unless you're doing this conversion a heck of a lot.

Edited September 24, 2009 by RevEng

[katchow]

The question isn't stupid at all!

 

In a normal programming environment, you'd just do something like val=(rand*160)/255

 

Since multiplication or division by a non-power of 2 is insanely expensive on a 6507 you have to kludge it...

 

1. You can test if the result is greater than your max, and regen the random number. The problem with this is you are intoducing random delays into your code.

 

2. Add it together in parts that are powers of 2. Ie. For for a max value out of 160 use 128+32, temp1=rand/2, temp2=rand/8, val=temp1+temp2

 

3. Create a lookup table that converts the range from 0-255 to 0-159 or whatever. IMO this is a waste of ROM space, unless you're doing this conversion a heck of a lot.

 

 

that's really cool. Now, I'm thinking of other things I can do w/ this as well. Thanks so much for your help

[SeaGtGruff]

2. Add it together in parts that are powers of 2. Ie. For for a max value out of 160 use 128+32, temp1=rand/2, temp2=rand/8, val=temp1+temp2

Huh, I never thought of that. It looks pretty cool, but I don't think it's quite that simple. Rather, I think there's a few things you'll need to keep in mind when using this trick.

 

First of all, the rand statement generates a "random" integer between 1 and 255, so there's no 0.

 

Second, if we take a number like 160 and split it up into 128+32, then do as your example showed, temp1 will be between 0 and 127, and temp2 will be between 0 and 31, therefore the resulting value will be between 0 and 158. You might want to add 1 to the result, to put it between 1 and 159, to essentially "maintain compatibility" with the "no 0" situation.

 

Third, the distribution won't be even. If you take a simple example like val=rand/n, where n is between 2 and 128, then you can a result between 0 and (256/n)-1, but you'll have n chances of getting a result between 1 and (256/n)-1, and n-1 chances of getting a result of 0.

 

Furthermore, if you split a number up into different powers of 2 and add them together, I think a graph of the probability is going to look like a pyramid, but I'm not certain of that-- and I think the more powers of 2 you have to use, the steeper the pyramid will be.

 

For example, with 128+32, there will be only 1 way to get a 0-- temp1=0 and temp2=0.

 

There will be 2 ways to get a 1-- temp1=1 and temp2=0; or temp1=0 and temp2=1.

 

There will be 3 ways to get a 2-- temp1=2 and temp2=0; temp1=1 and temp2=1; or temp1=0 and temp2=2.

 

You can see a pattern here-- N+1 ways to get an N. But I think the pyramid will level off to a platform near the middle, then drop off again, like a Mesoamerican pyramid. For example, there will be 32 ways to get a 31, but there will also be 32 ways to get a 32, 33, 34, 35, 36, etc. (because temp2 has only 32 possible values).

 

Taking it from the other end, there will be only 1 way to get a 158-- temp1=127 and temp2=31.

 

There will be 2 ways to get a 157-- temp1=127 and temp2=30; or temp1=126 and temp2=31.

 

There will be 3 ways to get a 156-- temp1=127 and temp2=29; temp1=126 and temp2=30; or temp1=125 and temp2=31.

 

This doesn't take into consideration the probability of getting a particular value for temp1 and temp2. For example, there's only 1 way to get a 0, as well as only 1 way to get a 158, but they won't have the same probabilities as each other-- the 0 will have a smaller probability than the 158.

 

Let me see if I can work this out...

 

Only 1 way to get a 0-- temp1=0 and temp2=0. For temp1=0, the probability is 1 out of 255. For temp2=0, the probability is 7 out of 255.

 

Only 1 way to get a 158-- temp1=127 and temp2=31. For temp1=127, the probability is 2 out of 255. For temp2=31, the probability is 8 out of 255.

 

The overall probabilities will depend on whether you're using the same rand to get temp1 and temp2, or are using two different rands-- in other words,

 

temp=rand : temp1=temp/2 : temp2=temp/8 : val=temp1+temp2

 

or

 

temp1=rand/2 : temp2=rand/8 : val=temp1+temp2

 

With the first method-- using a single rand value to get temp1 and temp2-- rand would have to be 1 for temp1 to be 0, and rand would have to be between 1 and 7 for temp2 to be 0, so for val to be 0, rand would have to be 1, hence the probability would be 1 out of 255. I guess you would take the smaller probability.

 

With the second method-- using two different rand values-- I guess you would multiply the probabilities to get 7 out of 65025, but I'm not sure.

 

If that's right, then for val=158 the probability would be 2 out of 255 the first way, or 16 out of 65025 the second way.

 

Michael

[RevEng]

No problem! Glad your wheels are turning.

 

[Edit - caught Michael's post after posting this... I suppose a lookup table is the only "perfect" way to go. Even then you run into some values being favoured by rounding errors.

 

Perhaps someone else has a better/easier suggestion]

Edited September 25, 2009 by RevEng

[SeaGtGruff]

I suppose a lookup table is the only "perfect" way to go. Even then you run into some values being favoured by rounding errors.

 

Perhaps someone else has a better/easier suggestion]

For most cases, there's no "perfect" solution, because you'll almost always have some variance in the distributions or probabilities.

 

A while back I created a batari Basic function to return a random value within a desired range. But it can take differing amounts of time to return a value, and the distributions aren't even, so you may or may not find it useful/desirable to use. Anyway, my approach was as follows:

 

Suppose the function is called "random" and takes two parameters-- the lowest and highest values in the desired range. For example, let's say you want a=random(5,26). The rand variable can never be 0, so let's start by changing the requested range of 5 through 26 so that it starts with 1. In other words, we subtract 4 to get a range of 1 through 22. Then, after we've gotten a number in that range, we'll add 4 back to it so it's between 5 and 26.

 

So rand is some number between 1 and 255. We store it in a temp variable. Then, as long as it's greater than 22 (the high end of our adjusted range), we keep reducing it by 22, until it's finally within the range of 1 through 22. Then we add 4 and return the result.

 

For example, if rand is 173, we get the following:

 

173 > 22? Yes. So 173 - 22 = 151.

151 > 22? Yes. So 151 - 22 = 129.

129 > 22? Yes. So 129 - 22 = 107.

107 > 22? Yes. So 107 - 22 = 85.

85 > 22? Yes. So 85 - 22 = 63.

63 > 22? Yes. So 63 - 22 = 41.

41 > 22? Yes. So 41 - 22 = 19.

19 > 22? No. So 19 + 4 = 23, our final result within the requested range of 5 through 26.

 

In this particular case, if we restate the possible values as 0 through 254, and restate the range as 0 through 21, you can see that this is essentially a mod(22) function-- or dividing by 22 and then using the remainder of 0 to 21. If we divide 254 by 22, we get 11 and change, so some of the values will have an 11-in-255 chance of occurring, and the rest will have a 12-in-255 chance of occurring:

 

1 to 22 => 1 to 22

23 to 44 => 1 to 22

45 to 66 => 1 to 22

67 to 88 => 1 to 22

89 to 110 => 1 to 22

111 to 132 => 1 to 22

133 to 154 => 1 to 22

155 to 176 => 1 to 22

177 to 198 => 1 to 22

199 to 220 => 1 to 22

221 to 242 => 1 to 22

243 to 255 => 1 to 13

 

So 1 to 13 have 12 chances of occurring, whereas 14 to 22 have 11 chances of occurring. Adding 4 to put things back within the desired range we get 5 to 17 (12 chances) versus 18 to 26 (11 chances).

 

Here's a link to the thread where I posted the routine:

 

http://www.atariage.com/forums/topic/103208-decided-to-play

 

Michael

 

Edit: Looking back over what I posted in that thread, I guess I didn't do it as described above, although it should work out the same-- except the function I posted looks like it can call rand more than once, and I think it's better to call rand only once each time.

Edited September 25, 2009 by SeaGtGruff

[+Random Terrain]

If your playfield isn't an empty box where the placement can be anywhere, you'll have a set of safe positions that you'll randomly choose from (similar to how dice work). It's Controlled Randomness.

[RevEng]

With the talk of distribution I was curious how the two methods would graph out for the case of a screen width of 160.

 

 

The first chart is just the rand() function mod 160. It's there just to show that the rand() in the libc I used had provided reasonably evenly distributed numbers.

 

The second chart is rand() mod 256 (to simulate picking a rand number from 0-255) mod 160.

 

The third chart is my rand() mod 128 + rand() mod 32. Its kinda pyramidy, just like Michael predicted, though I think its still fairly useful for the purpose of picking a random screen co-ordinate.

 

There's still the problem that bB uses a rand from 1-255. I'd personally just subtract the 1 from both rands and add one to the overall result, which would center the range on the screen. A couple pixels from the edges won't be missed.

[SeaGtGruff]

If you just keep getting a new rand until it falls within the desired range, the distribution will be perfectly even, as in your topmost graph. For example, if you want a random number between 1 and 160, the following will give you an even distribution:

 

get_rand

  a = rand
  if a > 160 then get_rand

Each value between 1 and 160 will occur exactly once before the "random" sequence starts to repeat itself, since you're just throwing away any values from 161 to 255.

 

If you use the 16-bit rand function, I think you'll get several "random" sequences before they start to repeat. I'm not sure what the figures are-- I think there will be 255 different sequences before they start to repeat? So the following will also give you an even distribution, but the results will appear to be much more random, since it will take a lot longer for the numbers to start repeating:

 

  dim rand16 = a

get_rand

  a = rand
  if a > 160 then get_rand

Now that I think about it, the main problem with using rand is that you'll typically be using it to get more than one random variable-- for example, a random player0x coordinate and a random player0y coordinate, as in the following code:

 

get_rand_player0x

  player0x = rand
  if player0x > 160 then get_rand_player0x

get_rand_player0y

  player0y = rand
  if player0y > 88 then get_rand_player0y

Some of the numbers that would have been returned for player0x will end up being used for player0y, and vice versa. Assuming (for simplicity) that you're using just the 8-bit rand function-- and depending on the specific ranges you're looking for, as well as the number of variables you're generating with rand-- it's possible that the overall sequence will repeat after 255 values, in which case some numbers will never occur for player0x, and others will never occur for player0y.

 

What would be most ideal is if we would let each variable have its own random sequence that's independent of the other variables. Fortunately, I think that should be easy to do if we "reseed" the rand function each time, as in the following example:

 

reinitialize

  player0x = 0 : player0y = 0

game_loop

  if player0x > 0 then rand = player0x

get_rand_player0x

  player0x = rand
  if player0x > 160 then get_rand_player0x

  if player0y > 0 then rand = player0y

get_rand_player0y

  player0y = rand
  if player0y > 88 then get_rand_player0y

  drawscreen
  goto game_loop

The statements where we set rand to one variable or another will "reseed" rand back to whatever its last value was in a particular sequence, such that the sequence of values for each variable should cycle independently of the other.

 

But I don't know about reseeding the 16-bit rand function. I presume we'd need to reseed both rand and rand16 for each variable to have its own independent sequence, which means (in this particular example) that we'd probably have to use two more variables for saving and reseeding rand16:

 

  dim rand16 = a
  dim player0x16 = b
  dim player0y16 = c

reinitialize

  player0x = 0 : player0y = 0

game_loop

  if player0x > 0 then rand = player0x : rand16 = player0x16

get_rand_player0x

  player0x = rand
  player0x16 = rand16
  if player0x > 160 then get_rand_player0x

  if player0y > 0 then rand = player0y : rand16 = player0y16

get_rand_player0y

  player0y = rand
  player0y16 = rand16
  if player0y > 88 then get_rand_player0y

  drawscreen
  goto game_loop

 

Michael

[Zufolek]

As a simple solution, here's a function a person could use:

 

function Rand

RandLoop
temp2=rand
if temp2 >= temp1 then RandLoop

return temp2
end

 

And you could use it like this:

 

player0x=Rand(160)

player0y=Rand(80)

 

It does have random delay and isn't very efficient, but may be handy for getting new games started.

[+batari]

Just a note - The 16-bit random number generator does not really mean you get a 16-bit random number, it means that you get about 2^16 different 8-bit numbers.

 

rand16 as a variable is not very random. While there are two bytes used to create each 8-bit random number, rand as a variable is actually a combination of the two bytes (one is bit-shifted one way, another is bit-shifted another way and possibly EOR'ed with a constant, then the two bytes are EOR'ed into one.) I have tested this method with random number evaluators and gotten excellent results. If you were to test rand16 by itself, you would get poor results.

 

That said, I think the best method for 0-160 might be to use a loop. You can evalute this loop for all 65535 combinations to see what the worst case is, and if it's not too bad I'd use that if an even distribution is desired.

 

For smaller numbers like 80, 40 or so on, maybe you can still use a loop, but AND off some of the upper bits first and evaluate the worst case.

[bogax]

 

 

With the first method-- using a single rand value to get temp1 and temp2-- rand would have to be 1 for temp1 to be 0, and rand would have to be between 1 and 7 for temp2 to be 0, so for val to be 0, rand would have to be 1, hence the probability would be 1 out of 255. I guess you would take the smaller probability.

.

.

 

If that's right, then for val=158 the probability would be 2 out of 255 the first way, or 16 out of 65025 the second way.

 

Michael

 

In the case of using a single rand it's just a hard coded multiplication

by .625 which scales 255 to 159.375, close to 160

 

Obviously you can't map 255 values to 160 values with out collisions.

 

In this case (approximately) every second value comes up

twice and the rest once for all 255 original values.

 

If you divide the 0-160 range in to groups of 2

consecutive values then any group is equally likely

(again, approximately).

 

If it were me, for this application, I'd just leave it

at that.

Does it really matter if it comes out to position 5 twice

in 255 and position 4 once in 255? (or that 160 is left

out)

 

I don't know how batari BASIC works.

 

A more serious problem IMO is if the fractional parts of

the partial products are truncated.

 

To get a nicer distribution you realy need 16 bits both

in the math and the random value. (but especially the math)

Edited September 28, 2009 by bogax

[RevEng]

In an ideal world, yes.

 

In a 6507 world, a multiplication (or a division) by a non-power-of-2 is horrendously costly in terms of time, and generally is avoided at all costs. Instead, 6507 coders use approximations, lookup tables, etc.

 

Hence all the gymnastics in this thread trying to find the ideal way to do it. (Though mostly the gymnastics are for fun. Any one of the posted methods would be good enough in most cases)

[+batari]

There is another alternative to random placement. In many cases, you do not really need to place an object every frame. Instead of doing fancy gymnastics or a loopback until you get a valid number, you can simply read one random number per frame and simply discard it if the number is not within the desired range and wait until the next frame. Provided the range is not too small, it could work just fine.

[bogax]

A little late replying here... (heh heh)

(came across this while Googling something)

 

Just for completeness, here's what I was talking about

 

in Bb

 

temp1=rand/2
temp1=(temp1/4/4+temp1)/4+temp1

 

which produces

 

.L00 ; temp1 = rand / 2

jsr randomize
lsr
STA temp1
.L01 ; temp1 = ( temp1 / 4 / 4 + temp1 ) / 4 + temp1

; complex statement detected
LDA temp1
lsr
lsr
lsr
lsr
CLC
ADC temp1
lsr
lsr
CLC
ADC temp1
STA temp1

 

in asm

 

jsr randomize
sta temp1
lsr
lsr
lsr
lsr
lsr
adc temp1
lsr
lsr
adc temp1
lsr
sta temp1

 

Well, not quite what I was talking about.

 

The Bb version mutiplies by .6328125

(1/2 + 1/8 + 1/128) and truncates the

partial products

 

The asm version multipies by .62890625

(1/2 + 1/8 + 1/256) and rounds the

partial products

 

 

 

In an ideal world, yes.

 

In a 6507 world, a multiplication (or a division) by a non-power-of-2 is horrendously costly in terms of time, and generally is avoided at all costs. Instead, 6507 coders use approximations, lookup tables, etc.

 

Hence all the gymnastics in this thread trying to find the ideal way to do it. (Though mostly the gymnastics are for fun. Any one of the posted methods would be good enough in most cases)

Edited September 1, 2012 by bogax

[+Gemintronic]

Here is my good enough solution for my Rogue-like game. "(rand&63) + 16" should give a coordinate value between 16 and 79. If it happens to place an object inside a wall I just call it again with a drawscreen to avoid going over.

 

warp_object
player0x = (rand&63) + 16
player0y = (rand&63) + 16
drawscreen
if collision(player0, playfield) then goto warp_object
return