Send Mail To:Steve Register

Populating The Dungeon Of Items & NPC's - Stuart George.
This article was originally written for Darren Hebden's RLNews

By Stuart George :: [entropy@ihug.com.au] :: 3may99

I have to say up front, I have not looked in depth
(if at all) at how other rogue likes approach this task.
So my methods are probably not as fast or good as ones
tried and tested in code like nethack + angband for the
past N years they have been using it ;)

Quite often one of the first tasks in a rogue like
is creating the mazes... Once you have created
a working maze generation routine you have to fill
it, both with items, traps, monsters, stairs, etc.

Kitting out your dungeon can be as hard or as easy
as you like, but a lot of it has to do with how you
generated your maze.

I'll discuss here how I've gone about doing it.

First I'll discuss how NOT to do it, I saw this example
only once (in a quite basic "in development" game)...
The dungeon was hewn from a static 128x128 grid
and for placement of objects, a random position of
x=rnd(128), y=rnd(128) was taken for every object
wanting to be placed on the map, this x.y was then
tested against the grid to see if it was a floor tile,
if so was placed, and if not was repeatedly calling for
random numbers for x.y and testing them all over the grid.

Needless to say, with lots of objects and a small dungeon, this
could make the computer test locations for days until it got a

That is how NOT to do it, basically its a poor mans algorithm.
(But as someone pointed out, its easy to do things this way
and it does indeed work if you maze fills most of the confines
of your 'grid')

When I generate the maze, i store in a list all the
rooms created.  Hallways are just "skinny" rooms in my
view, so they all get put on the list.

This list is quite basic, its a linked list and contains
the x1.y1-x2.y2 and a flag of every object and nothing else.
the flag is just set when its wider or longer than 1
(ie flag is set when its not a "hall"), if you have to refer
to the list often its easier to test a flag than to test
x2-x1 + y2-y1 for every object..

When I want to add say, stairs up, i just randomly pick 
an object from my list, then once you have your "room"
randomly pick an x.y within that room  y=rnd(y2)+y1, x=rnd(x2)+x1
and place the object. repeat as necessary.

You can check for overlapping if you wish or simply stack items
in a list.

Since hallways outnumber rooms by a great number, its nice to
not always have everything generated in a hallway, thats why
the flag is for, so when objects from the list are selected,
you can give a greater chance to gen something in a room than
in a hallway...

You could also store two lists, one for "rooms" and one for "halls".

My dungeons are created entirely by the RNG, so when i save/load
a level I only need take note of the RNG seed before creation
starts, since the same seed produces the same level, the object
list gets rebuilt and thus you don't have to store that list.

You _do_ have to save the x.y positions of static things, ala
traps (moving bear pits?) and stairs. monsters move (for the most
part) so if they are not in the same spot, you could say
they wandered about ;), and items, well they got picked
up and moved and dropped ;).  But these are weak excuses for
cutting code really... ^_^

When going from 1 level to another you can dump the object list
for the same reasons as the load/save given above.

This is of course, very simple and does not take into account
someone with a digging wand adding a new corridor to your dungeon
(since its user created, it wont be created with the RNG seed).
Of course it would be easy to add the newly created portions
to a list, stored with the RNG dungeon seed, etc.

I find this method quite good, its quick and easy to "spawn"
monsters with this method..

The one thing I thought I should mention is the fact that my
"rooms" and "hallways" are not connected. doors are placed
in between as "connections" but they not connected on creation
by "touching" each other, and thus doorways don't show up on my
object list. (good or bad I don't know, but I'm very happy
with my dun-gen routine, it also just means nothing will
be placed over the top of a doorway)
Copyright 2001 Steve Register.