import random
import itertools
# dungeon size
width = 80
height = 40
# how big are rooms?
room_width_max = 8
room_width_min = 3
room_height_max = 8
room_height_min = 3
# display style
tiles = {False:'#',True:'.'}
# how is connectivity defined?
dirs4 = [(0,1),(0,-1),(1,0),(-1,0)]
dirs8 = dirs4 + [(1,1),(1,-1),(-1,1),(-1,-1)]
# is (x,y) in the level rectangle?
def in_range(x,y):
return x >= 0 and y >= 0 and x < width and y < height
# unique integer index for each tile
def index(x,y):
return y*width+x
# print walls and floors nicely
def render(m):
for row in m:
print ''.join(map(lambda x: tiles[x], row))
print "\n"
# width * height grid of walls
def empty_map():
m = [[False]*width for y in range(height)]
return m
# n randomly placed rooms of various sizes.
# can overlap. no corridors
def disconnected_map(n):
m = empty_map()
for i in range(n):
# room size
room_width = random.randint(room_width_min,room_width_max)
room_height = random.randint(room_height_min,room_height_max)
# room location. mustn't be out of range.
room_x = random.randint(0,width-room_width)
room_y = random.randint(0,height-room_height)
# make floors in the designated area
for x in range(room_x,room_x+room_width):
for y in range(room_y,room_y+room_height):
m[y][x] = True
return m
# find and mark the connected component that contains a given location
# m: wall map
# f: floodfill map
# (x,y): seed coordinate
# forbid: treat this tile as a wall
# returns component size
def floodfill_sub(m,f,(x,y),forbid=(-1,-1)):
# don't floodfill from wall tiles
if m[y][x] == False or f[y][x] != -1 or (x,y) == forbid:
return 0
# this is the number to tag tiles in this connected component with
my_index = index(x,y)
# coordinates that might be in this connected component
boundary = [(x,y)]
# how big is the connected component?
size = 0
while len(boundary) > 0:
(xx,yy) = boundary.pop()
# ignore tiles that are already claimed, walls, not in range, or forbidden
if (xx,yy) == forbid: continue
if not in_range(xx,yy): continue
if not m[yy][xx]: continue
if f[yy][xx] != -1: continue
# mark the tile
size += 1
f[yy][xx] = my_index
# queue all neighbouring tiles
for (dx,dy) in dirs4:
boundary.append((xx+dx,yy+dy))
return size
# take a list of up to 8 coordinates and check whether they
# form a single connected component. some effect duplication
# with floodfill_sub.
def connected_neighbourhood(neighbours):
# store whether each neighbour has been connected to the first
m_neighbours = dict(zip(neighbours,itertools.repeat(False)))
# store neighbours that need to be expanded
boundary = [neighbours[0]]
while len(boundary) > 0:
(x,y) = boundary.pop()
# mark as explored
m_neighbours[(x,y)] = True
for (dx,dy) in dirs4:
# only consider listed neighbours
try:
if m_neighbours[(x+dx,y+dy)] == False:
boundary.append((x+dx,y+dy))
except KeyError: pass
# are all the neighbours in the same component?
components = set(m_neighbours.values())
return components == set([True])
# check if the whole floodfill can be skipped
def skip_floodfill(m,(x,y),connected=False):
if connected: # if the base map is not connected we can't skip
good_neighbours = []
for (dx,dy) in dirs8:
(xx,yy) = (x+dx,y+dy)
# if the neighbourhood of the forbidden square is connected and the
#map is connected, then the forbidden square is not a bridge
if in_range(xx,yy) and m[yy][xx]:
good_neighbours.append((xx,yy))
if connected_neighbourhood(good_neighbours):
return True
# the forbidden square may be a bridge or the map is disconnected
return False
# find all connected components of map m, treating forbidden tile as a wall.
# cheat when the map is known to be connected.
def floodfill(m, forbid=(-1,-1), connected=False):
if skip_floodfill(m,forbid,connected):
return [],{}
# initialise floodfill map with no tiles claimed
f = [[-1]*width for y in range(height)]
components = {}
for y in range(height):
for x in range(width):
# claim all tiles in the same component as (x,y)
ff_return = floodfill_sub(m,f,(x,y),forbid)
if ff_return > 0:
# make a note of components' size
components[(x,y)] = ff_return
return f,components
# find a corridor that connects the first two connected components of m,
# based on a precomputed floodfill f
def find_connector(m,f,components, forbid=(-1,-1)):
if len(components) < 2:
return None # nothing to be done
# seed locations of two randomly chosen connected components
# can be altered to connect all components but just two is enough
keys = components.keys()
random.shuffle(keys)
# values in the floodfill map are indices, not coordinates
index_a = index(*keys[0])
index_b = index(*keys[1])
# list all members of the connected components and choose two at random
component_a_coords = [(x,y) for x in range(width)
for y in range(height)
if f[y][x] == index_a]
component_b_coords = [(x,y) for x in range(width)
for y in range(height)
if f[y][x] == index_b]
ax,ay = random.choice(component_a_coords)
bx,by = random.choice(component_b_coords)
# which direction is (bx,by) from (ax,ay)?
dx,dy = cmp(bx,ax),cmp(by,ay)
# sequence of coordinates up to but not including bx,by
ax_bx = range(ax,bx,dx) if dx != 0 else [ax]
ay_by = range(ay,by,dy) if dy != 0 else [ay]
# try going horizontally then vertically
connect_h = zip(ax_bx,[ay]*len(ax_bx)) + \
zip([bx]*len(ay_by),ay_by) + \
[(bx,by)]
# try instead going vertically then horizontally
connect_v = zip([ax]*len(ay_by),ay_by) + \
zip(ax_bx,[by]*len(ax_bx)) + \
[(bx,by)]
# the connector is no use if a tile is forbidden
if forbid in connect_h:
connect = connect_v
elif forbid in connect_v:
connect = connect_h
else: # choose randomly if possible
connect = random.choice([connect_h,connect_v])
a_idx = 0
b_idx = 0
# what's the last tile in component a before the first tile in component b?
for (i,(x,y)) in zip(itertools.count(),connect):
if f[y][x] == index_a:
a_idx = i
elif f[y][x] == index_b:
b_idx = i
break
# cut out all unnecessary coordinates from the connector and return
connect = connect[a_idx+1:b_idx]
return connect
# take any map with at least 2 floor tiles and make it biconnected.
# there will be at least 2 disjoint paths between any pair of floor tiles.
def biconnected_map(m):
# queue all floor tiles for testing
c =[(x,y) for x in range(width) for y in range(height) if m[y][x]]
random.shuffle(c)
connected = False
while len(c) > 0:
(x,y) = c.pop()
# treat the chosen tile as wall, making an induced subgraph.
# What are the components of this subgraph?
f,components = floodfill(m,(x,y), connected)
if len(components) <= 1:
connected = True
continue
# If there's more than one connected component,
# find a way to connect them (not including (x,y)
connector = find_connector(m,f,components,(x,y))
if connector != None:
# check the tile in case any more needs to be done
c.append((x,y))
# add some of the new connector tiles for checking if necessary
if not connected:
c.append(connector[0])
c.append(connector[-1])
# alter the wall map
for (xx,yy) in connector:
m[yy][xx] = True
return m
# example usage
if __name__ == '__main__':
# start with something that has < 1 connected component
m = disconnected_map(20)
# print non-biconnected map for reference
render(m)
m = biconnected_map(m)
# print the map in order to gloat about the biconnected magicalness
render(m)
# This is free and unencumbered software released into the public domain.
# Anyone is free to copy, modify, publish, use, compile, sell, or
# distribute this software, either in source code form or as a compiled
# binary, for any purpose, commercial or non-commercial, and by any
# means.
# In jurisdictions that recognize copyright laws, the author or authors
# of this software dedicate any and all copyright interest in the
# software to the public domain. We make this dedication for the benefit
# of the public at large and to the detriment of our heirs and
# successors. We intend this dedication to be an overt act of
# relinquishment in perpetuity of all present and future rights to this
# software under copyright law.
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
# IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
# OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
# ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
# OTHER DEALINGS IN THE SOFTWARE.
# For more information, please refer to