Subject: Cave-building algorithm
Date: 15 Apr 2002 19:21:14 -0500
From: gdighton@geocities.com (Garth Dighton)
Organization: Newsfeeds.com http://www.newsfeeds.com 90,000+ UNCENSORED Newsgroups.
Newsgroups: rec.games.roguelike.development

Here's a cave-building algorithm (in Lua 3.2) which produces a fairly
decent cave which is guaranteed to be connected:

MAXX = 80
MAXY = 50
MAXBORDERS = min(MAXX, MAXY)
dx = {-1, 0, 0, 1}
dy = {0, -1, 1, 0}

array = {}
list = {}

-- Initialize with rock
randomseed(666)
i=0
while (i<MAXY) do
        j = 0
        while (j<MAXX) do
                array[j+MAXX*i] = '#'
                j = j + 1
        end
        i = i + 1
end

k = 0

-- We start in the center, simply to avoid being too close to the edges
y = floor(MAXY/2); x = floor(MAXX/2)

-- Through each iteration, we remove a cell, and add its neighbors to the
-- list of bordering cells. Adding to the list is not guaranteed -- the
-- more border cells we have available, the less likely any given cell is
-- to be added. This produces more random caves.

while(k < MAXX*MAXY/2) do
        array[x+MAXX*y] = '.'

        i=1
        while (i<=4) do
                x1 = x+dx[i]; y1 = y+dy[i];
                if (x1 >= 0 and x1 < MAXX and y1 >= 0 and y1 < MAXY
                        and array[x1+MAXX*y1] == '#') then
                        if (random(MAXBORDERS) > getn(list)) then
                                tinsert(list, {x1, y1})
                                array[x1+MAXX*y1] = '0' -- mark as border
                        end
                end
                i = i + 1
        end
        i = random(getn(list))
        t = list[i]
        list[i] = list[getn(list)]
        tremove(list)

        x = t[1]; y = t[2]
        k = k + 1
end

-- Print array
i=0
while (i < MAXY) do
        j = 0
        while (j < MAXX) do
                write(array[j+MAXX*i])
                j = j + 1
        end
        write('\n')
        i = i + 1
end

Here's an example of the caves it produces (with the given random seed
above):

#######################################..............#..........#####...###
#####################################......#.......#............#####...###
######################################...##....#....#...........#..###...##
########################################.#...............................##
#######################################.................#................##
#######################################.#..##...............##...........##
#######################################.#...................##........##.##
#######################################...............#......#...#....#...#
######################################........#...#.......#####..#........0
######################################............#.......#####..#........0
#################################.........................###.#...#......0#
#################################...#..................#..........#...0#0##
#################################................#...####...#..#......#####
##############################..............###..#...####......#.....######
##############################................#.....#...#.......#...#######
###########################.##..#.#...............#..............##########
##########################...................#....##....#......############
#######################............##.........#..###.#..#......#00#########
###################.#..........................#.............#.0..0########
###################...#.....#............###....#..................0#######
##################....#..................#####..#..................########
##################....##..................###...........#...#.......#######
#####################.###........#........##..........#######.......#######
###################....##....##..##.......##.....#.###########......#######
##################...............##.......##......############......#######
#################....................................#####..##...#..#######
####..###########..............................#......####........#..######
#####....####......##..........................##............##......######
###......####.............................#.....#........#......###.#######
###........#..........##..................#...................#############
#####..............#...#........#.........##.................###.##########
######.................#...####.........#####...............####...########
######...............#...######........###..................##0...#########
#######..........#####....####...#.....######................#.#..#########
######.......#...#####..######.##......######......#...............0#######
######.#.........##.##..#########.....######.......#................0######
##########..............#########......###..#...................#..0#######
############.........#....########.......##....................#...########
############..............#############................#..#.........#######
###########...............#################.............#.#....#.....######
###########.#.......###..##################...#................#......#####
.0#...##.#..........##...###############..............................#####
..#................#####.##############...............#####...........#####
......................#..##############.....#.......#######..........######
.........................###############......####..#########.#....########
#............#...........####0#0####.#...###.#####.########################
#...........#...#...........#.0...##.....##################################
##..........#...#..................#.......0###############################
###........#########...............0........###############################
###.......##########.##.........#.0###....#################################

--
Garth Dighton

-----=  Posted via Newsfeeds.Com, Uncensored Usenet News  =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
 Check out our new Unlimited Server. No Download or Time Limits!
-----==  Over 80,000 Newsgroups - 19 Different Servers!  ==-----