Page 1 of 1

Random Dungeon in DSB ("Dungeon Hack") [Abandoned]

Posted: Thu Mar 22, 2007 8:01 pm
by Joramun
Ok, when discussing with Parallax on Flashchat (i recommand FC to everyone it's funny and social)

An idea (yeah just one;) ) popped up in my mind :

What about using all the LUA capabilites to create a dungeon.lua that randomly generates a new dungeon everytime it is compiled ?

It would be like Dungeon Hack, except it would be so much better because it would be in DM :P

For the random, lua offers its own random number generator.

Here is how I would process :
define a "config.lua" file, where the player can set :
1/ the random seed (and set to -1 to have a random random seed)
2/ the difficulty / the difficulty slope
3/ the size of the dungeon
4/ several other parameters, like starting char level etc. Or maybe use a constant HoC level, and only change the champion levels ?

Then use these parameters in the following functions defined in other lua files :
- random level generator (influenced by size)
- random door, item & monster dispatcher

It looks very complicated BUT :
- all roguelike games do that. we/I can just take inspiration from them.

The main problems with the generators are :
A/ how to generate mostly "cool" levels ?
B/ how to prevent "stuck" situations ?
C/ how to balance the dungeon difficulty correctly ?
D/ how to allow additional stuff to be added by anyone without much effort ?

Posted: Thu Mar 22, 2007 8:06 pm
by beowuuf
We have a discussion thread about making interesting random dungeons ... it might be in the custom dungeon forum, or RTC/CSBwin

Posted: Thu Mar 22, 2007 8:08 pm
by Joramun
@Beo : sorry I will look for that. I would like this thread to stay here, though, because it is very DSB specific :)

Some proposed solutions :

A/ No definite solution. RTC has cool random level generators, but I have no idea of how they work (beside they seem to be "digger" type generators)
Other algorithm I know of are : wall-builders, life-game type, and fractal-type.
Wall builders are typically good for outdoors, life-game give astonishing results but are most useful for natural themes (caves and forests) and fractal well, give fractal results.

B/ To prevent stuck (door with no lock, pit in a dead-end), well the only choice are to be 1/ very clever 2/ put a lot of keys / way out, but making the dungeon easier.

C/ Well, for that, the answer should be TESTING !

D/ A clever usage of lua files could make mods very easy.

Posted: Thu Mar 22, 2007 8:14 pm
by beowuuf
Lol, this thread can stay here as it's to do with DSB, I just meant people ahve already voiced an opinion on the sunbest..umm, somewhere..that might be helpful :D

CSB also has a random layout generator program with seeds and rooms algorithmn too

Posted: Thu Mar 22, 2007 9:11 pm
by Joramun
I looked for it, but it seems it's very old and in the archive. I'll look into CSB's source for the generator then ;)

Posted: Thu Mar 22, 2007 9:13 pm
by Lunever
Probably in some parallel dimension Lord Chaos is right now setting up a dungeon that consists almost completely of gigglers toggling walls.

Posted: Fri Mar 23, 2007 3:35 pm
by zoom
What pops up in my mind whilst reading this:
the old dungeons and dragons system for dungeon creation.
you throw a dice and fill rooms with traps, monsters, nothing or special.
then with treasure , no treasure or trapped treasure
[Beo might know what I mean.]
there was some dice throwing involved in what exits a room has and there
were corridors, random (d4) for N,W, S,E
I let you know once I get this specific sheets out of my rpgchest.

Posted: Sat Mar 24, 2007 10:28 pm
by Joramun
Here are some proposition of features :

I will throw myself into coding, but only when I have some time and a clear idea of what I have to do. So if anyone want to discuss...

For the parameters of the generator, simply putting them in the startup.lua should be ok.

:arrow: CHARACTER GENERATION :
OPTION 1 :
1 to N characters are randomly generated and put into the party.
OPTION 2 :
N characters are generated and put into a Hall of Champion (level 0)

PARAMETERS :
AVERAGE SKILL LEVEL
SKILLS RANGE
ATTRIBUTE RANGE
STATS RANGE

:arrow: LEVEL GENERATION :
DESIGN :
SEVERAL LEVEL GENERATORS ( room&corridors, cave, etc. )
ITEM AND MONSTER DROPPER
CONNEXITY CHECKER

PARAMETERS :
SIZE (RANGE) X,Y,Z
TRAP DIFFICULTY ( traps, twists probability )
ENIGMAS DIFFICULTY ( distance between keys and doors, special puzzles etc. )

FOOD AMOUNT ( times min number of characters)
WATER AMOUNT ( probability of fountain per level
LIGHT AMOUNT ( probability of torches )
EQUIPMENT AMOUNT ( base weapons, base clothes / armors )

FLASK AMOUNT
MAGIC AMOUNT ( magic box etc. )
ARTIFACT AMOUNT (advanced / unique weapons amount )

MONSTER DIFFICULTY ( sets of monsters used )
MONSTER POPULATION ( monster set probability )

VICTORY CONDITION ( kill Boss(es) / reach End / collect Item(s) / bring Item(s) to End )

Posted: Sun Mar 25, 2007 1:02 pm
by ian_scho
FOOD AMOUNT ( times min number of characters)
Is food amount directly related to the number of characters? Will 4 characters take half the time to slay a monster compared to 2, or navegate through a dungeon twice as slowly? You will have a lot of time tinkering with these numbers to produce rough-guess-equations (empirical). Good luck!

Posted: Sun Mar 25, 2007 3:45 pm
by Joramun
Well, 4 characters eat 4 times as much as 1, roughly.

The goal is not "perfect balance", but rather not to have situation in which food is totally absent (unless food amoun is set to 0 :evil: ) and another one where the dungeon is crowded with bread and cheese ( no wine !?!? ) etc.

Concerning monsters that drop food, there's several solutions :
- edit their drop list
- define sets of monsters as a function of the number of players
- ignore the problem / add 1 to the monster difficulty level per player in the party

Posted: Mon Mar 26, 2007 12:06 pm
by Joramun
Hi, it's a bit of a lonely discussion, but I came up with an "algorithm".

First, about the way levels are drawn :

1/ Dungeon Hack uses a "wall builder" algorithm,
that always gives the square and repetitive feel
that this game has (and some other roguelikes).

2/ Cellular automatas give unpredictible result,
especially concerning connexion of dungeon.
Besides, they are more useful to make "caves"
or "wilds / forests" than dungeons.

3/ As you can guess, I prefer a "digger" algorithm.
But a digger algorithm only gives good results
if it does really complex connexity checking when
digging the corridors and rooms in the dungeon,
and same goes for laying out keys etc. Otherwise,
you'll end up with a linear key hunt like Dungeon Hack.

My idea is : generate an "abstract tree" of the dungeon.
The root of the tree is of course the starting point of the
party. If I keep the two options :
Joramund wrote::arrow: CHARACTER GENERATION :
OPTION 1 :
1 to N characters are randomly generated and put into the party.
OPTION 2 :
N characters are generated and put into a Hall of Champion (level 0)

Then the start is either :
1/ randomized level 0 or 2/ stairsdown to level 1
Since DSB allow "teleporting" staircases (ie non vertical),
option 2 is not a constraint on the layout of level 1.

Then the tree goes as follows :

Code: Select all

Node  ( Start  / Room / Corridor )
  |
Link   ( Blank tile / door with button / locked door* / Others* )
  |
  V
Node(s) ( Room / Corridor )

With some rules :
 1/ Start link is always a blank or door with button
 2/ Room only "fathers" corridors, N depending on the room size.
 3/ A corridor fathers at most one room (at the end) and N corridors,  
    where N depends of the length of the corridor.

Posted: Mon Mar 26, 2007 12:14 pm
by Joramun
Sorry if it's a kind of double post, but I don't like very long
posts, and I believe it will be more readable that way.

*Note that "locked door" includes : all kind of keys / triggers / puzzles to open doors + movable walls / closable pits.
*Others can be : stairs down, fake pit, fake wall.

Code: Select all

Each node has : 
 a/ a size
 b/ a type (octagonal_room, twisty_corridor etc.)
 c/ parent(s)
 d/ child(ren) (with their specified links)
And very important :
 e/ a hierarchy level
 f/ a key/button/puzzle stack

Additional rules :
  4/ Every time a "locked door" is chosen as a link, a puzzle / lock / button is chosen randomly as a trigger, and added on the stack of the parent room.
  5/ The childs of a node have the same hierarchy level as their parent except if the link is a locked door (or any other thing like movable wall or closable pit)
  6/ If a room has, say, 3 locked doors as links to its children,
      and it's hierarchy level is "a", then the children will have 
      hierarchy level "aa" "ab" and "ac" ( following me ? ) I don't
      expect a room / corridor to have more than 26 children, and
      if it happens, there are solutions (uppercases etc.)
  7/ Then arbitrary recurse keys / puzzles in the stack through nodes
      of the same hierarchy or higher in the alphabet ( "aa" > "abc" )
  8/ When digging the dungeon, instead of immediatly drawing blank
      tiles by 1, mark them with their hierarchy level. Allow corridors 
      and rooms to connect only if they have the exact same hierarchy
      level.
  9/ Clean up to draw the true dsb maps.
Then there are tricks to avoid "not enough room situations",
like forcing stairs down as a link, and monsters and objects
layout is not really a difficulty, except to balance. But do we
care about balance if the dungeon layout doesn't work :P

Posted: Thu Apr 05, 2007 7:36 pm
by Joramun
Well, I did some algorithm testing and some more thinking,
and I must confess that getting a reasonably good result as
in dungeon hack or roguelikes (NetHack / SLASHEM, Crawl,
Angband or ToME ...) is doable, but would already require a
lot of work, but getting something that would look and feel
like a DM dungeon would require A LOT more if even doable.
I'm not even talking about CSB style, which is undoable.
Besides, such a dungeon would only contain a finite number
of original puzzles, which is not very interesting.

Concluding remark : the idea of generating an abstract tree of
the dungeon is good, but it requires a lot of tweaking to actually
make the rooms and corridors fit in a definite space. That's why
you'd still have to dig them at the same time and make sure every
new room or corridor has enough spce to be created.

Posted: Thu Apr 05, 2007 9:13 pm
by ian_scho
It was a wonderful idea, though.
I'm sure with your experience of both LUA and DSB that you can put your knowledge to other works instead.

Posted: Thu Apr 05, 2007 9:28 pm
by Joramun
You guess well, I'm currently developping a dungeon.