\n",
"\n",
"# Making and Solving Mazes\n",
"\n",
"Let's make some mazes! I'm thinking of mazes like this one, which is a rectangular grid of squares, with walls on some of the sides of squares, and openings on other sides. The goal is to get from the red arrow to the green arrow.\n",
"\n",
"![Wikipedia](https://upload.wikimedia.org/wikipedia/commons/thumb/8/88/Maze_simple.svg/475px-Maze_simple.svg.png)\n",
"\n",
"The two main constraints are that there should be a path from entrance to exit, and it should be ***fun*** to solve the maze with pencil, paper, and brain power—not too easy, but also not impossible. \n",
"\n",
"As I think about how to model a maze on the computer, it seems like a **graph** is the right model: the nodes of\n",
"the graph are the squares of the grid, and the edges of the graph are the openings between adjacent squares. So what properties of a graph make a good maze?\n",
"- There must be a path from entrance to exit.\n",
"- There must not be too many such paths; maybe it is best if there is only one. \n",
"- Probably the graph should be *singly connected*—there shouldn't be islands of squares that are unreachable from the start. In fact, maybe we want exactly one path between any two squares.\n",
"- The path should have many twists; it would be too easy if it was mostly straight.\n",
"\n",
"I know that a **tree** has all these properties except the last one. So my goal has become: *Superimpose a tree over the grid, covering every square, and make sure the paths are twisty.* Here's how I'll do it:\n",
"\n",
"- Start with a grid with no edges (every square is surrounded by walls on all sides). \n",
"- Add edges (that is, knock down walls) for the entrance at upper left and exit at lower right.\n",
"- Place the root of the tree in some square.\n",
"- Then repeat until the tree covers the whole grid:\n",
" * Select some node already in the tree.\n",
" * Randomly select a neighbor that hasn't been added to the tree yet.\n",
" * Add an edge (knock down the wall) from the node to the neighbor.\n",
" \n",
"In the example below, the root, `A`, has been placed in the upper-left corner, and two branches,\n",
"`A-B-C-D` and `A-b-c-d`, have been randomly chosen (well, not actually random; they are starting to create the same maze as in the diagram above):\n",
"\n",
" o o--o--o--o--o--o--o--o--o--o\n",
" | A b c| | | | | | | |\n",
" o o--o o--o--o--o--o--o--o--o\n",
" | B| | d| | | | | | | |\n",
" o o--o--o--o--o--o--o--o--o--o\n",
" | C D| | | | | | | | |\n",
" o--o--o--o--o--o--o--o--o--o--o\n",
" | | | | | | | | | | |\n",
" o--o--o--o--o--o--o--o--o--o--o\n",
" | | | | | | | | | | |\n",
" o--o--o--o--o--o--o--o--o--o o\n",
" \n",
"Next I select node `d` and extend it to `e` (at which point there are no available neighbors, so `e` will not be selected in the future), and then I select `D` and extend from there all the way to `N`, at each step selecting the node I just added:\n",
"\n",
" o o--o--o--o--o--o--o--o--o--o\n",
" | A b c| | | | | | | |\n",
" o o--o o--o--o--o--o--o--o--o\n",
" | B| e d| | N| | | | | |\n",
" o o--o--o--o o--o--o--o--o--o\n",
" | C D| | | M| | | | | |\n",
" o--o o--o--o o--o--o--o--o--o\n",
" | F E| | K L| | | | | |\n",
" o o--o--o o--o--o--o--o--o--o\n",
" | G H I J| | | | | | |\n",
" o--o--o--o--o--o--o--o--o--o o\n",
" \n",
"Continue like this until every square in the grid has been added to the tree. At that point there will be a path from start to goal. Some walls will remain; some will be knocked down.\n",
"\n",
"\n",
"# Making Random Trees\n",
"\n",
"I'll make the following implementation choices:\n",
"\n",
"- A tree will be represented as a set of edges.\n",
"- An `Edge` is a tuple of two nodes. Edges are bidirectional, so to avoid confusion we will always us the tuple that is in sorted order: always `(A, B)`, never `(B, A)`. The constructor `edge` enforces that.\n",
"- A node in a tree can be anything: a number, a letter, ... In this notebook we will make trees where the nodes are squares in a grid, but the function `random_tree` accepts nodes of any type.\n",
"- The algorithm for `random_tree(nodes, neighbors, pop)` works as follows:\n",
" * The arguments are:\n",
" - `nodes`: a collection of nodes.\n",
" - `neighbors`: a function such that `neighbors(node)` returns a set of nodes.\n",
" - `pop`: a function such that `pop(frontier)` removes and returns an element from `frontier`.\n",
" * The function keeps track of three collections:\n",
" - `tree`: a set of edges that constitutes the tree.\n",
" - `nodes`: the set of nodes that have not yet been added to the tree, but will be.\n",
" - `frontier`: a queue of nodes in the tree that are eligible to have an edge added.\n",
" * On each iteration:\n",
" - Use `pop` to pick a `node` from the frontier, and find the neighbors that are not already in the tree.\n",
" - If there are any neighbors, randomly pick one (`nbr`), add `edge(node, nbr)` to `tree`, remove the\n",
" neighbor from `nodes`, and keep both the node and the neighbor on the frontier. If there are no neighbors,\n",
" drop the node from the frontier.\n",
" * When no `nodes` remain, return `tree`."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"import random\n",
"from collections import deque, namedtuple\n",
"\n",
"Edge = tuple\n",
"Tree = set\n",
"\n",
"def edge(A, B) -> Edge: return Edge(sorted([A, B]))\n",
"\n",
"def random_tree(nodes, neighbors, pop=deque.pop) -> Tree:\n",
" \"\"\"Repeat: pop a node and add edge(node, nbr) until all nodes have been added to tree.\"\"\"\n",
" tree = Tree()\n",
" nodes = set(nodes)\n",
" root = nodes.pop()\n",
" frontier = deque([root])\n",
" while nodes:\n",
" node = pop(frontier)\n",
" nbrs = neighbors(node) & nodes\n",
" if nbrs:\n",
" nbr = random.choice(list(nbrs))\n",
" tree.add(edge(node, nbr))\n",
" nodes.remove(nbr)\n",
" frontier.extend([node, nbr])\n",
" return tree"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Making Random Mazes\n",
"\n",
"Now let's use `random_tree` to implement `random_maze`. Basically, we just create a collection of `(x, y)` squares, pass these to `random_tree`, and let it do the work. Note that:\n",
"\n",
"* A `Maze` is a named tuple with three fields: the `width` and `height` of the grid, and a set of `edges` between squares. \n",
"* A square is denoted by an `(x, y)` tuple of integer coordinates.\n",
"* The function `neighbors4(square)` gives the four surrounding squares."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"Maze = namedtuple('Maze', 'width, height, edges')\n",
"\n",
"Square = tuple\n",
"\n",
"def neighbors4(square) -> {Square}:\n",
" \"\"\"The 4 neighbors of an (x, y) square.\"\"\"\n",
" (x, y) = square\n",
" return {(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)}\n",
"\n",
"def grid(width, height) -> {Square}: \n",
" \"\"\"All squares in a grid of these dimensions.\"\"\"\n",
" return {(x, y) for x in range(width) for y in range(height)}\n",
"\n",
"def random_maze(width, height, pop=deque.pop) -> Maze:\n",
" \"\"\"Generate a random maze, using random_tree.\"\"\"\n",
" tree = random_tree(grid(width, height), neighbors4, pop)\n",
" return Maze(width, height, tree)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"I'll make a 10x5 maze, as in the diagram at the top of this notebook:"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Maze(width=10, height=5, edges={((2, 1), (3, 1)), ((5, 0), (5, 1)), ((8, 3), (8, 4)), ((6, 2), (6, 3)), ((6, 4), (7, 4)), ((8, 0), (8, 1)), ((5, 3), (6, 3)), ((5, 4), (6, 4)), ((0, 2), (1, 2)), ((1, 0), (2, 0)), ((4, 3), (4, 4)), ((0, 2), (0, 3)), ((2, 0), (2, 1)), ((2, 1), (2, 2)), ((7, 0), (7, 1)), ((7, 4), (8, 4)), ((6, 0), (7, 0)), ((8, 0), (9, 0)), ((6, 1), (6, 2)), ((0, 3), (1, 3)), ((2, 3), (2, 4)), ((7, 1), (7, 2)), ((0, 4), (1, 4)), ((3, 2), (3, 3)), ((8, 1), (9, 1)), ((9, 1), (9, 2)), ((4, 2), (5, 2)), ((7, 3), (8, 3)), ((4, 0), (4, 1)), ((2, 4), (3, 4)), ((1, 0), (1, 1)), ((3, 1), (4, 1)), ((1, 1), (1, 2)), ((3, 3), (3, 4)), ((0, 0), (1, 0)), ((5, 1), (5, 2)), ((5, 0), (6, 0)), ((3, 4), (4, 4)), ((0, 0), (0, 1)), ((0, 3), (0, 4)), ((9, 2), (9, 3)), ((1, 3), (2, 3)), ((9, 3), (9, 4)), ((3, 0), (4, 0)), ((5, 3), (5, 4)), ((7, 2), (8, 2)), ((3, 2), (4, 2)), ((6, 0), (6, 1)), ((8, 2), (9, 2))})"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"random_maze(10, 5)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"That's not very pretty to look at. I'm going to need a way to visualize a maze.\n",
"\n",
"# Plotting a maze\n",
"\n",
"I will use `matplotlib` to plot the walls of a maze. I'm going to look ahead to when we have a *solution path,* and allow that to be plotted as well."
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [],
"source": [
"%matplotlib inline\n",
"import matplotlib.pyplot as plt\n",
"\n",
"def plot_maze(maze, figsize=None, path=None):\n",
" \"\"\"Plot a maze by drawing lines between adjacent squares, except for pairs in maze.edges\"\"\"\n",
" w, h = maze.width, maze.height\n",
" plt.figure(figsize=figsize or (w/5, h/5))\n",
" plt.axis('off')\n",
" plt.gca().invert_yaxis()\n",
" exits = {edge((0, 0), (0, -1)), edge((w-1, h-1), (w-1, h))}\n",
" edges = maze.edges | exits\n",
" for sq in grid(w, h):\n",
" for nbr in neighbors4(sq):\n",
" if edge(sq, nbr) not in edges:\n",
" plot_wall(sq, nbr)\n",
" if path: # Plot the solution (or any path) as a red line through the maze\n",
" X, Y = transpose((x + 0.5, y + 0.5) for (x, y) in path)\n",
" plt.plot(X, Y, 'r-', linewidth=2)\n",
" \n",
"def transpose(matrix): return list(zip(*matrix))\n",
"\n",
"def plot_wall(s1, s2):\n",
" \"\"\"Plot a wall: a black line between squares s1 and s2.\"\"\"\n",
" (x1, y1), (x2, y2) = s1, s2\n",
" if x1 == x2: # horizontal wall\n",
" y = max(y1, y2)\n",
" X, Y = [x1, x1+1], [y, y]\n",
" else: # vertical wall\n",
" x = max(x1, x2)\n",
" X, Y = [x, x], [y1, y1+1]\n",
" plt.plot(X, Y, 'k-', linewidth=2)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's see what it looks like:"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAASUAAACWCAYAAACYTp4YAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAACuklEQVR4nO3dQU7cQBRFUTvK/rdcGSFlQCSi2MWtn3MWALS7uTxG/15rXQAVP777BwD4nSgBKaIEpIgSkCJKQIooASmiBKSIEpAiSkCKKAEpogSk/Hzyi933va7rutZa95Nf97PvAbQ89XtvKQEpjy6lHd5cYRPtWK+7THotkzz934ulBKSIEpAiSkCKKAEpogSkiBKQIkpAiigBKaIEpIgSkCJKQIooASmiBKSIEpAiSkCKKAEpogSkiBKQIkpAiigBKaIEpIgSkHLciaWJxygnnAzaef5o0mdgx+HW0z5flhKQctxS+nBa/fl3k97zSWvvaZYSkCJKQIooASmiBKSIEpAiSkCKKAEpogSkiBKQIkpAiigBKaIEpIgSkCJKQIooASmiBKSIEpAiSkCKKAEpogSkiBKQcuw1E9cgmqa8L5Mup5zGUgJSjl1K/pJ9ze7l4n35Gs/pzywlIEWUgBRRAlJECUgRJSBFlIAUUQJSRAlIESUgRZSAFFECUkQJSBElIEWUgBRRAlJECUgRJSBFlIAUUQJSRAlIESUgRZSAlGNPLL1t52miSed2phyj5PtYSkDKcUtp96qYtGLe5Dn9nY9F+eZzO3W1WkpAiigBKaIEpIgSkCJKQIooASmiBKSIEpAiSkCKKAEpogSkiBKQIkpAiigBKaIEpIgSkCJKQIooASmiBKSIEpAiSkCKKAEpx51YOvVszGd2vpZJz43ZLCUg5biltOvo4Y5l4YAjbzr182UpASmiBKSIEpAiSkCKKAEpogSkiBKQIkpAiigBKaIEpIgSkCJKQIooASmiBKSIEpAiSkCKKAEpogSkiBKQIkpAiigBKaIEpLxyYmnS4cNJr4X/02mnliwlIOVeyxAAOiwlIEWUgBRRAlJECUgRJSBFlIAUUQJSRAlIESUgRZSAFFECUn4BAo5mOYT9KpYAAAAASUVORK5CYII=\n",
"text/plain": [
"