BlueGit

timfa frameworkv3

Files

frameworkv3 / framework / util / quadTree.js

quadTree.js

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