/
index.html
234 lines (211 loc) · 10.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
<!DOCTYPE html>
<html>
<head>
<title>Dark Maze - Computational Geometry</title>
<link rel="stylesheet" type="text/css" href="style.css">
<script src="js/jquery.js"></script>
</head>
<body>
<div class="container">
<h1 class="title centered">
Dark Maze
</h1>
<div>
<h3> What is this website? </h3>
<div>
I implemented a computational geometry algorithm and turned it into a game. The object of the game is to nagivate your way around a <i>dark maze</i>,
and when you get to the end, you have to get back to where you started.... faster than the time you took to get there. So make sure you remember your way as you
navigate around!
<br>
You have a few seconds of memory to represent what you've just seen, but that disappears after a bit, so you have to remember your way around the polygon.
<br>
Control your player by dragging your mouse around the maze.
</div>
</div>
</div>
<div class="container">
For full functionality, you should use Google Chrome.
</div>
<div class="container">
<div>Difficulty<span id="difficultytext"></span></div>
<select id="difficulty">
<option value="none" selected>Select a difficulty...</option>
<option value="easy">Easy</option>
<option value="medium">Medium</option>
<option value="hard">Hard</option>
</select>
</div>
<div class="container">
<div>
<span class="left">
Timer: <span id="timer">00:00.00</span>
<br>
<div id="uptime_parent" style="display:block;">
Time (exploring the maze): <span id="uptime">--</span>
</div>
<div id="upscore_parent" style="display:block;">
Points (exploring the maze): <span id="upscore">--</span>
</div>
<br>
<div id="downtime_parent" style="display:block;">
Time (returning home): <span id="downtime">--</span>
</div>
<div id="downscore_parent" style="display:block;">
Points (returning home): <span id="downscore">--</span>
</div>
<br>
<div>
Total score: <span id="total_score" style="display:inline;">--</span>
</div>
</span>
<span class="right">
High score: <span id="highscore">0</span>
<div id="up_highscore_parent">
Fastest time to the end: <span id="up_highscore">00:00.00</span>
</div>
<div id="down_highscore_parent">
Fastest time back to the start: <span id="down_highscore">00:00.00</span>
</div>
<div>
<button id="reset_scores" style="font-size: 1em;">Reset High Scores</button>
</div>
<br>
<div>
Mazes left: <span id="mazes_left">3</span>
</div>
</span>
</div>
<svg width="1024" height="768">
<polygon class="maze" id="maze"/>
<polygon class="visibility clickable" id="visibility"/>
<circle r="10" id="end" class="endpoint"/>
<circle r="5" id="player" class="player clickable"/>
<rect id="messagebox"/>
<text text-anchor="middle" id="messageparent">
<tspan id="firstline"></tspan>
<tspan x="0" dy="1.4em" id="secondline"></tspan>
<tspan x="0" dy="1.4em" id="thirdline"></tspan>
</text>
</svg>
</div>
<div class="container">
<div>
<h3> Visibility Polygons </h3>
<div>
The visibility polygon of a point with respect to a polygon is defined as all the points in the polygon that that point can "see". It's a pretty intuitive
idea, but to implement a correct, general, fast algorithm to compute it is rather <a href="http://www.cs.tufts.edu/comp/163/lectures/163-chapter07.pdf">tricky</a>.
</div>
</div>
<br>
<div><h3> An Alternative Algorithm </h3>
<div>
An alternate to this linear-time algorithm is explained <a href="http://ncase.me/sight-and-light/">here</a>. Essentially these are the steps:
<ol>
<li>
Cast a ray from the point to all vertices and record the first collision (<i>O(n)</i> for each vertex to get all the collisions,
for a total runtime of <i>O(n²)</i>)
</li>
<li>
For all collisions, create 2 more collisions by shooting another ray +/- 0.000001 radians (for the walls behind any vertex).
</li>
<li>
Sort all the collisions (<i>O(n log n)</i>) to piece together the polygon.
</li>
</ol>
</div>
</div>
<br>
<div>
<h3> Linear algorithm explanation </h3>
<div>
Essentially, here is how the algorithm works:
<br>
(You can visually follow along <a href="http://www.cs.tufts.edu/comp/163/lectures/163-chapter07.pdf">here</a>)
<br>
<br>
We do 4 instances of an algorithm that finds the visibility of a 90 degree cone, and stitch the visibility
polygons (at all 4 angles; 0, 90, 180, and 270) together.
First, we find the two points in the polygon where the 90 degree cone intersects an edge and add the player's point and
those intersection points to a stack. This can be done in linear time by just looping through all the edges and seeing
if the visibility cone intersects with that edge.
Then, (without loss of generality, assume the polygon faces CCW) we walk linearly along the edges in a CCW direction.
Assuming a convex polygon, this is all we need to do. If it's not convex, we may have more cases to check for.
However, while the edges still face in a CCW direction with respect to the player, we can keep adding them to the stack.
<br>
<br>
If the polygon enters an "upwards backtrack" (denoted by if an edge points in a CW direction with respect to
the player and goes away from the player), we ignore edges until the algorithm emerges from the upwards backtrack, going CCW again, but this time
above the edge that caused the upwards backtrack. When we find the emerging edge, we add a new window edge starting from
the edge before the one that caused the upwards backtrack and ending at the emergence point that just became visible
after returning from the upwards backtrack. Then, we resume walking in a CCW fashion and keep adding
to the stack.
<br>
<br>
If the polygon enters a "downwards backtrack" (denoted by if an edge points in a CW direction with respect to
the player and faces towards the player), then the edge causing the downwards backtrack is covering up some edges, and
we pop the edges that are completely covered from the stack, and add a window edge that intersects with the edge that
is only <i>partially</i> covered by the downwards backtrack. Then, we resume walking in a CCW fashion and keep adding
to the stack..
<br>
<br>
There are more cases for what the polygon can do (such as a downwards backtrack crossing a window, in which case we need
to slightly modify the case we're dealing with), but these cases are better described on the class slides <a href="http://www.cs.tufts.edu/comp/163/lectures/163-chapter07.pdf">here</a>.
<br>
<br>
When we reach the last intersection point, the stack represents the visibility polygon in a cone! Now we just need to
calculate the visibility polygon 3 more times (after changing the angle by 90 degrees) and stitch it together,
and we have the entire visibility region of that point.
<br>
<br>
Clearly, this algorithm is linear with respect to the number of edges of the polygon, becauase it takes linear time
to find the intersection points, and takes linear time to walk along the edge list of the polygon sequentially, and
potentially push/pop edges to/from the stack (at most once per edge).
</div>
</div>
<br>
<div>
<h3>Some bugs I ran into</h3>
<div>
One problem I ran into was trying to implement the stack using points rather than edges, and then
just use the stack as the parameter for the polygon creation. Because the algorithm so heavily
relies on certain information about edges (like which direction an edge points), the point stack idea
messed up my logic in code, even though the two are technically equivalent (we can determine the "next
edge" we're looking at by just peeking ahead in the point list of the polygon). After about
a week of messing around with convoluted point logic, I fixed my implementation by pretty
much starting from scratch and using an edge stack. It took me only a few hours to get back the progress
I had made previously, and was done with the entire algorithm within a few days after that.
<br>
<br>
Another problem I encountered was with the upwards backtrack mode, as described above. We emerge from the upwards
backtrack when we return from the polygon's edges with an edge facing CCW with respect to the player. However,
if the polygon first loops back around CW and <i>then</i> comes back in a CCW direction, as denoted here,
<div>
<img src="https://i.imgur.com/xOPSpU7.png"/>
</div>
then this edge is invisible to the player. To solve this, I just created a stack that I pushed
CW-faced edges on (represented by the grey CW facing edge that intersects with the orange visibility ray), and
popped when I encountered the CCW-facing visibility ray, denoted by the blue CCW facing edge that has the
crossed out symbol over it.
When the stack is empty, that means the edge is now visible - all CW-facing edges have
been accounted for. (This works because
of the Jordan curve theorem - the polygon has to come back around.)
<br>
This is just one example of the many edge cases that you have to deal with when implementing the visibility
polygon algorithm.
</div>
</div>
<br>
<div>
<h3><a href="https://github.com/popcorncolonel/DarkMaze/blob/master/js/visibilityregion.js">Source code</a></h3>
</div>
</div>
</body>
<script src="js/innerhtml.js"></script>
<script src="js/highscore.js"></script>
<script src="js/polygon.js"></script>
<script src="js/config.js"></script>
<script src="js/game.js"></script>
<script src="js/maze.js"></script>
<script src="js/player.js"></script>
<script src="js/visibilityregion.js"></script>
</html>