A random dungeon generator that fits on a business card

https://twitter.com/munificentbob/status/1101903466111283200

by munificent • 7 years ago

142 64 7 years ago

msie• 7 years ago

I like the old-school notion that I can just copy and paste it into vi and then compile with gcc. It just works. No complicated installation of a runtime or dependencies.

jdmoreira• 7 years ago

For me this is the appeal of C and I feel it as well. Any unix will have a C compiler supporting at least C89

yorwba2• 7 years ago

Except a recent gcc will refuse to compile that code because of a technicality.

Here's some modified code that runs on my machine if pasted directly into bash:

gcc -x c - <<EOF

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

EOF

./a.out

philshem• 7 years ago

                                                               ###############  
                                                               #.......^...$.#  
  ###################                ##############            #.....Z.......#  
  #..$...#..........#                #............#            #.....e.......#  
  #..a...#........$.#                #...$....$...# ############.............#  
  #......#.}........#      ###########....y.......# #.........#######+########  
  #......#..........#      #........##............# #.........##....~.#         
  #......#..........#      #........########'###### #....d....##......#         
  #......+..........#      #H....^$.#.....$...#     #.........##......#         
  ###########'#######      #........+c......O.#     #.........##......#         
   #...........#           ##########.........#     #...$.....##.z$...#         
   #.....x.$...#                    #.........#     #.........##......########  
   #...........#                    #.....Q...#     #.........##Q.....+......#  
   #...........#       ###########  #.........#     #.........##......#......#  
   ######'#########    #.........#  #.........#  ###########'###+######......#  
       #........`.#    #.....H...#  #.........#  #...............#    #.C....#  
       #..R.......#    #.........####+############~........P.....#    #..d...#  
       #..........#    #..{......#...............#...............#    #......#  
       #..$.......#    #.........#...............#....t..........#    #......#  
       #..........#    #.........#...............#...............#    #...`V.#  
     #######+######    #.........+...............#...............#    #......#  
     #....$...#        #.........#...............+....v..........#    ########  
     #fT......#        ###########....@..........#...............#              
     #........#                  #...............#########'#####'############   
     #...H....#                  #...............#    #......#..............#   
     #........#           ########+#######'#######    #..d.b.#..............#   
     #........#           #...X...s.#   #....$.#      #.J....#..............#   
   #######'#'##############..|....E.#   #...]a.#      #......#..............#   
   #.......#..............+$........#   #......#      ########..............#   
   #.......#..............#.........#   #......#             #..............#   
   #.......#......~.......#########'#   #......#             #$.............#   
   #.......#..v...........# #...\...#   #......#             #..............#   
   #n......#........}.....# #.......#   #......#             #..............#   
   #....$..#......`.......# #....u$.#   #......#             ################   
   #...r...#..............# #.......#   #......#                                
   #.......#..............# #########   ########                                
   #########..............#                                                     
           ################

munificent6• 7 years ago

I fixed the technicality in the latest version of the Gist. Interestingly, Clang doesn't seem to have any problems with the original code.

femto113• 7 years ago

If like me you're interested in looking at how the code actually works I put a deobfuscated fork here

https://gist.github.com/femto113/28f69626acddc70a002ecead0b3...

Just expands the macros/typedefs and applies standard indenting, code is otherwise same as the original.

munificent6• 7 years ago

There are a few tweaks I made along the way while tightening it up, but here's the readable original I started from:

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

PhasmaFelis3• 7 years ago

Is there an executable available somewhere?

This is kind of a pet peeve of mine, but if you post simple, standalone code you really ought to post the compiled executable(s) as well. I don't currently have a C compiler installed on my home Windows box.

falsedan• 7 years ago

I hear Visual Studio Code is all right at doing compile stuff with C++

But more seriously, this is a toy implementation and the value is in reading it to see how it works, not in seeing its output

davidjhall• 7 years ago

You can go to online GDB and run it : https://www.onlinegdb.com/

But you have to use the modified code in the comments above or you will get a : main.c:8:7: error: variably modified ‘m’ at file scope =80;i m[H][W];i g(i x) {r rand()%x;}

yorwba2• 7 years ago

Why use an executable when you can run it on someone else's computer™: https://repl.it/repls/NiceEvilBoard

I swear the URL wasn't chosen by me.

PhasmaFelis3• 7 years ago

Thanks for an actually constructive answer! That's pretty neat. I hadn't heard of Repl.it before.

Insanity• 7 years ago

But then you need to trust that the executable is the same as the source!

lixtra• 7 years ago

Here, you can just disassemble the binary and it will be more readable than the code.

dmurray• 7 years ago

If he'd posted an executable, unless it was for exactly your platform, wouldn't you just have complained you didn't currently have a machine running the correct operating system on the correct hardware?

PhasmaFelis3• 7 years ago

Not at all. Tiny textmode programs do not generally require specific hardware or OS versions. Windows/Mac/Linux should cover the large majority of users. Or you could just do Windows, since Unix machines (including Macs) most likely have gcc installed already. Or you could skip all that and include a Repl.it link, like Yorwba thoughtfully provided in the sibling comment.

If it did require specific hardware or software, that would be different, which is why I specifically said "simple, standalone code."

na85• 7 years ago

Hang on, I'll get you an executable. Be sure to run it, okay?

harperlee• 7 years ago

This is not mine, but from the “clojure grams” twitter account:

  (defn maze [n]
    (->> (repeatedly (* n n) #(rand-nth "╱╲"))
      (partition n)
      (transduce
        (comp
          (map #(apply str %))
          (interpose "\n"))
        str)))

Simpler output but related and also quite interesting!

Aardappel2• 7 years ago

Looks like a port of this Basic one-liner: http://www.slate.com/articles/technology/books/2012/11/compu...

coroxout• 7 years ago

This is really cool, nice work (and sorry about your dog).

It reminds me that once upon a time the roguelike dev newsgroup had a "1k (source code) roguelike challenge".

The thread is here [1] and submissions are here in a slightly annoying format [2] but sadly I can't find the entry I remember, which I thought was in C and actually quite playable, if slightly at the mercy of the random number generator to make each new level solvable. Perhaps it was for a later iteration of the same challenge.

[1] https://rec.games.roguelike.development.narkive.com/3tm7xGpn... [2] https://sites.google.com/site/1024brl/

yourfate• 7 years ago

Very cool.

To try and understand it I reformated it to make it somewhat readable:

https://gitlab.com/snippets/1832264

benj111• 7 years ago

Thanks... But someone was there first, with expanded macros.

https://gist.github.com/femto113/28f69626acddc70a002ecead0b3...

homarp2• 7 years ago

https://gist.github.com/munificent/ce8f7a9e6b09938ca8d2d43fa... (from the author)

https://gist.github.com/femto113/28f69626acddc70a002ecead0b3... (from https://news.ycombinator.com/item?id=19290841 )

codetrotter6• 7 years ago

Hopefully without sounding like I am trying to boast or anything... I find the difference in readability and clarity dramatic between those two on one hand and my own deobfuscated, refactored and commented version of the OP. https://gist.github.com/ctsrc/fef3006e1d728bb7271cff0656eb02...

codetrotter6• 7 years ago

Been spending the past hour deobfuscating it a bit.

https://gist.github.com/ctsrc/fef3006e1d728bb7271cff0656eb02...

Meanwhile others have posted fully deobfuscated versions that the original author and someone else has published in the past. Oh well :P

codetrotter6• 7 years ago

Either way, deobfuscating this is fun so I'll keep going.

The link above goes to the first revision.

Here is a link to the most recent revision at all times:

https://gist.github.com/ctsrc/fef3006e1d728bb7271cff0656eb02...

choeger• 7 years ago

I really hope Ginny was a dog or a cat or some other pet. Terrifying thought, it might have been a child.

vanni• 7 years ago

dog https://twitter.com/munificentbob/status/1101903466111283200

supermw• 7 years ago

Not sure how I'd feel about someone writing a piece of code in response to the death of their young child. Equally terrifying.

jackhack2• 7 years ago

People cope with grief and loss in a lot of different ways. Some dwell, others distract. Similarly, while some folks need to be surrounded by family and friends, others just want to be alone for a while. What's sure is you're never the same afterwards.

munificent6• 7 years ago

She was my dog: https://imgur.com/a/p1QQosK

ben174• 7 years ago

Sorry for your loss :(

hawkeye424• 7 years ago

...still waiting for the google maps to for instance counterstrike map generator that must not fit on a business card...

packetpirate• 7 years ago

Fucking black magic obfuscation. Is it possible to learn this power?

I want to see someone try to rewrite C++'s entire syntax in the form of another language (I just have to assume it has already been done.)

cdata• 7 years ago

I'm no expert, but in this case there are a few strategic definitions that help a lot to both conserve space and obfuscate:

  #define r return
  #define l(a, b, c, d) for (i y = a; y < b; y++) for (int x = c; x < d; x++)
  typedef int i;

munificent6• 7 years ago

My goal was less to obfuscate than it was to compress the code. I kept it as clear as I could within the limits of trying to get the code really small. There weren't any deliberate obfuscations like using misleading variable names.

The "l" macro cut the code down significantly and is one of the tricks I'm most proud of.

"r" and "i" aren't that impactful in terms of length. Their main benefit is that they make it easier to split the code where I need to in order to render the big ASCII art "@" sign. That's a lot harder when you have multiple-letter identifiers that can't be split in the middle.

woodrowbarlow• 7 years ago

you may enjoy this article, where the author of a really clever bit of obfuscated C breaks down everything the code is doing.

https://www.a1k0n.net/2011/07/20/donut-math.html

tromp• 7 years ago

The maze generator at http://tromp.github.io/pearls.html#maze is similarly accompanied by a link to a book chapter documenting the obfuscation.

theoh• 7 years ago

There are a lot of examples to read through here: http://ioccc.org

C is used rather than C++, because C++ is a car crash before you even start trying to obfuscate.

alien1993• 7 years ago

He's the same guy that wrote the book Game Programming Patterns. http://gameprogrammingpatterns.com/

jameskilton• 7 years ago

And is currently writing the online book Crafting Interpreters http://www.craftinginterpreters.com/

strenholme• 7 years ago

I have written an obfuscated cryptographically secure random password generator:

https://github.com/samboy/rg32hash/blob/master/C/tinyrg32.c

The file has test cases, documentation:

https://github.com/samboy/rg32hash/blob/master/C/tinyrg32.md

and I even have a 12-page de-obfuscation of an earlier version of this program:

https://github.com/samboy/rg32hash/blob/master/C/nanorg32.md

(I have since then come up more size optimizations)

holografix• 7 years ago

Does anyone know of a dungeon generated tool that takes a few, or many inputs? Type of creatures, terrain, season, presence of water, etc etc?

ioata• 7 years ago

here is one in python(a very very basic version, big enough to fill an A4 size sheet :D ) https://github.com/anekix/dungeon-generator

airstrike• 7 years ago

Backported this to run on MS Visual Studio 2008 in case anyone is equally constrained and still wants to give it a go. Did it based on @Joker-vD's deobfuscated gist

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

metalliqaz• 7 years ago

So this creates random maps? What does one do with the output of this thing?

fb03• 7 years ago

Well i'm not sure it is meant to be 'used' as input to anything else.

It's nice as it is: just someone having fun coding with self-imposed constraints (in this case: doing something interesting with a really small card/code size).

Same as the business card raytracer :)

jackhack2• 7 years ago

I think this could be useful for old-school table gaming D&D style.

munificent6• 7 years ago

Author here. I love all of the deobfuscations. Usually, when I put code online, I try to make it as clear as possible. It's really interesting to see that going the other direction actually makes it a more interactive experience for the reader.

This one is great: https://gist.github.com/airstrike/66e0152e75c3a81fd1496bfbf5...

A couple of remarks:

    // 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 randInt(1) always
    // returns 0.
    if (atWallButNotAtCorner && FIELD[y][x] == TILE_WALL) {
        doorCounter++;
        if (randInt(doorCounter) == 0) {
            doorX = x;
            doorY = y;
        }
    }

The randInt() part here is pretty confusing. Here's the intent of the code. It picks a random boundary for the new room. Then it walks over the edges and finds every tile where the room's wall overlaps the wall of an existing room. Those are candidates where a door can be placed to connect this room to the existing one.

If no candidates are found, the room is discarded. This ensures the dungeon is always connected.

If there are multiple candidates, we only need to pick one. We want to pick one randomly because otherwise you'd get obviously biased choices where the door always appeared at the left-most edge between two rooms or something. The obvious way to do that is to build a list of the candidate coordinates and then choose a random element from the list.

But that's a lot of code. Instead, I use Algorithm R [0]. It's a streaming algorithm for selecting a random item as you walk the set of items being sampled. The idea is that you keep a running winner. Each new element, you have a random chance of replacing the winner. As the number of elements visited increases, the chances of replacing the winner decreases. So the first element has a 1/1 chance of being the winner. The second has a 1/2 chance of replacing the winner, the third 1/3, etc.

    // If the cave's walls were made completely out of corners
    // and doors, don't make such a cave
    if (doorCounter == 0) { return; }

This case actually means the new room didn't share a wall with any existing room.

    // We need to somehow record corners of all caves to check
    // for intersections later, so we use a special tile for it
    FIELD[y][x] = atCorner
        ? TILE_CORNER
        : (atWallButNotAtCorner ? TILE_WALL : TILE_FLOOR);

For a room to connect to an existing one, they need to share a tile on their actual sides, like:

    #####
    #...#
    #...#####
    #...X...#
    #####...#
        #...#
        #####

That's leaves at least one tile where we can place a door. If only the corners overlap, there may not be enough room to connect them:

    #####
    #...#
    #...#
    #...#####
    #####...# ???
        #...#
        #...#
        #####

    #####
    #...#
    #...#
    #...#
    ######### ???
        #...#
        #...#
        #...#
        #####

So, during room placement, the corners are not treated as part of the room:

     ###
    #...#
    #...####
    #...X...#
     ####...#
        #...#
         ### 

     ###
    #...#
    #...#
    #...####
     ####...# ???
        #...#
        #...#
         ### 

     ###
    #...#
    #...#
    #...#
     ### ###  ???
        #...#
        #...#
        #...#
         ###

But, when rendering the rooms, I want them to look rectangular. So the special "!" means "render like a wall, but don't act like a wall".

    // 1d6 of entities total, 25% chance of gold, 75% of a mob.
    // Mob letters range from 'A' to '~', inclusive

Technically, the "mob" case includes all of the non-"$" treasure too. Punctuation characters are in that character range as well and represent items.

Otherwise, the comments are all spot on. It's really gratifying seeing people figure this all out.

[0] https://en.wikipedia.org/wiki/Reservoir_sampling#Algorithm_R

grownseed• 7 years ago

Added a javascript version, for those who want to try it out without compiling anything: https://gist.github.com/munificent/b1bcd969063da3e6c298be070....

Online version: https://jsfiddle.net/dfu7ws69/

jackbrookes• 7 years ago

My favourite "world" generator one-liner (two liner in python):

  import random as r
  print(''.join([r.choice(["/", "\\"]) for _ in range(9999)]))

Output:

  //\\/\//\\/\\\\/\\\/\//\\\\/\\/\\/\///\\\\///\\/\//\\\\/\\/\ 
  /\\\\/////\\\\\/\\\\////\/\//////\////\\\//////\\\\\/\//\\\/
  //\\\\\\/\/\\//\/\\\\///\\/\\//\\///\\/\/\\//\/\\/\///\\\\//
  \\/\//\\\//////\/\/\/\\/\\//\/\///\\///\/\////\//\/\\\/\/\//
  \\\\\\\\\/\//\\\//\\\/\\/\\\\\/\\\\\///\/\\/\\\\//\\/\\/\///
  //\\/\//////////\\//\\\////\\/////\/\/\\\\\\\\///\/\\/\///\/
  \///\//\\//\\\/\/\\\\\//\\\\\\//\/\\//\\\/\/\/////\/\//\/\//
  /\\\\//\\\\/\\///\\\\/\\\/////\\\\\\//\///\//\\////\//\/\\\/
  /\\/\\\//\/\/\//\//\//\\\//\\\\\\\/\\\/\\\\/\\///\/\/\//\///
  \\/\\/////\/\\\///\\\/\\/\//\/\/\/\\\//\\\\\\\\/////\\/\\/\/
  //\\\\\\\\/\\/////\\/\\\\\///\/\\/\\\/\\//\\\\\\/\\/\\\/////
  \\//\\\\/\\/\\///\///\/\\\/\/\/////\//\\//\/\/\/\/\/\/\\/\//
  \//\\\\\\///\/\\/\\\\/\\\/\/\/\/\//\////\/////\\\/\/\\/\\\\/
  //\\\/\\//\\/\\/\/\\////\/\\//\/\/\///\//////\\///////\/\\//
  \/\////\/\//\\\\//\\/\\/\\\\/\/////\///\/\\/\///\\\\/\\\//\/
  \///\\/\\/\\\\\\/\\\\\\\/\\\///\\\/\\///\\\\//\/\/\/\\//\/\\
  /\\\////\/\//\/////\\///\\//\/\\\/\/\\\/\/\\\\\////\\/\\////

schoen2• 7 years ago

This is inspired by this classic BASIC program, which is the inspiration for a whole book:

https://10print.org/

(Note that this version of the original is half the size of this Python adaptation!)

schoen2• 7 years ago

Also, I guess you didn't sign up for a code golf session, but this version is 11 bytes shorter:

   import random
   print(''.join(random.choice("/\\") for _ in "x"*9999))

I was surprised to discover that "import random\nrandom.choice", "import random as r\nrandom.choice", and "__import__("random").choice" are all exactly 27 bytes, so no byte count is saved by preferring any of these forms over another!

flend• 7 years ago

Why not go for a full roguelike game in 1KB: https://wasyl.eu/games/another-visit-in-hell.html

donarb• 7 years ago

Here's my quick port to Swift. It can run in a playground.

https://gist.github.com/donarb/1502a12cb16fa74f4fd2e295867da...

volkk• 7 years ago

granted that it's probably safe, but seeing a screenshot in the comments of someone running this code with no clue as to what it actually does under an "admin" user is kind of funny.

Aardappel2• 7 years ago

Port to Lobster: https://gist.github.com/munificent/b1bcd969063da3e6c298be070...

A random dungeon generator that fits on a business card

Related Stories