-
Notifications
You must be signed in to change notification settings - Fork 1
/
index.html
500 lines (362 loc) · 22.9 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
<!DOCTYPE html>
<html lang="en" dir="ltr">
<head>
<meta charset="utf-8">
<title>PathFinder: The Amazing Maze Algorithm Demonstrator!</title>
<script src='dist/main.js'></script>
<link href="https://fonts.googleapis.com/css?family=Roboto:400,400i,700" rel="stylesheet">
<link rel="stylesheet" href="main.css">
</head>
<body>
<div id="github">
<a href="https://www.github.com/emmilco/path_finder">
<svg version="1.1"
xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:a="http://ns.adobe.com/AdobeSVGViewerExtensions/3.0/"
x="0px" y="0px" width="32.6px" height="31.8px" viewBox="0 0 32.6 31.8" style="enable-background:new 0 0 32.6 31.8;"
xml:space="preserve">
<style type="text/css">
.st0{fill-rule:evenodd;clip-rule:evenodd;fill:#191717;}
</style>
<path class="st0" d="M16.3,0C7.3,0,0,7.3,0,16.3c0,7.2,4.7,13.3,11.1,15.5c0.8,0.1,1.1-0.4,1.1-0.8c0-0.4,0-1.4,0-2.8
c-4.5,1-5.5-2.2-5.5-2.2c-0.7-1.9-1.8-2.4-1.8-2.4c-1.5-1,0.1-1,0.1-1c1.6,0.1,2.5,1.7,2.5,1.7c1.5,2.5,3.8,1.8,4.7,1.4
c0.1-1.1,0.6-1.8,1-2.2c-3.6-0.4-7.4-1.8-7.4-8.1c0-1.8,0.6-3.2,1.7-4.4C7.4,10.7,6.8,9,7.7,6.8c0,0,1.4-0.4,4.5,1.7
c1.3-0.4,2.7-0.5,4.1-0.5c1.4,0,2.8,0.2,4.1,0.5c3.1-2.1,4.5-1.7,4.5-1.7c0.9,2.2,0.3,3.9,0.2,4.3c1,1.1,1.7,2.6,1.7,4.4
c0,6.3-3.8,7.6-7.4,8c0.6,0.5,1.1,1.5,1.1,3c0,2.2,0,3.9,0,4.5c0,0.4,0.3,0.9,1.1,0.8c6.5-2.2,11.1-8.3,11.1-15.5
C32.6,7.3,25.3,0,16.3,0z"/>
</svg>
</a>
<a href="https://www.linkedin.com/in/elliot-milco"><img width="32.6px" src="linkedin.png" /></a>
<a href="http://www.elliotmilco.com">created by Elliot Milco</a>
</div>
<h1 id="making-mazes">PathFinder: Algorithms for Making and Solving Mazes</h1>
<h3 id="making-mazes">An interactive demo by Elliot Milco</h3>
<p><em>Click any box to generate a new maze.</em></p>
<div class="canvas-box-wrapper">
<div class="left-text">
<h2 id="spanning-trees-and-maze-design">Spanning Trees and Maze Design</h2>
<p>Mazes are designed to thwart our best intuitions about how to get from one place to another. In a well-designed maze, there is no straight path to the goal, and there are many dead ends along the way.</p>
<p>How would you go about building one?</p>
<p>Making a good maze requires a heavy dose of randomness. We want walls and paths to appear without any apparent order. But we do need there to be <em>some</em> order, otherwise the maze would be insoluble.</p>
</div>
<div class="canvas-wrapper">
<canvas id="0" width="495px" height="495px"></canvas>
<p class="caption">A* Search solving a maze generated using Prim's Algorithm.</p>
</div>
</div>
<div class="canvas-box-wrapper">
<div class="left-text">
<p>One way to provide the minimum necessary order to create a solvable maze is to build the maze as a spanning tree.</p>
<p>A <strong>spanning tree</strong> is a kind of network. It follows two simple rules: (1) Every available point must be connected to the network, and (2) no point can be connected to itself. Total coverage, no cycles.</p>
<p>There are many ways to generate spanning trees. Since points in a two-dimensional plane each have four neighbors, the easiest way for us will be to radiate outward from the start of the maze, connecting each point to all of its unconnected neighbors,
until the whole grid is connected.</p>
<p>This produces a pretty boring maze. How can we do better?</p>
</div>
<div class="canvas-wrapper">
<!-- BFS non-maze, B&W -->
<canvas id="1" width="495px" height="495px"></canvas>
<p class="caption">Our simplest maze.</p>
</div>
</div>
<div class="canvas-box-wrapper">
<div class="left-text">
<h2 id="randomized-growth">Randomized Growth</h2>
<p>Let's inject some randomness into our spanning tree generation. Here's the simplest way, represented as an algorithm:</p>
<ol style="list-style-type: decimal">
<li>Keep a list of possible path extensions, starting with just the entry point.</li>
<li>Pick a <strong>random element</strong> out of the list.</li>
<li>Will adding that point to the maze cause the maze to intersect itself?</li>
<li>If not, add that point to the maze, and add all of its unvisited neighbors to the list of possible path extensions.</li>
<li>Either way, mark that point as visited.</li>
<li>Repeat until the list is empty.</li>
</ol>
<p>This approach produces mazes like the one seen here.</p>
<p>The maze grows evenly and organically to fill the space. Each next path extension may be randomly chosen, but in any given round, all the available extensions have the same chance of being chosen. This way of structuring our randomness produces
locally unpredictable, but globally regular behavior.</p>
</div>
<div class="canvas-wrapper">
<!-- BFS maze, B&W -->
<canvas id="2" width="495px" height="495px"></canvas>
<p class="caption">A randomized growth maze.</p>
</div>
</div>
<div class="canvas-box-wrapper">
<div class="left-text">
<p>If we color the maze based on the path-distance of each segment from the starting point ("the root"), we can get a decent sense of its global structure:</p>
<p>Notice how the color gradient shifts evenly from the top left corner (the root), outward. This tells us that there aren't any crazy backtracking paths in the maze. But what if we wanted a maze that was more chaotic?</p>
</div>
<div class="canvas-wrapper">
<!-- BFS maze, Colored -->
<canvas id="3" width="495px" height="495px"></canvas>
<p class="caption">A randomized growth maze, colored by path-distance from the root.</p>
</div>
</div>
<div class="canvas-box-wrapper">
<div class="left-text">
<h2 id="weighted-randomness-prims-algorithm">Random Weights & Prim's Algorithm</h2>
<p>In our simple randomized growth algorithm, we used random selection from the set of candidate extensions to grow the maze. Because every node has a fresh chance in every drawing, the overall tendency is toward unbiased radial expansion outward from the root.</p>
<p>We want to put the randomness into the <em>global structure</em> instead of just the local path expansion. We can do this by assigning every square on the grid a random weight, and then using Prim's algorithm to build our maze.</p>
<p><strong>Prim's algorithm</strong> is a method for building a minimum spanning tree. A minimum spanning tree is a spanning tree that's designed to choose the <em>least expensive</em> way of connecting all the tree's nodes, based on the cost of drawing any particular connection.</p>
<p>Prim's accomplishes this by always using the least expensive available path extension. Because each node has a fixed weight, if a node is generated with a high weight, it will be selected against in every successive round until it is the least expensive remaining node.</p>
<p>For the most part, our implementation of Prim's algorithm is identical to our earlier algorithm. We add an initial step before our old step 1,</p>
<ol start="0" style="list-style-type: decimal">
<li>First, assign every potential square a random numerical weight.</li>
</ol>
<p>and we change step 2,</p>
<ol start="2" style="list-style-type: decimal">
<li>Pick the <strong>least expensive element</strong> out of the list.</li>
</ol>
<p>This approach produces mazes like the one seen here.</p>
</div>
<div class="canvas-wrapper">
<!-- Prim's maze, B&W -->
<canvas id="4" width="495px" height="995px"></canvas>
<p class="caption">A maze generated using randomized weight-assignment and Prim's algorithm.</p>
</div>
</div>
<div class="canvas-box-wrapper">
<div class="left-text">
<p>Let's color the maze to get a better sense of its global structure.</p>
<p>Notice that the randomized Prim's maze is much more complex, but that the local structure remains random. </p>
<p>This maze also constitutes a <em>good</em> maze from a straightforward design perspective: there are long, complex, blind alleys, and the path-distance of any given node is not easily predicted based on its position in the grid.</p>
</div>
<div class="canvas-wrapper">
<!-- Prim's maze, Colored -->
<canvas id="5" width="495px" height="495px"></canvas>
<p class="caption">A maze generated with Prim's algorithm, colored by path-distance from the root.</p>
</div>
</div>
<div class="canvas-box-wrapper">
<div class="left-text">
<h2 id="restricted-randomness-depth-first-growth">Restricted Randomness & Depth First Growth</h2>
<p>Before solving our mazes, let's try out one more generator. Suppose we wanted mazes with extremely deep, winding paths. How would we change our path-extension algorithm to produce that?</p>
<p>One way to create deep mazes is based on <strong>depth first search</strong> (DFS), a tree-searching algorithm. DFS sets its search trajectory to prioritize the current branch. In other words, it tries to keep going along a particular path as far as
possible before exploring other, earlier options.</p>
<p>A non-randomized depth-first growth maze looks like this:</p>
</div>
<div class="canvas-wrapper">
<!-- DFS non-maze, B&W -->
<canvas id="6" width="495px" height="495px"></canvas>
<p class="caption">Our simplest depth-first maze.</p>
</div>
</div>
<div class="canvas-box-wrapper">
<div class="left-text">
<p>In order to give our DFS maze some complexity, we choose randomly from the N most recently added elements in our list of possible path extensions.</p>
<p>Let's set N to 4, since any given node can have at most four valid unincorporated neighbor nodes. And here's our maze:</p>
</div>
<div class="canvas-wrapper">
<!-- DFS maze, B&W -->
<canvas id="7" width="495px" height="495px"></canvas>
<p class="caption">A randomized depth-first maze.</p>
</div>
</div>
<div class="canvas-box-wrapper">
<div class="left-text">
<p>When we colorize the DFS maze, its global structure becomes clear. Compare a DFS maze, top, with our initial random-growth maze, bottom. Notice how many times our DFS maze cycles through the color spectrum before it fills the space.</p>
<p>Depth first mazes are much deeper than random growth mazes of the same size. At this scale, they are generally about five times deeper, but that factor increases with the size of the maze.</p>
<p>However, there's a big downside to our DFS maze. Because DFS is biased in favor of extending the current branch of the tree, our maze ends up dominated by a couple of very long, locally simple corridors.</p>
<p>A we will see below, the solution to a DFS maze may be very convoluted, but it's often not hard to find.</p>
<p>Speaking of solving mazes, let's do some of that!</p>
</div>
<div class="maze-double">
<div class="canvas-wrapper">
<!-- DFS maze, Colorized -->
<canvas id="8" width="495px" height="495px"></canvas>
<p class="caption">Depth-first maze, colored by path distance from the root.</p>
</div>
<div class="canvas-wrapper">
<!-- BFS maze, Colorized -->
<canvas id="9" width="495px" height="495px"></canvas>
<p class="caption">Random expansion (breadth-first) maze, colored by path distance from the root.</p>
</div>
</div>
</div>
<div class="canvas-box-wrapper">
<div class="left-text">
<h1 id="maze-solvers">Maze Solvers</h1>
<h2 id="depth-first-search">Depth First Search</h2>
<p>Depth First Search is a simple algorithm for finding the path to a target node in a tree, given a starting point. DFS uses a stack to maintain a list of nodes to explore.</p>
<ol style="list-style-type: decimal">
<li>Start at the root.</li>
<li>Pop the last (i.e. most recently added) element off the stack.</li>
<li>Check for a match. If found, return the target node.</li>
<li>Add each of the current node's children to the stack.</li>
<li>Repeat until a match is found, or the stack is empty.</li>
</ol>
<p>The result is a search path that goes as deep as possible down a single branch before trying another branch. </p>
<p>To the right you can see DFS solving each of our three maze types. Whenever a given path segment is explored, the search algorithm colors it white to show where it's been.</p>
<p>I have placed the root of each maze in the exact center to better show the behavior of the algorithm.</p>
</div>
<div class="maze-double">
<div class="canvas-wrapper">
<!-- BFS maze, with DFS solver, root at center -->
<canvas id="10" width="495px" height="495px"></canvas>
<p class="caption">Breadth-first maze, solved by Depth First Search, root at center</p>
</div>
<div class="canvas-wrapper">
<!-- Prim's maze, with DFS solver, root at center -->
<canvas id="11" width="495px" height="495px"></canvas>
<p class="caption">Prim's maze, solved by Depth First Search, root at center</p>
</div>
<div class="canvas-wrapper">
<!-- DFS maze, with DFS solver, root at center -->
<canvas id="12" width="495px" height="495px"></canvas>
<p class="caption">Depth-first maze, solved by Depth First Search, root at center</p>
</div>
</div>
</div>
<div class="canvas-box-wrapper">
<div class="left-text">
<h2 id="breadth-first-search">Breadth First Search</h2>
<p>Breadth First Search is similar to DFS, but it treats the list of nodes to search as a queue instead of a stack. In other words, step 2 of the algorithm listed above becomes:</p>
<ol start="2" style="list-style-type: decimal">
<li>Shift the first (i.e. least recently added) element out of the queue.</li>
</ol>
<p>The result is the smooth radial expansion you see here.</p>
<p>Comparing BFS to DFS, we see that BFS is potentially much more expensive in terms of the number of nodes explored before finding the solution. This depends in part on the relative position of root and target within the maze.</p>
<p>If the path distance between root and target is small relative to the size of the maze, BFS (left) will tend to outperform DFS (right). Run the demo a few times to get a sense for their relative performance!</p>
</div>
<div class="canvas-wrapper">
<!-- BFS maze, BFS Solver, Root at center -->
<canvas id="13" width="495px" height="495px"></canvas>
<p class="caption">BFS solving a random expansion (breadth-first) maze, root at center.</p>
</div>
</div>
<div class="canvas-box-wrapper no-top">
<div class="canvas-wrapper no-left">
<!-- Prim's maze, BFS Solver, Root and Target near center -->
<canvas id="14" width="495px" height="495px"></canvas>
<p class="caption">BFS solving a Prim's maze, with root and target near center.</p>
</div>
<div class="canvas-wrapper">
<!-- Prim's maze, DFS Solver, Root and Target near center -->
<canvas id="15" width="495px" height="495px"></canvas>
<p class="caption">DFS solving a Prim's maze, with root and target near center.</p>
</div>
</div>
<div class="canvas-box-wrapper">
<div class="left-text">
<p>Both methods have their weak spots, though. If the root and target are maximally distant from each other within the maze, BFS will have to explore the entire tree before finding the goal, while DFS goes straight for the fringes.</p>
</div>
</div>
<div class="canvas-box-wrapper no-top">
<div class="canvas-wrapper no-left">
<!-- BFS maze, BFS Solver, Root at corner -->
<canvas id="16a" width="495px" height="495px"></canvas>
<p class="caption">BFS solving a random-growth maze, maximum distance between root and target.</p>
</div>
<div class="canvas-wrapper">
<!-- BFS maze, DFS Solver, Root at corner -->
<canvas id="16" width="495px" height="495px"></canvas>
<p class="caption">DFS solving a random-growth maze, maximum distance between root and target.</p>
</div>
</div>
<div class="canvas-box-wrapper">
<div class='left-text'>
<h2 id="dijkstras-algorithm">Dijkstra's Algorithm</h2>
</div>
</div>
<div class="canvas-box-wrapper no-top">
<div class="left-text">
<p>DFS and BFS are cool, and they're both guaranteed to find solutions under normal conditions (e.g. provided our maze is finite and our target is reachable). But they're not very smart. As we've seen above, both algorithms are agnostic about the structure
of the maze and the probability of success searching along any given trajectory. We can do better!</p>
<p>When we wanted to improve the structure of our generated maze, we used randomized weighting and Prim's algorithm. In order to build a smart maze solver, we're going to take a similar approach. In this case we will use a heuristic-guided improvement
on Dijkstra's algorithm called A* ("A-Star").</p>
<p><strong>Dijkstra's Algorithm</strong> is a path-finding method that prioritizes the least-expensive available node in our search queue. Typically we implement this using a <strong>min-heap priority queue</strong>, which is a <em>very speedy</em> data
structure for maintaining a list in which the first element is guaranteed to have the minimum value in the entire list. (Note, our implementation of Prim's above uses a priority queue like this too!)</p>
<p>In spanning trees like ours, Dijkstra's proceeds like BFS, with changes to step 2:</p>
<ol start="2" style="list-style-type: decimal">
<li>Remove the minimum entry from the priority queue.</li>
</ol>
<p>and step 4:</p>
<ol start="4" style="list-style-type: decimal">
<li>Insert each of the current node's children into the priority queue.</li>
</ol>
<p>So far so good. The only problem is that, because in reality our maze is an <em>unweighted</em> graph, there's actually no difference between the cost of exploring any one node and exploring any other. That means that our priority queue will honor a First-In, First-Out (FIFO) ordering principle, making Dijkstra's algorithm identical in execution to Breadth First Search.</p>
<p>So much for doing better! Dijkstra's algorithm really shines in weighted graphs with cycles, not in our unweighted, spanning tree mazes.</p>
</div>
<div class="canvas-wrapper">
<!-- BFS maze, Dijkstra solver -->
<canvas id="17" width="495px" height="995px"></canvas>
<p class="caption">Dijkstra's algorithm solving a random-growth maze. Looks a lot like BFS!</p>
</div>
</div>
<div class="canvas-box-wrapper">
<div class="left-text">
<h2 id="a-search">A* Search</h2>
<p>Now that we've built out a Dijkstra maze solver, though, we can use it to implement an intuition-based path-finding-algorithm called A*.</p>
<p>A* keeps track of two different factors. First, how expensive it was to get to a given node from the origin. Second, the minimum predicted cost of getting from that node to the goal. A* predicts the cost of traveling through a given node based on a
heuristic function we provide it, which is based on the structure of our graph.</p>
<p>In this case, we set the heuristic function to calculate the diagonal distance between the current node and the target node, so that our search will be encouraged to go as directly toward the goal as possible.</p>
<p>How does A* perform? You can see it in action on the right.</p>
<p>As with DFS I have placed the root of the maze at the center, to better illustrate the behavior of the algorithm.</p>
<p>You can see that when a relatively direct path is available, A* tends to find it, and quickly. A* also has an advantage when the root and target are close together, relative to the size of the graph.</p>
<p>A* doesn't always outperform DFS (or even BFS—intuition can lead us astray!), but it is about as good in the worst case, and better on average.</p>
</div>
<div class="maze-double">
<div class="canvas-wrapper">
<!-- BFS maze, A* solver, Root at center -->
<canvas id="18" width="495px" height="495px"></canvas>
<p class="caption">A* solving a random-growth maze, root at center.</p>
</div>
<div class="canvas-wrapper">
<!-- Prim's maze, A* solver, Root at center -->
<canvas id="19" width="495px" height="495px"></canvas>
<p class="caption">A* solving a Prim's maze, root at center.</p>
</div>
<div class="canvas-wrapper">
<!-- DFS maze, A* solver, Root at center -->
<canvas id="20" width="495px" height="495px"></canvas>
<p class="caption">A* solving a depth-first maze, root at center.</p>
</div>
</div>
</div>
<p>Finally, to sum up, you can see all three of our solvers solving all three of our mazes at once!</p>
<div class="final-recap">
<div class="canvas-wrapper">
<canvas id="21" width="495px" height="495px"></canvas>
<p class="caption">DFS solving a random-growth maze.</p>
</div>
<div class="canvas-wrapper">
<canvas id="22" width="495px" height="495px"></canvas>
<p class="caption">BFS solving a random-growth maze.</p>
</div>
<div class="canvas-wrapper">
<canvas id="23" width="495px" height="495px"></canvas>
<p class="caption">A* solving a random-growth maze.</p>
</div>
<div class="canvas-wrapper">
<canvas id="24" width="495px" height="495px"></canvas>
<p class="caption">DFS solving a depth-first maze.</p>
</div>
<div class="canvas-wrapper">
<canvas id="25" width="495px" height="495px"></canvas>
<p class="caption">BFS solving a depth-first maze.</p>
</div>
<div class="canvas-wrapper">
<canvas id="26" width="495px" height="495px"></canvas>
<p class="caption">A* solving a depth-first maze.</p>
</div>
<div class="canvas-wrapper">
<canvas id="27" width="495px" height="495px"></canvas>
<p class="caption">DFS solving a Prim's maze.</p>
</div>
<div class="canvas-wrapper">
<canvas id="28" width="495px" height="495px"></canvas>
<p class="caption">BFS solving a Prim's maze.</p>
</div>
<div class="canvas-wrapper">
<canvas id="29" width="495px" height="495px"></canvas>
<p class="caption">A* solving a Prim's maze.</p>
</div>
</div>
<div class="canvas-wrapper" style="width: 90%">
<canvas id="30" width="1495px" height="1495px"></canvas>
<p class="caption">Just for fun, A* solving a gigantic Prim's maze.</p>
</div>
<div class="canvas-wrapper" style="width: 90%">
<canvas id="31" width="1495px" height="1495px"></canvas>
<p class="caption">Just for fun, DFS solving a gigantic Prim's maze.</p>
</div>
</body>
</html>