Re: A dungeon generator

At Fri, 7 Sep 2007 13:31:24 +0100,
Gerry Quinn wrote:

In article <slrnfdvu7j.ejr.news@xxxxxxxxxxxxxxxxxxxx>,
news@xxxxxxxxxxxx says...

I know only two methods of proving that a certain construct actually
exists. One is non-direct, and involves showing that from the object's
non-existence follows a contradiction -- hence the object must exist.

The second possible method is much simpler and straightforward -- it's
based on actually providing an algorithm by which you can construct the
object in question.

Your point being? I assume such an algorithm will take time to
construct; time that could be used instead, for example, to develop
actual game content.

For the record, I am not saying that a roguelike that sometimes takes
forever to generate maps is acceptable. I'm saying that time-unbound
algorithms are often excellent sub-components of algorithms that are
statistically or sometimes even provably time-bound.

My point is that both algorithms require time to design, and from my
own experience I know that the ones using "trial and error" in a random
way take a lot of time and effort to design and analyze properly. At
least for a programmer.

You see, to design and analyze an algorithm that constructs your level
map systematically (that is, without trial and error), you only need
the skills and knowledge that you already need for programming -- basic
"mechanical" imagination, ability to analyze every step, knowledge of
how to perform basic operations. Nothing fancy. In particular, you don't
usually need advanced knowledge about the theory of probability -- you
rarely even need to compute any probabilities at all.

If your algorithm is a "trial and error" one, computing the probabilities
is the first step of the analysis. Without it you cannot estimate the
running time of your algorithm, you can't tell if it will find solutions
every time it is run or how much "tries" to give it, etc. Computing of
these probabilities, derived from constraints that are not always clear,
is very laborious, not to mention that it requires some knowledge that is
not common among programmers.

You might think that I'm overemphasizing it. Obviously you never even
tried to analyze your "Method 2". Can you even do it? Incidentally, I
know how much work it requires, so maybe you could try and analyze a
greatly simplified case: instead of two-dimensional rooms, randomly place
one-dimensional sectors. Instead of placing seven of them, place only two.
Place the first one, and try to (randomly, with even distribution) place
the ends of the second one, trying until they are not overlapping. Can
you give me the formula for the probability of this process taking exactly
n steps? This is the basic information you need to decide whether the
constraints are not too tight. Then you can generalize it to seven
two-dimensional rooms. I'm sure that by the time you do it, you could have
written several good "non-trial-and-error" algorithms doing the same
thing.

In Poland we have a saying "wypędzać diabła szatanem", which basically
means "get rid of a devil by using satan", which is what you do using
the "simple" solution of trial and error: replacing a simple problem
with a difficult one that only looks simple because you are not familiar
with it.

--
Radomir `The Sheep' Dopieralski <http://sheep.art.pl>
() ascii ribbon campaign - against html e-mail
/\ <www.asciiribbon.org> - against proprietary attachments
.

Relevant Pages

  • Re: A dungeon generator
    ... way take a lot of time and effort to design and analyze properly. ... I don't think I have needed to compute any probabilities, ... running time of your algorithm, you can't tell if it will find solutions ... say in the above paragraph is completely irrelevant to map generation ...
    (rec.games.roguelike.development)
  • Re: Are DSP Processors losing out to ARMs?
    ... The lack of real understanding matters now, ... In 1970 it mattered that every programmer who wanted to ... well-known that quick sort is the algorithm of choise, ... limitations of memory sizes, as computers as often as not ...
    (comp.dsp)
  • Re: Is this all there is?
    ... (with the exception of HLA or Intel syntax code). ... assembly language source file. ... The algorithm is generally independent of the language, ... I can understand why a FORTRAN IV programmer would have ...
    (alt.lang.asm)
  • Re: EC-PRNG
    ... If using the LSB makes the algorithm easier to analyze, ... the use of affine coordinates for elliptic curve ...
    (sci.crypt)
  • Re: Which is faster?
    ... > Suppose the building of a hybrid car cause more pollution than ... Then suppose the saved pollution ... > Often programmer time is much more expensive than CPU time, ... I understand the point about finding a better algorithm. ...
    (comp.lang.c)