19716357641

Committed 26 Nov 2025 08:18PM UTC coverage: 88.641% (+0.07%) from 88.576%

Build # 19716357641

Build Type

Pull #3585

github

Committed by

web-flow

Commit Message

Merge 7d0f94fd5 into 3b683c589

Pull Request Pull Request #3585: feat!: debug draw improvements

Run Details

5289 of 7219 branches covered (73.26%)

280 of 306 new or added lines in 18 files covered. (91.5%)

4 existing lines in 2 files now uncovered.

14655 of 16533 relevant lines covered (88.64%)

24567.88 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

50.21

/src/engine/Collision/Detection/DynamicTree.ts

import { BoundingBox } from '../BoundingBox';
import type { Ray } from '../../Math/ray';
import { Logger } from '../../Util/Log';
import type { Id } from '../../Id';
import type { Entity } from '../../EntityComponentSystem/Entity';
import { BodyComponent } from '../BodyComponent';
import type { ExcaliburGraphicsContext } from '../..';
import { Color } from '../..';
import type { DynamicTreeConfig } from '../PhysicsConfig';

/**
 * Dynamic Tree Node used for tracking bounds within the tree
 */
export class TreeNode<T> {
  public left: TreeNode<T>;
  public right: TreeNode<T>;
  public bounds: BoundingBox;
  public height: number;
  public data: T;
  constructor(public parent?: TreeNode<T>) {
    this.parent = parent || null;
    this.data = null;
    this.bounds = new BoundingBox();
    this.left = null;
    this.right = null;
    this.height = 0;
  }

  public isLeaf(): boolean {
    return !this.left && !this.right;
  }
}

export interface ColliderProxy<T> {
  id: Id<'collider'>;
  owner: T;
  bounds: BoundingBox;
}

/**
 * The DynamicTrees provides a spatial partitioning data structure for quickly querying for overlapping bounding boxes for
 * all tracked bodies. The worst case performance of this is O(n*log(n)) where n is the number of bodies in the tree.
 *
 * Internally the bounding boxes are organized as a balanced binary tree of bounding boxes, where the leaf nodes are tracked bodies.
 * Every non-leaf node is a bounding box that contains child bounding boxes.
 */
export class DynamicTree<TProxy extends ColliderProxy<Entity>> {
  public root: TreeNode<TProxy>;
  public nodes: { [key: number]: TreeNode<TProxy> };
  constructor(
    private _config: Required<DynamicTreeConfig>,
    public worldBounds: BoundingBox = new BoundingBox(-Number.MAX_VALUE, -Number.MAX_VALUE, Number.MAX_VALUE, Number.MAX_VALUE)
  ) {
    this.root = null;
    this.nodes = {};
  }

  /**
   * Inserts a node into the dynamic tree
   */
  private _insert(leaf: TreeNode<TProxy>): void {
    // If there are no nodes in the tree, make this the root leaf
    if (this.root === null) {
      this.root = leaf;
      this.root.parent = null;
      return;
    }

    // Search the tree for a node that is not a leaf and find the best place to insert
    const leafAABB = leaf.bounds;
    let currentRoot = this.root;
    while (!currentRoot.isLeaf()) {
      const left = currentRoot.left;
      const right = currentRoot.right;

      const area = currentRoot.bounds.getPerimeter();
      const combinedAABB = currentRoot.bounds.combine(leafAABB);
      const combinedArea = combinedAABB.getPerimeter();

      // Calculate cost heuristic for creating a new parent and leaf
      const cost = 2 * combinedArea;

      // Minimum cost of pushing the leaf down the tree
      const inheritanceCost = 2 * (combinedArea - area);

      // Cost of descending
      let leftCost = 0;
      const leftCombined = leafAABB.combine(left.bounds);
      let newArea;
      let oldArea;
      if (left.isLeaf()) {
        leftCost = leftCombined.getPerimeter() + inheritanceCost;
      } else {
        oldArea = left.bounds.getPerimeter();
        newArea = leftCombined.getPerimeter();
        leftCost = newArea - oldArea + inheritanceCost;
      }

      let rightCost = 0;
      const rightCombined = leafAABB.combine(right.bounds);
      if (right.isLeaf()) {
        rightCost = rightCombined.getPerimeter() + inheritanceCost;
      } else {
        oldArea = right.bounds.getPerimeter();
        newArea = rightCombined.getPerimeter();
        rightCost = newArea - oldArea + inheritanceCost;
      }

      // cost is acceptable
      if (cost < leftCost && cost < rightCost) {
        break;
      }

      // Descend to the depths
      if (leftCost < rightCost) {
        currentRoot = left;
      } else {
        currentRoot = right;
      }
    }

    // Create the new parent node and insert into the tree
    const oldParent = currentRoot.parent;
    const newParent = new TreeNode(oldParent);
    newParent.bounds = leafAABB.combine(currentRoot.bounds);
    newParent.height = currentRoot.height + 1;

    if (oldParent !== null) {
      // The sibling node was not the root
      if (oldParent.left === currentRoot) {
        oldParent.left = newParent;
      } else {
        oldParent.right = newParent;
      }

      newParent.left = currentRoot;
      newParent.right = leaf;

      currentRoot.parent = newParent;
      leaf.parent = newParent;
    } else {
      // The sibling node was the root
      newParent.left = currentRoot;
      newParent.right = leaf;

      currentRoot.parent = newParent;
      leaf.parent = newParent;
      this.root = newParent;
    }

    // Walk up the tree fixing heights and AABBs
    let currentNode = leaf.parent;
    while (currentNode) {
      currentNode = this._balance(currentNode);

      if (!currentNode.left) {
        throw new Error('Parent of current leaf cannot have a null left child' + currentNode);
      }
      if (!currentNode.right) {
        throw new Error('Parent of current leaf cannot have a null right child' + currentNode);
      }

      currentNode.height = 1 + Math.max(currentNode.left.height, currentNode.right.height);
      currentNode.bounds = currentNode.left.bounds.combine(currentNode.right.bounds);

      currentNode = currentNode.parent;
    }
  }

  /**
   * Removes a node from the dynamic tree
   */
  private _remove(leaf: TreeNode<TProxy>) {
    if (leaf === this.root) {
      this.root = null;
      return;
    }

    const parent = leaf.parent;
    const grandParent = parent.parent;
    let sibling: TreeNode<TProxy>;
    if (parent.left === leaf) {
      sibling = parent.right;
    } else {
      sibling = parent.left;
    }

    if (grandParent) {
      if (grandParent.left === parent) {
        grandParent.left = sibling;
      } else {
        grandParent.right = sibling;
      }
      sibling.parent = grandParent;

      let currentNode = grandParent;
      while (currentNode) {
        currentNode = this._balance(currentNode);
        currentNode.bounds = currentNode.left.bounds.combine(currentNode.right.bounds);
        currentNode.height = 1 + Math.max(currentNode.left.height, currentNode.right.height);

        currentNode = currentNode.parent;
      }
    } else {
      this.root = sibling;
      sibling.parent = null;
    }
  }

  /**
   * Tracks a body in the dynamic tree
   */
  public trackCollider(collider: TProxy) {
    const node = new TreeNode<TProxy>();
    node.data = collider;
    node.bounds = collider.bounds;
    node.bounds.left -= 2;
    node.bounds.top -= 2;
    node.bounds.right += 2;
    node.bounds.bottom += 2;
    this.nodes[collider.id.value] = node;
    this._insert(node);
  }

  /**
   * Updates the dynamic tree given the current bounds of each body being tracked
   */
  public updateCollider(collider: TProxy) {
    const node = this.nodes[collider.id.value];
    if (!node) {
      return false;
    }
    const b = collider.bounds;

    // if the body is outside the world no longer update it
    if (!this.worldBounds.contains(b)) {
      Logger.getInstance().warn(
        'Collider with id ' + collider.id.value + ' is outside the world bounds and will no longer be tracked for physics'
      );
      this.untrackCollider(collider);
      return false;
    }

    if (node.bounds.contains(b)) {
      return false;
    }

    this._remove(node);
    b.left -= this._config.boundsPadding;
    b.top -= this._config.boundsPadding;
    b.right += this._config.boundsPadding;
    b.bottom += this._config.boundsPadding;

    // THIS IS CAUSING UNNECESSARY CHECKS
    if (collider.owner) {
      const body = collider.owner?.get(BodyComponent);
      if (body) {
        const multdx = ((body.vel.x * 32) / 1000) * this._config.velocityMultiplier;
        const multdy = ((body.vel.y * 32) / 1000) * this._config.velocityMultiplier;

        if (multdx < 0) {
          b.left += multdx;
        } else {
          b.right += multdx;
        }

        if (multdy < 0) {
          b.top += multdy;
        } else {
          b.bottom += multdy;
        }
      }
    }

    node.bounds = b;
    this._insert(node);
    return true;
  }

  /**
   * Untracks a body from the dynamic tree
   */
  public untrackCollider(collider: TProxy) {
    const node = this.nodes[collider.id.value];
    if (!node) {
      return;
    }
    this._remove(node);
    this.nodes[collider.id.value] = null;
    delete this.nodes[collider.id.value];
  }

  /**
   * Balances the tree about a node
   */
  private _balance(node: TreeNode<TProxy>) {
    if (node === null) {
      throw new Error('Cannot balance at null node');
    }

    if (node.isLeaf() || node.height < 2) {
      return node;
    }

    const left = node.left;
    const right = node.right;

    const a = node;
    const b = left;
    const c = right;
    const d = left.left;
    const e = left.right;
    const f = right.left;
    const g = right.right;

    const balance = c.height - b.height;
    // Rotate c node up
    if (balance > 1) {
      // Swap the right node with it's parent
      c.left = a;
      c.parent = a.parent;
      a.parent = c;

      // The original node's old parent should point to the right node
      // this is mega confusing
      if (c.parent) {
        if (c.parent.left === a) {
          c.parent.left = c;
        } else {
          c.parent.right = c;
        }
      } else {
        this.root = c;
      }

      // Rotate
      if (f.height > g.height) {
        c.right = f;
        a.right = g;
        g.parent = a;

        a.bounds = b.bounds.combine(g.bounds);
        c.bounds = a.bounds.combine(f.bounds);

        a.height = 1 + Math.max(b.height, g.height);
        c.height = 1 + Math.max(a.height, f.height);
      } else {
        c.right = g;
        a.right = f;
        f.parent = a;

        a.bounds = b.bounds.combine(f.bounds);
        c.bounds = a.bounds.combine(g.bounds);

        a.height = 1 + Math.max(b.height, f.height);
        c.height = 1 + Math.max(a.height, g.height);
      }

      return c;
    }
    // Rotate left node up
    if (balance < -1) {
      // swap
      b.left = a;
      b.parent = a.parent;
      a.parent = b;

      // node's old parent should point to b
      if (b.parent) {
        if (b.parent.left === a) {
          b.parent.left = b;
        } else {
          if (b.parent.right !== a) {
            throw 'Error rotating Dynamic Tree';
          }
          b.parent.right = b;
        }
      } else {
        this.root = b;
      }

      // rotate
      if (d.height > e.height) {
        b.right = d;
        a.left = e;
        e.parent = a;

        a.bounds = c.bounds.combine(e.bounds);
        b.bounds = a.bounds.combine(d.bounds);

        a.height = 1 + Math.max(c.height, e.height);
        b.height = 1 + Math.max(a.height, d.height);
      } else {
        b.right = e;
        a.left = d;
        d.parent = a;

        a.bounds = c.bounds.combine(d.bounds);
        b.bounds = a.bounds.combine(e.bounds);

        a.height = 1 + Math.max(c.height, d.height);
        b.height = 1 + Math.max(a.height, e.height);
      }
      return b;
    }

    return node;
  }

  /**
   * Returns the internal height of the tree, shorter trees are better. Performance drops as the tree grows
   */
  public getHeight(): number {
    if (this.root === null) {
      return 0;
    }
    return this.root.height;
  }

  /**
   * Queries the Dynamic Axis Aligned Tree for bodies that could be colliding with the provided body.
   *
   * In the query callback, it will be passed a potential collider. Returning true from this callback indicates
   * that you are complete with your query and you do not want to continue. Returning false will continue searching
   * the tree until all possible colliders have been returned.
   */
  public query(collider: TProxy, callback: (other: TProxy) => boolean): void {
    const bounds = collider.bounds;
    const helper = (currentNode: TreeNode<TProxy>): boolean => {
      if (currentNode && currentNode.bounds.overlaps(bounds)) {
        if (currentNode.isLeaf() && currentNode.data !== collider) {
          if (callback.call(collider, currentNode.data)) {
            return true;
          }
        } else {
          return helper(currentNode.left) || helper(currentNode.right);
        }
      }
      return false;
    };
    helper(this.root);
  }

  /**
   * Queries the Dynamic Axis Aligned Tree for bodies that could be intersecting. By default the raycast query uses an infinitely
   * long ray to test the tree specified by `max`.
   *
   * In the query callback, it will be passed a potential body that intersects with the raycast. Returning true from this
   * callback indicates that your are complete with your query and do not want to continue. Return false will continue searching
   * the tree until all possible bodies that would intersect with the ray have been returned.
   */
  public rayCastQuery(ray: Ray, max: number = Infinity, callback: (other: TProxy) => boolean): void {
    const helper = (currentNode: TreeNode<TProxy>): boolean => {
      if (currentNode && currentNode.bounds.rayCast(ray, max)) {
        if (currentNode.isLeaf()) {
          if (callback.call(ray, currentNode.data)) {
            // ray hit a leaf! return the body
            return true;
          }
        } else {
          // ray hit but not at a leaf, recurse deeper
          return helper(currentNode.left) || helper(currentNode.right);
        }
      }
      return false; // ray missed
    };
    helper(this.root);
  }

  public getNodes(): TreeNode<TProxy>[] {
    const helper = (currentNode: TreeNode<TProxy>): TreeNode<TProxy>[] => {
      if (currentNode) {
        return [currentNode].concat(helper(currentNode.left), helper(currentNode.right));
      } else {
        return [];
      }
    };
    return helper(this.root);
  }

  public debug(ex: ExcaliburGraphicsContext) {
    // draw all the nodes in the Dynamic Tree
    const helper = (currentNode: TreeNode<TProxy>) => {
      if (currentNode) {
        if (currentNode.isLeaf()) {
          currentNode.bounds.debug(ex, { color: Color.Green });
        } else {
          currentNode.bounds.debug(ex, { color: Color.White });
        }

        if (currentNode.left) {
          helper(currentNode.left);
        }
        if (currentNode.right) {
          helper(currentNode.right);
        }
      }
    };

    helper(this.root);
  }
}

1	import { BoundingBox } from '../BoundingBox';
2	import type { Ray } from '../../Math/ray';
3	import { Logger } from '../../Util/Log';
4	import type { Id } from '../../Id';
5	import type { Entity } from '../../EntityComponentSystem/Entity';
6	import { BodyComponent } from '../BodyComponent';
7	import type { ExcaliburGraphicsContext } from '../..';
8	import { Color } from '../..';
9	import type { DynamicTreeConfig } from '../PhysicsConfig';
10
11	/**
12	* Dynamic Tree Node used for tracking bounds within the tree
13	*/
14	export class TreeNode<T> {
15	public left: TreeNode<T>;
16	public right: TreeNode<T>;
17	public bounds: BoundingBox;
18	public height: number;
19	public data: T;
20	constructor(public parent?: TreeNode<T>) {	337✔
21	this.parent = parent \|\| null;	337✔
22	this.data = null;	337✔
23	this.bounds = new BoundingBox();	337✔
24	this.left = null;	337✔
25	this.right = null;	337✔
26	this.height = 0;	337✔
27	}
28
29	public isLeaf(): boolean {
30	return !this.left && !this.right;	393✔
31	}
32	}
33
34	export interface ColliderProxy<T> {
35	id: Id<'collider'>;
36	owner: T;
37	bounds: BoundingBox;
38	}
39
40	/**
41	* The DynamicTrees provides a spatial partitioning data structure for quickly querying for overlapping bounding boxes for
42	* all tracked bodies. The worst case performance of this is O(n*log(n)) where n is the number of bodies in the tree.
43	*
44	* Internally the bounding boxes are organized as a balanced binary tree of bounding boxes, where the leaf nodes are tracked bodies.
45	* Every non-leaf node is a bounding box that contains child bounding boxes.
46	*/
47	export class DynamicTree<TProxy extends ColliderProxy<Entity>> {
48	public root: TreeNode<TProxy>;
49	public nodes: { [key: number]: TreeNode<TProxy> };
50	constructor(
51	private _config: Required<DynamicTreeConfig>,	194✔
52	public worldBounds: BoundingBox = new BoundingBox(-Number.MAX_VALUE, -Number.MAX_VALUE, Number.MAX_VALUE, Number.MAX_VALUE)	194✔
53	) {
54	this.root = null;	194✔
55	this.nodes = {};	194✔
56	}
57
58	/**
59	* Inserts a node into the dynamic tree
60	*/
61	private _insert(leaf: TreeNode<TProxy>): void {
62	// If there are no nodes in the tree, make this the root leaf
63	if (this.root === null) {	222✔
64	this.root = leaf;	107✔
65	this.root.parent = null;	107✔
66	return;	107✔
67	}
68
69	// Search the tree for a node that is not a leaf and find the best place to insert
70	const leafAABB = leaf.bounds;	115✔
71	let currentRoot = this.root;	115✔
72	while (!currentRoot.isLeaf()) {	115✔
73	const left = currentRoot.left;	18✔
74	const right = currentRoot.right;	18✔
75
76	const area = currentRoot.bounds.getPerimeter();	18✔
77	const combinedAABB = currentRoot.bounds.combine(leafAABB);	18✔
78	const combinedArea = combinedAABB.getPerimeter();	18✔
79
80	// Calculate cost heuristic for creating a new parent and leaf
81	const cost = 2 * combinedArea;	18✔
82
83	// Minimum cost of pushing the leaf down the tree
84	const inheritanceCost = 2 * (combinedArea - area);	18✔
85
86	// Cost of descending
87	let leftCost = 0;	18✔
88	const leftCombined = leafAABB.combine(left.bounds);	18✔
89	let newArea;
90	let oldArea;
91	if (left.isLeaf()) {	18!
92	leftCost = leftCombined.getPerimeter() + inheritanceCost;	18✔
93	} else {
94	oldArea = left.bounds.getPerimeter();	×
95	newArea = leftCombined.getPerimeter();	×
96	leftCost = newArea - oldArea + inheritanceCost;	×
97	}
98
99	let rightCost = 0;	18✔
100	const rightCombined = leafAABB.combine(right.bounds);	18✔
101	if (right.isLeaf()) {	18!
102	rightCost = rightCombined.getPerimeter() + inheritanceCost;	18✔
103	} else {
104	oldArea = right.bounds.getPerimeter();	×
105	newArea = rightCombined.getPerimeter();	×
106	rightCost = newArea - oldArea + inheritanceCost;	×
107	}
108
109	// cost is acceptable
110	if (cost < leftCost && cost < rightCost) {	18✔
111	break;	1✔
112	}
113
114	// Descend to the depths
115	if (leftCost < rightCost) {	17✔
116	currentRoot = left;	2✔
117	} else {
118	currentRoot = right;	15✔
119	}
120	}
121
122	// Create the new parent node and insert into the tree
123	const oldParent = currentRoot.parent;	115✔
124	const newParent = new TreeNode(oldParent);	115✔
125	newParent.bounds = leafAABB.combine(currentRoot.bounds);	115✔
126	newParent.height = currentRoot.height + 1;	115✔
127
128	if (oldParent !== null) {	115✔
129	// The sibling node was not the root
130	if (oldParent.left === currentRoot) {	17✔
131	oldParent.left = newParent;	2✔
132	} else {
133	oldParent.right = newParent;	15✔
134	}
135
136	newParent.left = currentRoot;	17✔
137	newParent.right = leaf;	17✔
138
139	currentRoot.parent = newParent;	17✔
140	leaf.parent = newParent;	17✔
141	} else {
142	// The sibling node was the root
143	newParent.left = currentRoot;	98✔
144	newParent.right = leaf;	98✔
145
146	currentRoot.parent = newParent;	98✔
147	leaf.parent = newParent;	98✔
148	this.root = newParent;	98✔
149	}
150
151	// Walk up the tree fixing heights and AABBs
152	let currentNode = leaf.parent;	115✔
153	while (currentNode) {	115✔
154	currentNode = this._balance(currentNode);	132✔
155
156	if (!currentNode.left) {	132!
157	throw new Error('Parent of current leaf cannot have a null left child' + currentNode);	×
158	}
159	if (!currentNode.right) {	132!
160	throw new Error('Parent of current leaf cannot have a null right child' + currentNode);	×
161	}
162
163	currentNode.height = 1 + Math.max(currentNode.left.height, currentNode.right.height);	132✔
164	currentNode.bounds = currentNode.left.bounds.combine(currentNode.right.bounds);	132✔
165
166	currentNode = currentNode.parent;	132✔
167	}
168	}
169
170	/**
171	* Removes a node from the dynamic tree
172	*/
173	private _remove(leaf: TreeNode<TProxy>) {
174	if (leaf === this.root) {	2✔
175	this.root = null;	1✔
176	return;	1✔
177	}
178
179	const parent = leaf.parent;	1✔
180	const grandParent = parent.parent;	1✔
181	let sibling: TreeNode<TProxy>;
182	if (parent.left === leaf) {	1!
183	sibling = parent.right;	1✔
184	} else {
185	sibling = parent.left;	×
186	}
187
188	if (grandParent) {	1!
189	if (grandParent.left === parent) {	×
190	grandParent.left = sibling;	×
191	} else {
192	grandParent.right = sibling;	×
193	}
194	sibling.parent = grandParent;	×
195
196	let currentNode = grandParent;	×
197	while (currentNode) {	×
198	currentNode = this._balance(currentNode);	×
199	currentNode.bounds = currentNode.left.bounds.combine(currentNode.right.bounds);	×
200	currentNode.height = 1 + Math.max(currentNode.left.height, currentNode.right.height);	×
201
202	currentNode = currentNode.parent;	×
203	}
204	} else {
205	this.root = sibling;	1✔
206	sibling.parent = null;	1✔
207	}
208	}
209
210	/**
211	* Tracks a body in the dynamic tree
212	*/
213	public trackCollider(collider: TProxy) {
214	const node = new TreeNode<TProxy>();	222✔
215	node.data = collider;	222✔
216	node.bounds = collider.bounds;	222✔
217	node.bounds.left -= 2;	222✔
218	node.bounds.top -= 2;	222✔
219	node.bounds.right += 2;	222✔
220	node.bounds.bottom += 2;	222✔
221	this.nodes[collider.id.value] = node;	222✔
222	this._insert(node);	222✔
223	}
224
225	/**
226	* Updates the dynamic tree given the current bounds of each body being tracked
227	*/
228	public updateCollider(collider: TProxy) {
229	const node = this.nodes[collider.id.value];	×
230	if (!node) {	×
231	return false;	×
232	}
233	const b = collider.bounds;	×
234
235	// if the body is outside the world no longer update it
236	if (!this.worldBounds.contains(b)) {	×
237	Logger.getInstance().warn(	×
238	'Collider with id ' + collider.id.value + ' is outside the world bounds and will no longer be tracked for physics'
239	);
240	this.untrackCollider(collider);	×
241	return false;	×
242	}
243
244	if (node.bounds.contains(b)) {	×
245	return false;	×
246	}
247
248	this._remove(node);	×
249	b.left -= this._config.boundsPadding;	×
250	b.top -= this._config.boundsPadding;	×
251	b.right += this._config.boundsPadding;	×
252	b.bottom += this._config.boundsPadding;	×
253
254	// THIS IS CAUSING UNNECESSARY CHECKS
255	if (collider.owner) {	×
256	const body = collider.owner?.get(BodyComponent);	×
257	if (body) {	×
258	const multdx = ((body.vel.x * 32) / 1000) * this._config.velocityMultiplier;	×
259	const multdy = ((body.vel.y * 32) / 1000) * this._config.velocityMultiplier;	×
260
261	if (multdx < 0) {	×
262	b.left += multdx;	×
263	} else {
264	b.right += multdx;	×
265	}
266
267	if (multdy < 0) {	×
268	b.top += multdy;	×
269	} else {
270	b.bottom += multdy;	×
271	}
272	}
273	}
274
275	node.bounds = b;	×
276	this._insert(node);	×
277	return true;	×
278	}
279
280	/**
281	* Untracks a body from the dynamic tree
282	*/
283	public untrackCollider(collider: TProxy) {
284	const node = this.nodes[collider.id.value];	2✔
285	if (!node) {	2!
286	return;	×
287	}
288	this._remove(node);	2✔
289	this.nodes[collider.id.value] = null;	2✔
290	delete this.nodes[collider.id.value];	2✔
291	}
292
293	/**
294	* Balances the tree about a node
295	*/
296	private _balance(node: TreeNode<TProxy>) {
297	if (node === null) {	132!
298	throw new Error('Cannot balance at null node');	×
299	}
300
301	if (node.isLeaf() \|\| node.height < 2) {	132✔
302	return node;	131✔
303	}
304
305	const left = node.left;	1✔
306	const right = node.right;	1✔
307
308	const a = node;	1✔
309	const b = left;	1✔
310	const c = right;	1✔
311	const d = left.left;	1✔
312	const e = left.right;	1✔
313	const f = right.left;	1✔
314	const g = right.right;	1✔
315
316	const balance = c.height - b.height;	1✔
317	// Rotate c node up
318	if (balance > 1) {	1!
319	// Swap the right node with it's parent
320	c.left = a;	×
321	c.parent = a.parent;	×
322	a.parent = c;	×
323
324	// The original node's old parent should point to the right node
325	// this is mega confusing
326	if (c.parent) {	×
327	if (c.parent.left === a) {	×
328	c.parent.left = c;	×
329	} else {
330	c.parent.right = c;	×
331	}
332	} else {
333	this.root = c;	×
334	}
335
336	// Rotate
337	if (f.height > g.height) {	×
338	c.right = f;	×
339	a.right = g;	×
340	g.parent = a;	×
341
342	a.bounds = b.bounds.combine(g.bounds);	×
343	c.bounds = a.bounds.combine(f.bounds);	×
344
345	a.height = 1 + Math.max(b.height, g.height);	×
346	c.height = 1 + Math.max(a.height, f.height);	×
347	} else {
348	c.right = g;	×
349	a.right = f;	×
350	f.parent = a;	×
351
352	a.bounds = b.bounds.combine(f.bounds);	×
353	c.bounds = a.bounds.combine(g.bounds);	×
354
355	a.height = 1 + Math.max(b.height, f.height);	×
356	c.height = 1 + Math.max(a.height, g.height);	×
357	}
358
359	return c;	×
360	}
361	// Rotate left node up
362	if (balance < -1) {	1!
363	// swap
364	b.left = a;	×
365	b.parent = a.parent;	×
366	a.parent = b;	×
367
368	// node's old parent should point to b
369	if (b.parent) {	×
370	if (b.parent.left === a) {	×
371	b.parent.left = b;	×
372	} else {
373	if (b.parent.right !== a) {	×
374	throw 'Error rotating Dynamic Tree';	×
375	}
376	b.parent.right = b;	×
377	}
378	} else {
379	this.root = b;	×
380	}
381
382	// rotate
383	if (d.height > e.height) {	×
384	b.right = d;	×
385	a.left = e;	×
386	e.parent = a;	×
387
388	a.bounds = c.bounds.combine(e.bounds);	×
389	b.bounds = a.bounds.combine(d.bounds);	×
390
391	a.height = 1 + Math.max(c.height, e.height);	×
392	b.height = 1 + Math.max(a.height, d.height);	×
393	} else {
394	b.right = e;	×
395	a.left = d;	×
396	d.parent = a;	×
397
398	a.bounds = c.bounds.combine(d.bounds);	×
399	b.bounds = a.bounds.combine(e.bounds);	×
400
401	a.height = 1 + Math.max(c.height, d.height);	×
402	b.height = 1 + Math.max(a.height, e.height);	×
403	}
404	return b;	×
405	}
406
407	return node;	1✔
408	}
409
410	/**
411	* Returns the internal height of the tree, shorter trees are better. Performance drops as the tree grows
412	*/
413	public getHeight(): number {
414	if (this.root === null) {	×
415	return 0;	×
416	}
417	return this.root.height;	×
418	}
419
420	/**
421	* Queries the Dynamic Axis Aligned Tree for bodies that could be colliding with the provided body.
422	*
423	* In the query callback, it will be passed a potential collider. Returning true from this callback indicates
424	* that you are complete with your query and you do not want to continue. Returning false will continue searching
425	* the tree until all possible colliders have been returned.
426	*/
427	public query(collider: TProxy, callback: (other: TProxy) => boolean): void {
428	const bounds = collider.bounds;	24✔
429	const helper = (currentNode: TreeNode<TProxy>): boolean => {	24✔
430	if (currentNode && currentNode.bounds.overlaps(bounds)) {	100✔
431	if (currentNode.isLeaf() && currentNode.data !== collider) {	60✔
432	if (callback.call(collider, currentNode.data)) {	22!
433	return true;	×
434	}
435	} else {
436	return helper(currentNode.left) \|\| helper(currentNode.right);	38✔
437	}
438	}
439	return false;	62✔
440	};
441	helper(this.root);	24✔
442	}
443
444	/**
445	* Queries the Dynamic Axis Aligned Tree for bodies that could be intersecting. By default the raycast query uses an infinitely
446	* long ray to test the tree specified by `max`.
447	*
448	* In the query callback, it will be passed a potential body that intersects with the raycast. Returning true from this
449	* callback indicates that your are complete with your query and do not want to continue. Return false will continue searching
450	* the tree until all possible bodies that would intersect with the ray have been returned.
451	*/
452	public rayCastQuery(ray: Ray, max: number = Infinity, callback: (other: TProxy) => boolean): void {	×
453	const helper = (currentNode: TreeNode<TProxy>): boolean => {	10✔
454	if (currentNode && currentNode.bounds.rayCast(ray, max)) {	35✔
455	if (currentNode.isLeaf()) {	33✔
456	if (callback.call(ray, currentNode.data)) {	20✔
457	// ray hit a leaf! return the body
458	return true;	2✔
459	}
460	} else {
461	// ray hit but not at a leaf, recurse deeper
462	return helper(currentNode.left) \|\| helper(currentNode.right);	13✔
463	}
464	}
465	return false; // ray missed	20✔
466	};
467	helper(this.root);	10✔
468	}
469
470	public getNodes(): TreeNode<TProxy>[] {
471	const helper = (currentNode: TreeNode<TProxy>): TreeNode<TProxy>[] => {	×
472	if (currentNode) {	×
473	return [currentNode].concat(helper(currentNode.left), helper(currentNode.right));	×
474	} else {
475	return [];	×
476	}
477	};
478	return helper(this.root);	×
479	}
480
481	public debug(ex: ExcaliburGraphicsContext) {
482	// draw all the nodes in the Dynamic Tree
483	const helper = (currentNode: TreeNode<TProxy>) => {	×
484	if (currentNode) {	×
485	if (currentNode.isLeaf()) {	×
NEW 486	currentNode.bounds.debug(ex, { color: Color.Green });	×
487	} else {
NEW 488	currentNode.bounds.debug(ex, { color: Color.White });	×
489	}
490
491	if (currentNode.left) {	×
492	helper(currentNode.left);	×
493	}
494	if (currentNode.right) {	×
495	helper(currentNode.right);	×
496	}
497	}
498	};
499
500	helper(this.root);	×
501	}
502	}

excaliburjs / Excalibur / 19716357641

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous