Monday, March 21, 2011

Dungeon design journal #1: random dungeon generation

Would it enhance my productivity if I start a public design journal for my projects? That is one question I'm willing to answer by performing an experiment, and the other question is: will anyone be interested in reading these posts, or will they just clutter up Planet IF? The second is the more important one.

I am torn between two desires. On the one hand, I want to write a showcase for the ATTACK extension that is just good dungeon crawling fun. On the other hand, I want to write a piece that is important in terms of story or character or, well, anything artistic. I first considered some far-fetched ways of putting them together. I then told myself sternly that I had to make a choice. I have finally decided to just do both at the same time. Fail-proof strategy right? Anyway, here is the first design journal for what is going to be the unapologetically tactical game -- which I haven't named yet, so I'll call it Dungeon for now.

The basic idea was given to me by playing Desktop Dungeons: a small randomly generated adventure which should be playable in, say, 30 minutes (and certainly comes with permanent death and without undo); but winning the adventure will unlock new features that will be used the next time you play the game, while losing it will probably do nothing. So I am envisaging a game where as you win more games, more rooms, items, monsters and abilities will be added to the pool that is used for random generation, constantly expanding the tactical possibilities and depth of the game. (I would use an external file to keep track of what has been unlocked.)

Obviously, the framework for a combat system is already available: ATTACK. But I also need a framework for random dungeon generation. Once these two are in place, writing the game will "just" be a matter of adding content.

So, random dungeon generation! It seemed logical to start with generating the actual lay-out of the rooms first, and add everything else (including "doors") later. So I have spent today implementing an algorithm that creates a dungeon by:

  1. Putting a room called "Entrance Hall" at location (0,0,0). This room is now "placed".
  2. Choosing a random "placed" room, and trying to put a random "unplaced" room in one of the six cardinal directions (n,s,w,e,u,d). Create a two-way passage between the two rooms.
  3. Repeating step 2 until enough rooms have been placed.
  4. Checking whether there are pairs of adjacent rooms without a connection, and randomly making or not making a connection between them.

Steps 1-3 create a three-dimensional branch starting from Entrance Hall, and step 4 makes circular connections possible.

Now this is all very well, but we want more control over the lay-out of the dungeon. For instance, it would make no sense for a basement to be above ground level. We might want to group thematically related rooms together. And perhaps some rooms need to be dead ends, or passages between at least (or exactly) two other rooms. And so on. We need random generation, but we also want to be able to easily impose structure.

If there is one thing I have learned from writing ATTACK, it is that if you have open-ended design ideas ("I'm not sure what kinds of structure I might want to impose"), you should immediately build a system that is as general as possible. So I created three rulebooks:
  • The placement possible rules ask whether a certain room could be placed at the location currently under consideration. (The cellar, for instance, will say no if the z-coordinate of the location is not negative. It must be below street level.)
  • The placement scoring rules check how likely it is for a room to be placed at the location currently under consideration. (This can be used to make thematically related rooms more likely to be next to each other, for instance. I'm currently only using it to make the underground rooms more likely -- than other rooms -- to appear under ground.)
  • The additional placement rules run after a room has been placed, and can be used to implement further restrictions on the map. (The chasm, for instance, makes sure that it is always placed in a straight line between exactly two rooms -- serving as a barrier between them, except that I have not implemented any barrier. If the drawing room or the quartering room is placed, the other is immediately placed next to it. Okay, that is a pretty bad joke, but this is just a testing prototype.)
It all seems to work fine. One of the great joys of writing IF is the joy of programming: tackling a problem, and then seeing it work. I could generate stuff like this for the rest of the evening:
* down of Entrance Hall (0, 0, 0) is Kitchen (0, 0, -1).
* east of Entrance Hall (0, 0, 0) is Ballroom (0, 1, 0).
* west of Entrance Hall (0, 0, 0) is Quartering Room (0, -1, 0).
* Placed Drawing Room south of Quartering Room.
* east of Ballroom (0, 1, 0) is Alchemical Laboratory (0, 2, 0).
* down of Kitchen (0, 0, -1) is Basement (0, 0, -2).
* south of Alchemical Laboratory (0, 2, 0) is Chasm (-1, 2, 0).
* south of Chasm (-1, 2, 0) is Dark Shrine (-2, 2, 0).
* up of Dark Shrine (-2, 2, 0) is Chapel (-2, 2, 1).
* east of Basement (0, 0, -2) is Crypt (0, 1, -2).
* down of Ballroom (0, 1, 0) is Cellar (0, 1, -1).
* Adding connection between Entrance Hall and Ballroom.
* Adding connection between Entrance Hall and Quartering Room.
* Adding connection between Ballroom and Entrance Hall.
* Adding connection between Alchemical Laboratory and Ballroom.
* Adding connection between Chasm and Alchemical Laboratory.
* Adding connection between Drawing Room and Quartering Room.

Well, maybe not the rest of the evening, but it still so much fun to watch the  machine you have created run and work.

(The reader may notice that all connections added in this example already existed. This is because "if A is mapped north of B" compiles, but "if A is mapped way of B" apparently does not, even where "way" is a direction that varies. Which means I cannot easily test whether a connection already exists. Not a big problem right now, because there is nothing wrong with remapping things that are already mapped. But if someone knows how to formulate this if-statement in a way that does compile, that would be great.)

I also like this little command I put in to make exploration easier:
You have not yet explored:
 - the down exit of the Library (which lies north from here)
 - the south exit of the Chapel (where you currently are)
Although I know it will become a pain to rewrite it when I add locked doors, monsters, chasms, or anything else that might make going somewhere in a straight line not the most feasible thing. Also, I suspect that the command currently assumes total knowledge of the map. But there is an extension by Emily Short that I think I can change to suit my needs.


  1. Do it! I find Planet IF insufficiently cluttered. Or anyway, I only get bothered when a) a post winds up on it that fills ten screens, especially when it somehow manages to load an entire presentation of slides to Planet IF and b) someone does some software change that dumps a month's worth of their posts to Planet IF at once. And you only wind up with excerpts on Planet IF, so that's all good.

    Anyway, I'm intrinsically interested in this. I applaud doing a straight-up dungeon crawl. I've in fact been thinking of a post on a related topic, namely: I like my randomly-generated dungeon crawls to be unbalanced, specifically in terms of the powers of items you can find.

  2. Two out of two Matt Ws agree... :)

    I would like to both hear about this project in particular, and to follow design journals on Planet IF in general.

    Good luck with the project!

  3. As for technical question, looks like you want "If A is the room way of B"; the following compiles and even seems to work:

    Poking is an action applying to two visible things. Understand "poke [any room] [any direction]" as poking.
    Carry out poking:
    if the noun is the room the second noun from the location:
    say "Yes.";
    say "No."

    ("The room way of B" is in 6.14 of the documentation.)

  4. Yes, please! I always like hearing about other people's stuff - especially yours, and especially stuff that looks fun. Which this does.

  5. Thanks for your encouraging comments!

    Matt W(einer), would you care to elaborate on the goodness of unbalance? Also, that code works beautifully, thanks.

  6. would you care to elaborate on the goodness of unbalance?

    Yes!, sometime. Watch my blog -- I promise to write something more about it sometime after finally getting around to putting up my IF Demo.

    (Real short: It provides a more varied experience that I enjoy, in that sometimes you have to spend ages skulking around and sometimes you find Grayswandir in the first room and roll over everything; and also it provides a kind of autocorrection for player skill, in that very good players can try to win in the face of bad item drops and beginning players can keep trying until they wind up with something good enough that they can win with this. Obviously it shouldn't be so unbalanced that there's no skill at all to winning with the best items, but having some items be better than others has a role.)

    (I did find Grayswandir in the first room once. It was in a game I'd started up in wizard mode so I could check the message for artifact blast, for a comic I was writing.)