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:
