https://gist.github.com/munificent/b1bcd969063da3e6c298be070a22b604

Skip to content
 
[                    ]
All gists Back to GitHub Sign in Sign up
 
Sign in Sign up
You signed in with another tab or window. Reload to refresh your
session. You signed out in another tab or window. Reload to refresh
your session. You switched accounts on another tab or window. Reload
to refresh your session. Dismiss alert
{{ message }}

Instantly share code, notes, and snippets.

@munificent

munificent/generate.c

Last active February 18, 2024 22:39

  * Star 628 You must be signed in to star a gist
  * Fork 37 You must be signed in to fork a gist

Star You must be signed in to star a gist
Code Revisions 2 Stars 628 Forks 37
Embed

  * Embed Embed this gist in your website.
  * Share Copy sharable link for this gist.
  * Clone via HTTPS Clone using the web URL.
  * 
  * Learn more about clone URLs

Clone this repository at <script src="https://gist.github.com
/munificent/b1bcd969063da3e6c298be070a22b604.js"></script&
gt;
[<script src="https:/]
Save munificent/b1bcd969063da3e6c298be070a22b604 to your computer and
use it in GitHub Desktop.
Download ZIP
A random dungeon generator that fits on a business card
Raw
generate.c
This file contains bidirectional Unicode text that may be interpreted
or compiled differently than what appears below. To review, open the
file in an editor that reveals hidden Unicode characters. Learn more
about bidirectional Unicode characters
Show hidden characters

 #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;}

Load earlier comments...
Copy link

ghost commented Mar 5, 2019

Cool  pure C forever 

Sorry, something went wrong.

@thebigG
Copy link

thebigG commented Mar 5, 2019

This is so cool! Thanks for writing this!

screen shot 2019-03-05 at 7 57 49 am

Sorry, something went wrong.

@deepdeepdot
Copy link

deepdeepdot commented Mar 5, 2019

Truly amazing piece of art 

Sorry, something went wrong.

@xyproto
Copy link

xyproto commented Mar 5, 2019

Another way of building and running it, using cxx:

businesscard

Sorry, something went wrong.

@yujunz
Copy link

yujunz commented Mar 5, 2019

Cool

Sorry, something went wrong.

@Joker-vD
Copy link

Joker-vD commented Mar 5, 2019

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.

Sorry, something went wrong.

@Tombert
Copy link

Tombert commented Mar 5, 2019

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.

Sorry, something went wrong.

@ctsrc
Copy link

ctsrc commented Mar 5, 2019

@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 :)

Sorry, something went wrong.

@ctsrc
Copy link

ctsrc commented Mar 5, 2019

@Joker-vD

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

Sorry, something went wrong.

@antimeme
Copy link

antimeme commented Mar 5, 2019

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;
}

Sorry, something went wrong.

@ydniw
Copy link

ydniw commented Mar 5, 2019

wicked!!!

Sorry, something went wrong.

@jesuschris
Copy link

jesuschris commented Mar 5, 2019

Nice work Bob! 

Sorry, something went wrong.

@johnmathews
Copy link

johnmathews commented Mar 5, 2019

flashbacks of s/angband!

Sorry, something went wrong.

@airstrike
Copy link

airstrike commented Mar 5, 2019

    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

Sorry, something went wrong.

@grownseed
Copy link

grownseed commented Mar 5, 2019 *
edited

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...$....#
  #..........$...#                                     ########    #.........#
  #..............#                                                 #..$......#
  #..............#                                                 #.........#
  ################                                                 ###########

Sorry, something went wrong.

@adam-arold
Copy link

adam-arold commented Mar 5, 2019

@Tombert did you have luck with the Racket version?

Sorry, something went wrong.

@ctsrc
Copy link

ctsrc commented Mar 5, 2019

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

Sorry, something went wrong.

@munificent
Copy link
Author

munificent commented Mar 5, 2019

@ctsrc nice catch!

Sorry, something went wrong.

@DoktorCranium
Copy link

DoktorCranium commented Mar 5, 2019

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

Sorry, something went wrong.

@aardappel
Copy link

aardappel commented Mar 5, 2019

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.

Sorry, something went wrong.

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

Sorry, something went wrong.

@jonoliver82
Copy link

jonoliver82 commented Mar 6, 2019

Ported to Python

Sorry, something went wrong.

@PluieElectrique
Copy link

PluieElectrique commented Mar 6, 2019

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

Sorry, something went wrong.

@obxfisherman
Copy link

obxfisherman commented Mar 6, 2019

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

Very cool concept, Thanks for sharing!

Sorry, something went wrong.

@aardappel
Copy link

aardappel commented Mar 6, 2019

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

Sorry, something went wrong.

@higsch
Copy link

higsch commented Mar 17, 2019

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

Sorry, something went wrong.

@somebody1234
Copy link

somebody1234 commented Mar 30, 2020 *
edited

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.

Sorry, something went wrong.

@tinspin
Copy link

tinspin commented Aug 17, 2020 *
edited

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.

Sorry, something went wrong.

@samme
Copy link

samme commented Apr 24, 2023

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

Sorry, something went wrong.

@paskozdilar
Copy link

paskozdilar commented Feb 18, 2024 *
edited

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

Sorry, something went wrong.

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

Footer

 (c) 2024 GitHub, Inc.

Footer navigation

  * Terms
  * Privacy
  * Security
  * Status
  * Docs
  * Contact
  * Manage cookies
  * Do not share my personal information

You can't perform that action at this time.