Skip to content

Instantly share code, notes, and snippets.

@munificent
Last active September 15, 2024 03:16
Show Gist options
  • Save munificent/b1bcd969063da3e6c298be070a22b604 to your computer and use it in GitHub Desktop.
Save munificent/b1bcd969063da3e6c298be070a22b604 to your computer and use it in GitHub Desktop.
A random dungeon generator that fits on a business card
#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;}
@aardappel
Copy link

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.

@bbqbaron
Copy link

bbqbaron commented Mar 5, 2019

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 😄 .

@jonoliver82
Copy link

Ported to Python

@PluieElectrique
Copy link

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

@obxfisherman
Copy link

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

Very cool concept, Thanks for sharing!

@aardappel
Copy link

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

@higsch
Copy link

higsch commented Mar 17, 2019

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

@somebody1234
Copy link

somebody1234 commented Mar 30, 2020

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.

@tinspin
Copy link

tinspin commented Aug 17, 2020

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.

@samme
Copy link

samme commented Apr 24, 2023

@paskozdilar
Copy link

paskozdilar commented Feb 18, 2024

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

@declann
Copy link

declann commented Feb 20, 2024

@fiurato74
Copy link

truly beautiful, thank you for sharing this work of art

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment