-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathindex.html
227 lines (226 loc) · 13.7 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
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>Maze Race</title>
<link rel="stylesheet" href="./lib/assets/css/style.css" media="screen" title="no title">
<script src="https://use.fontawesome.com/47840e1e1f.js"></script>
<script src="./lib/vendor/async.js" charset="utf-8"></script>
<script src="./lib/vendor/raphael.js" charset="utf-8"></script>
<script src="./lib/bundle.js" charset="utf-8"></script>
</head>
<body>
<nav class="pos-f 50-px-tall p top-nav red-bg">
<a href="./" class="white-font darkblue-font-hover 24px-font logo bold">
MazeRace
</a>
<ul class="pull-right">
<li class="p-r">
<a href="#" modal="#about" class="white-font darkblue-font-hover bold-hover">
About
</a>
</li>
<li class="p-r">
<a href="https://www.linkedin.com/in/toddnestor" target="_blank" class="white-font darkblue-font-hover bold-hover">
LinkedIn
</a>
</li>
<li class="p-r">
<a href="http://toddnestor.com" target="_blank" class="white-font darkblue-font-hover bold-hover">
Portfolio
</a>
</li>
<li class="p-r">
<a href="https://github.com/toddnestor/mazerace" target="_blank" class="white-font darkblue-font-hover bold-hover">
GitHub
</a>
</li>
</ul>
</nav>
<div class="row">
<div class="col-8 p-lg pos-r" id="chooser-grid">
</div>
<div class="col-4 p-lg controls-parent">
<div class="controls">
<div class="header text-center white-font red-bg p">
Controls
</div>
<div class="demo">
<button class="demo-button red-bg m white-font bold">Demo</button>
</div>
<div class="instructions darkblue-font p">
<span class="bold asterisk">Instructions: </span> Drag the <span class="emerald-font bold">green</span> square to set the start position.
Drag the <span class="red-font bold">red</span> square to set the end position.
Click any of the white squares and drag to set the walls.
Click a wall (the <span class="lightgrey-font bold">gray</span> squares) and drag to remove the walls.
<p class="m-t">
Choose two algorithms to watch them "race" each other, or choose one just to watch it go!
</p>
</div>
<div class="m-t-md algorithm-selection">
<h3 class="text-center">Algorithms <small class="grey-font">(select up to two)</small></h3>
<div class="text-center m-t hidden" id="did-it-wrong"><span class="red-font bold asterisk">You must select at least one algorithm</span></div>
<ul class="p-l p-r m-t-md">
</ul>
</div>
<div class="m-t-md algorithm-options">
<h3 class="text-center">Options</h3>
<ul class="p-l p-r m-t-md">
<li>
<label>
<input type="checkbox" checked id="allow-diagonal" /> Allow diagonal
</label>
</li>
<li>
<label>
<input type="number" id="delay" min="0" value="10" /> Delay
</label>
</li>
</ul>
</div>
<div class="m control-buttons text-center m-t-lg">
<span class="tooltip" title="Solve maze">
<i class="fa fa-play fa-4x emerald-font p pointer play-button control-button"></i>
</span>
<span class="tooltip" title="Pause">
<i class="fa fa-pause fa-4x grey-font p pointer pause-button control-button hidden"></i>
</span>
<span class="tooltip" title="Reset">
<i class="fa fa-refresh fa-4x pomegranate-font p pointer restart-button control-button"></i>
</span>
<span class="tooltip" title="Clear walls and reset">
<i class="fa fa-eraser fa-4x pink-font p pointer erase-button control-button"></i>
</span>
</div>
</div>
</div>
<div class="col-6 p-lg text-center">
<h2 class="darkblue-font text-center bold m-b algorithm1"></h2>
<div id="firstAlgorithm" class="pos-r"></div>
</div>
<div class="col-6 p-lg text-center">
<h2 class="darkblue-font text-center bold m-b algorithm2"></h2>
<div id="secondAlgorithm" class="pos-r"></div>
</div>
</div>
<div class="modal hidden">
<div class="content p-lg">
<span class="pos-a darkgrey-font close">×</span>
<div class="body">
</div>
</div>
</div>
<div id="about" class="hidden">
<div class="darkblue-font">
<h2 class="text-center m-b-md">About MazeRace</h2>
<p class="p">
MazeRace compares algorithms such as Breadth First Search, A*, Best First Search, and Depth First Search. Maze Race is inspired by Pathfinder.js
</p>
<p class="p">
It shows a visual representation of how the algorithms work. It also shows those algorithms happening side-by-side for a visual comparison. Like Pathfinder.js, Maze race has a grid where a start and end point can be placed. Walls can also be placed that the search algorithms will have to go around when searching for the endpoint.
</p>
<p class="p">
Users can create the maze by setting the start/end positions and placing walls on a grid. Then they can choose from the algorithm options and watch how the maze gets solved, and compare the algorithms with each other.
</p>
<p class="p">
When the user presses "Start" the grid is duplicated and side-by-side grids are displayed. Each step lights up the square actively being searched on each grid based on the algorithms being used. A square remains lit up until one of it's children squares is searched so the perimeter that has been searched will be lit up. When the end is found a line will be rendered to show the path from the start point to the end point.
</p>
<p class="p">
One thing to keep in mind is that in MazeRace it is only considered one step to get from a square to it's neighbor regardless of whether the neighbor is diagonal from the square or not. This leads to paths that are considred equal lengths even though one may technically be longer due to diagonal movement.
</p>
</div>
</div>
<div id="bfs" class="hidden">
<div class="darkblue-font">
<h2 class="text-center m-b-md">Breadth First Search</h2>
<p class="p">
In a <span class="bold">Breadth First Search</span>, we start by processing the starting node (in the context of Maze Race, nodes are squares) and getting it's neighbors.
</p>
<p class="p">
We check each of it's neighbors to see if they are the target (or ending square), if they are we return that target and then trace the path from it back to the starting node.
If we don't find the target we add each of the neighbors to the queue and then we start the process over taking the node from the queue that has been in there the longest (this is known as "First In First Out") and processing it the same way as the starting node.
</p>
<p class="p">
We continue this process until we find the target or the queue is empty. This method ensures if we do find the target, we found the shortest path to it also as it was the first path we found while checking every possible path.
</p>
<p class="p">
To be able to trace the path back to the starting node, we set the parent of each of a node's neighbors to the node itself. Then to trace the path from the target we simply follow it's the parent of each node until we reach the starting node.
</p>
</div>
</div>
<div id="dfs" class="hidden">
<div class="darkblue-font">
<h2 class="text-center m-b-md">Depth First Search</h2>
<p class="p">
In a <span class="bold">Depth First Search</span>, we start by processing the starting node (in the context of Maze Race, nodes are squares) and getting it's neighbors.
</p>
<p class="p">
We check each of it's neighbors to see if they are the target (or ending square), if they are we return that target and then trace the path from it back to the starting node.
If we don't find the target we add each of the neighbors to the stack and then we start the process over taking the node from the stack that was most recently added, this is known as "Last In First Out."
</p>
<p class="p">
We contiue this process until we find the target or the queue is empty. This method does not return the shortest path as it just keeps checking neighbors of the last node added until it reaches the target. It is not an effective algorithm to solve a maze.
</p>
<p class="p">
To be able to trace the path back to the starting node, we set the parent of each of a node's neighbors to the node itself. Then to trace the path from the target we simply follow it's the parent of each node until we reach the starting node.
</p>
</div>
</div>
<div id="best" class="hidden">
<div class="darkblue-font">
<h2 class="text-center m-b-md">Best First Search</h2>
<p class="p">
In a <span class="bold">Best First Search</span>, we start by processing the starting node (in the context of Maze Race, nodes are squares) and getting it's neighbors.
</p>
<p class="p">
We check each of it's neighbors to see if they are the target (ending square), if they are we return that target and then trace the path from it back to the starting node.
If we don't find the target we add each of the neighbors to the store and then we start the process over taking the node that is closest to the target.
In Maze Race closeness is calculated as the distance between the square and the target.
</p>
<p class="p">
To optimize grabbing the square closest to the target each time we use a priority queue (implemented using a heap).
With the priority queue grabbing the item closest to the end square is done in O(log n) time, and inserting items into the store also takes O(log n) time.
</p>
<p class="p">
This is a vast improvement over the O(n) (linear) time that would be used if we had to iterate through the store each time to find the closest square.
</p>
<p class="p">
We contiue this process until we find the target or the queue is empty. This method does not necessarily return the shortest path, just the quickest to find.
</p>
<p class="p">
To be able to trace the path back to the starting node, we set the parent of each of a node's neighbors to the node itself. Then to trace the path from the target we simply follow it's the parent of each node until we reach the starting node.
</p>
</div>
</div>
<div id="astar" class="hidden">
<div class="darkblue-font">
<h2 class="text-center m-b-md">A*</h2>
<p class="p">
In an <span class="bold">A*</span>, we start by processing the starting node (in the context of Maze Race, nodes are squares) and getting it's neighbors.
<span class="bold">A*</span> is a type of <span class="bold">Best First Search</span> that returns the shortest route.
</p>
<p class="p">
We check each of it's neighbors to see if they are the target (or ending square), if they are we return that target and then trace the path from it back to the starting node.
If we don't find the target we add each of the neighbors to the stack and then we start the process over taking the node that is closest to the target. In Maze Race closeness is calculated as the distance between the square and the target.
</p>
<p class="p">
We contiue this process until we find the target or the queue is empty. Unlike the more generic <span class="bold">Best First Search</span>, the <span class="bold">A*</span> search returns the shortest path.
</p>
<p class="p">
Like the Best First Search, A* also utilizes a priority queue (implemented using a heap) to speed up the square selection when grabbing the next square to test. See the description of the Best First Search for more details on that.
</p>
<p class="p">
To be able to have the shortest path, in addition to setting the parent of each of a square's neighbors to itself, it also keeps track of how many steps it took to get to each square.
When checking neighbors, if a neighbor already has a parent it checks to see how many steps it took to get to that square from its parent. If it took less to get to the current square plus one, then it sets the neighbor square's parent to itself, and the steps count to get to that neighbor to that of the current square plus one.
</p>
<p class="p">
This ensures each square's parent is the one with the shortest route from the start, ensuring that we have the shortest route when we find the target.
</p>
<p class="p">
These extra steps do make this algorithm a bit slower than the more generic <span class="bold">Best First Search</span> in terms of actual processing speed, but still the same amount of steps.
However if you need the shortest path, then this will be superior to the <span class="bold">Best First Search</span>.
</p>
</div>
</div>
</body>
</html>