-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathmilestone3.html
343 lines (313 loc) · 25 KB
/
milestone3.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
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no">
<meta name="description" content="">
<meta name="author" content="">
<title>Milestone 3</title>
<link rel="shortcut icon" href="favicon-paper-plane.ico" />
<!-- Bootstrap Core CSS -->
<link href="vendor/bootstrap/css/bootstrap.min.css" rel="stylesheet">
<!-- Custom Fonts -->
<link href="vendor/fontawesome-free/css/all.min.css" rel="stylesheet" type="text/css">
<link href="https://fonts.googleapis.com/css?family=Source+Sans+Pro:300,400,700,300italic,400italic,700italic" rel="stylesheet" type="text/css">
<link href="vendor/simple-line-icons/css/simple-line-icons.css" rel="stylesheet">
<!-- Custom CSS -->
<link href="css/stylish-portfolio.min.css" rel="stylesheet">
</head>
<body id="page-top">
<!-- Navigation -->
<a class="menu-toggle rounded" href="#">
<i class="fas fa-bars"></i>
</a>
<nav id="sidebar-wrapper">
<ul class="sidebar-nav">
<li class="sidebar-nav-item">
<a class="js-scroll-trigger" href="index.html#page-top">Home</a>
</li>
<li class="sidebar-nav-item">
<a class="js-scroll-trigger" href="index.html#about">About</a>
</li>
<li class="sidebar-nav-item">
<a class="js-scroll-trigger" href="index.html#milestones">Milestones</a>
</li>
<li class="sidebar-nav-item">
<a class="js-scroll-trigger" href="index.html#labs">Labs</a>
</li>
</ul>
</nav>
<!-- Header -->
<header class="masthead d-flex">
<div class="container text-center my-auto">
<h1 class="mb-1">Milestone 3</h1>
<h3 class="mb-5">
<em>Finding our way around any maze</em>
</h3>
<a class="btn btn-primary btn-xl js-scroll-trigger" href="#about">Wanna know more?</a>
</div>
<div class="overlay"></div>
</header>
<section id="about" class="content-section">
<div class="container">
<h1>Overall</h1>
<p>For Milestone 3, we decided to implement DFS using recursion. In order to this, we wrote a function called traverseHelper. This function had parameters: coordX and coordY which corresponded to our global x and y variables. Our method of implementation gave priority to directions in the following order: front, left, right. So, if the front node has been been visited, we check the left node and if the right has been visited, we check the right node.</p>
</div>
</section>
<!-- Milestones -->
<section class="content-section bg-primary text-white text-center" id="milestones">
<div class="container">
<div class="content-section-heading">
<h2 class="mb-5">Let's Break it Down</h2>
</div>
<div class="row">
<div class="col-lg-3 col-md-6 mb-5 mb-lg-0">
<a href="#implementation" class="text-white text-center js-scroll-trigger">
<span class="service-icon rounded-circle mx-auto mb-3">
<i class="far fa-lightbulb"></i>
</span>
<h4>
<strong>Implementation</strong>
</h4>
<p class="text-faded mb-0"></p>
</a>
</div>
<div class="col-lg-3 col-md-6 mb-5 mb-lg-0">
<a href="#backtracking" class="text-white text-center js-scroll-trigger">
<span class="service-icon rounded-circle mx-auto mb-3">
<i class="fas fa-screwdriver"></i>
</span>
<h4>
<strong>Backtracking</strong>
</h4>
<p class="text-faded mb-0"></p>
</a>
</div>
<div class="col-lg-3 col-md-6 mb-5 mb-md-0">
<a href="#results" class="text-white text-center js-scroll-trigger">
<span class="service-icon rounded-circle mx-auto mb-3">
<i class="fas fa-toolbox"></i>
</span>
<h4>
<strong>Final Results</strong>
</h4>
<p class="text-faded mb-0"></p>
</a>
</div>
</div>
</div>
</section>
<section class="content-section" id="implementation">
<div class="container">
<h1>Implementation</h1>
<h2>One Word: Recursion</h2>
<p>We initially just implemented this by checking each sensor in the above mentioned order and then turning and/or moving forward accordingly. We soon realised that in order to accurately call traverseHelper(coordX, coordY) on the node we moved to, we would have to take Arnold's direction into account. So we added a direction dependent switch statement to our code, updated our coordinates accordingly with the help of local variables nextX and nextY and then called traverseHelper(coordX, coordY) on the newly updated coordinates.</p>
<p>With this alone, our code correctly traversed an empty maze (no walls) using DFS but failed to return to it's starting point after that. This led us to realise that we hadn't implemented any form of backtracking for Arnold. While the recursive functions returned to their caller functions, Arnold had no idea how to move to his parent nodes. To fix this, we implemented another helper function called moveSrcToDest(dx, dy) which we called after calling traverseHelper(coordX, coordY) on the updated coordinates. This way, when the recursive functions returned to their caller, Arnold actually had a way to return to where he was when the function was called.</p>
<p>The function moveSrcToDest(dx, dy) takes in parameters dx and dy which are the change in x and change in y respectively. For this, we also used a direction dependent switch statement. We used this function to decide how Arnold needed to move based on the difference between his source and destination coordinates. Source coordinates in this case is where he currently is and destination coordinates refers to where he went (the coordX and coordY when the child traverseHelper() was initially called).</p>
<!-- HTML generated using hilite.me --><div style="background: #ffffff; overflow:auto;width:auto;border:solid gray;border-width:.1em .1em .1em .8em;padding:.2em .6em;"><pre style="margin: 0; line-height: 125%"><span style="color: #333399; font-weight: bold">void</span> <span style="color: #0066BB; font-weight: bold">moveSrcToDest</span>(<span style="color: #333399; font-weight: bold">int</span> dx, <span style="color: #333399; font-weight: bold">int</span> dy) { <span style="color: #888888">// Dest - Src</span>
<span style="color: #008800; font-weight: bold">switch</span> (dir) {
<span style="color: #008800; font-weight: bold">case</span> NORTH: {
<span style="color: #008800; font-weight: bold">if</span> (dx <span style="color: #333333">==</span> <span style="color: #333333">-</span><span style="color: #0000DD; font-weight: bold">1</span>) {
turnAround();
goToIntersection();
} <span style="color: #008800; font-weight: bold">else</span> <span style="color: #008800; font-weight: bold">if</span> (dx <span style="color: #333333">==</span> <span style="color: #0000DD; font-weight: bold">1</span>) {
<span style="color: #888888">// Go forward</span>
goToIntersection();
} <span style="color: #008800; font-weight: bold">else</span> <span style="color: #008800; font-weight: bold">if</span> (dy <span style="color: #333333">==</span> <span style="color: #333333">-</span><span style="color: #0000DD; font-weight: bold">1</span>) {
turnRight();
goToIntersection();
} <span style="color: #008800; font-weight: bold">else</span> <span style="color: #008800; font-weight: bold">if</span> (dy <span style="color: #333333">==</span> <span style="color: #0000DD; font-weight: bold">1</span>) {
turnLeft();
goToIntersection();
} <span style="color: #008800; font-weight: bold">else</span> {
<span style="color: #888888">// Do nothing</span>
}
<span style="color: #888888">// goToIntersection();</span>
<span style="color: #008800; font-weight: bold">break</span>;
}
<span style="color: #008800; font-weight: bold">case</span> EAST: {
<span style="color: #008800; font-weight: bold">if</span> (dx <span style="color: #333333">==</span> <span style="color: #333333">-</span><span style="color: #0000DD; font-weight: bold">1</span>) {
turnRight();
goToIntersection();
} <span style="color: #008800; font-weight: bold">else</span> <span style="color: #008800; font-weight: bold">if</span> (dx <span style="color: #333333">==</span> <span style="color: #0000DD; font-weight: bold">1</span>) {
turnLeft();
goToIntersection();
} <span style="color: #008800; font-weight: bold">else</span> <span style="color: #008800; font-weight: bold">if</span> (dy <span style="color: #333333">==</span> <span style="color: #333333">-</span><span style="color: #0000DD; font-weight: bold">1</span>) {
<span style="color: #888888">// Do nothing</span>
goToIntersection();
} <span style="color: #008800; font-weight: bold">else</span> <span style="color: #008800; font-weight: bold">if</span> (dy <span style="color: #333333">==</span> <span style="color: #0000DD; font-weight: bold">1</span>) {
turnAround();
goToIntersection();
} <span style="color: #008800; font-weight: bold">else</span> {
<span style="color: #888888">// Do nothing</span>
}
<span style="color: #888888">//goToIntersection();</span>
<span style="color: #008800; font-weight: bold">break</span>;
}
<span style="color: #008800; font-weight: bold">case</span> SOUTH: {
<span style="color: #008800; font-weight: bold">if</span> (dx <span style="color: #333333">==</span> <span style="color: #333333">-</span><span style="color: #0000DD; font-weight: bold">1</span>) {
<span style="color: #888888">// Do nothing</span>
goToIntersection();
} <span style="color: #008800; font-weight: bold">else</span> <span style="color: #008800; font-weight: bold">if</span> (dx <span style="color: #333333">==</span> <span style="color: #0000DD; font-weight: bold">1</span>) {
turnAround();
goToIntersection();
} <span style="color: #008800; font-weight: bold">else</span> <span style="color: #008800; font-weight: bold">if</span> (dy <span style="color: #333333">==</span> <span style="color: #333333">-</span><span style="color: #0000DD; font-weight: bold">1</span>) {
turnLeft();
goToIntersection();
} <span style="color: #008800; font-weight: bold">else</span> <span style="color: #008800; font-weight: bold">if</span> (dy <span style="color: #333333">==</span> <span style="color: #0000DD; font-weight: bold">1</span>) {
turnRight();
goToIntersection();
} <span style="color: #008800; font-weight: bold">else</span> {
<span style="color: #888888">// Do nothing</span>
}
<span style="color: #888888">//goToIntersection();</span>
<span style="color: #008800; font-weight: bold">break</span>;
}
<span style="color: #008800; font-weight: bold">case</span> WEST: {
<span style="color: #008800; font-weight: bold">if</span> (dx <span style="color: #333333">==</span> <span style="color: #333333">-</span><span style="color: #0000DD; font-weight: bold">1</span>) {
turnLeft();
goToIntersection();
} <span style="color: #008800; font-weight: bold">else</span> <span style="color: #008800; font-weight: bold">if</span> (dx <span style="color: #333333">==</span> <span style="color: #0000DD; font-weight: bold">1</span>) {
turnRight();
goToIntersection();
} <span style="color: #008800; font-weight: bold">else</span> <span style="color: #008800; font-weight: bold">if</span> (dy <span style="color: #333333">==</span> <span style="color: #333333">-</span><span style="color: #0000DD; font-weight: bold">1</span>) {
turnAround();
goToIntersection();
} <span style="color: #008800; font-weight: bold">else</span> <span style="color: #008800; font-weight: bold">if</span> (dy <span style="color: #333333">==</span> <span style="color: #0000DD; font-weight: bold">1</span>) {
<span style="color: #888888">// Do nothing</span>
goToIntersection();
} <span style="color: #008800; font-weight: bold">else</span> {
<span style="color: #888888">// Do nothing</span>
}
<span style="color: #888888">//goToIntersection();</span>
<span style="color: #008800; font-weight: bold">break</span>;
}
}
}
</pre></div>
<p>After implementing this function, Arnold was still having trouble traversing different maze configurations using DFS. We eventually realised that this was because when he returned to a particular node, he was facing a different direction than when he originally visited the node. Because of how we wrote our if-statements, this meant that Arnold didn't end up checking all paths from every node. He would sometimes end up checking one path two times. For example, when Arnold wants to go from node A to node B, he checks the front-wall sensor. Since there is no front-wall (hypothetically), he goes forward i.e. to node B. When he comes back (as part of backtracking) to node A, then he tries to check left-wall as part of the sequence (Remember our order of checking walls? Front-Left-Right). But Arnold’s left is not left anymore because it came back from node B and his direction is flipped. So we should have incorporated his previous direction and current direction while choosing walls, which we didn’t so that was the problem! We decided to fix this problem by forcing Arnold to remember his original direction and checking sensors based on that direction instead of his current direction. We kept track of the direction everytime traverseHelper was called in a variable called referenceDir. We also wrote functions for each wall Arnold could possibly see, to decide which sensor to check. The choice of sensor was dependent on the difference between referenceDir and dir (our global direction variable). The functions were frontWallDetection(referenceDir), leftWallDetection(referenceDir) and rightWallDetection(referenceDir).</p>
<p>Below is our fronWallDetection function, to give an idea of how all three of the wallDetection functions were written:</p>
<!-- HTML generated using hilite.me --><div style="background: #ffffff; overflow:auto;width:auto;border:solid gray;border-width:.1em .1em .1em .8em;padding:.2em .6em;"><pre style="margin: 0; line-height: 125%"><span style="color: #333399; font-weight: bold">bool</span> <span style="color: #0066BB; font-weight: bold">frontWallDetection</span>(<span style="color: #333399; font-weight: bold">int</span> referenceDir) {
<span style="color: #333399; font-weight: bold">int</span> change <span style="color: #333333">=</span> referenceDir <span style="color: #333333">-</span> dir;
<span style="color: #008800; font-weight: bold">switch</span> (change) {
<span style="color: #008800; font-weight: bold">case</span> <span style="color: #333333">-</span><span style="color: #0000DD; font-weight: bold">3</span>: {
<span style="color: #008800; font-weight: bold">return</span> leftWall();
}
<span style="color: #008800; font-weight: bold">case</span> <span style="color: #333333">-</span><span style="color: #0000DD; font-weight: bold">2</span> : {
<span style="color: #008800; font-weight: bold">return</span> <span style="color: #007020">false</span>;
}
<span style="color: #008800; font-weight: bold">case</span> <span style="color: #333333">-</span><span style="color: #0000DD; font-weight: bold">1</span>: {
<span style="color: #008800; font-weight: bold">return</span> rightWall();
}
<span style="color: #008800; font-weight: bold">case</span> <span style="color: #0000DD; font-weight: bold">0</span>: {
<span style="color: #008800; font-weight: bold">return</span> frontWall();
}
<span style="color: #008800; font-weight: bold">case</span> <span style="color: #0000DD; font-weight: bold">1</span>: {
<span style="color: #008800; font-weight: bold">return</span> leftWall();
}
<span style="color: #008800; font-weight: bold">case</span> <span style="color: #0000DD; font-weight: bold">2</span>: {
<span style="color: #008800; font-weight: bold">return</span> <span style="color: #007020">false</span>;
}
<span style="color: #008800; font-weight: bold">case</span> <span style="color: #0000DD; font-weight: bold">3</span>: {
<span style="color: #008800; font-weight: bold">return</span> rightWall();
}
}
}
</pre></div>
</div>
</section>
<section id="backtracking" class="content-section bg-primary text-white">
<div class="container">
<h1>Backtracking</h1>
<h2>Going back to square one</h2>
<p>After implementing these functions, Arnold was still struggling. He could now successfully traverse the maze but he wasn't backtracking correctly. He kept running into walls that he knew were there (as seen from the GUI). After stepping through the code and pretending to be Arnold, we realised that we were deciding where walls were based on the initial direction but we were still turning based on Arnold's current direction. This caused him to keep running into walls, because even though we fixed the checking-wall function, we still had to fix the turning function. Confused? Consider the same above example. Arnold is smart enough now to check the right wall (for instance) even though he wants to detect left wall; because he know his heading is flipped in process of backtracking. But what he still doesn’t know is the fact that his capability of turning is also flipped. What that means is, he has to dynamically decide where to turn. For example, a left turn for Arnold when he is facing North is equal to right turn when facing South. In order to dynamically decide turns, we added decideLeft() and decideRight().</p>
<p>Below is the code for decideLeft(), which closely mirrors decideRight() in structure:</p>
<!-- HTML generated using hilite.me --><div style="background: #ffffff; overflow:auto;width:auto;border:solid gray;border-width:.1em .1em .1em .8em;padding:.2em .6em;"><pre style="margin: 0; line-height: 125%"><span style="color: #333399; font-weight: bold">void</span> <span style="color: #0066BB; font-weight: bold">decideLeft</span>(<span style="color: #333399; font-weight: bold">int</span> referenceDir) {
<span style="color: #333399; font-weight: bold">int</span> change <span style="color: #333333">=</span> dir <span style="color: #333333">-</span> referenceDir;
<span style="color: #008800; font-weight: bold">switch</span> (change) {
<span style="color: #008800; font-weight: bold">case</span> <span style="color: #333333">-</span><span style="color: #0000DD; font-weight: bold">3</span>: {
<span style="color: #888888">//nothing</span>
<span style="color: #008800; font-weight: bold">break</span>;
}
<span style="color: #008800; font-weight: bold">case</span> <span style="color: #333333">-</span><span style="color: #0000DD; font-weight: bold">2</span>: {
turnRight();
goToIntersection();
<span style="color: #008800; font-weight: bold">break</span>;
}
<span style="color: #008800; font-weight: bold">case</span> <span style="color: #333333">-</span><span style="color: #0000DD; font-weight: bold">1</span>: {
goToIntersection();
<span style="color: #008800; font-weight: bold">break</span>;
}
<span style="color: #008800; font-weight: bold">case</span> <span style="color: #0000DD; font-weight: bold">0</span>: {
turnLeft();
goToIntersection();
<span style="color: #008800; font-weight: bold">break</span>;
}
<span style="color: #008800; font-weight: bold">case</span> <span style="color: #0000DD; font-weight: bold">1</span>: {
<span style="color: #888888">//nothing</span>
<span style="color: #008800; font-weight: bold">break</span>;
}
<span style="color: #008800; font-weight: bold">case</span> <span style="color: #0000DD; font-weight: bold">2</span>: {
turnRight();
goToIntersection();
<span style="color: #008800; font-weight: bold">break</span>;
}
<span style="color: #008800; font-weight: bold">case</span> <span style="color: #0000DD; font-weight: bold">3</span>: {
goToIntersection();
<span style="color: #008800; font-weight: bold">break</span>;
}
}
}
</pre></div>
</div>
</section>
<section id="results" class="content-section">
<div class="container">
<h1>Final Results</h1>
<h2>Dreams sometimes do come true</h2>
<p>After adding those functions, Arnold was able to successfully traverse multiple maze configurations using DFS successfully. Here are a few videos of Arnold doing his thing.</p>
<p>Here's Arnold traversing a (nearly) empty 4x5 maze:</p>
<iframe width="560" height="315" src="https://www.youtube.com/embed/n3DbzoTrUAI" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>
<p>Here are some more complicated 4x5 mazes to fully show off our DFS and backtracking:</p>
<iframe width="560" height="315" src="https://www.youtube.com/embed/f1nADrb4yFo" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>
<iframe width="560" height="315" src="https://www.youtube.com/embed/NmIrN2H--Lo" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>
<p>Here are a few instances of Arnold starting on a tone and traversing a maze:</p>
<iframe width="560" height="315" src="https://www.youtube.com/embed/Hbq3RHm4TLg" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>
<iframe width="560" height="315" src="https://www.youtube.com/embed/hlJ-k0jJOV0" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>
</div>
</section>
<!-- Map -->
<!-- POINT TO PHILLIPS -->
<section id="contact" class="map">
<iframe width="100%" height="100%" frameborder="0" scrolling="no" marginheight="0" marginwidth="0" src="https://maps.google.com/maps?q=phillips%20hall%2C%20ithaca&t=&z=13&ie=UTF8&iwloc=&output=embed"></iframe>
<br/>
<small>
<a href="https://www.google.com/maps/place/Phillips+Hall/@42.4445807,-76.4842416,17z/data=!4m7!3m6!1s0x89d0818c816cffe3:0xfd9ee07ff22c5aa4!8m2!3d42.4445768!4d-76.4820529!9m1!1b1"></a>
</small>
</section>
<!-- Footer -->
<footer class="footer text-center">
<div class="container">
<ul class="list-inline mb-5">
<li class="list-inline-item">
<a class="social-link rounded-circle text-white" href="https://github.com/ece3400-team16">
<i class="icon-social-github"></i>
</a>
</li>
</ul>
<p class="text-muted small mb-0">Copyright © ECE 3400 2018</p>
</div>
</footer>
<!-- Scroll to Top Button-->
<a class="scroll-to-top rounded js-scroll-trigger" href="#page-top">
<i class="fas fa-angle-up"></i>
</a>
<!-- Bootstrap core JavaScript -->
<script src="vendor/jquery/jquery.min.js"></script>
<script src="vendor/bootstrap/js/bootstrap.bundle.min.js"></script>
<!-- Plugin JavaScript -->
<script src="vendor/jquery-easing/jquery.easing.min.js"></script>
<!-- Custom scripts for this template -->
<script src="js/stylish-portfolio.min.js"></script>
</body>
</html>