A random dungeon generator in C, small enough to fit on a business card
Author here. I love all of the deobfuscations. Usually, when I put code online, I try to make it as <i>clear</i> as possible. It&#x27;s really interesting to see that going the other direction actually makes it a more interactive experience for the reader.<p>This one is great: <a href="https:&#x2F;&#x2F;gist.github.com&#x2F;airstrike&#x2F;66e0152e75c3a81fd1496bfbf590105a" rel="nofollow">https:&#x2F;&#x2F;gist.github.com&#x2F;airstrike&#x2F;66e0152e75c3a81fd1496bfbf5...</a><p>A couple of remarks:<p><pre><code>    &#x2F;&#x2F; The door should not be created in the cave&#x27;s corner or over
    &#x2F;&#x2F; another door, or in another cave&#x27;s corner. It&#x27;s impossible
    &#x2F;&#x2F; to make a cave without a door, because randInt(1) always
    &#x2F;&#x2F; returns 0.
    if (atWallButNotAtCorner &amp;&amp; FIELD[y][x] == TILE_WALL) {
        doorCounter++;
        if (randInt(doorCounter) == 0) {
            doorX = x;
            doorY = y;
        }
    }
</code></pre>
The randInt() part here is pretty confusing. Here&#x27;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&#x27;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.<p>If no candidates are found, the room is discarded. This ensures the dungeon is always connected.<p>If there are <i>multiple</i> candidates, we only need to pick one. We want to pick one randomly because otherwise you&#x27;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.<p>But that&#x27;s a lot of code. Instead, I use Algorithm R [0]. It&#x27;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&#x2F;1 chance of being the winner. The second has a 1&#x2F;2 chance of replacing the winner, the third 1&#x2F;3, etc.<p><pre><code>    &#x2F;&#x2F; If the cave&#x27;s walls were made completely out of corners
    &#x2F;&#x2F; and doors, don&#x27;t make such a cave
    if (doorCounter == 0) { return; }
</code></pre>
This case actually means the new room didn&#x27;t share a wall with any existing room.<p><pre><code>    &#x2F;&#x2F; We need to somehow record corners of all caves to check
    &#x2F;&#x2F; for intersections later, so we use a special tile for it
    FIELD[y][x] = atCorner
        ? TILE_CORNER
        : (atWallButNotAtCorner ? TILE_WALL : TILE_FLOOR);
</code></pre>
For a room to connect to an existing one, they need to share a tile on their actual sides, like:<p><pre><code>    #####
    #...#
    #...#####
    #...X...#
    #####...#
        #...#
        #####
</code></pre>
That&#x27;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:<p><pre><code>    #####
    #...#
    #...#
    #...#####
    #####...# ???
        #...#
        #...#
        #####

    #####
    #...#
    #...#
    #...#
    ######### ???
        #...#
        #...#
        #...#
        #####
</code></pre>
So, during room placement, the corners are not treated as part of the room:<p><pre><code>     ###
    #...#
    #...####
    #...X...#
     ####...#
        #...#
         ### 

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

     ###
    #...#
    #...#
    #...#
     ### ###  ???
        #...#
        #...#
        #...#
         ### 
</code></pre>
But, when rendering the rooms, I want them to look rectangular. So the special &quot;!&quot; means &quot;render like a wall, but don&#x27;t act like a wall&quot;.<p><pre><code>    &#x2F;&#x2F; 1d6 of entities total, 25% chance of gold, 75% of a mob.
    &#x2F;&#x2F; Mob letters range from &#x27;A&#x27; to &#x27;~&#x27;, inclusive
</code></pre>
Technically, the &quot;mob&quot; case includes all of the non-&quot;$&quot; treasure too. Punctuation characters are in that character range as well and represent items.<p>Otherwise, the comments are all spot on. It&#x27;s really gratifying seeing people figure this all out.<p>[0]: <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Reservoir_sampling#Algorithm_R" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Reservoir_sampling#Algorithm_R</a>