13 ms·
A random dungeon generator in C, small enough to fit on a business card
- yourfate 8y agoVery cool. To try and understand it I reformated it to make it somewhat readable: https://gitlab.com/snippets/1832264 https://gitlab.com/snippets/1832264
- benj111 8y agoThanks... But someone was there first, with expanded macros. https://gist.github.com/femto113/28f69626acddc70a002ecead0b311da4 https://gist.github.com/femto113/28f69626acddc70a002ecead0b3...
- homarp 8y agohttps://gist.github.com/munificent/ce8f7a9e6b09938ca8d2d43fa62f9864 https://gist.github.com/munificent/ce8f7a9e6b09938ca8d2d43fa... (from the author) https://gist.github.com/femto113/28f69626acddc70a002ecead0b311da4 https://gist.github.com/femto113/28f69626acddc70a002ecead0b3... (from https://news.ycombinator.com/item?id=19290841 https://news.ycombinator.com/item?id=19290841 )
- codetrotter 8y agoHopefully 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/fef3006e1d728bb7271cff0656eb0280#file-dungeon-c https://gist.github.com/ctsrc/fef3006e1d728bb7271cff0656eb02...
- homarp 8y agoregarding your comment: >// Probably plus means a locked door, and single quote means unlocked, or the other way around. http://angband.oook.cz/stuff/manual.txt http://angband.oook.cz/stuff/manual.txt gives ' An open /broken door + A closed door $ Gold or gems A Angelic being ~ Light sources, Tools, Chests, Junk, Sticks, Skeletons, etc
- codetrotter 8y agoNice, thanks. I've updated the comments with the information you provided here :)
- codetrotter 8y agoBeen spending the past hour deobfuscating it a bit. https://gist.github.com/ctsrc/fef3006e1d728bb7271cff0656eb0280/14375eb385e48947999bb370dbcd514f0041ee4c 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
- codetrotter 8y agoEither 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/fef3006e1d728bb7271cff0656eb0280 https://gist.github.com/ctsrc/fef3006e1d728bb7271cff0656eb02...
- codetrotter 8y agoPretty much done deobfuscating, refactoring and commenting the code now. I think at this point most of it is pretty understandable. https://gist.github.com/ctsrc/fef3006e1d728bb7271cff0656eb0280 https://gist.github.com/ctsrc/fef3006e1d728bb7271cff0656eb02...
- codetrotter 8y agoI worked a little bit more on it, and thanks to my refactoring I have identified a bug in the original code (which I have intentionally retained in my own code because the point is to produce the same output as the original version, all the way down to and including bug-for-bug compatibility). Description of bug, which I also posted as a comment on the OP gist: > 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 https://gist.github.com/ctsrc/fef3006e1d728bb7271cff0656eb02... [...]. In my refactored version of your code the bug is explained at the line I linked to in this comment. https://gist.github.com/munificent/b1bcd969063da3e6c298be070a22b604#gistcomment-2854636 https://gist.github.com/munificent/b1bcd969063da3e6c298be070...
- yorwba 8y agoPreviously: https://news.ycombinator.com/item?id=19290215 https://news.ycombinator.com/item?id=19290215
- dang 3y agoComments belatedly moved thither. Thanks!
- choeger 8y agoI really hope Ginny was a dog or a cat or some other pet. Terrifying thought, it might have been a child.
- vanni 8y agodog https://twitter.com/munificentbob/status/1101903466111283200 https://twitter.com/munificentbob/status/1101903466111283200
- supermw 8y agoNot sure how I'd feel about someone writing a piece of code in response to the death of their young child. Equally terrifying.
- jackhack 8y agoPeople 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.
- munificent 8y agoShe was my dog: https://imgur.com/a/p1QQosK https://imgur.com/a/p1QQosK
- ben174 8y agoSorry for your loss :(
- hawkeye424 8y ago...still waiting for the google maps to for instance counterstrike map generator that must not fit on a business card...
- packetpirate 8y agoFucking 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 8y agoI'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;
- munificent 8y agoMy 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 8y agoyou 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 https://www.a1k0n.net/2011/07/20/donut-math.html
- tromp 8y agoThe maze generator at http://tromp.github.io/pearls.html#maze http://tromp.github.io/pearls.html#maze is similarly accompanied by a link to a book chapter documenting the obfuscation.
- theoh 8y agoThere are a lot of examples to read through here: http://ioccc.org http://ioccc.org C is used rather than C++, because C++ is a car crash before you even start trying to obfuscate.
- alien1993 8y agoHe's the same guy that wrote the book Game Programming Patterns. http://gameprogrammingpatterns.com/ http://gameprogrammingpatterns.com/
- jameskilton 8y agoAnd is currently writing the online book Crafting Interpreters http://www.craftinginterpreters.com/ http://www.craftinginterpreters.com/
- strenholme 8y agoI have written an obfuscated cryptographically secure random password generator: https://github.com/samboy/rg32hash/blob/master/C/tinyrg32.c 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 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 https://github.com/samboy/rg32hash/blob/master/C/nanorg32.md (I have since then come up more size optimizations)
- holografix 8y agoDoes 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 8y agohere is one in python(a very very basic version, big enough to fill an A4 size sheet :D ) https://github.com/anekix/dungeon-generator https://github.com/anekix/dungeon-generator
- airstrike 8y agoBackported 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/66e0152e75c3a81fd1496bfbf590105a https://gist.github.com/airstrike/66e0152e75c3a81fd1496bfbf5...
- metalliqaz 8y agoSo this creates random maps? What does one do with the output of this thing?
- fb03 8y agoWell 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 :)
- jackhack 8y agoI think this could be useful for old-school table gaming D&D style.
- munificent 8y agoAuthor 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/66e0152e75c3a81fd1496bfbf590105a 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 https://en.wikipedia.org/wiki/Reservoir_sampling#Algorithm_R
- grownseed 8y agoAdded a javascript version, for those who want to try it out without compiling anything: https://gist.github.com/munificent/b1bcd969063da3e6c298be070a22b604#gistcomment-2854606 https://gist.github.com/munificent/b1bcd969063da3e6c298be070.... Online version: https://jsfiddle.net/dfu7ws69/ https://jsfiddle.net/dfu7ws69/
- jackbrookes 8y agoMy favourite "world" generator one-liner (two liner in python): import random as r print(''.join([r.choice(["/", "\\"]) for _ in range(9999)])) Output: //\\/\//\\/\\\\/\\\/\//\\\\/\\/\\/\///\\\\///\\/\//\\\\/\\/\ /\\\\/////\\\\\/\\\\////\/\//////\////\\\//////\\\\\/\//\\\/ //\\\\\\/\/\\//\/\\\\///\\/\\//\\///\\/\/\\//\/\\/\///\\\\// \\/\//\\\//////\/\/\/\\/\\//\/\///\\///\/\////\//\/\\\/\/\// \\\\\\\\\/\//\\\//\\\/\\/\\\\\/\\\\\///\/\\/\\\\//\\/\\/\/// //\\/\//////////\\//\\\////\\/////\/\/\\\\\\\\///\/\\/\///\/ \///\//\\//\\\/\/\\\\\//\\\\\\//\/\\//\\\/\/\/////\/\//\/\// /\\\\//\\\\/\\///\\\\/\\\/////\\\\\\//\///\//\\////\//\/\\\/ /\\/\\\//\/\/\//\//\//\\\//\\\\\\\/\\\/\\\\/\\///\/\/\//\/// \\/\\/////\/\\\///\\\/\\/\//\/\/\/\\\//\\\\\\\\/////\\/\\/\/ //\\\\\\\\/\\/////\\/\\\\\///\/\\/\\\/\\//\\\\\\/\\/\\\///// \\//\\\\/\\/\\///\///\/\\\/\/\/////\//\\//\/\/\/\/\/\/\\/\// \//\\\\\\///\/\\/\\\\/\\\/\/\/\/\//\////\/////\\\/\/\\/\\\\/ //\\\/\\//\\/\\/\/\\////\/\\//\/\/\///\//////\\///////\/\\// \/\////\/\//\\\\//\\/\\/\\\\/\/////\///\/\\/\///\\\\/\\\//\/ \///\\/\\/\\\\\\/\\\\\\\/\\\///\\\/\\///\\\\//\/\/\/\\//\/\\ /\\\////\/\//\/////\\///\\//\/\\\/\/\\\/\/\\\\\////\\/\\////
- schoen 8y agoThis is inspired by this classic BASIC program, which is the inspiration for a whole book: https://10print.org/ https://10print.org/ (Note that this version of the original is half the size of this Python adaptation!)
- schoen 8y agoAlso, 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 8y agoWhy not go for a full roguelike game in 1KB: https://wasyl.eu/games/another-visit-in-hell.html https://wasyl.eu/games/another-visit-in-hell.html
- donarb 8y agoHere's my quick port to Swift. It can run in a playground. https://gist.github.com/donarb/1502a12cb16fa74f4fd2e295867da253 https://gist.github.com/donarb/1502a12cb16fa74f4fd2e295867da...
- volkk 8y agogranted 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.
- Aardappel 8y agoPort to Lobster: https://gist.github.com/munificent/b1bcd969063da3e6c298be070a22b604#gistcomment-2854781 https://gist.github.com/munificent/b1bcd969063da3e6c298be070...