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 |
|
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 |
|
52 | function 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<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 …
|
70 | for(var i=0;i<myObjects.length;i++) {
|
71 |
|
72 | var myObject = myObjects[i];
|
73 |
|
74 | //[4] … 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<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 | // … 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> – 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 |
|
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 |
|
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 |
|
138 | <script src="./quadtree.min.js"></script>
|
139 |
|
140 |
|
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 |
|
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 |
|
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 |
|
246 | var thisLoop = new Date();
|
247 | var fps = 1000 / (thisLoop - lastLoop);
|
248 | lastLoop = thisLoop;
|
249 | cnt_fps.innerHTML = Math.round(fps);
|
250 |
|
251 |
|
252 | myTree.clear();
|
253 | ctx.clearRect(0, 0, 640, 480);
|
254 |
|
255 |
|
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 |
|
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 |
|
272 | for(var i=0;i<myObjects.length;i++) {
|
273 |
|
274 | var myObject = myObjects[i];
|
275 |
|
276 |
|
277 | var candidates = myTree.retrieve(myObject);
|
278 |
|
279 |
|
280 | for(k=0;k<candidates.length;k++) {
|
281 |
|
282 | var myCandidate = candidates[k];
|
283 |
|
284 |
|
285 | if(myObject === myCandidate) continue;
|
286 |
|
287 |
|
288 | var intersect = getIntersection(myObject, myCandidate);
|
289 |
|
290 |
|
291 | if(intersect === false) continue;
|
292 |
|
293 |
|
294 | myObject.check = true;
|
295 | myCandidate.check = true;
|
296 |
|
297 |
|
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 |
|
307 | myObject.vx *= -1;
|
308 |
|
309 |
|
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 |
|
319 | myObject.vy *= -1;
|
320 | }
|
321 | }
|
322 | }
|
323 |
|
324 |
|
325 | drawQuadtree(myTree);
|
326 | drawObjects();
|
327 |
|
328 |
|
329 | var candidates = myObjects.filter(function(e) { return e.check === true; })
|
330 | updateCandidatesInfo(candidates);
|
331 |
|
332 |
|
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 |
|
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>
|