Re: Agduria dungeon generation

On Jun 25, 3:18 pm, Jeff Lait <torespondisfut...@xxxxxxxxxxx> wrote:
You seem to be treating the RNG as the same sort of input as any of
the other dungeon generating parameters.  It isn't.
...
Depends entirely on the pseudo random number generator, how you seed
it, what its dimensionality is vs. the number of dependent calls you
make.
...
Thankfully we have access to modern RNGs, such as Mersenne Twister, to
minimize this issue. But we should keep in mind that they still have
finite dimensionality.

Truthfully I'm no expert on RNG's, but I am surprised to hear this
objection. I'm also not sure how it's relevant that they have finite
dimension -- of course they do, but so does the domain of n-bit
integers.

Let rand_chocie(n) return a number from 0..n-1

if ((rand_choice(5) == 0) && (rand_choice(5) == 0))
vs
if (rand_choice(25) == 0)

have very different behaviours.  The second is easy to verify any RNG
will eventually satisfy.  The first requires you to not merely check
to ensure the RNG will generate all possible numbers, but also all
possible pairs of numbers - this is a much larger space than the
first!

I'm going to assume that people who design RNG's understand that and
tailor the algorithm not only to cover as much of the number domain as
possible but also the n-length number sequence domain. If you can find
a widely-used RNG that will not satisfy rand(x) == 0 && rand(x) == 0
almost exactly as frequently as rand((x+1)^2 - 1) == 0 (watch the off-
by-one), I will be very surprised.

First you need to compute the probability to know it is remote
enough.  You could just compute it by generating the level X thousand
times, but the risk here is that probability might depend on some of
the inputs.  Ie, maybe it is 1 in 20 passes for normal levels, but
when you try and build the special Minotaur level it spikes to 1 in
5000 passes.
Second you need to ensure future changes to the
algorithm don't suddenly change that probability.  You could slip from
one failure in 44 years to one failure in a day (ie, a failure every
86 thousand games) without noticing it in simple testing
...
There is also the serious downside that while your generator failing
19 in 20 might be fine, you do not know how you'll build on this
code. There has already been a nice anecdote about what happened in
Angband where this sort of behaviour is rampant. Try & discard is
built on top of try and discard until you finally *do* get to a case
where it fails frequently or takes 25 minutes.

Or you need to test your future changes to the algorithm, or
understand how it works and what kind of changes will spike the
probabilities. Just treat those changes like any other bug. There are
plenty of cases where adding something to a NTAE level generator will
generate recurring but very rare errors. TAE isn't even obviously less
likely to produce this kind of rare error, I think, when you consider
the additional code complexity necessary to transition from TAE to
NTAE. No game programmer proves his code, and ordinary testing will
rarely catch all bugs in a program because some bugs will inevitably
manifest too infrequently with respect to the number of trials in
testing.

There is the rather serious downside that you don't have a clue of
*why* things are working.  You are just throwing more numbers at it
until it passes.  It is much better to stop, think about it, and
rephrase it in a deterministic manner.  If you have to use try &
repeat it should be restricted to very narrow domains where you can
guarantee the RNG will pass.  Ie, finding a point inside a circle by
rejecting points in the square that are outside the circle is
something any pRNG will pass in short order.

Programmers can always generate more reliable code when they
understand how the algorithm works than when they don't. So sure, if
you just assume that programmers do not understand their TAE
algorithms but do understand their NTAE algorithms, then on balance
the NTAE algorithms will be more reliable. But you're basically
begging the question -- it's a ridiculous assumption to make. The
comprehensibility of an algorithm is not obviously related to whether
it is TAE, at least in the direction you are assuming -- in fact, I
think the more compelling argument is that NTAE algorithms will
generally be more complex and therefore less comprehensible than TAE
algorithms if both generate the same output, in which case the TAE
algorithms will tend to have fewer bugs. I certainly understand
exactly how my TAE level generation algorithm works, and it works
reliably and quickly and generates far more interesting levels than
would any NTAE algorithm that I would have been able to code in the
same amount of time.

The only time a TAE fails categorically where a NTAE will succeed is
where there is a huge answer domain to choose from and only a tiny
number of successful solutions. I wouldn't advocate using a TAE
algorithm for calculating square roots to a thousand digits, for
example, even though one is obvious (pick a random thousand-digit
float, and if that number squared isn't the input number then repeat).
But then there are also situations where a NTAE will fail but a TAE
will succeed: any problem where it is cheap to check a solution and
solutions occupy a decent proportion of the answer space, but where
the space is so large and chaotic that it is hard or Hard to solve
directly. Using the wrong approach on either of these problems is
equally wrong-headed; it's not a point for either type of algorithm.
.

Relevant Pages

  • Re: Agduria dungeon generation
    ... stage of the algorithm and rise appropriate error, ... A NTAE generator doesn't have to have any ... NTAE will happily accept all valid inputs and RNG states and produce ...
    (rec.games.roguelike.development)
  • Re: Math.random
    ... That's not the only possible algorithm; ... without much difficulty implement a long shift-register generator; ... doublevalue or null/undefined/false for auto reseeding, ... I think 0 to 364 would be better; it goes well with zero-based arrays, ...
    (comp.lang.javascript)
  • Re: real random
    ... Feel free to post such an algorithm, ... it as a generator of a stream of numbers, ... You need a genuine source of entropy, ... By suggesting Fortuna (which gathers genuine entropy as it goes), ...
    (comp.lang.c)
  • Re: My cave room generator using wave functions
    ... for generating a generic cave room generator. ... algorithm, ... Randmonly choose n values to seed the wave function to be used. ... If the distance to the center is less than the radius of the room ...
    (rec.games.roguelike.development)
  • Re: rand() pattern in texture?
    ... > Phil Carmody wrote: ... > programming implementation of a given algorithm. ... > Looks to me like the period of the single lowest bit is 17, ... > as is the period of the generator itself. ...
    (sci.math)