Initial commit

Signed-off-by: Johannes Löthberg <johannes@kyriasis.com>

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)