Re: A dungeon generator

In article <slrnfe2rfa.s08.news@xxxxxxxxxxxxxxxxxxxx>,
news@xxxxxxxxxxxx says...
At Fri, 7 Sep 2007 14:04:22 +0100,
Gerry Quinn wrote:

Yes, and many of the best ways of doing that include time-unbound sub-
algorithms that can fall back to safe territory if they fail too many
times.

If that is all you are saying (I see a hint of it above) I don't
disagree. It is what I have been saying from the start when I have
talked about relaxation of constraints, and/or time-indeterminate
solutions that are statistically acceptable.

That's not all. In addition, I'm trying to argue that this approach,
although often gives unique and interesting results that would be hard
to achieve in other ways, is incredibly costly for the programmer, both
in development time and in maintenance costs.

No it is not. I use it, so I know.

1. You need to analyze your algorith every time the constraints change.
If the constraints change randomly or as a result of how the game is
played, you need to analyze all possible combinations. This is very
laborious, as you can see for yourself by solving the little exercise
I mentioned in my other recent post in this thread.

You exercise might be of interest on rec.puzzles, but it is a pointless
academisation of a useless simplified version of the common problem in
roguelikes of placing a number of rooms in a given region. This
problem is solved in almost every roguelike, and it is solved in many
different ways, *including* the two contrasting methods I described.

If your constraints change randomly, they are not the actual
constraints, so that is a red herring. In any case, suppose you have
an algorithm that provably works for seven rooms, and the constraints
randomly change so that five million rooms are requested. Five million
rooms will not fit in the map, so your algorithm will fail. The
constraint-relaxing random placement algorithm, by contrast, will try
to reduce the number of rooms, and will eventually produce a map!
Because it accepts the possibility of failure, it can deal with this
situation.

2. You need to program a loop and a trial-counting mechanism practically
around every block that generates something randomly -- otherwise the
some value that was randomly picked outside the loop might be preventing
the loop from finishing. In addition, you must guarantee that the code can
be repeated safely. This is easier in some languages and programming
styles than in others. You need to watch out and not lazily skip any of
them -- one more opportunity to shoot yourself in the foot.

It should be easy in any language that is useful for writing
roguelikes. Anyway, this kind of defensive programming is something I
have always advocated for roguelikes. Since they tend to include
complex interactions that cannot practically be proved correct or fully
tested, they should be able to fail gracefuly without disrupting
gameplay.

3. If the constraints are not completely random, but instead depend on how
the game is played, the players can find a way to always get the
"fallback". If it's advantageus for them in any way, they *will*.

This is not the case. Even if the players can affect some of the
constraints, which is rare except in the case of them choosing whether
to go to one zone or another in the game, there is no reason why the
fallback should be accessible. The fallback is something that should
never happen. If you still worry about that, make the fallback
undesirable, e.g. a level with monsters but no items.

4. You don't have a direct control on the number and probability of
elements that get generated. If you did the analyzis properly, you
can anticipate the changes in probabilities that changing the number of
tries brings, but you still can't add a "half" of a trial to get exactly
the probability you want (and yes, the steps between them can be large).

I don't know what you are saying here, to be honest.

5. You seem to be gliding over it, but you *still* need your fallback
algorithm, so the trial-and-error didn't save you any work or made you
write less patentially-buggy code.

No, because the ultimate fallback is something simple like an empty
level, or perhaps a level generated from a list of seeds known to be
valid - all it needs to do is prevent the game from failing. In
practice, in a properly written program it will never happen. In Lair,
for example, the large room used as the ultimate fallback is the first
thing generated on any level anyway, so it was already coded!

6. Because of all that, the code is very hard to read and document
properly. You usually can't really use mathematical notation inside
comments to describe what you are doing and how it impacts the results.
Even if you use plain English, you are still using advanced concepts and
obscure vocabulary -- because there are no plain English words for these
concepts.

I disagree. The methodology may be simple or complicated, and thus
easier or harder to grasp, but there is really no reason why it will be
intrinsically difficult, or why there should be mathematical notation.
YOU are the one bringing mathematics into it!

I fail to see what is hard to understand about the following excerpt
from Lair:

int nTries = 50;
// if it fails after 50 tries it will return false
bool emptyMap = false;
// did it resort to empty map?
for ( int iTry = 0; iTry < nTries; iTry++ )
// etc.

7. It's inefficient.

In terms of what? CPU? Brainpower? Programming time? Map elegance?
Map variety? Map generation on the target machine in Lair is so fast
as to be unnoticeable.

Which is generally a topic for a Phd thesis or several of them and is
a subject of ongoing research of mathematicians all over the world. Plus,
obviously you don't want to go through all the computations and proofs
for every new constraint you add.

Dude, *you* are the one who is talking about doing a load of pointless
computations and proofs. This is trivial stuff, not rocket science.

They are required to, as you said it "do it right". Other wise you can
only hope to "get it right this time" by coincidence (and you will never
be sure).

I clearly have a different definition of 'doing it right' than you. I
have, however produced a pretty bug-free roguelike. I haven't played
yours but I assume it is also pretty bug free. If so we have
presumably both 'done it right' albeit in different ways.

For example, suppose you know you want every level to have at least two
rooms, but for a particular level you'd like to have a seven. Just
start generating maps for that level. If it fails to generate a map
with seven rooms after a hundred tries, try to generate one with 6
rooms, then after a hundred more fails, five rooms, etc. If it fails
on two, just give it a standard map.

Now load that level a few dozen times, and if all of them have five to
seven rooms and none of them took more than a second to generate, your
job is done. No Phd thesis, no mathematical research, no proofs, just
a stochastic map generation algorithm coded quickly and easily.

That's not how computers work in my world :)

Well, that's how they work in mine.

In my game Lair, most levels are built based on templates that are used
as the basis of locally random maps with an overall structure derived
from the template; each level has 16 possible starting templates. The
map generation process can fail on any given attempt, and for some
templates it happens more than others. I think for some templates it
may often happen up to ten times, though I'm not really sure. After 50
fails on any template, it will choose a new template at random.
Conceivably (though very unlikely IMO) there are templates included
that will never generate a valid map. I've never gone to the trouble
of formally testing this.

So it saves your work... how exactly? You have written a lot of content
for your game and now you *suspect* that part of it is actually never
used. And remeber, data entry is the *hard* part of writing a roguelike :)

No, I said it is conceivable but very unlikely that one or more
templates may never generate maps. These templates take about 2
minutes to create. They are my solution to the problem of creating
slightly themed structural elements (e.g. store-rooms on one level)
combined with semi-random cavern-type maps. [A downside is that 16 per
level is not really enough, because when you start in a structured area
you will eventually come to recognise it, even when the unstructured
parts are different. You wouldn't know the exact map, but you would
know something about it, and which direction the exit is. I should
have about 64 per level, with many identical structured areas appearing
on different maps.]

"Data entry (to be precise, content creation) is the hard part" is a
useful adage, but not all content is created equal. In this case I
chose manual content creation ahead of algorithmic because I felt it
was the easier way to achieve something like the result I wanted.
[With only seven levels, an additional constraint was that the exit
must be a long way from the starting point.]

It doesn't matter! I know that there are enough statistically valid
templates that the game will always generate a map for each level.

So you are giving up control over how your code works. A little here,
a little there. If you use such algorithms freely and without enough care,
soon your pet project will become a wild beast and you will have to kill
it.

I am the master, and my code knows it! I do not have to keep it semi-
throttled on a leash!

My code is actually pretty well-behaved, and has to be. Because of the
punishing nature of roguelikes in which there is no natural health or
mana regeneration, Lair is purposely less random than most (another
reason for level templates: I place coloured dots where I want boss
monsters, groups of average monsters etc. in a given template, rather
than rely on the RNG to disperse them fairly).

- Gerry Quinn
--
Lair of the Demon Ape
http://indigo.ie/~gerryq/lair/lair.htm
.

Relevant Pages

  • Re: A dungeon generator
    ... then it automatically turns in the former kind of algorithm. ... If it fails to generate a map ... rooms, then after a hundred more fails, five rooms, etc. ... each level has 16 possible starting templates. ...
    (rec.games.roguelike.development)
  • Re: A dungeon generator
    ... then it automatically turns in the former kind of algorithm. ... we want a valid level map *every time* we call ... rooms, then after a hundred more fails, five rooms, etc. ... most levels are built based on templates that are used ...
    (rec.games.roguelike.development)
  • Re: one sentence proof of 4 Color Mapping Problem; direct method
    ... for you to determine whether you can color this map with THREE ... So an algorithm for this machine would look ... building the algorithm in P to solve the NP-complete problems, ... Perhaps the equivalency is the idea that Eucl geom is what is ...
    (sci.math)
  • A Random Town Generation Algorithm
    ... I have implemented a random town generation algorithm algorithm. ... Pick a random point close to the centre of the map. ... And do the same for each of the new rectangles created by this until you've reached a minimum size. ... Ideally all these new created subdivisions should be stored in some list. ...
    (rec.games.roguelike.development)
  • Re: Precise Permissive Field of View: Request for comments
    ... that convinced me to use it as a default FOV algorithm in RoguelikeLib:) ... The interface is not yet very swapable, I will work on it with a new version. ... map data structure, it should have a map interface (not necessarily ...
    (rec.games.roguelike.development)