13
\$\begingroup\$

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.max then
                if y >= self.min and y <= self.max then
                    self[x][y] = c
                end
            end
        end,

        print = function(self)
            for y = self.max, self.min, -1 do
                for x = self.min, self.max do
                    io.write(self[x][y] or "#")
                end

                io.write"\n"
            end
        end
    }
end

local function point(x, y)
    p = {
        x = x, 
        y = y,

        print = function(self)
            io.write("<" .. self.x .. ", " .. self.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 < #list + 1 do
        local currentPoint = list[index]
        local last
        if (index == #list) then
            last = true
        end

        local numChecks = random(last and 1 or 0, 4)
        local neighbors = circular_iterator_of(shuffle(offsets(currentPoint)), 1)

        for i = 1, numChecks do
            local neighbor = neighbors()

            if not contains_point(list, neighbor) then
                table.insert(list, neighbor)
            end
        end

        index = index + 1
    end
end 

function generate_map(width, minTilesCarved, seed)
    local map = grid()
    map:init(-width/2, width/2)

    local start = point(0, 0)

    local carvedList = {}
    table.insert(carvedList, start)

    math.randomseed(seed)

    repeat
        carve(carvedList)
    until #carvedList > 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 posting here, please be somewhat gentle :)

Note:

While it doesn't appear to be on topic for this site, bonus points will be awarded to those who can suggest ways to make my algorithm produce results closer to those on the original site (my caves feel too chunky in general).

Ideal Caves:

Good Cave 1 Good Cave 2

My Results:

My Cave 1 My Cave 2

\$\endgroup\$
  • 1
    \$\begingroup\$ This question has been well received, is Lua just not a very popular language for code reviews? \$\endgroup\$ – Nikolai97 May 19 '16 at 7:41
  • \$\begingroup\$ We are a small community, "rare" languages sadly often lack reviewers. It is not your fault. \$\endgroup\$ – Caridorc May 25 '16 at 20:32
  • \$\begingroup\$ I see, thats quite a shame, i was hoping to improve my lua skills. But next time I guess I'll use a more popular language. \$\endgroup\$ – Nikolai97 May 25 '16 at 20:55
  • \$\begingroup\$ @Demyx97 Just a tip. When I want a code review for an unpopular language, I'll find a G+ community for that language and post either a copy of the review request, or a link. That's helped me a few times. \$\endgroup\$ – Carcigenicate Jun 6 '16 at 23:49
  • \$\begingroup\$ @Carcigenicate Thank you for the tip, I may just try that :) \$\endgroup\$ – Nikolai97 Jun 6 '16 at 23:57
5
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.