UNPKG

11.9 kBHTMLView Raw
1<!doctype html>
2<html>
3 <head>
4 <title>quadtree-js Many-to-many 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>many-to-many example</small></h1>
16
17 <nav class="nav">
18 <strong>Demos:</strong>
19 <a href="simple.html">simple</a>
20 <a href="dynamic.html">dynamic</a>
21 <span>many to many</span>
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 Total Objects: <span id="cnt_total">0</span>
32 </div>
33 <div class="ctrl-right">
34 Total candidates: <span id="cnt_cand">0</span> (avg. per object: <span id="cnt_perc">0</span>)<br />
35 FPS: <span id="cnt_fps">0</span>
36 </div>
37 </div>
38
39
40 <p>
41 This example shows how Quadtrees can be used for many-to-many checks. All objects can collide with each other.
42 Two loops are neccessary to first insert all objects into the tree <code>[2]</code> and then check each object for collisions <code>[3]</code>.
43 </p>
44
45 <pre><code class="language-javascript">var myTree = new Quadtree({
46 x: 0,
47 y: 0,
48 width: 640,
49 height: 480
50});
51
52function loop() {
53
54 //[1] First, we will clear the quadtree with every game loop.
55 //This is neccessary to keep the tree clean and accurate
56 //(due to its recursive nature).
57 myTree.clear();
58
59 //[2] Then we will update the positions of all objects
60 //and re-insert them into the tree.
61 for(var i=0;i&lt;myObjects.length;i++) {
62
63 myObjects[i].x += myObjects[i].vx;
64 myObjects[i].y += myObjects[i].vy;
65
66 myTree.insert(myObjects[i]);
67 }
68
69 //[3] Now we loop over all objects again &hellip;
70 for(var i=0;i&lt;myObjects.length;i++) {
71
72 var myObject = myObjects[i];
73
74 //[4] &hellip; and retrieve all objects from the same tree node
75 var candidates = myTree.retrieve(myObject);
76
77 //[5] Check all collision candidates
78 for(k=0;k&lt;candidates.length;k++) {
79
80 var myCandidate = candidates[k];
81
82 //[6] since all objects are inside the tree,
83 //we will also retrieve the current object itself.
84 //That's a collision case we want to skip.
85 if(myObject === myCandidate) continue;
86
87 //[7] check each candidate for real intersection
88 var intersect = getIntersection(myObject, myCandidate);
89
90 //[8] if they actually intersect, we can take further
91 //actions. In this script, colliding objects will turn
92 //green and change velocity
93 if(intersect) {
94 // &hellip; take actions
95 }
96 }
97 }
98
99 //[9] finally, draw all objects and the quadtree
100 drawQuadtree(myTree);
101 drawObjects();
102
103 //request next frame
104 requestAnimFrame(loop);
105}
106 </pre></code>
107
108 <p>
109 To see the full example code please check the page source or
110 <a href="https://github.com/timohausmann/quadtree-js/tree/master/docs" target="_blank" rel="noopener noreferrer">visit GitHub</a>.
111 </p>
112 <p>
113 <em>Collision detection is beyond the scope of quadtree-js</em> &ndash; this example uses a very
114 basic collision algorithm that is not bullet-proof and won't fit all cases. Please research a
115 collision system that will work for you.
116 </p>
117 <p>
118 The collision code in this example is based on
119 <a href="https://www.metanetsoftware.com/technique/tutorialA.html" target="_blank" rel="noreferrer noopener">
120 Metanet's N Game Collision Tutorial</a>, which may be a starting point if you are new to collision detection.
121 There are many great tutorials out there.
122 </p>
123
124 </div>
125
126 <!-- github corner (https://github.com/tholman/github-corners) -->
127 <a href="https://github.com/timohausmann/quadtree-js" class="github-corner" aria-label="View source on GitHub"
128 target="_blank" rel="noopener noreferrer">
129 <svg width="80" height="80" viewBox="0 0 250 250" aria-hidden="true">
130 <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>
131 </svg>
132 </a>
133
134 <!-- prism syntax highlighting -->
135 <script src="https://cdnjs.cloudflare.com/ajax/libs/prism/1.21.0/prism.min.js" integrity="sha512-WkVkkoB31AoI9DAk6SEEEyacH9etQXKUov4JRRuM1Y681VsTq7jYgrRw06cbP6Io7kPsKx+tLFpH/HXZSZ2YEQ==" crossorigin="anonymous"></script>
136
137 <!-- quadtree lib and script -->
138 <script src="./quadtree.min.js"></script>
139 <!-- CDN alternative: -->
140 <!-- <script src="https://cdn.jsdelivr.net/npm/@timohausmann/quadtree-js/quadtree.min.js"></script> -->
141 <script>
142
143 (function(w) {
144
145 w.requestAnimFrame = (function () {
146 return w.requestAnimationFrame ||
147 w.webkitRequestAnimationFrame ||
148 w.mozRequestAnimationFrame ||
149 w.oRequestAnimationFrame ||
150 w.msRequestAnimationFrame ||
151 function (callback) {
152 w.setTimeout(callback, 1000 / 60);
153 };
154 })();
155
156
157 var ctx = document.getElementById('canvas').getContext('2d');
158
159 var cnt_total = document.querySelector('#cnt_total'),
160 cnt_cand = document.querySelector('#cnt_cand'),
161 cnt_fps = document.querySelector('#cnt_fps'),
162 cnt_perc = document.querySelector('#cnt_perc');
163
164
165 /*
166 * the main Quadtree
167 */
168 var myTree = new Quadtree({
169 x: 0,
170 y: 0,
171 width: 640,
172 height: 480
173 });
174
175 /*
176 * our objects will be stored here
177 */
178 var myObjects = [];
179
180
181 /*
182 * create some objects and save them in myObjects
183 */
184 for(var i=0;i<800;i++) {
185 myObjects.push({
186 x : randMinMax(0, 640-16),
187 y : randMinMax(0, 480-16),
188 width : randMinMax(4, 16),
189 height : randMinMax(4, 16),
190 vx: randMinMax(-0.5,0.5),
191 vy: randMinMax(-0.5,0.5),
192 check : false
193 });
194 }
195 cnt_total.innerHTML = myObjects.length;
196
197
198 /*
199 * draw Quadtree nodes
200 */
201 var drawQuadtree = function(node) {
202
203 var bounds = node.bounds;
204
205 //no subnodes? draw the current node
206 if(node.nodes.length === 0) {
207 ctx.strokeStyle = 'rgba(255,0,0,0.25)';
208 ctx.strokeRect(bounds.x, bounds.y, bounds.width, bounds.height);
209
210 //has subnodes? drawQuadtree them!
211 } else {
212 for(var i=0;i<node.nodes.length;i++) {
213 drawQuadtree(node.nodes[i]);
214 }
215 }
216 };
217
218 /*
219 * draw all objects
220 */
221 var drawObjects = function() {
222
223 var obj;
224
225 for(var i=0;i<myObjects.length;i++) {
226
227 obj = myObjects[i];
228
229 if(obj.check) {
230 ctx.strokeStyle = 'rgba(48,255,48,0.5)';
231 } else {
232 ctx.strokeStyle = 'rgba(255,255,255,0.5)';
233 }
234 ctx.strokeRect(obj.x, obj.y, obj.width, obj.height);
235 }
236 };
237
238
239 /*
240 * our main loop
241 */
242 var lastLoop = new Date();
243 var loop = function() {
244
245 //calculate FPS
246 var thisLoop = new Date();
247 var fps = 1000 / (thisLoop - lastLoop);
248 lastLoop = thisLoop;
249 cnt_fps.innerHTML = Math.round(fps);
250
251 //[1] clear the tree
252 myTree.clear();
253 ctx.clearRect(0, 0, 640, 480);
254
255 //[2] update myObjects and insert them into the tree again
256 for(var i=0;i<myObjects.length;i++) {
257
258 myObjects[i].x += myObjects[i].vx;
259 myObjects[i].y += myObjects[i].vy;
260 myObjects[i].check = false;
261
262 //bounce objects when they reach the canvas border
263 if(myObjects[i].x > 640 - myObjects[i].width ||
264 myObjects[i].x < 0) myObjects[i].vx *= -1;
265 if(myObjects[i].y > 480 - myObjects[i].height ||
266 myObjects[i].y < 0) myObjects[i].vy *= -1;
267
268 myTree.insert(myObjects[i]);
269 }
270
271 //[3] now that the tree is filled, we have to check each object for collisions
272 for(var i=0;i<myObjects.length;i++) {
273
274 var myObject = myObjects[i];
275
276 //[4] first, get all collision candidates
277 var candidates = myTree.retrieve(myObject);
278
279 //[5] let's check them for actual collision
280 for(k=0;k<candidates.length;k++) {
281
282 var myCandidate = candidates[k];
283
284 //[6] don't check objects against themselves
285 if(myObject === myCandidate) continue;
286
287 //[7] get intersection data
288 var intersect = getIntersection(myObject, myCandidate);
289
290 //no intersection - continue
291 if(intersect === false) continue;
292
293 //[8]
294 myObject.check = true;
295 myCandidate.check = true;
296
297 //Perform X Push
298 if(intersect.pushX < intersect.pushY) {
299
300 if(intersect.dirX < 0) {
301 myObject.x = myCandidate.x - myObject.width;
302 } else if(intersect.dirX > 0) {
303 myObject.x = myCandidate.x + myCandidate.width;
304 }
305
306 //reverse X trajectory (bounce)
307 myObject.vx *= -1;
308
309 //Perform Y Push
310 } else {
311
312 if(intersect.dirY < 0) {
313 myObject.y = myCandidate.y - myObject.height;
314 } else if(intersect.dirY > 0) {
315 myObject.y = myCandidate.y + myCandidate.height;
316 }
317
318 //reverse Y trajectory (bounce)
319 myObject.vy *= -1;
320 }
321 }
322 }
323
324 //[9] draw objects and quadtree
325 drawQuadtree(myTree);
326 drawObjects();
327
328 //update UI info
329 var candidates = myObjects.filter(function(e) { return e.check === true; })
330 updateCandidatesInfo(candidates);
331
332 //request next frame
333 requestAnimFrame(loop);
334 };
335
336
337
338 function getIntersection(r1, r2) {
339
340 var r1w = r1.width/2,
341 r1h = r1.height/2,
342 r2w = r2.width/2,
343 r2h = r2.height/2;
344
345 var distX = (r1.x + r1w) - (r2.x + r2w);
346 var distY = (r1.y + r1h) - (r2.y + r2h);
347
348 if(Math.abs(distX) < r1w + r2w && Math.abs(distY) < r1h + r2h) {
349 return {
350 pushX : (r1w + r2w) - Math.abs(distX),
351 pushY : (r1h + r2h) - Math.abs(distY),
352 dirX : distX === 0 ? 0 : distX < 0 ? -1 : 1,
353 dirY : distY === 0 ? 0 : distY < 0 ? -1 : 1
354 }
355 } else {
356 return false;
357 }
358 }
359
360 var updateCandidatesInfo = function(candidates) {
361
362 var avg = myObjects.length/candidates.length;
363 cnt_cand.innerHTML = candidates.length;
364 if(!myObjects.length) return;
365 cnt_perc.innerHTML = Math.round(avg);
366 }
367
368 //init first loop
369 loop();
370
371 /**
372 * return a random number within given boundaries.
373 *
374 * @param {number} min the lowest possible number
375 * @param {number} max the highest possible number
376 * @param {boolean} round if true, return integer
377 * @return {number} a random number
378 */
379 function randMinMax(min, max, round) {
380 var val = min + (Math.random() * (max - min));
381
382 if(round) val = Math.round(val);
383
384 return val;
385 };
386
387 })(window);
388 </script>
389 </body>
390</html>