Add maze blog article to repo

scipython · Jun 13, 2018 · 51aa57c · 51aa57c
1 parent 8d4d361
commit 51aa57c
Show file tree

Hide file tree

Showing 4 changed files with 465 additions and 0 deletions.
diff --git a/.gitignore b/.gitignore
@@ -4,3 +4,4 @@
 *.db
 .DS_Store
 .coverage
+maze/ca_frames/*
diff --git a/maze/ca_maze.py b/maze/ca_maze.py
@@ -0,0 +1,46 @@
+import numpy as np
+from scipy.signal import convolve2d
+import matplotlib.pyplot as plt
+
+# Create a maze using the cellular automaton approach described at
+# https://scipython.com/blog/maze-generation-by-cellular-automaton/
+# The frames for animation of the growth of the maze are saved to
+# the subdirectory ca_frames/.
+# Christian Hill, January 2018.
+
+def ca_step(X):
+    """Evolve the maze by a single CA step."""
+
+    K = np.ones((3, 3))
+    n = convolve2d(X, K, mode='same', boundary='wrap') - X
+    return (n == 3) | (X & ((n > 0) & (n < 6)))
+
+# Maze size
+nx, ny = 200, 150
+X = np.zeros((ny, nx), dtype=np.bool)
+# Size of initial random area (must be even numbers)
+mx, my = 20, 16
+
+# Initialize a patch with a random mx x my region
+r = np.random.random((my, mx)) > 0.75
+X[ny//2-my//2:ny//2+my//2, nx//2-mx//2:nx//2+mx//2] = r
+
+# Total number of iterations
+nit = 400
+# Make an image every ipf iterations
+ipf = 10
+
+# Figure dimensions (pixels) and resolution (dpi)
+width, height, dpi = 600, 450, 10
+fig = plt.figure(figsize=(width/dpi, height/dpi), dpi=dpi)
+ax = fig.add_subplot(111)
+
+for i in range(nit):
+    X = ca_step(X)
+    if not i % ipf:
+        print('{}/{}'.format(i,nit))
+        im = ax.imshow(X, cmap=plt.cm.binary, interpolation='nearest')
+        plt.axis('off')
+        plt.savefig('ca_frames/_img{:04d}.png'.format(i), dpi=dpi)
+        plt.cla()
+
diff --git a/maze/df_maze.py b/maze/df_maze.py
@@ -0,0 +1,176 @@
+# df_maze.py
+import random
+
+# Create a maze using the depth-first algorithm described at
+# https://scipython.com/blog/making-a-maze/
+# Christian Hill, April 2017.
+
+class Cell:
+    """A cell in the maze.
+
+    A maze "Cell" is a point in the grid which may be surrounded by walls to
+    the north, east, south or west.
+
+    """
+
+    # A wall separates a pair of cells in the N-S or W-E directions.
+    wall_pairs = {'N': 'S', 'S': 'N', 'E': 'W', 'W': 'E'}
+
+    def __init__(self, x, y):
+        """Initialize the cell at (x,y). At first it is surrounded by walls."""
+
+        self.x, self.y = x, y
+        self.walls = {'N': True, 'S': True, 'E': True, 'W': True}
+
+    def has_all_walls(self):
+        """Does this cell still have all its walls?"""
+
+        return all(self.walls.values())
+
+    def knock_down_wall(self, other, wall):
+        """Knock down the wall between cells self and other."""
+
+        self.walls[wall] = False
+        other.walls[Cell.wall_pairs[wall]] = False
+
+class Maze:
+    """A Maze, represented as a grid of cells."""
+
+    def __init__(self, nx, ny, ix=0, iy=0):
+        """Initialize the maze grid.
+        The maze consists of nx x ny cells and will be constructed starting
+        at the cell indexed at (ix, iy).
+
+        """
+
+        self.nx, self.ny = nx, ny
+        self.ix, self.iy = ix, iy
+        self.maze_map = [[Cell(x, y) for y in range(ny)] for x in range(nx)]
+
+    def cell_at(self, x, y):
+        """Return the Cell object at (x,y)."""
+
+        return self.maze_map[x][y]
+
+    def __str__(self):
+        """Return a (crude) string representation of the maze."""
+
+        maze_rows = ['-' * nx*2]
+        for y in range(ny):
+            maze_row = ['|']
+            for x in range(nx):
+                if self.maze_map[x][y].walls['E']:
+                    maze_row.append(' |')
+                else:
+                    maze_row.append('  ')
+            maze_rows.append(''.join(maze_row))
+            maze_row = ['|']
+            for x in range(nx):
+                if self.maze_map[x][y].walls['S']:
+                    maze_row.append('-+')
+                else:
+                    maze_row.append(' +')
+            maze_rows.append(''.join(maze_row))
+        return '\n'.join(maze_rows)
+
+    def write_svg(self, filename):
+        """Write an SVG image of the maze to filename."""
+
+        aspect_ratio = self.nx / self.ny
+        # Pad the maze all around by this amount.
+        padding = 10
+        # Height and width of the maze image (excluding padding), in pixels
+        height = 500
+        width = int(height * aspect_ratio)
+        # Scaling factors mapping maze coordinates to image coordinates
+        scy, scx = height / ny, width / nx
+
+        def write_wall(f, x1, y1, x2, y2):
+            """Write a single wall to the SVG image file handle f."""
+
+            print('<line x1="{}" y1="{}" x2="{}" y2="{}"/>'
+                                .format(x1, y1, x2, y2), file=f)
+
+        # Write the SVG image file for maze
+        with open(filename, 'w') as f:
+            # SVG preamble and styles.
+            print('<?xml version="1.0" encoding="utf-8"?>', file=f)
+            print('<svg xmlns="http://www.w3.org/2000/svg"', file=f)
+            print('    xmlns:xlink="http://www.w3.org/1999/xlink"', file=f)
+            print('    width="{:d}" height="{:d}" viewBox="{} {} {} {}">'
+                    .format(width+2*padding, height+2*padding,
+                        -padding, -padding, width+2*padding, height+2*padding),
+                  file=f)
+            print('<defs>\n<style type="text/css"><![CDATA[', file=f)
+            print('line {', file=f)
+            print('    stroke: #000000;\n    stroke-linecap: square;', file=f)
+            print('    stroke-width: 5;\n}', file=f)
+            print(']]></style>\n</defs>', file=f)
+            # Draw the "South" and "East" walls of each cell, if present (these
+            # are the "North" and "West" walls of a neighbouring cell in
+            # general, of course).
+            for x in range(nx):
+                for y in range(ny):
+                    if maze.cell_at(x,y).walls['S']:
+                        x1, y1, x2, y2 = x*scx, (y+1)*scy, (x+1)*scx, (y+1)*scy
+                        write_wall(f, x1, y1, x2, y2)
+                    if maze.cell_at(x,y).walls['E']:
+                        x1, y1, x2, y2 = (x+1)*scx, y*scy, (x+1)*scx, (y+1)*scy
+                        write_wall(f, x1, y1, x2, y2)
+            # Draw the North and West maze border, which won't have been drawn
+            # by the procedure above. 
+            print('<line x1="0" y1="0" x2="{}" y2="0"/>'.format(width), file=f)
+            print('<line x1="0" y1="0" x2="0" y2="{}"/>'.format(height),file=f)
+            print('</svg>', file=f)
+
+    def find_valid_neighbours(self, cell):
+        """Return a list of unvisited neighbours to cell."""
+
+        delta = [('W', (-1,0)),
+                 ('E', (1,0)),
+                 ('S', (0,1)),
+                 ('N', (0,-1))]
+        neighbours = []
+        for direction, (dx,dy) in delta:
+            x2, y2 = cell.x + dx, cell.y + dy
+            if (0 <= x2 < nx) and (0 <= y2 < ny):
+                neighbour = maze.cell_at(x2, y2)
+                if neighbour.has_all_walls():
+                    neighbours.append((direction, neighbour))
+        return neighbours
+
+    def make_maze(self):
+        # Total number of cells.
+        n = self.nx * self.ny
+        cell_stack = []
+        current_cell = self.cell_at(ix, iy)
+        # Total number of visited cells during maze construction.
+        nv = 1
+
+        while nv < n:
+            neighbours = self.find_valid_neighbours(current_cell)
+
+            if not neighbours:
+                # We've reached a dead end: backtrack.
+                current_cell = cell_stack.pop()
+                continue
+
+            # Choose a random neighbouring cell and move to it.
+            direction, next_cell = random.choice(neighbours)
+            current_cell.knock_down_wall(next_cell, direction)
+            cell_stack.append(current_cell)
+            current_cell = next_cell
+            nv += 1
+
+# Maze dimensions (ncols, nrows)
+nx, ny = 15, 15
+# Maze entry position
+ix, iy = 0, 0
+
+maze = Maze(nx, ny, ix, iy)
+maze.make_maze()
+
+print(maze)
+maze.write_svg('maze.svg')
+
+