diff options
| -rw-r--r-- | binary_tree.py | 17 | ||||
| -rw-r--r-- | binary_tree_demo.py | 7 | ||||
| -rw-r--r-- | cell.py | 47 | ||||
| -rw-r--r-- | grid.py | 124 | ||||
| -rw-r--r-- | maze.py | 50 | ||||
| -rw-r--r-- | requirements.txt | 1 | ||||
| -rw-r--r-- | sidewinder.py | 28 | ||||
| -rw-r--r-- | sidewinder_demo.py | 8 |
8 files changed, 282 insertions, 0 deletions
diff --git a/binary_tree.py b/binary_tree.py new file mode 100644 index 0000000..b125539 --- /dev/null +++ b/binary_tree.py @@ -0,0 +1,17 @@ +import random + + +class BinaryTree(object): + def on(grid): + for cell in grid.each_cell(): + neighbors = [] + if cell.north: + neighbors.append(cell.north) + if cell.east: + neighbors.append(cell.east) + + if neighbors: + neighbor = random.choice(neighbors) + cell.link(neighbor) + + return grid diff --git a/binary_tree_demo.py b/binary_tree_demo.py new file mode 100644 index 0000000..ca1d363 --- /dev/null +++ b/binary_tree_demo.py @@ -0,0 +1,7 @@ +from grid import Grid +from binary_tree import BinaryTree + +grid = Grid(4, 4) +BinaryTree.on(grid) + +print(grid) @@ -0,0 +1,47 @@ +class Cell(object): + row = None + column = None + links = None + + north = None + south = None + east = None + west = None + + def __init__(self, row, column): + self.row = row + self.column = column + self.links = {} + + def link(self, cell, bidirectional=True): + self.links[cell] = True + + if bidirectional: + cell.link(self, bidirectional=False) + + def unlink(self, cell, bidirectional=True): + self.links.pop(cell) + + if bidirectional: + cell.unlink(cell, bidirectional=False) + + def links(self): + return self.links.keys() + + def is_linked_to(self, cell): + return cell in self.links + + def neighbors(self): + n = [] + + if self.north: + n.append(self.north) + + if self.south: + n.append(self.south) + + if self.east: + n.append(self.east) + + if self.west: + n.append(self.west) @@ -0,0 +1,124 @@ +import random + +from PIL import Image, ImageDraw, ImageFilter + +from cell import Cell + + +class Grid(object): + rows = None + columns = None + + def __init__(self, rows, columns): + self.rows = rows + self.columns = columns + self.grid = self.prepare_grid() + self.configure_cells() + + def prepare_grid(self): + grid = [] + for x in range(0, self.rows): + row = [] + for y in range(0, self.columns): + row.append(Cell(x, y)) + grid.append(row) + + return grid + + def configure_cells(self): + for cell in self.each_cell(): + row, col = cell.row, cell.column + cell.north = self[row - 1, col] + cell.south = self[row + 1, col] + cell.west = self[row, col - 1] + cell.east = self[row, col + 1] + + def __getitem__(self, key): + row, column = key + if not 0 <= row <= self.rows - 1: + return None + + if not 0 <= column <= len(self.grid[row]) - 1: + return None + + return self.grid[row][column] + + def random_cell(self): + row = random.randint(0, self.rows - 1) + column = random.randint(0, len(self.grid[row])) + return self[row, column] + + def size(self): + return self.rows * self.columns + + def each_row(self): + for row in self.grid: + yield row + + def each_cell(self): + for row in self.each_row(): + for cell in row: + if cell: + yield cell + + def __str__(self): + output = '+' + '---+' * self.columns + '\n' + + for row in self.each_row(): + top = '|' + bottom = '+' + + for cell in row: + if not cell: + cell = Cell(-1, -1) + + if cell.is_linked_to(cell.east): + east_boundary = ' ' + else: + east_boundary = '|' + top = top + ' ' + east_boundary + + if cell.is_linked_to(cell.south): + south_boundary = ' ' + else: + south_boundary = '---' + bottom = bottom + south_boundary + '+' + + output += top + '\n' + output += bottom + '\n' + + return output + + def to_img(self, cell_size=50): + img_width = cell_size * self.columns + img_height = cell_size * self.rows + + img = Image.new(mode='RGB', size=(img_width + 1, img_height + 1), color='#FFFFFF') + draw = ImageDraw.Draw(img) + + for cell in self.each_cell(): + x1 = cell.column * cell_size + y1 = cell.row * cell_size + x2 = (cell.column + 1) * cell_size + y2 = (cell.row + 1) * cell_size + + if not cell.north: + draw.line([(x1, y1), (x2, y1)], fill='#000000') + + if not cell.west: + draw.line([(x1, y1), (x1, y2)], fill='#000000') + + if not cell.is_linked_to(cell.east): + r=1 + draw.line([(x2, y1), (x2, y2)], fill='#000000', width=4) + draw.ellipse((x2-r, y1-r, x2+r, y1+r), fill='#000000') + draw.ellipse((x2-r, y2-r, x2+r, y2+r), fill='#000000') + + if not cell.is_linked_to(cell.south): + r=1 + draw.line([(x1, y2), (x2, y2)], fill='#000000', width=4) + draw.ellipse((x1-r, y2-r, x1+r, y2+r), fill='#000000') + draw.ellipse((x2-r, y2-r, x2+r, y2+r), fill='#000000') + + img = img.filter(ImageFilter.GaussianBlur(radius=0.8)) + img.save('maze.png') @@ -0,0 +1,50 @@ +import random +import sys + + +grid = [ [0] * 10 for x in range(10) ] + +N, S, E, W = 1, 2, 4, 8 +DX = { E: 1, W: -1, N: 0, S: 0 } +DY = { E: 0, W: 0, N: -1, S: 1 } +OPPOSITE = { E: W, W: E, N: S, S: N } + + +def carve_passages_from(cx, cy, grid): + directions = [N, S, E, W] + random.shuffle(directions) + + for direction in directions: + nx, ny = cx + DX[direction], cy + DY[direction] + + if 0 <= ny <= len(grid) - 1 and 0 <= nx <= len(grid[ny]) - 1 and grid[ny][nx] == 0: + grid[cy][cx] |= direction + grid[ny][nx] |= OPPOSITE[direction] + carve_passages_from(nx, ny, grid) + +carve_passages_from(0, 0, grid) + + +def print_maze(grid): + height = len(grid) + width = len(grid[0]) + + for y in range(0, height): + sys.stdout.write("|") + for x in range(0, width): + + if grid[y][x] & S != 0: + sys.stdout.write(" ") + else: + sys.stdout.write("_") + + if grid[y][x] & E != 0: + if grid[y][x] | grid[y][x+1] & S != 0: + sys.stdout.write(" ") + else: + sys.stdout.write("_") + else: + sys.stdout.write("|") + print() + +print_maze(grid) diff --git a/requirements.txt b/requirements.txt new file mode 100644 index 0000000..3868fb1 --- /dev/null +++ b/requirements.txt @@ -0,0 +1 @@ +pillow diff --git a/sidewinder.py b/sidewinder.py new file mode 100644 index 0000000..c047eed --- /dev/null +++ b/sidewinder.py @@ -0,0 +1,28 @@ +import random + + +class Sidewinder(object): + def on(grid): + for row in grid.each_row(): + run = [] + + for cell in row: + run.append(cell) + + at_eastern_boundary = (cell.east == None) + at_northern_boundary = (cell.north == None) + + should_close_out = at_eastern_boundary or \ + (not at_northern_boundary and random.randint(0, 1) == 0) + + if should_close_out: + member = random.choice(run) + if member.north: + member.link(member.north) + del run[:] + else: + cell.link(cell.east) + + #print(grid) + + return grid diff --git a/sidewinder_demo.py b/sidewinder_demo.py new file mode 100644 index 0000000..3fe790f --- /dev/null +++ b/sidewinder_demo.py @@ -0,0 +1,8 @@ +from grid import Grid +from sidewinder import Sidewinder + +grid = Grid(10, 10) +Sidewinder.on(grid) +grid.to_img() + +print(grid) |