RNG theory question

[Krice]

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]

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.

[amjh]

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]

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.

[Krice]

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.

[roguedjack]

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" 

[AgingMinotaur]

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