Implementing The Proper Undead's Cave Generator

I recently stumbled onto a very old article about procedural dungeon generation on this site. Unfortunately, the author did not provide any code, only a description of the algorithm he used. Wanting to use this in my game, I tried to write my own generator following their algorithm:

local random = math.random

local function grid()
    return {
        min = 0,
        max = 0,

        init = function(self, min, max)
            for i = min, max do
                self[i] = {}
            end

            self.min = min
            self.max = max
        end,

        set = function(self, x, y, c)
            if x >= self.min and x = self.min and y \n")
        end,
    }

    setmetatable(p, {__eq = function(self, right)
        return self.x == right.x and self.y == right.y
    end})

    return p
end

local function contains_point(array, p)
    for i = 1, #array do
        if array[i] == p then
            return true
        end
    end

    return false
end

local function shuffle(array)
    local size = #array

    for i = 1, size do
        local swap = random(1, size)
        array[i], array[swap] = array[swap], array[i]
    end

    return array
end

local function offsets(p)
    return {
        point(p.x, p.y+1),
        point(p.x, p.y-1),
        point(p.x+1, p.y),
        point(p.x-1, p.y),
    }
end

local function circular_iterator_of(items, start)
    local index = start - 1
    return function()
        local ret =  items[index + 1]
        index = index + 1
        index = index % #items + 1
        return ret
    end
end

local function carve(list)
    local index = 1 
    while index  minTilesCarved

    for i = 1, #carvedList do
        p = carvedList[i]
        if i == 1 then
            map:set(p.x, p.y, "D")
        elseif i == #carvedList then
            map:set(p.x, p.y, "U")
        else
            map:set(p.x, p.y, ".")
        end
    end

    return map
end

map = generate_map(64, 170, os.time())

map:print()

First time pos

Your code looks nice.

Now, as for your bonus question. The most probable cause for the diff between your "chunky" maps and the example maps provided in the article I think is that the article author simply generated a lot of maps and chose those that looked best.

Other reasons may be that your implementation differ in some way from what the author did. Since the details are not given, we'll never know. And since the "algorithm" has a random component it's even harder to tell whether the nature of the maps are due to differences in implementation or just randomness.

I spent a portion of my day mimicking your code in C++, and my results are pretty close to yours. Well, that is to say, some of my results. Due to the randomness, some runs result in small blobs of about 100 cells, whereas other become rather large, 200-3000 cell grids.

An example of the former:

###   
##    
#    #
##  ##
#   ##
   ###
#   ##
#  ###

An example of the latter:

############################## #######################
#############################   ######################
#############################  #######################
#############################   ######################
##############################    ####################
##############################    ####################
############################       ###################
############################        ######## ## ######
#### ######################         #######      #####
#### #######################         ######      #####
###   #################### #          #####    #######
     #####################              ##      #  ###
## #     ###############           #         #     ###
###    #########   #######                         ###
##     # #######   ########                   #       
###       ##       ########                ####       
###      ####      #######                ###         
#####     ###    ########                        ##   
####       # ## ### ####                           ###
###               # #####                       ######
####                   ###         #            ######
#####                 ####  ##       #         #######
######                #######        #         #######
#######   ##            ######    #           ########
#####      #   #        ######       #     ###########
####          ##       ########      ##    #### ######
###          ####        #######    #####  ###   # ###
####         ###    ## ##########   #####   ##     ###
####         ###    #############   ###             ##
###         ###         ####### #   ####    #        #
####         #         ########    ####     #         
####                 ##########                   ####
###                      #####                     ###
###                        ##               #   ######
###        #                               ### #######
####                 ###               ### ###########
####                 ###     ##        ###############
####          ##     #       ##        ###############
########      ###           ###         ##############
#######        #          ######        ##############
##### #       ##         ########      ###############
####  ##  #######        ########## ##################
###       #######         ############################
###        #### #          ###########################
###         ##            ############################
###        ##               ##########################
####     # #####      #      #########################
#####    #######          # ##########################
##### #    #####          ############################
######### #####       ################################
######### ######      ################################
##################   #################################

An observation I've made though is that the grids generally tend to stretch out more in one dimension than the other, suggesting that I may have messed up some randomness. Hmm.

Edit: After about 200k map runs gathering statistics, I conclude that they actually do not have a bias towards any direction. I was just fooled by the line distance and initial hypothesis bias, so to speak.

Well, I hope this answer has contributed to your sense of fulfillment with regards to caves. :)

StackExchange Code Review Q#128557, answer score: 5