Author Topic: RNG theory question  (Read 15842 times)

Krice

  • (Banned)
  • Rogueliker
  • ***
  • Posts: 2316
  • Karma: +0/-2
    • View Profile
    • Email
RNG theory question
« on: May 06, 2010, 02:56:03 PM »
Let's say I'm getting random locations for rooms. Is it possible to have two exactly same locations for two or more rooms? It looks like basic rand() is giving a set of numbers that don't produce two matching locations, but I'm not sure about this. It would be nice to know, because two rooms can't have same locations (stairs are placed at room center). Is it better to test previous rooms for possible equal location?

mariodonick

  • Rogueliker
  • ***
  • Posts: 296
  • Karma: +0/-0
    • View Profile
    • LambdaRogue .:. roguelike RPG
Re: RNG theory question
« Reply #1 on: May 06, 2010, 03:27:48 PM »
I can't talk for C++, but at least the random() function in Free Pascal sometimes produces the same value in a short time.

So,

x[n] := random(100);
y[n] := random(100);

could produce

x[1] = 15
y[1] = 34

x[2] = 20
y[2] = 10

and

x[3] = 15
y[3] = 18

Thus, if I used these values as upper left corner of a room, two rooms would overlap. So I had to do a separate check.

But perhaps C++ does it a different way.
https://mariodonick.itch.io/lambdarogue-the-book-of-stars
-- LR: The Book of Stars graphical roguelike RPG

amjh

  • Newcomer
  • Posts: 6
  • Karma: +0/-0
    • View Profile
Re: RNG theory question
« Reply #2 on: May 06, 2010, 03:36:59 PM »
Well, if the random number generator wouldn't sometimes repeat itself, it would eventually run out of numbers to generate. Also that wouldn't be that random, since it would have previous numbers visibly affect results.
So, you will eventually get set of maching locations.

mariodonick

  • Rogueliker
  • ***
  • Posts: 296
  • Karma: +0/-0
    • View Profile
    • LambdaRogue .:. roguelike RPG
Re: RNG theory question
« Reply #3 on: May 06, 2010, 04:49:39 PM »
Quote
Well, if the random number generator wouldn't sometimes repeat itself, it would eventually run out of numbers to generate. Also that wouldn't be that random, since it would have previous numbers visibly affect results.

Exactly.
https://mariodonick.itch.io/lambdarogue-the-book-of-stars
-- LR: The Book of Stars graphical roguelike RPG

Krice

  • (Banned)
  • Rogueliker
  • ***
  • Posts: 2316
  • Karma: +0/-2
    • View Profile
    • Email
Re: RNG theory question
« Reply #4 on: May 06, 2010, 08:09:44 PM »
Actually it should be easy to test this by generating pixels on screen and test overlapping pixels, but I'm going to try it tomorrow.. Anyway, it could be wiser just check previous locations for match than trust the rng.

Edit: yes, it does produce same locations, but quite rarely. From 5000 points only two or three were a match.
« Last Edit: May 07, 2010, 10:55:16 AM by Krice »

roguedjack

  • Rogueliker
  • ***
  • Posts: 70
  • Karma: +0/-0
    • View Profile
    • Rogue Survivor blog
    • Email
Re: RNG theory question
« Reply #5 on: May 07, 2010, 01:08:27 PM »
amjh is right.

If you want to be 100% sure to never pick the same location twice you could try an algorithm like this:

  • 1. Generate a list of all locations. Order doesn't matter.
  • 2. When you want one:
  • 2.1 Pick one at random from the list (pick an index in the list with your usual rng).
  • 2.2 Remove it from the list.
  • 3. When you free a location, put it back in the list.

I use a similar algorithm when I want to pick a random choice from a set of possibilities.
The only drawback is having a quite large list for large locations.
But as with most algorithms, you trade memory vs performance.

...But sometimes I just use the brute-force loop "roll rng until it gives a good answer"  :D

AgingMinotaur

  • Rogueliker
  • ***
  • Posts: 805
  • Karma: +2/-0
  • Original Discriminating Buffalo Man
    • View Profile
    • Land of Strangers
Re: RNG theory question
« Reply #6 on: May 07, 2010, 06:15:31 PM »
I think Angband starts by dividing up the map in N square sectors, digging them out one by one. Something like roguedjack said. The original Rogue certainly sports maps that are divided into nine sectors, as can clearly be seen from a few play-throughs. I just brute-force in Squirm, trying to circumvent too much pussyfooting around by letting the program "remember" difficult spots. Eg.: "if putting a northbound corridor from room A fails, never try that again."

In any case, you shouldn't listen to me, as my algorithms are all a bit on the slow and messy side ;)

As always,
Minotauros
This matir, as laborintus, Dedalus hous, hath many halkes and hurnes ... wyndynges and wrynkelynges.