BlueGit

timfa frameworkv3

Files

frameworkv3 / framework / util / quadTree.js

quadTree.js

96b50ae1 History
quadTree.js 18.0 KiB Download Raw
1/**
2 * Quadtree is a data-structure that contains a root node, and child nodes up to a defined depth. These nodes can be considered 'buckets' that can hold up to X objects.
3 * When that number is exceeded (and the maximum depth is not yet reached), the node will split up into 4 separate nodes
4 * (top left, top right, bottom left, bottom right),
5 * dividing up the objects into the correct quadrant based on their location.
6 *
7 */
8
9class QuadTree
10{
11 constructor (width, height, maxDepth = 7, bucketSize = 30)
12 {
13 this.root = new Node(0, 0, width, height, 0, null, "", this);
14
15 this.maxDepth = maxDepth;
16 this.bucketSize = bucketSize;
17
18 this.width = width;
19 this.height = height;
20
21 this.merge = [];
22 }
23
24 /**
25 * Adds object to the quadtree. if the amount of objects in the target node is higher than
26 * the permitted size, it divides up into 4 new nodes. Contents of this node is then divided up.
27 * @param {GameObject} object
28 * @returns {void}
29 */
30 add (object)
31 {
32 let dirOfOob = this.outOfBounds(object);
33 if (dirOfOob)
34 {
35 this.embiggen(dirOfOob);
36 }
37
38 if (!this.root.hasChildren)
39 {
40 this.root.add(object);
41 object.node = this.root;
42
43 return;
44 }
45
46 let node = this.findNodeFromRoot(object);
47
48 node.add(object);
49 object.node = node;
50 }
51
52 /**
53 * Removes object from quadtree. If the total amount of objects held by siblings is lower than the maximum size,
54 * a cleanup phase is triggered to remove the objects from siblings, moved up to parent node
55 * @param {GameObject} object
56 * @returns {void}
57 */
58
59 remove (object)
60 {
61 if (!this.root.hasChildren)
62 {
63 this.root.remove(object);
64 object.node = null;
65 return;
66 }
67
68 let node = object.node;
69 object.node = null;
70
71 node && node.remove(object);
72 }
73
74 /**
75 * Retrieves objects within range of a given position. Sorted by distance from position
76 *
77 * @param {vector} position
78 * @param {number} range (radius)
79 * @returns {GameObject[]} result
80 */
81
82 getObjectsInRange (position, range)
83 {
84 return this.getObjectsOfTypesInRange(position, range, null);
85 }
86
87 /**
88 * Retrieves objects within range of a given position matching a type. Sorted by distance from position
89 *
90 * @param {vector} position
91 * @param {number} range (radius)
92 * @param {class[]} types
93 * @returns {GameObject[]} result
94 */
95
96 getObjectsOfTypesInRange (position, range, types)
97 {
98 let result = [];
99
100 let nodes = [];
101
102 nodes.push(this.root);
103
104 while (nodes.length > 0)
105 {
106 let node = nodes.pop();
107
108 if (this.isInRange(position, range, node))
109 {
110 if (!node.hasChildren)
111 {
112 let filtered = node.getObjects()
113 .filter(obj => obj.transform.position.distanceTo(position) < range && obj.transform.position.distanceTo(position) > 0);
114
115 if (types != null)
116 {
117 filtered = filtered.filter(obj => types.some(t => obj instanceof t));
118 }
119
120 result.push(...filtered);
121 }
122 else
123 {
124 nodes.push(...node.getChildren());
125 }
126 }
127 }
128
129 return result.sort((a, b) => a.transform.position.distanceTo(position) - b.transform.position.distanceTo(position));
130 }
131
132 getObjectsWithTagInRange = function (position, range, tags)
133 {
134 let result = [];
135
136 let nodes = [];
137
138 nodes.push(this.root);
139
140 while (nodes.length > 0)
141 {
142 let node = nodes.pop();
143
144 if (this.isInRange(position, range, node))
145 {
146 if (!node.hasChildren)
147 {
148 let filtered = node.getObjects()
149 .filter(obj => obj.transform.position.distanceTo(position) < range && obj.transform.position.distanceTo(position) > 0);
150
151 if (types != null)
152 {
153 filtered = filtered.filter(obj => types.some(t => obj.tags.some(tag => tag == t)));
154 }
155
156 result.push(...filtered);
157 }
158 else
159 {
160 nodes.push(...node.getChildren());
161 }
162 }
163 }
164
165 return result.sort((a, b) => a.transform.position.distanceTo(position) - b.transform.position.distanceTo(position));
166 };
167
168 isInRange (vector, range, node)
169 {
170 var points =
171 [
172 vector.x - range,
173 vector.x + range,
174 vector.y - range,
175 vector.y + range
176 ];
177
178 if (points[1] >= node.x1 && points[0] <= node.x2)
179 {
180 if (points[3] >= node.y1 && points[2] <= node.y2)
181 {
182 return true;
183 }
184 }
185 return false;
186 }
187
188 embiggen (dirOfOob)
189 {
190 if (dirOfOob == "L")
191 {
192 this.root = this.root.createParent("bottomright");
193 }
194 else if (dirOfOob == "R")
195 {
196 this.root = this.root.createParent("topleft");
197 }
198 else if (dirOfOob == "U")
199 {
200 this.root = this.root.createParent("bottomleft");
201 }
202 else if (dirOfOob == "D")
203 {
204 this.root = this.root.createParent("topleft");
205 }
206
207 }
208
209 traverseTo (path)
210 {
211 let node = this.root;
212
213 for (let i = 0, len = path.length; i < len; i++)
214 {
215 if (!node.hasChildren)
216 return node;
217
218 node = node.getChildren()[path[i]];
219 }
220
221 return node;
222 }
223
224 findNodeFromRoot (object)
225 {
226 return this.findNodeFromRootAtPosition(object.transform.position);
227 }
228
229 findNodeFromRootAtPosition (position)
230 {
231 if (!this.root.hasChildren)
232 {
233 return this.root;
234 }
235
236 let node = this.root.findChildNode(position);
237
238 while (node.hasChildren)
239 {
240 node = node.findChildNode(position);
241 }
242
243 return node;
244 }
245
246 countObjectsInChild (parentNode)
247 {
248 if (!parentnode.hasChildren)
249 {
250 return 0;
251 }
252
253 return parentNode.topleft.size() + parentNode.topright.size()
254 + parentNode.bottomleft.size() + parentNode.bottomright.size();
255 }
256
257 show (ctx)
258 {
259 this.showAll(this.root, ctx);
260 }
261
262 showAll (node, ctx)
263 {
264 node.show(ctx);
265
266 if (node.hasChildren)
267 {
268 node.getChildren().forEach((element) => this.showAll(element, ctx));
269 }
270 }
271
272 update (deltaTime)
273 {
274 this.root.update(deltaTime);
275 }
276
277 outOfBounds (object)
278 {
279 let pos = object.transform.position;
280
281 if (pos.x < this.root.x1)
282 {
283 return "L";
284 }
285
286 if (pos.x > this.root.x2 + this.root.x1)
287 {
288 return "R";
289 }
290
291 if (pos.y < this.root.y1)
292 {
293 return "U";
294 }
295
296 if (pos.y > this.root.y2 + this.root.y1)
297 {
298 return "D";
299 }
300
301 return false;
302 }
303}
304
305class Node
306{
307 get canBeMerged ()
308 {
309 return !this.hasChildren && this.parent && this.parent.recursiveCount < this.quadTree.bucketSize;
310 }
311
312 get shouldSplit ()
313 {
314 return !this.hasChildren && this.recursiveCount > this.quadTree.bucketSize;
315 }
316
317 get hasChildren ()
318 {
319 return this.bottomright != null; //assume the rest is there too
320 }
321
322 constructor (x1, y1, x2, y2, depth, parent, name, quadTree)
323 {
324 this.name = name;
325
326 this.x1 = x1;
327 this.x2 = x2;
328 this.y1 = y1;
329 this.y2 = y2;
330
331 this.objects = [];
332
333 this.topleft = null;
334 this.topright = null;
335 this.bottomleft = null;
336 this.bottomright = null;
337
338 this.parent = parent;
339
340 this.depth = depth;
341 this.recursiveCount = 0;
342
343 this.lengthX = this.x2 - this.x1;
344 this.lengthY = this.y2 - this.y1;
345
346 this.halfLengthX = this.lengthX / 2;
347 this.halfLengthY = this.lengthY / 2;
348
349 this.markedForCleanup = false;
350 this.timer = 0;
351
352 this.quadTree = quadTree;
353 }
354
355 addCount ()
356 {
357 this.recursiveCount++;
358
359 this.parent && this.parent.addCount();
360
361 if (this.shouldSplit)
362 {
363 this.divide();
364 }
365 }
366
367 removeCount ()
368 {
369 this.recursiveCount--;
370
371 this.parent && this.parent.removeCount();
372
373 if (this.hasChildren)
374 {
375 let merge = true;
376 let children = this.getChildren();
377 for (let i = 0, l = children.length; i < l; i++)
378 {
379 if (!children[i].canBeMerged)
380 merge = false;
381 }
382
383 if (merge)
384 {
385 this.merge();
386 }
387 }
388 }
389
390 remove (obj)
391 {
392 if (this.objects && this.objects.indexOf(obj) >= 0)
393 {
394 this.objects = this.objects.filter(ind => ind != obj);
395 this.removeCount();
396 }
397 }
398
399 add (obj, ignoreCount)
400 {
401 if (this.objects.indexOf(obj) < 0)
402 {
403 this.objects.push(obj);
404
405 if (!ignoreCount)
406 this.addCount();
407 }
408 }
409
410 divide ()
411 {
412 this.createNodes();
413 let center = new vector((this.x1 + this.x2) / 2, (this.y1 + this.y2) / 2);
414
415 this.objects.forEach(object =>
416 {
417 if (object.transform.position.y > center.y)
418 {
419 if (object.transform.position.x > center.x)
420 {
421 object.node = this.bottomright;
422 this.bottomright.add(object, true);
423 }
424 else
425 {
426 object.node = this.bottomleft;
427 this.bottomleft.add(object, true);
428 }
429 }
430 else
431 {
432 if (object.transform.position.x > center.x)
433 {
434 object.node = this.topright;
435 this.topright.add(object, true);
436 }
437 else
438 {
439 object.node = this.topleft;
440 this.topleft.add(object, true);
441 }
442 }
443 });
444
445 this.objects = [];
446 }
447
448 merge ()
449 {
450 this.getChildren().forEach(child =>
451 {
452 child.getObjects().forEach(object =>
453 {
454 this.add(object, true);
455 object.node = this;
456 });
457 });
458
459 this.removeNodes();
460 }
461
462 size ()
463 {
464 if (this.objects != null)
465 {
466 return this.objects.length;
467 }
468 return 0;
469 }
470
471 getObjects ()
472 {
473 return this.objects;
474 }
475
476 getChildren ()
477 {
478 if (!this.hasChildren)
479 {
480 return [];
481 }
482
483 return [this.topleft, this.topright, this.bottomleft, this.bottomright];
484 }
485
486 findChildNode (position)
487 {
488 if (!this.hasChildren)
489 return this;
490
491 if (position.x >= this.topleft.x1 && position.x <= this.topleft.x2 && position.y >= this.topleft.y1 && position.y <= this.topleft.y2)
492 {
493 return this.topleft;
494 }
495 else if (position.x >= this.bottomleft.x1 && position.x <= this.bottomleft.x2 && position.y >= this.bottomleft.y1 && position.y <= this.bottomleft.y2)
496 {
497 return this.bottomleft;
498 }
499 else if (position.x >= this.topright.x1 && position.x <= this.topright.x2 && position.y >= this.topright.y1 && position.y <= this.topright.y2)
500 {
501 return this.topright;
502 }
503 else if (position.x >= this.bottomright.x1 && position.x <= this.bottomright.x2 && position.y >= this.bottomright.y1 && position.y <= this.bottomright.y2)
504 {
505 return this.bottomright;
506 }
507 }
508
509 createNodes ()
510 {
511 if (this.hasChildren)
512 return;
513
514 let depth = this.depth + 1;
515
516 this.topleft = new Node(this.x1, this.y1, this.x1 + this.halfLengthX, this.y1 + this.halfLengthY, depth, this, this.name + 0, this.quadTree);
517
518 this.topright = new Node(this.x1 + this.halfLengthX, this.y1, this.x2, this.y1 + this.halfLengthY, depth, this, this.name + 1, this.quadTree);
519
520 this.bottomleft = new Node(this.x1, this.y1 + this.halfLengthY, this.x1 + this.halfLengthX, this.y2, depth, this, this.name + 2, this.quadTree);
521
522 this.bottomright = new Node(this.x1 + this.halfLengthX, this.y1 + this.halfLengthY, this.x2, this.y2, depth, this, this.name + 3, this.quadTree);
523
524 return this.getChildren();
525 }
526
527 createParent (nodePosition)
528 {
529 let parentNode;
530
531 if (nodePosition == "topleft")
532 {
533 parentNode = new Node(this.x1, this.y1, this.lengthX * 2, this.lengthY * 2, this.depth - 1, null, "", this.quadTree);
534
535 parentNode.topleft == this;
536 }
537
538 if (nodePosition == "topright")
539 {
540 parentNode = new Node(this.x1 - this.lengthX, this.y1, this.lengthX * 2, this.lengthY * 2, this.depth - 1, null, "", this.quadTree);
541
542 parentNode.topright == this;
543 }
544
545 if (nodePosition == "bottomleft")
546 {
547 parentNode = new Node(this.x1, this.y1 - this.lengthY, this.lengthX * 2, this.lengthY * 2, this.depth - 1, null, "", this.quadTree);
548
549 parentNode.bottomleft == this;
550 }
551
552 if (nodePosition == "bottomright")
553 {
554 parentNode = new Node(this.x1 - this.lengthX, this.y1 - this.lengthY, this.lengthX * 2, this.lengthY * 2, this.depth - 1, null, "", this.quadTree);
555
556 parentNode.bottomright == this;
557 }
558
559 if (!parentNode.topleft)
560 {
561 parentNode.topleft = new Node(parentNode.x1, parentNode.y1, parentNode.x1 + parentNode.halfLengthX, parentNode.y1 + parentNode.halfLengthY, this.depth, parentNode, parentNode.name + 0, this.quadTree);
562 }
563
564 if (!parentNode.topright)
565 {
566 parentNode.topright = new Node(parentNode.x1 + parentNode.halfLengthX, parentNode.y1, parentNode.x2, parentNode.y1 + parentNode.halfLengthY, this.depth, parentNode, parentNode.name + 1, this.quadTree);
567 }
568
569 if (!parentNode.bottomleft)
570 {
571 parentNode.bottomleft = new Node(parentNode.x1, parentNode.y1 + parentNode.halfLengthY, parentNode.x1 + parentNode.halfLengthX, parentNode.y2, this.depth, parentNode, parentNode.name + 2, this.quadTree);
572 }
573
574 if (!parentNode.bottomright)
575 {
576 parentNode.bottomright = new Node(parentNode.x1 + parentNode.halfLengthX, parentNode.y1 + parentNode.halfLengthY, parentNode.x2, parentNode.y2, this.depth, parentNode, parentNode.name + 3, this.quadTree);
577 }
578
579 this.startReconfigureNames();
580 return parentNode;
581 }
582
583 startReconfigureNames ()
584 {
585 let parent = this;
586 while (parent.parent)
587 {
588 parent = parent.parent;
589 }
590
591 parent.reconfigureNames("");
592 }
593
594 reconfigureNames (name)
595 {
596 this.name = name;
597 let children = this.getChildren();
598 for (let i = 0, l = children.length; i < l; i++)
599 {
600 children[i].reconfigureNames(name + i);
601 }
602 }
603
604 removeNodes ()
605 {
606 this.topleft = null;
607 this.topright = null;
608 this.bottomleft = null;
609 this.bottomright = null;
610 }
611
612 update (deltaTime)
613 {
614 if (this.hasChildren)
615 {
616 this.topleft.update(deltaTime);
617 this.topright.update(deltaTime);
618 this.bottomleft.update(deltaTime);
619 this.bottomright.update(deltaTime);
620 }
621 }
622
623 /**
624 * Retrieves the same-level neighbour if possible, or the lowest level if not.
625 *
626 * @param {string} direction L, R, U or D
627 */
628 getNeighbour (direction)
629 {
630 let name = this.name.split("");
631 let hmap = { 0: 1, 1: 0, 2: 3, 3: 2 };
632 let vmap = { 0: 2, 2: 0, 1: 3, 3: 1 };
633
634 switch (direction)
635 {
636 case "L":
637 if (name[name.length - 1] == "0" || name[name.length - 1] == "2")
638 {
639 if (name.length > 1)
640 name[name.length - 2] = hmap[name[name.length - 2]];
641 else
642 return null;
643 }
644 name[name.length - 1] = hmap[name[name.length - 1]];
645 break;
646 case "R":
647 if (name[name.length - 1] == "1" || name[name.length - 1] == "3")
648 {
649 if (name.length > 1)
650 name[name.length - 2] = hmap[name[name.length - 2]];
651 else
652 return null;
653 }
654 name[name.length - 1] = hmap[name[name.length - 1]];
655 break;
656 case "U":
657 if (name[name.length - 1] == "0" || name[name.length - 1] == "1")
658 {
659 if (name.length > 1)
660 name[name.length - 2] = vmap[name[name.length - 2]];
661 else
662 return null;
663 }
664 name[name.length - 1] = vmap[name[name.length - 1]];
665 break;
666 case "D":
667 if (name[name.length - 1] == "2" || name[name.length - 1] == "3")
668 {
669 if (name.length > 1)
670 name[name.length - 2] = vmap[name[name.length - 2]];
671 else
672 return null;
673 }
674 name[name.length - 1] = vmap[name[name.length - 1]];
675 break;
676 }
677
678 return quadTree.traverseTo(name.join(""));
679 }
680
681 show (ctx)
682 {
683 ctx.strokeStyle = "white";
684 ctx.strokeRect(this.x1, this.y1, this.lengthX, this.lengthY);
685 }
686}