Re: Agduria dungeon generation

On Jun 25, 2:04 pm, Pender <penderpr...@xxxxxxxxx> wrote:
On Jun 22, 8:56 pm, Radomir Dopieralski <n...@xxxxxxxxxxxx> wrote:

The problem is that while with reasonably deterministic algorithm you can
usually easily calculate the constraints in advance, or check them at some
stage of the algorithm and rise appropriate error, it's much harder to do
that with highly stochastic algorithms.

Completely wrong. If you add in a host of dynamic interrelated
constraints where some possible combinations will never work, a non-
trial-and-error ("NTAE") generator will barf just as hard as a TAE
generator. You'll have to check either way.

True, but irrelevant. A NTAE generator doesn't have to have any
possible combinations that will never work. Indeed, a properly coded
NTAE will happily accept all valid inputs and RNG states and produce
dungeons. That is what makes it a NTAE.

While it seems to work, it's an equivalent of catching
and silently ignoring all errors in the program: a technique surely adding
a lot to the confidence of players, but often hiding real problems that
could have been easily solved, had the programmer be aware of them.

Same problem exists for NTAE approaches. What happens when you run
your NTAE generation algorithm with a bunch of inputs that make it
impossible to generate a valid level?

I can't really understand your arguement here. The "impossible" input
to the TAE generator is the RNG state. The "impossible" input to the
NTAE generator is something like asking it to make a -1,50 sized
dungeon. They are different classes of errors. The NTAE one is
clearly the fault of the caller - the invoker has passed incorrect
parameters. You cannot, however, in any seriousness say that the
caller of a TAE generator must verify the RNG is in a state that will
let it proceed?

You seem to be treating the RNG as the same sort of input as any of
the other dungeon generating parameters. It isn't.

The general comment -- "[t]he problem is that if it fails randomly,
you don't have a guarantee it will ever succeed" -- belies a
fundamental misunderstanding of probabilities.

I could easily say the same thing about this comment. Do you have
something, anything, to support this?

Sure. Suppose a valid level is generated only 1 time out of 20 but you
do 500 attempts before giving up and declaring failure. Suppose you
ran that algorithm once per second non-stop. Do you know how long it
would have to run before there was even a ONE PERCENT chance of even a
SINGLE failure?

Depends entirely on the pseudo random number generator, how you seed
it, what its dimensionality is vs. the number of dependent calls you
make.

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!

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.

Not good enough? Try running the calculations if your level is invalid
only 70% of the time. Try making 700 attempts before declaring
failure. Try generating levels once per minute instead of once per
second. Etc. Devoting even a single minute of programmer time to a
possibility this remote is nuts.

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

Not to mention that you will have to write the checks for connectivity
or whatever other properties you want to have anyways, so why not save
yourself some work and incorporate them into the algorithm from the start?

Because it's often easier -- often substantially easier -- to do it
with trial and error methods, and as I've said there are no downsides.

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.

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.
--
Jeff Lait
(POWDER: http://www.zincland.com/powder)
.

Relevant Pages

  • Re: Do RNGs have artificial intelligence?
    ... the answer is NO. RNG stands for "Random Number ... Generator". ... If there was some type of AI algorithm ... involved, it would not be a true RNG, as it would not be truly random. ...
    (rec.gambling.poker)
  • 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: Agduria dungeon generation
    ... Depends entirely on the pseudo random number generator, ... algorithm don't suddenly change that probability. ... TAE isn't even obviously less ... algorithms but do understand their NTAE algorithms, ...
    (rec.games.roguelike.development)
  • Re: Agduria dungeon generation
    ... how and why a trial-and-error dungeon generator can fail. ... generator -- I have generated probably hundreds of thousands of maps ... if the NTAE generator had to be more complex to generate the ... same richness that comes with a decent TAE method. ...
    (rec.games.roguelike.development)