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 |
|
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 |
|
67 | myTree.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 |
|
81 | var 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<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 |
|
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 |
|
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 |
|
120 | <script src="./quadtree.min.js"></script>
|
121 |
|
122 |
|
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 |
|
217 | myObjects.push(rect);
|
218 |
|
219 |
|
220 | myTree.insert(rect);
|
221 |
|
222 |
|
223 | updateTotal();
|
224 | }
|
225 |
|
226 | /*
|
227 | * clear the tree
|
228 | */
|
229 | var handleClear = function() {
|
230 |
|
231 |
|
232 | myObjects = [];
|
233 |
|
234 |
|
235 | myTree.clear();
|
236 |
|
237 |
|
238 | updateTotal();
|
239 | }
|
240 |
|
241 |
|
242 | /*
|
243 | * draw Quadtree nodes
|
244 | */
|
245 | var drawQuadtree = function(node) {
|
246 |
|
247 | var bounds = node.bounds;
|
248 |
|
249 |
|
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 |
|
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 |
|
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 |
|
324 | candidates = myTree.retrieve(myCursor);
|
325 |
|
326 |
|
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 |
|
355 | loop();
|
356 |
|
357 |
|
358 | document.getElementById('canvas').addEventListener('mousemove', handleMousemove);
|
359 | document.getElementById('canvas').addEventListener('mouseout', handleMouseout);
|
360 |
|
361 |
|
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>
|