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

My Results:

• This question has been well received, is Lua just not a very popular language for code reviews? May 19, 2016 at 7:41
• We are a small community, "rare" languages sadly often lack reviewers. It is not your fault. May 25, 2016 at 20:32
• 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. May 25, 2016 at 20:55
• @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. Jun 6, 2016 at 23:49
• @Carcigenicate Thank you for the tip, I may just try that :) Jun 6, 2016 at 23:57

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