A random dungeon generator that fits on a business card

generate.c

#include <time.h> //  Robert Nystrom
#include <stdio.h> // @munificentbob
#include <stdlib.h> //     for Ginny
#define  r return    //    2008-2019
#define  l(a, b, c, d) for (i y=a;y\
<b; y++) for (int x = c; x < d; x++)
typedef int i;const i H=40;const i W
=80;i m[40][80];i g(i x){r rand()%x;
}void cave(i s){i w=g(10)+5;i h=g(6)
+3;i t=g(W-w-2)+1;i u=g(H-h-2)+1;l(u
-1,u+h+2,t-1            ,t+w+2)if(m[
y][x]=='.'                  )r;i d=0
;i e,f        ;if(!s){l(      u-1,u+
h+2,t-    1,t+w+2){i s=x<t     ||x>t
+w;i    t=y<u||           y>    u+h;
if(s    ^t&&              m[      y]
[x    ]=='#'    ){d++;    if(g    (d
)     ==0)    e=x,f=y;    }}if    (d
==    0)r;    }l(u-1,u    +h+2    ,t
-1    ,t+w    +2){i s=    x< t    ||
x>    t+w;    i t= y<u    ||y>    u+
h;    m[y]      [x]= s    &&t?   '!'
:s^t    ?'#'                    :'.'
;}if    (d>0)m                  [f][
e]=g(2    )?'\'':'+';for(i j=0;j<(s?
1:g(6)        +1);j++)m[g(h)+u][g(w)
+t]=s?'@'                 :g(4) ==0?
'$':65+g(62)              ;}i main(i
argc, const char* argv[]) {srand((i)
time(NULL));l(0, H, 0,W)m[y][x]=' ';
for(i j=0;j<1000;j++)cave(j==0);l(0,
H,0,W) {i c=m[y][x]; putchar(c=='!'?
'#':c);if(x==W-1)printf("\n");}r 0;}

There's a part of me that wonders if I could make this shorter with a newer language. I might take a stab at writing this in Scheme tonight.

@Joker-vD

Really nice, I had some fun uncompressing and deobfuscating it — there are some nifty tricks in it! If anyone interested, there it is with some comments: https://gist.github.com/Joker-vD/cc5372a349559b9d1a3b220d5eaf2b01

It's amazing how much can be accomplished in so few lines of code.

I too deobfuscated and commented the code, as well as refactoring it a little bit. We have commented it very similarly :)

@Joker-vD

I forgot to put the link to mine, heh. Here it is: https://gist.github.com/ctsrc/fef3006e1d728bb7271cff0656eb0280#file-dungeon-c

I unwound the obfuscation before reading the other comments and discovering two other people did too. It would be fun to make this playable by accepting input, moving the player, moving the monsters and then displaying the map again.

Here's my entry for what it's worth. I didn't feel right about adding comments but I did rename most variables for clarity.

/* Robert Nystrom @munificentbob for Ginny 2008-2019 */
#include <time.h>
#include <stdio.h>
#include <stdlib.h>

const int HEIGHT = 40;
const int WIDTH  = 80;
int map[40][80];

const int PLAYER   = '@';
const int TREASURE = '$';
const int ROCK     = ' ';
const int CORNER   = '!';
const int WALL     = '#';
const int FLOOR    = '.';
const int DOOR1    = '+';
const int DOOR2    = '\'';

void
cave(int start)
{
  int width = (rand() % 10) + 5;
  int height = (rand() % 6) + 3;
  int left = (rand() % (WIDTH - width - 2)) + 1;
  int top = (rand() % (HEIGHT - height - 2)) + 1;

  for (int y = top - 1; y < top + height + 2; y++)
    for (int x = left - 1; x < left + width + 2; x++)
      if (map[y][x] == FLOOR)
        return;

  int doors = 0;
  int door_x, door_y;

  if (!start) {
    for (int y = top - 1; y < top + height + 2; y++)
      for (int x = left - 1; x < left + width + 2; x++) {
        int s = x < left || x > left + width;
        int t = y < top || y > top + height;
        if (s ^ t && map[y][x] == WALL) {
          doors++;
          if (rand() % doors == 0)
            door_x = x, door_y = y;
        }
      }

    if (doors == 0)
      return;
  }

  for (int y = top - 1; y < top + height + 2; y++)
    for (int x = left - 1; x < left + width + 2; x++) {
      int s = x < left || x > left + width;
      int t = y < top || y > top + height;
      map[y][x] = s && t ? CORNER : s ^ t ? WALL : FLOOR;
    }

  if (doors > 0)
    map[door_y][door_x] = (rand() % 2) ? DOOR2 : DOOR1;

  for (int j = 0; j < (start ? 1 : (rand() % 6) + 1); j++)
    map[(rand() % height) + top][(rand() % width) + left] =
      start ? PLAYER :
      (rand() % 4) == 0 ? TREASURE : 'A' + (rand() % 62);
}

int
main(int argc, const char* argv[])
{
  srand((int)time(NULL));
  for (int y = 0; y < HEIGHT; y++)
    for (int x = 0; x < WIDTH; x++)
      map[y][x] = ROCK;

  for (int j = 0; j < 1000; j++)
    cave(j == 0);

  for (int y = 0; y < HEIGHT; y++)
    for (int x = 0; x < WIDTH; x++) {
      int c = map[y][x];
      putchar(c == CORNER ? WALL : c);
      if (x == WIDTH - 1)
        printf("\n");
    }
  return 0;
}

wicked!!!

Nice work Bob! 🤙

flashbacks of s/angband!

Really nice, I had some fun uncompressing and deobfuscating it — there are some nifty tricks in it! If anyone interested, there it is with some comments: https://gist.github.com/Joker-vD/cc5372a349559b9d1a3b220d5eaf2b01

It's amazing how much can be accomplished in so few lines of code.

I backported this to work under MS Visual Studio 2008 which is all I have access to at work...

https://gist.github.com/airstrike/66e0152e75c3a81fd1496bfbf590105a

Obligatory javascript version:

(online version: https://jsfiddle.net/dfu7ws69/)

const HEIGHT = 40;
const WIDTH  = 80;
const map = [];

const PLAYER = '@';
const TREASURE = '$';
const ROCK = ' ';
const CORNER = '!';
const WALL = '#';
const FLOOR = '.';
const DOOR1 = '+';
const DOOR2 = '\'';

function rand (val) {
  return Math.floor(Math.random() * val);
}

function cave (start) {
  const width = rand(10) + 5;
  const height = rand(6) + 3;
  const left = rand(WIDTH - width - 2) + 1;
  const top = rand(HEIGHT - height - 2) + 1;

  for (let y = top - 1; y < top + height + 2; y++) {
    for (let x = left - 1; x < left + width + 2; x++) {
      if (map[y][x] === FLOOR)
        return;
    }
  }

  let doors = 0;
  let door_x;
  let door_y;

  if (!start) {
    for (let y = top - 1; y < top + height + 2; y++) {
      for (let x = left - 1; x < left + width + 2; x++) {
        let s = x < left || x > left + width;
        let t = y < top || y > top + height;
        if (s ^ t && map[y][x] === WALL) {
          doors++;
          if (rand(doors) === 0) {
            door_x = x;
            door_y = y;
          }
        }
      }
    }

    if (doors === 0) {
      return;
    }
  }

  for (let y = top - 1; y < top + height + 2; y++) {
    for (let x = left - 1; x < left + width + 2; x++) {
      let s = x < left || x > left + width;
      let t = y < top || y > top + height;
      map[y][x] = s && t ? CORNER : (s ^ t ? WALL : FLOOR);
    }
  }

  if (doors > 0) {
    map[door_y][door_x] = rand(2) ? DOOR2 : DOOR1;
  }

  for (let j = 0; j < (start ? 1 : rand(6) + 1); j++) {
    map[rand(height) + top][rand(width) + left] =
      start ? PLAYER :
      (rand(4) === 0 ? TREASURE : String.fromCharCode(rand(62) + 65));
  }
}

function generate () {
  for (let y = 0; y < HEIGHT; y++) {
    map[y] = [];
    for (let x = 0; x < WIDTH; x++) {
      map[y][x] = ROCK;
    }
  }

  for (let j = 0; j < 1000; j++) {
    cave(j === 0);
  }
}

generate();
console.log(map.map(r => r.map(c => c === CORNER ? WALL : c).join('')).join('\n'));

                                                             ###################
                                                             #......R...'..Q...#
                                                             #f.....$...#.$.c..#
             ########       ################   ###############...d......#s.....#
             #......#       #............$.#   #........S...##..........#......#
 ########### #......#       #I.............#   #............##########'#########
 #......N..# #......#       #..............#   #........O...#        #.`u....#  
 #.........# #....N.#       #..............#   #............#        #.......#  
 #.n.......# #......#       #..............#   #######'###############.......#  
 #.........# #......#       #..............#     #$.....# #..........+.......#  
 #.........# #......#       #..............#     #......# #........C.#########  
 ########'######+########## ######+#########     #T.....# #...m......#          
        #..........+......#    #..........#      #h.....# #..........#          
        #.....@....#$.OW..#    #......}...########......# #..........#          
        #..........#......#    #....$.....'......'$.....# #..........#          
        #..........#......#    #..........#......#......# #....O.....#          
        #..........########    #.t........#..$O..######## #..........#          
        #..........#           #..........#......#        #..........#          
        #########'##############..........#..n...#        ##########'##         
               #...............#..........#.Lw...#         #..........#         
   #############...^...........'..........#......#         #.L........#         
   #...........#.....$.....w...############......#         #........w.#         
   #...T....h..+...............#          #......#         #..........#         
   #.......f...#######'#########          ############     #.Q..B.....#         
   #...........# #{......#                   #.......#     #..........#         
   ############# #.......#                   #...d...#     #..........#         
                 #.......#         ######### #.......# #####'########'#######   
                 #.......#         #$......# #.......# #......#     #.......#   
########  ########'#####'###########.......# #..$....# #.Q....#     #.......#   
#...`C.#  #.....T..#   #.m.........'.......# #.......# #......#     #.......#   
#.$u...#  #N...~...#   #...........#.......####+########......#     #.......#   
#......#  #........#   #...........#.......'C$.........'......#     #.......#   
#......#  #........#   #........h..#.......#...........#......#     #.w.....#   
#......#  #........#   #...........#########..s........#......#     #.......#   
###+########'#######   #...........#       #...........#......#    #######+###  
  #..............#     #############       #############......#    #l...$....#  
  #..........$...#                                     ########    #.........#  
  #..............#                                                 #..$......#  
  #..............#                                                 #.........#  
  ################                                                 ###########

@Tombert did you have luck with the Racket version?

@munificent I've identified a bug. Player and other entities will never be placed on the rightmost column of the room floor, nor on the bottom-most row of the room floor. See https://gist.github.com/ctsrc/fef3006e1d728bb7271cff0656eb0280/3088bc0b79eae9ac29190e7dde012e3097cd1e16#file-dungeon-c-L177 which is my refactored version of your code. You will observe that my refactored code produces the exact same output as your code given the same seed. In my refactored version of your code the bug is explained at the line I linked to in this comment.

@ctsrc nice catch!

Works on OpenVMS 8.4 (Alpha) too with HP CC 7.3-009

Port to Lobster.

I used the language's vector operations and some additional refactoring to significantly cut down on the amount of "math" the original does.

// based on: https://gist.github.com/munificent/b1bcd969063da3e6c298be070a22b604
// via: https://gist.github.com/Joker-vD/cc5372a349559b9d1a3b220d5eaf2b01

include std
include vec
include color

let TILE_VOID        = ' '
let TILE_FLOOR       = '.'
let TILE_WALL        = '#'
let TILE_CORNER      = '!'
let TILE_OPEN_DOOR   = '\''
let TILE_CLOSED_DOOR = '+'
let TILE_PLAYER      = '@'

let fsize = xy { 80, 40 }
var field = mapxy(fsize): TILE_VOID

def cave(with_player):
    // csize/start are all inner dimensions/coordinates (w/o walls)
    let csize = xy_rndi(xy { 10, 6 }) + xy { 5, 3 }
    let start = xy_rndi(fsize - csize - 2) + 1

    // Cave iterator function that supplies wall/corner type.
    def in_box(f):
        forxy(csize + 2) v:
            v += start - 1
            let at_wall = (v < start) + (v >= start + csize)
            // We need to somehow record corners of all caves to check
            // for intersections later, so we use a special tile for it
            f(v, [ TILE_FLOOR, TILE_WALL, TILE_CORNER ][manhattan(at_wall)])

    // Check if the new cave (with walls) intersects with the interior of
    // any already existing cave. Touching walls/corners are okay
    in_box() v:
        if field[v] == TILE_FLOOR: return

    // Find a suitable place for a door
    var door_counter = 0
    var door_pos = xy_0i
    if not with_player:
        in_box() v, tile:
            // The door should not be created in the cave's corner or over
            // another door, or in another cave's corner. It's impossible
            // to make a cave without a door, because rnd always
            // returns 0.
            if tile == TILE_WALL and field[v] == TILE_WALL:
                door_counter++
                if rnd(door_counter) == 0: door_pos = v

        // If the cave's walls were made completely out of corners
        // and doors, don't make such a cave
        if door_counter == 0: return

    // The cave looks okay, let's draw it. First, draw the walls and the floor
    in_box() v, tile:
        field[v] = tile

    // Now draw the door.
    if door_counter > 0:
        field[door_pos] = if rnd(2): TILE_OPEN_DOOR else: TILE_CLOSED_DOOR

    if with_player:
        // A cave with the player has only the player inside it
        field[xy_rndi(csize) + start] = TILE_PLAYER
    else:
        // A cave without the player has some random mobs and/or gold in it;
        // 1d6 of entities total, 25% chance of gold, 75% of a mob.
        // Mob letters range from 'A' to '~', inclusive
        for rnd(6) + 1:
            field[xy_rndi(csize) + start] =
                if rnd(4) == 0: '$' else: 'A' + rnd('~' - 'A' + 1)

rnd_seed(int(seconds_elapsed() * 1000000))

// A call to cave() is not guaranteed to actually make a new cave,
// so call it many times
for(1000) j:
    cave(j == 0)

// Remove special corner type.
forxy(fsize) v:
    if field[v] ==  TILE_CORNER:
        field[v] = TILE_WALL

// Print the generated field
for(field) row:
    print unicode_to_string(row)

File: https://github.com/aardappel/lobster/blob/master/lobster/samples/dungeongen.lobster

The language has no syntax highlighting on github, so the above is better than nothing.

Clojure!

Tragically was doing this between meetings and from an early deobfuscation that I think may have had a quirk in it. Doors are chosen randomly from candidates, not moved with decreasing probability. Almost certainly other quirks 😄 .

Ported to Python

Took a stab at writing a version in J.

NB.           111...666
NB. 0123456789012...789
NB.  !#.'+@$ABCDE...|}~

'H W' =: 40 80

choose =: ] {~ [: ? [ # #@]
chooseidx =: $@] #: [ choose I.@,@]
boundary =: 4 : 'x {. (0 #~ ? x - y + 2) , 1 , (y # 2) , 1'
room =: (3 : 0)"0
  room =. 3 <. (H boundary 3 + ? 6) */ (W boundary 5 + ? 10)
  obj =. (y ~: 0) {:: 6 ; 7 + (+ [: ? 1 62 {~ ]) 0 ~: (>: ? 6) ?@# 4
  obj (<"1 (# obj) chooseidx room = 3) } room
)

hasone =: 1 (e. ,) ]
merge =: 4 : 0
  walls =. x *.&(2&=) y
  if. (-. hasone walls) +. hasone (x ~: 0) *. y = 3 do. y
  else. (4 + ? 2) (< , 1 chooseidx walls) } x + y * x = 0 end.
)

(' ##.''+@$' , a. {~ 65 + i. 62) {~ merge/ room |. i. 1000

Here's a Python version I was able to put together:
https://github.com/obxfisherman/connectedRooms

Very cool concept, Thanks for sharing!

@PluieElectrique wow, that's.. impressive. I have a love-desperation relationship with point free code ;)

Cool work, @obxfisherman! I send you a pull request with the correct formatting for the readme. ;)

Obligatory (badly-)golfed version:

#include <time.h> //  Robert Nystrom
#define l for(y=u-1; y< u+h+2; y++)\
for  (x = t - 1; x < t + w + 2; x++)
a,b,d,e,f,h,j,k,n,u,t,w,x,y;m[40][80
];g(x){return rand()%x;};cave(s){w=g
(10)+5;h=g(6)+3;t=g(80-w-2)+1;u=g(40
-h-2)+1;l if(m[y][x]==14)return;d=0;
if(!s){l{k=x<t||x>t+w;n=y<u||y>u+h ;
if(k^n&&m[y][x]==3){d++;if(!g(d))e=x
,f=y;}}if(!d)return;}l{a=x<t||x>t+w;
b=y<u||y>u+h;m[y][x]="/$ "[a+b]-33;}
if(d)m[f][e]=g(2)?7:11;for(j=0;j++<(
s?1:g(6)+1);)m[g(h)+u][g(w)+t]=s?32:
g(4)?33+g(62):4;}main(){srand(time(j
=0));for(;j<999;j++)cave(!j);for(y=0
;y<40;puts(""),y++)for(x=0;x<80;x++)
putchar(32 + (a = m[y][x])+4*!~a) ;}

Putting the @ back in left as an exercise for the reader because I'm too lazy.
Note that this relies heavily on UB as you can see from the screenful of warnings.

I found a bug where rooms are placed corner-to-corner and the door is not traversable:

..#
..'##
###..

Quick and dirty workaround (added - 1):

let s = x < left || x > left + width - 1;
let t = y < top || y > top + height - 1;

On @grownseed .js version.

CoffeeScript https://codepen.io/samme/pen/gOppRwV

Haha, I also de-obfuscated this code before coming here and seeing that other people did it too!
I've had a lot of fun in understanding how this piece of code works :)

Here's my version: https://gist.github.com/paskozdilar/48d7532733ccd11144bb43fed953c334

conversion to calculang formulas; visualizations with animated evolution: https://declann.observablehq.cloud/calculang-dx-pattern-exampling/dungeon/dungeon

or https://fosstodon.org/@calculang/111961605363861853

truly beautiful, thank you for sharing this work of art