BlueGit

timfa frameworkv3

Files

frameworkv3 / framework / util / quadTree.js

quadTree.js

engine optimisations
timfa Tim Falken · pushed by timfa · 3 months ago
74d8cdb3 History
quadTree.js 16.1 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 // Reused across queries (results are valid until the next query).
22 this._queryNodes = [];
23 this._queryResult = [];
24 this._queryScored = [];
25 }
26
27 /**
28 * Adds object to the quadtree. if the amount of objects in the target node is higher than
29 * the permitted size, it divides up into 4 new nodes. Contents of this node is then divided up.
30 * @param {GameObject} object
31 * @returns {void}
32 */
33 add (object)
34 {
35 let dirOfOob = this.outOfBounds(object);
36 while (dirOfOob)
37 {
38 this.embiggen(dirOfOob);
39 dirOfOob = this.outOfBounds(object);
40 }
41
42 // Node.add may split and move the object into a descendant leaf
43 // (divide sets object.node). Otherwise assign the leaf we inserted into.
44 const node = this.findNodeFromRoot(object);
45 node.add(object);
46 if (!object.node)
47 { object.node = node; }
48 }
49
50 /**
51 * Removes object from quadtree. If the total amount of objects held by siblings is lower than the maximum size,
52 * a cleanup phase is triggered to remove the objects from siblings, moved up to parent node
53 * @param {GameObject} object
54 * @returns {void}
55 */
56
57 remove (object)
58 {
59 const node = object.node || (!this.root.hasChildren ? this.root : null);
60
61 if (node && node.remove(object))
62 {
63 object.node = null;
64 }
65 }
66
67 /**
68 * Retrieves objects within range of a given position. Sorted by distance from position
69 *
70 * @param {vector} position
71 * @param {number} range (radius)
72 * @returns {GameObject[]} result
73 */
74
75 getObjectsInRange (position, range)
76 {
77 return this.getObjectsOfTypesInRange(position, range, null);
78 }
79
80 /**
81 * Retrieves objects within range of a given position matching a type. Sorted by distance from position
82 *
83 * @param {vector} position
84 * @param {number} range (radius)
85 * @param {class[]} types
86 * @returns {GameObject[]} result
87 */
88
89 getObjectsOfTypesInRange (position, range, types, options)
90 {
91 const typeFilter = Array.isArray(types)
92 ? types.filter(t => t != null)
93 : (types != null ? [types] : []);
94
95 return this.collectInRange(position, range, (obj) =>
96 {
97 if (typeFilter.length === 0)
98 { return true; }
99
100 for (let i = 0, len = typeFilter.length; i < len; i++)
101 {
102 if (obj instanceof typeFilter[i])
103 { return true; }
104 }
105
106 return false;
107 }, options);
108 }
109
110 getObjectsWithTagInRange (position, range, tags, options)
111 {
112 const tagFilter = Array.isArray(tags)
113 ? tags.filter(t => t != null)
114 : (tags != null ? [tags] : []);
115
116 return this.collectInRange(position, range, (obj) =>
117 {
118 if (tagFilter.length === 0)
119 { return true; }
120
121 const objTags = obj.tags;
122 if (!objTags || objTags.length === 0)
123 { return false; }
124
125 for (let i = 0, len = tagFilter.length; i < len; i++)
126 {
127 const want = tagFilter[i];
128 for (let j = 0, jl = objTags.length; j < jl; j++)
129 {
130 if (objTags[j] == want)
131 { return true; }
132 }
133 }
134
135 return false;
136 }, options);
137 }
138
139 getClosestObjectWithTagInRange (position, range, tags)
140 {
141 const tagFilter = Array.isArray(tags)
142 ? tags.filter(t => t != null)
143 : (tags != null ? [tags] : []);
144
145 return this.getClosestObjectInRange(position, range, (obj) =>
146 {
147 if (tagFilter.length === 0)
148 { return true; }
149
150 const objTags = obj.tags;
151 if (!objTags || objTags.length === 0)
152 { return false; }
153
154 for (let i = 0, len = tagFilter.length; i < len; i++)
155 {
156 const want = tagFilter[i];
157 for (let j = 0, jl = objTags.length; j < jl; j++)
158 {
159 if (objTags[j] == want)
160 { return true; }
161 }
162 }
163
164 return false;
165 });
166 }
167
168 /**
169 * @param {vector} position
170 * @param {number} range
171 * @param {Function} predicate
172 * @param {{ sort?: boolean }} [options] - sort defaults true (closest first)
173 * @returns {GameObject[]} reused buffer — consume before the next query
174 */
175 collectInRange (position, range, predicate, options)
176 {
177 const sort = !options || options.sort !== false;
178 const rangeSq = range * range;
179 const result = this._queryResult;
180 result.length = 0;
181
182 const nodes = this._queryNodes;
183 nodes.length = 0;
184 nodes.push(this.root);
185
186 if (!sort)
187 {
188 while (nodes.length > 0)
189 {
190 const node = nodes.pop();
191
192 if (!this.isInRange(position, range, node))
193 { continue; }
194
195 if (node.hasChildren)
196 {
197 nodes.push(node.topleft, node.topright, node.bottomleft, node.bottomright);
198 continue;
199 }
200
201 const objects = node.objects;
202 for (let i = 0, len = objects.length; i < len; i++)
203 {
204 const obj = objects[i];
205 const distSq = obj.transform.position.distanceToSq(position);
206 if (distSq > 0 && distSq < rangeSq && predicate(obj))
207 { result.push(obj); }
208 }
209 }
210
211 return result;
212 }
213
214 const scored = this._queryScored;
215 scored.length = 0;
216
217 while (nodes.length > 0)
218 {
219 const node = nodes.pop();
220
221 if (!this.isInRange(position, range, node))
222 { continue; }
223
224 if (node.hasChildren)
225 {
226 nodes.push(node.topleft, node.topright, node.bottomleft, node.bottomright);
227 continue;
228 }
229
230 const objects = node.objects;
231 for (let i = 0, len = objects.length; i < len; i++)
232 {
233 const obj = objects[i];
234 const distSq = obj.transform.position.distanceToSq(position);
235 if (distSq > 0 && distSq < rangeSq && predicate(obj))
236 { scored.push({ obj, dist: distSq }); }
237 }
238 }
239
240 if (scored.length > 1)
241 { scored.sort((a, b) => a.dist - b.dist); }
242
243 for (let i = 0, len = scored.length; i < len; i++)
244 { result.push(scored[i].obj); }
245
246 return result;
247 }
248
249 getClosestObjectInRange (position, range, predicate)
250 {
251 const rangeSq = range * range;
252 const nodes = this._queryNodes;
253 nodes.length = 0;
254 nodes.push(this.root);
255 let closest = null;
256 let closestDistSq = rangeSq;
257
258 while (nodes.length > 0)
259 {
260 const node = nodes.pop();
261
262 if (!this.isInRange(position, range, node))
263 { continue; }
264
265 if (node.hasChildren)
266 {
267 nodes.push(node.topleft, node.topright, node.bottomleft, node.bottomright);
268 continue;
269 }
270
271 const objects = node.objects;
272 for (let i = 0, len = objects.length; i < len; i++)
273 {
274 const obj = objects[i];
275 const distSq = obj.transform.position.distanceToSq(position);
276 if (distSq > 0 && distSq < closestDistSq && predicate(obj))
277 {
278 closestDistSq = distSq;
279 closest = obj;
280 }
281 }
282 }
283
284 return closest;
285 }
286
287 isInRange (vector, range, node)
288 {
289 var points =
290 [
291 vector.x - range,
292 vector.x + range,
293 vector.y - range,
294 vector.y + range
295 ];
296
297 if (points[1] >= node.x1 && points[0] <= node.x2)
298 {
299 if (points[3] >= node.y1 && points[2] <= node.y2)
300 {
301 return true;
302 }
303 }
304 return false;
305 }
306
307 embiggen (dirOfOob)
308 {
309 // Place the current root as a child of a 2x parent that grows into the
310 // out-of-bounds direction (L←, R→, U↑, D↓).
311 if (dirOfOob == "L")
312 {
313 this.root = this.root.createParent("topright");
314 }
315 else if (dirOfOob == "R")
316 {
317 this.root = this.root.createParent("topleft");
318 }
319 else if (dirOfOob == "U")
320 {
321 this.root = this.root.createParent("bottomleft");
322 }
323 else if (dirOfOob == "D")
324 {
325 this.root = this.root.createParent("topleft");
326 }
327
328 this.width = this.root.lengthX;
329 this.height = this.root.lengthY;
330 }
331
332 traverseTo (path)
333 {
334 let node = this.root;
335
336 for (let i = 0, len = path.length; i < len; i++)
337 {
338 if (!node.hasChildren)
339 { return node; }
340
341 node = node.getChildren()[path[i]];
342 }
343
344 return node;
345 }
346
347 findNodeFromRoot (object)
348 {
349 return this.findNodeFromRootAtPosition(object.transform.position);
350 }
351
352 findNodeFromRootAtPosition (position)
353 {
354 let node = this.root;
355
356 while (node && node.hasChildren)
357 {
358 node = node.findChildNode(position) || node.topleft;
359 }
360
361 return node || this.root;
362 }
363
364 show (ctx)
365 {
366 this.showAll(this.root, ctx);
367 }
368
369 showAll (node, ctx)
370 {
371 node.show(ctx);
372
373 if (node.hasChildren)
374 {
375 node.getChildren().forEach((element) => this.showAll(element, ctx));
376 }
377 }
378
379 update (/* deltaTime */)
380 {
381 // Merge/split happen eagerly on add/remove; nothing to tick per frame.
382 }
383
384 outOfBounds (object)
385 {
386 const pos = object.transform.position;
387
388 if (pos.x < this.root.x1)
389 {
390 return "L";
391 }
392
393 if (pos.x > this.root.x2)
394 {
395 return "R";
396 }
397
398 if (pos.y < this.root.y1)
399 {
400 return "U";
401 }
402
403 if (pos.y > this.root.y2)
404 {
405 return "D";
406 }
407
408 return false;
409 }
410}
411
412class Node
413{
414 get canBeMerged ()
415 {
416 // Leaf siblings may collapse into their parent when the parent's
417 // whole subtree fits in one bucket again.
418 return !this.hasChildren && this.parent && this.parent.recursiveCount <= this.quadTree.bucketSize;
419 }
420
421 get shouldSplit ()
422 {
423 return !this.hasChildren
424 && this.recursiveCount > this.quadTree.bucketSize
425 && this.depth < this.quadTree.maxDepth;
426 }
427
428 get hasChildren ()
429 {
430 return this.bottomright != null; //assume the rest is there too
431 }
432
433 constructor (x1, y1, x2, y2, depth, parent, name, quadTree)
434 {
435 this.name = name;
436
437 this.x1 = x1;
438 this.x2 = x2;
439 this.y1 = y1;
440 this.y2 = y2;
441
442 this.objects = [];
443
444 this.topleft = null;
445 this.topright = null;
446 this.bottomleft = null;
447 this.bottomright = null;
448
449 this.parent = parent;
450
451 this.depth = depth;
452 this.recursiveCount = 0;
453
454 this.lengthX = this.x2 - this.x1;
455 this.lengthY = this.y2 - this.y1;
456
457 this.halfLengthX = this.lengthX / 2;
458 this.halfLengthY = this.lengthY / 2;
459
460 this.quadTree = quadTree;
461 }
462
463 addCount ()
464 {
465 this.recursiveCount++;
466
467 this.parent && this.parent.addCount();
468
469 if (this.shouldSplit)
470 {
471 this.divide();
472 }
473 }
474
475 removeCount ()
476 {
477 this.recursiveCount--;
478
479 // Merge before notifying the parent. If the parent is checked first,
480 // it still sees this node as a branch and skips the collapse; after
481 // this node merges into a leaf the parent never re-checks.
482 if (this.hasChildren)
483 {
484 let merge = true;
485 const children = this.getChildren();
486 for (let i = 0, l = children.length; i < l; i++)
487 {
488 if (!children[i].canBeMerged)
489 { merge = false; }
490 }
491
492 if (merge)
493 {
494 this.merge();
495 }
496 }
497
498 this.parent && this.parent.removeCount();
499 }
500
501 remove (obj)
502 {
503 const index = this.objects ? this.objects.indexOf(obj) : -1;
504 if (index >= 0)
505 {
506 this.objects.splice(index, 1);
507 this.removeCount();
508 return true;
509 }
510
511 return false;
512 }
513
514 add (obj, ignoreCount)
515 {
516 if (this.objects.indexOf(obj) < 0)
517 {
518 this.objects.push(obj);
519
520 if (!ignoreCount)
521 { this.addCount(); }
522 }
523 }
524
525 divide ()
526 {
527 this.createNodes();
528 const center = new vector((this.x1 + this.x2) / 2, (this.y1 + this.y2) / 2);
529
530 this.objects.forEach(object =>
531 {
532 if (object.transform.position.y > center.y)
533 {
534 if (object.transform.position.x > center.x)
535 {
536 object.node = this.bottomright;
537 this.bottomright.add(object, true);
538 }
539 else
540 {
541 object.node = this.bottomleft;
542 this.bottomleft.add(object, true);
543 }
544 }
545 else
546 {
547 if (object.transform.position.x > center.x)
548 {
549 object.node = this.topright;
550 this.topright.add(object, true);
551 }
552 else
553 {
554 object.node = this.topleft;
555 this.topleft.add(object, true);
556 }
557 }
558 });
559
560 this.objects = [];
561
562 // add(..., true) skips counting so the parent is not double-counted.
563 // Children still need a correct local recursiveCount, and may themselves
564 // need to split when this redistribute dumps more than bucketSize in one cell.
565 this.getChildren().forEach(child =>
566 {
567 child.recursiveCount = child.objects.length;
568 if (child.shouldSplit)
569 {
570 child.divide();
571 }
572 });
573 }
574
575 merge ()
576 {
577 this.getChildren().forEach(child =>
578 {
579 child.getObjects().forEach(object =>
580 {
581 this.add(object, true);
582 object.node = this;
583 });
584 });
585
586 this.removeNodes();
587 }
588
589 size ()
590 {
591 if (this.objects != null)
592 {
593 return this.objects.length;
594 }
595 return 0;
596 }
597
598 getObjects ()
599 {
600 return this.objects;
601 }
602
603 getChildren ()
604 {
605 if (!this.hasChildren)
606 {
607 return [];
608 }
609
610 return [this.topleft, this.topright, this.bottomleft, this.bottomright];
611 }
612
613 findChildNode (position)
614 {
615 if (!this.hasChildren)
616 { return this; }
617
618 // Same midpoint rule as divide() so add/remove/query stay consistent,
619 // and we never return undefined on shared edges.
620 const midX = this.x1 + this.halfLengthX;
621 const midY = this.y1 + this.halfLengthY;
622
623 if (position.y > midY)
624 {
625 return position.x > midX ? this.bottomright : this.bottomleft;
626 }
627
628 return position.x > midX ? this.topright : this.topleft;
629 }
630
631 createNodes ()
632 {
633 if (this.hasChildren)
634 { return; }
635
636 const depth = this.depth + 1;
637
638 this.topleft = new Node(this.x1, this.y1, this.x1 + this.halfLengthX, this.y1 + this.halfLengthY, depth, this, this.name + 0, this.quadTree);
639
640 this.topright = new Node(this.x1 + this.halfLengthX, this.y1, this.x2, this.y1 + this.halfLengthY, depth, this, this.name + 1, this.quadTree);
641
642 this.bottomleft = new Node(this.x1, this.y1 + this.halfLengthY, this.x1 + this.halfLengthX, this.y2, depth, this, this.name + 2, this.quadTree);
643
644 this.bottomright = new Node(this.x1 + this.halfLengthX, this.y1 + this.halfLengthY, this.x2, this.y2, depth, this, this.name + 3, this.quadTree);
645
646 return this.getChildren();
647 }
648
649 createParent (nodePosition)
650 {
651 let parentNode;
652
653 if (nodePosition == "topleft")
654 {
655 parentNode = new Node(this.x1, this.y1, this.x1 + (this.lengthX * 2), this.y1 + (this.lengthY * 2), this.depth - 1, null, "", this.quadTree);
656
657 parentNode.topleft = this;
658 }
659
660 if (nodePosition == "topright")
661 {
662 parentNode = new Node(this.x1 - this.lengthX, this.y1, this.x1 + this.lengthX, this.y1 + (this.lengthY * 2), this.depth - 1, null, "", this.quadTree);
663
664 parentNode.topright = this;
665 }
666
667 if (nodePosition == "bottomleft")
668 {
669 parentNode = new Node(this.x1, this.y1 - this.lengthY, this.x1 + (this.lengthX * 2), this.y1 + this.lengthY, this.depth - 1, null, "", this.quadTree);
670
671 parentNode.bottomleft = this;
672 }
673
674 if (nodePosition == "bottomright")
675 {
676 parentNode = new Node(this.x1 - this.lengthX, this.y1 - this.lengthY, this.x1 + this.lengthX, this.y1 + this.lengthY, this.depth - 1, null, "", this.quadTree);
677
678 parentNode.bottomright = this;
679 }
680
681 this.parent = parentNode;
682 parentNode.recursiveCount = this.recursiveCount;
683
684 if (!parentNode.topleft)
685 {
686 parentNode.topleft = new Node(parentNode.x1, parentNode.y1, parentNode.x1 + parentNode.halfLengthX, parentNode.y1 + parentNode.halfLengthY, this.depth, parentNode, parentNode.name + 0, this.quadTree);
687 }
688
689 if (!parentNode.topright)
690 {
691 parentNode.topright = new Node(parentNode.x1 + parentNode.halfLengthX, parentNode.y1, parentNode.x2, parentNode.y1 + parentNode.halfLengthY, this.depth, parentNode, parentNode.name + 1, this.quadTree);
692 }
693
694 if (!parentNode.bottomleft)
695 {
696 parentNode.bottomleft = new Node(parentNode.x1, parentNode.y1 + parentNode.halfLengthY, parentNode.x1 + parentNode.halfLengthX, parentNode.y2, this.depth, parentNode, parentNode.name + 2, this.quadTree);
697 }
698
699 if (!parentNode.bottomright)
700 {
701 parentNode.bottomright = new Node(parentNode.x1 + parentNode.halfLengthX, parentNode.y1 + parentNode.halfLengthY, parentNode.x2, parentNode.y2, this.depth, parentNode, parentNode.name + 3, this.quadTree);
702 }
703
704 parentNode.reconfigureNames("");
705 return parentNode;
706 }
707
708 startReconfigureNames ()
709 {
710 let parent = this;
711 while (parent.parent)
712 {
713 parent = parent.parent;
714 }
715
716 parent.reconfigureNames("");
717 }
718
719 reconfigureNames (name)
720 {
721 this.name = name;
722 const children = this.getChildren();
723 for (let i = 0, l = children.length; i < l; i++)
724 {
725 children[i].reconfigureNames(name + i);
726 }
727 }
728
729 removeNodes ()
730 {
731 this.topleft = null;
732 this.topright = null;
733 this.bottomleft = null;
734 this.bottomright = null;
735 }
736
737 show (ctx)
738 {
739 ctx.strokeStyle = "white";
740 ctx.strokeRect(this.x1, this.y1, this.lengthX, this.lengthY);
741 }
742}