BlueGit

timfa frameworkv3

Files

frameworkv3 / framework / util / quadTree.js

quadTree.js

run linter with --fix
timfa Tim Falken · pushed by timfa · 2 years ago
80d13a97 History
quadTree.js 14.4 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 const 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 const 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 const 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 const result = [];
99
100 const nodes = [];
101
102 types = Array.isArray(types) ? types : [types];
103
104 nodes.push(this.root);
105
106 while (nodes.length > 0)
107 {
108 const node = nodes.pop();
109
110 if (this.isInRange(position, range, node))
111 {
112 if (!node.hasChildren)
113 {
114 let filtered = node.getObjects()
115 .filter(obj => obj.transform.position.distanceTo(position) < range && obj.transform.position.distanceTo(position) > 0);
116
117 if (types != null)
118 {
119 filtered = filtered.filter(obj => types.some(t => obj instanceof t));
120 }
121
122 result.push(...filtered);
123 }
124 else
125 {
126 nodes.push(...node.getChildren());
127 }
128 }
129 }
130
131 return result.sort((a, b) => a.transform.position.distanceTo(position) - b.transform.position.distanceTo(position));
132 }
133
134 getObjectsWithTagInRange = function (position, range, tags)
135 {
136 const result = [];
137
138 const nodes = [];
139
140 tags = Array.isArray(tags) ? tags : [tags];
141
142 nodes.push(this.root);
143
144 while (nodes.length > 0)
145 {
146 const node = nodes.pop();
147
148 if (this.isInRange(position, range, node))
149 {
150 if (!node.hasChildren)
151 {
152 let filtered = node.getObjects()
153 .filter(obj => obj.transform.position.distanceTo(position) < range && obj.transform.position.distanceTo(position) > 0);
154
155 if (tags != null)
156 {
157 filtered = filtered.filter(obj => tags.some(t => obj.tags.some(tag => tag == t)));
158 }
159
160 result.push(...filtered);
161 }
162 else
163 {
164 nodes.push(...node.getChildren());
165 }
166 }
167 }
168
169 return result.sort((a, b) => a.transform.position.distanceTo(position) - b.transform.position.distanceTo(position));
170 };
171
172 isInRange (vector, range, node)
173 {
174 var points =
175 [
176 vector.x - range,
177 vector.x + range,
178 vector.y - range,
179 vector.y + range
180 ];
181
182 if (points[1] >= node.x1 && points[0] <= node.x2)
183 {
184 if (points[3] >= node.y1 && points[2] <= node.y2)
185 {
186 return true;
187 }
188 }
189 return false;
190 }
191
192 embiggen (dirOfOob)
193 {
194 if (dirOfOob == "L")
195 {
196 this.root = this.root.createParent("bottomright");
197 }
198 else if (dirOfOob == "R")
199 {
200 this.root = this.root.createParent("topleft");
201 }
202 else if (dirOfOob == "U")
203 {
204 this.root = this.root.createParent("bottomleft");
205 }
206 else if (dirOfOob == "D")
207 {
208 this.root = this.root.createParent("topleft");
209 }
210
211 }
212
213 traverseTo (path)
214 {
215 let node = this.root;
216
217 for (let i = 0, len = path.length; i < len; i++)
218 {
219 if (!node.hasChildren)
220 { return node; }
221
222 node = node.getChildren()[path[i]];
223 }
224
225 return node;
226 }
227
228 findNodeFromRoot (object)
229 {
230 return this.findNodeFromRootAtPosition(object.transform.position);
231 }
232
233 findNodeFromRootAtPosition (position)
234 {
235 if (!this.root.hasChildren)
236 {
237 return this.root;
238 }
239
240 let node = this.root.findChildNode(position);
241
242 while (node.hasChildren)
243 {
244 node = node.findChildNode(position);
245 }
246
247 return node;
248 }
249
250 countObjectsInChild (parentNode)
251 {
252 if (!parentnode.hasChildren)
253 {
254 return 0;
255 }
256
257 return parentNode.topleft.size() + parentNode.topright.size()
258 + parentNode.bottomleft.size() + parentNode.bottomright.size();
259 }
260
261 show (ctx)
262 {
263 this.showAll(this.root, ctx);
264 }
265
266 showAll (node, ctx)
267 {
268 node.show(ctx);
269
270 if (node.hasChildren)
271 {
272 node.getChildren().forEach((element) => this.showAll(element, ctx));
273 }
274 }
275
276 update (deltaTime)
277 {
278 this.root.update(deltaTime);
279 }
280
281 outOfBounds (object)
282 {
283 const pos = object.transform.position;
284
285 if (pos.x < this.root.x1)
286 {
287 return "L";
288 }
289
290 if (pos.x > this.root.x2 + this.root.x1)
291 {
292 return "R";
293 }
294
295 if (pos.y < this.root.y1)
296 {
297 return "U";
298 }
299
300 if (pos.y > this.root.y2 + this.root.y1)
301 {
302 return "D";
303 }
304
305 return false;
306 }
307}
308
309class Node
310{
311 get canBeMerged ()
312 {
313 return !this.hasChildren && this.parent && this.parent.recursiveCount < this.quadTree.bucketSize;
314 }
315
316 get shouldSplit ()
317 {
318 return !this.hasChildren && this.recursiveCount > this.quadTree.bucketSize;
319 }
320
321 get hasChildren ()
322 {
323 return this.bottomright != null; //assume the rest is there too
324 }
325
326 constructor (x1, y1, x2, y2, depth, parent, name, quadTree)
327 {
328 this.name = name;
329
330 this.x1 = x1;
331 this.x2 = x2;
332 this.y1 = y1;
333 this.y2 = y2;
334
335 this.objects = [];
336
337 this.topleft = null;
338 this.topright = null;
339 this.bottomleft = null;
340 this.bottomright = null;
341
342 this.parent = parent;
343
344 this.depth = depth;
345 this.recursiveCount = 0;
346
347 this.lengthX = this.x2 - this.x1;
348 this.lengthY = this.y2 - this.y1;
349
350 this.halfLengthX = this.lengthX / 2;
351 this.halfLengthY = this.lengthY / 2;
352
353 this.markedForCleanup = false;
354 this.timer = 0;
355
356 this.quadTree = quadTree;
357 }
358
359 addCount ()
360 {
361 this.recursiveCount++;
362
363 this.parent && this.parent.addCount();
364
365 if (this.shouldSplit)
366 {
367 this.divide();
368 }
369 }
370
371 removeCount ()
372 {
373 this.recursiveCount--;
374
375 this.parent && this.parent.removeCount();
376
377 if (this.hasChildren)
378 {
379 let merge = true;
380 const children = this.getChildren();
381 for (let i = 0, l = children.length; i < l; i++)
382 {
383 if (!children[i].canBeMerged)
384 { merge = false; }
385 }
386
387 if (merge)
388 {
389 this.merge();
390 }
391 }
392 }
393
394 remove (obj)
395 {
396 if (this.objects && this.objects.indexOf(obj) >= 0)
397 {
398 this.objects = this.objects.filter(ind => ind != obj);
399 this.removeCount();
400 }
401 }
402
403 add (obj, ignoreCount)
404 {
405 if (this.objects.indexOf(obj) < 0)
406 {
407 this.objects.push(obj);
408
409 if (!ignoreCount)
410 { this.addCount(); }
411 }
412 }
413
414 divide ()
415 {
416 this.createNodes();
417 const center = new vector((this.x1 + this.x2) / 2, (this.y1 + this.y2) / 2);
418
419 this.objects.forEach(object =>
420 {
421 if (object.transform.position.y > center.y)
422 {
423 if (object.transform.position.x > center.x)
424 {
425 object.node = this.bottomright;
426 this.bottomright.add(object, true);
427 }
428 else
429 {
430 object.node = this.bottomleft;
431 this.bottomleft.add(object, true);
432 }
433 }
434 else
435 {
436 if (object.transform.position.x > center.x)
437 {
438 object.node = this.topright;
439 this.topright.add(object, true);
440 }
441 else
442 {
443 object.node = this.topleft;
444 this.topleft.add(object, true);
445 }
446 }
447 });
448
449 this.objects = [];
450 }
451
452 merge ()
453 {
454 this.getChildren().forEach(child =>
455 {
456 child.getObjects().forEach(object =>
457 {
458 this.add(object, true);
459 object.node = this;
460 });
461 });
462
463 this.removeNodes();
464 }
465
466 size ()
467 {
468 if (this.objects != null)
469 {
470 return this.objects.length;
471 }
472 return 0;
473 }
474
475 getObjects ()
476 {
477 return this.objects;
478 }
479
480 getChildren ()
481 {
482 if (!this.hasChildren)
483 {
484 return [];
485 }
486
487 return [this.topleft, this.topright, this.bottomleft, this.bottomright];
488 }
489
490 findChildNode (position)
491 {
492 if (!this.hasChildren)
493 { return this; }
494
495 if (position.x >= this.topleft.x1 && position.x <= this.topleft.x2 && position.y >= this.topleft.y1 && position.y <= this.topleft.y2)
496 {
497 return this.topleft;
498 }
499 else if (position.x >= this.bottomleft.x1 && position.x <= this.bottomleft.x2 && position.y >= this.bottomleft.y1 && position.y <= this.bottomleft.y2)
500 {
501 return this.bottomleft;
502 }
503 else if (position.x >= this.topright.x1 && position.x <= this.topright.x2 && position.y >= this.topright.y1 && position.y <= this.topright.y2)
504 {
505 return this.topright;
506 }
507 else if (position.x >= this.bottomright.x1 && position.x <= this.bottomright.x2 && position.y >= this.bottomright.y1 && position.y <= this.bottomright.y2)
508 {
509 return this.bottomright;
510 }
511 }
512
513 createNodes ()
514 {
515 if (this.hasChildren)
516 { return; }
517
518 const depth = this.depth + 1;
519
520 this.topleft = new Node(this.x1, this.y1, this.x1 + this.halfLengthX, this.y1 + this.halfLengthY, depth, this, this.name + 0, this.quadTree);
521
522 this.topright = new Node(this.x1 + this.halfLengthX, this.y1, this.x2, this.y1 + this.halfLengthY, depth, this, this.name + 1, this.quadTree);
523
524 this.bottomleft = new Node(this.x1, this.y1 + this.halfLengthY, this.x1 + this.halfLengthX, this.y2, depth, this, this.name + 2, this.quadTree);
525
526 this.bottomright = new Node(this.x1 + this.halfLengthX, this.y1 + this.halfLengthY, this.x2, this.y2, depth, this, this.name + 3, this.quadTree);
527
528 return this.getChildren();
529 }
530
531 createParent (nodePosition)
532 {
533 let parentNode;
534
535 if (nodePosition == "topleft")
536 {
537 parentNode = new Node(this.x1, this.y1, this.lengthX * 2, this.lengthY * 2, this.depth - 1, null, "", this.quadTree);
538
539 parentNode.topleft == this;
540 }
541
542 if (nodePosition == "topright")
543 {
544 parentNode = new Node(this.x1 - this.lengthX, this.y1, this.lengthX * 2, this.lengthY * 2, this.depth - 1, null, "", this.quadTree);
545
546 parentNode.topright == this;
547 }
548
549 if (nodePosition == "bottomleft")
550 {
551 parentNode = new Node(this.x1, this.y1 - this.lengthY, this.lengthX * 2, this.lengthY * 2, this.depth - 1, null, "", this.quadTree);
552
553 parentNode.bottomleft == this;
554 }
555
556 if (nodePosition == "bottomright")
557 {
558 parentNode = new Node(this.x1 - this.lengthX, this.y1 - this.lengthY, this.lengthX * 2, this.lengthY * 2, this.depth - 1, null, "", this.quadTree);
559
560 parentNode.bottomright == this;
561 }
562
563 if (!parentNode.topleft)
564 {
565 parentNode.topleft = new Node(parentNode.x1, parentNode.y1, parentNode.x1 + parentNode.halfLengthX, parentNode.y1 + parentNode.halfLengthY, this.depth, parentNode, parentNode.name + 0, this.quadTree);
566 }
567
568 if (!parentNode.topright)
569 {
570 parentNode.topright = new Node(parentNode.x1 + parentNode.halfLengthX, parentNode.y1, parentNode.x2, parentNode.y1 + parentNode.halfLengthY, this.depth, parentNode, parentNode.name + 1, this.quadTree);
571 }
572
573 if (!parentNode.bottomleft)
574 {
575 parentNode.bottomleft = new Node(parentNode.x1, parentNode.y1 + parentNode.halfLengthY, parentNode.x1 + parentNode.halfLengthX, parentNode.y2, this.depth, parentNode, parentNode.name + 2, this.quadTree);
576 }
577
578 if (!parentNode.bottomright)
579 {
580 parentNode.bottomright = new Node(parentNode.x1 + parentNode.halfLengthX, parentNode.y1 + parentNode.halfLengthY, parentNode.x2, parentNode.y2, this.depth, parentNode, parentNode.name + 3, this.quadTree);
581 }
582
583 this.startReconfigureNames();
584 return parentNode;
585 }
586
587 startReconfigureNames ()
588 {
589 let parent = this;
590 while (parent.parent)
591 {
592 parent = parent.parent;
593 }
594
595 parent.reconfigureNames("");
596 }
597
598 reconfigureNames (name)
599 {
600 this.name = name;
601 const children = this.getChildren();
602 for (let i = 0, l = children.length; i < l; i++)
603 {
604 children[i].reconfigureNames(name + i);
605 }
606 }
607
608 removeNodes ()
609 {
610 this.topleft = null;
611 this.topright = null;
612 this.bottomleft = null;
613 this.bottomright = null;
614 }
615
616 update (deltaTime)
617 {
618 if (this.hasChildren)
619 {
620 this.topleft.update(deltaTime);
621 this.topright.update(deltaTime);
622 this.bottomleft.update(deltaTime);
623 this.bottomright.update(deltaTime);
624 }
625 }
626
627 /**
628 * Retrieves the same-level neighbour if possible, or the lowest level if not.
629 *
630 * @param {string} direction L, R, U or D
631 */
632 getNeighbour (direction)
633 {
634 const name = this.name.split("");
635 const hmap = { 0: 1, 1: 0, 2: 3, 3: 2 };
636 const vmap = { 0: 2, 2: 0, 1: 3, 3: 1 };
637
638 switch (direction)
639 {
640 case "L":
641 if (name[name.length - 1] == "0" || name[name.length - 1] == "2")
642 {
643 if (name.length > 1)
644 { name[name.length - 2] = hmap[name[name.length - 2]]; }
645 else
646 { return null; }
647 }
648 name[name.length - 1] = hmap[name[name.length - 1]];
649 break;
650 case "R":
651 if (name[name.length - 1] == "1" || name[name.length - 1] == "3")
652 {
653 if (name.length > 1)
654 { name[name.length - 2] = hmap[name[name.length - 2]]; }
655 else
656 { return null; }
657 }
658 name[name.length - 1] = hmap[name[name.length - 1]];
659 break;
660 case "U":
661 if (name[name.length - 1] == "0" || name[name.length - 1] == "1")
662 {
663 if (name.length > 1)
664 { name[name.length - 2] = vmap[name[name.length - 2]]; }
665 else
666 { return null; }
667 }
668 name[name.length - 1] = vmap[name[name.length - 1]];
669 break;
670 case "D":
671 if (name[name.length - 1] == "2" || name[name.length - 1] == "3")
672 {
673 if (name.length > 1)
674 { name[name.length - 2] = vmap[name[name.length - 2]]; }
675 else
676 { return null; }
677 }
678 name[name.length - 1] = vmap[name[name.length - 1]];
679 break;
680 }
681
682 return quadTree.traverseTo(name.join(""));
683 }
684
685 show (ctx)
686 {
687 ctx.strokeStyle = "white";
688 ctx.strokeRect(this.x1, this.y1, this.lengthX, this.lengthY);
689 }
690}