BlueGit

timfa frameworkv3

Files

frameworkv3 / framework / util / quadTree.js

quadTree.js

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