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