UNPKG

10.9 kBHTMLView Raw
1<!doctype html>
2<html>
3 <head>
4 <title>quadtree-js Simple Demo</title>
5 <link rel="stylesheet" type="text/css" href="style.css?v=2" />
6 <meta name="viewport" content="width=device-width, initial-scale=1" />
7
8 <!-- prism syntax highlighting (https://prismjs.com/) -->
9 <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/prism/1.21.0/themes/prism.min.css" integrity="sha512-tN7Ec6zAFaVSG3TpNAKtk4DOHNpSwKHxxrsiw4GHKESGPs5njn/0sMCUMl2svV4wo4BK/rCP7juYz+zx+l6oeQ==" crossorigin="anonymous" />
10 </head>
11 <body>
12
13 <div class="outer">
14
15 <h1><a href="https://github.com/timohausmann/quadtree-js">quadtree-js</a> <small>simple example</small></h1>
16
17 <nav class="nav">
18 <strong>Demos:</strong>
19 <span>simple</span>
20 <a href="dynamic.html">dynamic</a>
21 <a href="many.html">many to many</a>
22 <a href="test-retrieve.html">benchmark</a>
23 </nav>
24
25 <div id="canvasContainer">
26 <canvas id="canvas" width="640" height="480"></canvas>
27 </div>
28
29 <div class="ctrl">
30 <div class="ctrl-left">
31 <button id="btn_add">add small object</button>
32 <button id="btn_add_big">add big object</button>
33 <button id="btn_add_10">add 10 small objects</button>
34 <button id="btn_clear">clear tree</button>
35 </div>
36
37 <div class="ctrl-right">
38 Total Objects: <span id="cnt_total">0</span><br />
39 Candidates: <span id="cnt_cand">0</span> (<span id="cnt_perc">0</span>%)
40 </div>
41 </div>
42
43 <p>
44 This quadtree starts off empty. Click the buttons to add elements to the Quadtree.
45 </p>
46 <p>
47 After adding five objects to the Quadtree it will split, because we initially set <code>max_objects</code> to 4.
48 </p>
49 <pre><code class="language-javascript">var myTree = new Quadtree({
50 x: 0,
51 y: 0,
52 width: 640,
53 height: 480
54}, 4);</code></pre>
55
56 <p>
57 Objects that you insert into the tree need to have <code>x</code>, <code>y</code>, <code>width</code> and <code>height</code> properties in order to work.
58 Of course you can extend these objects with your own data.
59 </p>
60 <pre><code class="language-javascript">var myObject = {
61 x: 200,
62 y: 100,
63 width: 35,
64 height: 70
65}
66
67myTree.insert(myObject);</code></pre>
68
69
70 <p>
71 In this example, we constantly retrieve collision candidates for the white area at your mouse cursor. The candidates are highlighted in green.
72 </p>
73
74 <pre><code class="language-javascript">var myCursor = {
75 x: mouseX,
76 y: mouseY,
77 width: 20,
78 height: 20
79};
80
81var candidates = myTree.retrieve(myCursor);</code></pre>
82 <p>
83 The object passed to the retrieve function does not have to be inside the quadtree. It could be though, if that's your thing.
84 </p>
85
86 <p>
87 What you get is an array of your collision candidates. In this example, we will only mark them with a <code>check</code>-property to paint them green. In a real world example, you may want to check them for collisions.
88 </p>
89
90 <pre><code class="language-javascript">for(var i=0;i&lt;candidates.length;i=i+1) {
91 candidates[i].check = true;
92}</code></pre>
93
94
95 <p>
96 Run clear() to remove all objects from the quadtree and reset it.
97 </p>
98
99 <pre><code class="language-javascript">myTree.clear();</code></pre>
100
101 <p>
102 To see the full example code please check the page source or
103 <a href="https://github.com/timohausmann/quadtree-js/tree/master/docs" target="_blank" rel="noopener noreferrer">visit GitHub</a>.
104 </p>
105
106 </div>
107
108 <!-- github corner (https://github.com/tholman/github-corners) -->
109 <a href="https://github.com/timohausmann/quadtree-js" class="github-corner" aria-label="View source on GitHub"
110 target="_blank" rel="noopener noreferrer">
111 <svg width="80" height="80" viewBox="0 0 250 250" aria-hidden="true">
112 <path d="M0,0 L115,115 L130,115 L142,142 L250,250 L250,0 Z"></path><path d="M128.3,109.0 C113.8,99.7 119.0,89.6 119.0,89.6 C122.0,82.7 120.5,78.6 120.5,78.6 C119.2,72.0 123.4,76.3 123.4,76.3 C127.3,80.9 125.5,87.3 125.5,87.3 C122.9,97.6 130.6,101.9 134.4,103.2" fill="currentColor" style="transform-origin: 130px 106px;" class="octo-arm"></path><path d="M115.0,115.0 C114.9,115.1 118.7,116.5 119.8,115.4 L133.7,101.6 C136.9,99.2 139.9,98.4 142.2,98.6 C133.8,88.0 127.5,74.4 143.8,58.0 C148.5,53.4 154.0,51.2 159.7,51.0 C160.3,49.4 163.2,43.6 171.4,40.1 C171.4,40.1 176.1,42.5 178.8,56.2 C183.1,58.6 187.2,61.8 190.9,65.4 C194.5,69.0 197.7,73.2 200.1,77.6 C213.8,80.2 216.3,84.9 216.3,84.9 C212.7,93.1 206.9,96.0 205.4,96.6 C205.1,102.4 203.0,107.8 198.3,112.5 C181.9,128.9 168.3,122.5 157.7,114.1 C157.9,116.9 156.7,120.9 152.7,124.9 L141.0,136.5 C139.8,137.7 141.6,141.9 141.8,141.8 Z" fill="currentColor" class="octo-body"></path>
113 </svg>
114 </a>
115
116 <!-- prism syntax highlighting -->
117 <script src="https://cdnjs.cloudflare.com/ajax/libs/prism/1.21.0/prism.min.js" integrity="sha512-WkVkkoB31AoI9DAk6SEEEyacH9etQXKUov4JRRuM1Y681VsTq7jYgrRw06cbP6Io7kPsKx+tLFpH/HXZSZ2YEQ==" crossorigin="anonymous"></script>
118
119 <!-- quadtree lib and script -->
120 <script src="./quadtree.min.js"></script>
121 <!-- CDN alternative: -->
122 <!-- <script src="https://cdn.jsdelivr.net/npm/@timohausmann/quadtree-js/quadtree.min.js"></script> -->
123 <script>
124
125 (function(w, M) {
126
127 w.requestAnimFrame = (function () {
128 return w.requestAnimationFrame ||
129 w.webkitRequestAnimationFrame ||
130 w.mozRequestAnimationFrame ||
131 w.oRequestAnimationFrame ||
132 w.msRequestAnimationFrame ||
133 function (callback) {
134 w.setTimeout(callback, 1000 / 60);
135 };
136 })();
137
138 /*
139 * the main Quadtree
140 */
141 var myTree = new Quadtree({
142 x: 0,
143 y: 0,
144 width: 640,
145 height: 480
146 }, 4);
147
148 /*
149 * our objects will be stored here
150 */
151 var myObjects = [];
152
153
154 /*
155 * our "hero", aka the mouse cursor.
156 * He is not in the quadtree, we only use this object to retrieve objects from a certain area
157 */
158 var myCursor = {
159 x : 0,
160 y : 0,
161 width : 28,
162 height : 28
163 };
164
165 var isMouseover = false;
166
167 var ctx = document.getElementById('canvas').getContext('2d');
168
169 var cnt_total = document.querySelector('#cnt_total'),
170 cnt_cand = document.querySelector('#cnt_cand'),
171 cnt_perc = document.querySelector('#cnt_perc');
172
173
174 /*
175 * position hero at mouse
176 */
177 var handleMousemove = function(e) {
178
179 isMouseover = true;
180
181 if(!e.offsetX) {
182 e.offsetX = e.layerX - e.target.offsetLeft;
183 e.offsetY = e.layerY - e.target.offsetTop;
184 }
185
186 myCursor.x = e.offsetX - (myCursor.width/2);
187 myCursor.y = e.offsetY - (myCursor.height/2);
188 };
189
190
191 /*
192 * hide hero
193 */
194 var handleMouseout = function(e) {
195
196 isMouseover = false;
197 };
198
199
200
201 /*
202 * add a random object to our simulation
203 */
204 var handleAdd = function(rect) {
205
206 if(!rect) {
207 rect = {
208 x : randMinMax(0, myTree.bounds.width-32),
209 y : randMinMax(0, myTree.bounds.height-32),
210 width : randMinMax(4, 32, true),
211 height : randMinMax(4, 32, true),
212 check : false
213 };
214 }
215
216 //store object in our array
217 myObjects.push(rect);
218
219 //insert object in our quadtree
220 myTree.insert(rect);
221
222 //update total counter
223 updateTotal();
224 }
225
226 /*
227 * clear the tree
228 */
229 var handleClear = function() {
230
231 //empty our array
232 myObjects = [];
233
234 //empty our quadtree
235 myTree.clear();
236
237 //update total counter
238 updateTotal();
239 }
240
241
242 /*
243 * draw Quadtree nodes
244 */
245 var drawQuadtree = function(node) {
246
247 var bounds = node.bounds;
248
249 //no subnodes? draw the current node
250 if(node.nodes.length === 0) {
251 ctx.strokeStyle = 'rgba(255,0,0,0.5)';
252 ctx.strokeRect(bounds.x, bounds.y, bounds.width, bounds.height);
253
254 //has subnodes? drawQuadtree them!
255 } else {
256 for(var i=0;i<node.nodes.length;i=i+1) {
257 drawQuadtree(node.nodes[i]);
258 }
259 }
260 };
261
262 /*
263 * draw all objects
264 */
265 var drawObjects = function() {
266
267 var obj;
268
269 for(var i=0;i<myObjects.length;i=i+1) {
270
271 obj = myObjects[i];
272
273 if(obj.check) {
274 ctx.fillStyle = 'rgba(48,255,48,0.5)';
275 ctx.fillRect(obj.x, obj.y, obj.width, obj.height);
276 } else {
277 ctx.strokeStyle = 'rgba(255,255,255,0.5)';
278 ctx.strokeRect(obj.x, obj.y, obj.width, obj.height);
279 }
280
281
282 }
283 };
284
285
286 /**
287 * return a random number within given boundaries.
288 *
289 * @param {number} min the lowest possible number
290 * @param {number} max the highest possible number
291 * @param {boolean} round if true, return integer
292 * @return {number} a random number
293 */
294 randMinMax = function(min, max, round) {
295 var val = min + (Math.random() * (max - min));
296
297 if(round) val = Math.round(val);
298
299 return val;
300 };
301
302 /*
303 * our main loop
304 */
305 var loop = function() {
306
307 var candidates = [];
308
309 ctx.clearRect(0, 0, 640, 480);
310
311 //reset myObjects check flag
312 for(var i=0;i<myObjects.length;i=i+1) {
313
314 myObjects[i].check = false;
315 }
316
317
318 if(isMouseover) {
319
320 ctx.fillStyle = 'rgba(255,255,255,0.5)';
321 ctx.fillRect(myCursor.x, myCursor.y, myCursor.width, myCursor.height);
322
323 //retrieve all objects in the bounds of the hero
324 candidates = myTree.retrieve(myCursor);
325
326 //flag retrieved objects
327 for(i=0;i<candidates.length;i=i+1) {
328 candidates[i].check = true;
329 }
330 }
331
332 updateCandidatesInfo(candidates);
333
334 drawQuadtree(myTree);
335
336 drawObjects();
337
338 requestAnimFrame(loop);
339 };
340
341
342 var updateTotal = function() {
343
344 cnt_total.innerHTML = myObjects.length;
345 }
346
347 var updateCandidatesInfo = function(candidates) {
348
349 cnt_cand.innerHTML = candidates.length;
350 if(!myObjects.length) return;
351 cnt_perc.innerHTML = Math.round((candidates.length/myObjects.length)*100);
352 }
353
354 //init first loop
355 loop();
356
357 //set eventListener for mousemove
358 document.getElementById('canvas').addEventListener('mousemove', handleMousemove);
359 document.getElementById('canvas').addEventListener('mouseout', handleMouseout);
360
361 //set eventListener for buttons
362 document.getElementById('btn_add').addEventListener('click', function() {
363 handleAdd();
364 });
365 document.getElementById('btn_add_big').addEventListener('click', function() {
366 handleAdd({
367 x : randMinMax(0, myTree.bounds.width/2),
368 y : randMinMax(0, myTree.bounds.height/2),
369 width : randMinMax(myTree.bounds.height/4, myTree.bounds.height/2, true),
370 height : randMinMax(myTree.bounds.height/4, myTree.bounds.height/2, true),
371 check : false
372 });
373 });
374 document.getElementById('btn_add_10').addEventListener('click', function() {
375 for(var i=0;i<10;i++) { handleAdd() };
376 });
377 document.getElementById('btn_clear').addEventListener('click', handleClear);
378
379
380 })(window, Math);
381 </script>
382 </body>
383</html>