summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorJohannes Löthberg <johannes@kyriasis.com>2016-07-23 01:14:27 +0200
committerJohannes Löthberg <johannes@kyriasis.com>2016-07-23 01:14:27 +0200
commite1ed22231d955eedf3895adf72fd3fbbeb133376 (patch)
tree7741d2c4cfa2eac191def2a272b1cfa7dad57d95
downloadmaze-e1ed22231d955eedf3895adf72fd3fbbeb133376.tar.xz
Initial commit
Signed-off-by: Johannes Löthberg <johannes@kyriasis.com>
-rw-r--r--binary_tree.py17
-rw-r--r--binary_tree_demo.py7
-rw-r--r--cell.py47
-rw-r--r--grid.py124
-rw-r--r--maze.py50
-rw-r--r--requirements.txt1
-rw-r--r--sidewinder.py28
-rw-r--r--sidewinder_demo.py8
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)
diff --git a/cell.py b/cell.py
new file mode 100644
index 0000000..eb71cb3
--- /dev/null
+++ b/cell.py
@@ -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)
diff --git a/grid.py b/grid.py
new file mode 100644
index 0000000..8cc442a
--- /dev/null
+++ b/grid.py
@@ -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')
diff --git a/maze.py b/maze.py
new file mode 100644
index 0000000..bea4808
--- /dev/null
+++ b/maze.py
@@ -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)