14804036802

Committed 02 May 2025 09:58PM UTC coverage: 5.927% (-83.4%) from 89.28%

Build # 14804036802

Build Type

Pull #3404

github

Committed by

web-flow

Commit Message

Merge 5c103d7f8 into 0f2ccaeb2

Pull Request Pull Request #3404: feat: added Graph module to Math

Run Details

234 of 8383 branches covered (2.79%)

229 of 246 new or added lines in 1 file covered. (93.09%)

13145 existing lines in 208 files now uncovered.

934 of 15759 relevant lines covered (5.93%)

4.72 hits per line

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

0.0

/src/engine/Collision/Detection/DynamicTreeCollisionProcessor.ts

import { CollisionProcessor } from './CollisionProcessor';
import { DynamicTree } from './DynamicTree';
import { Pair } from './Pair';

import { Vector } from '../../Math/vector';
import { Ray } from '../../Math/ray';
import { FrameStats } from '../../Debug';
import { Logger } from '../../Util/Log';
import { CollisionType } from '../CollisionType';
import { Collider } from '../Colliders/Collider';
import { CollisionContact } from '../Detection/CollisionContact';
import { BodyComponent } from '../BodyComponent';
import { CompositeCollider } from '../Colliders/CompositeCollider';
import { CollisionGroup } from '../Group/CollisionGroup';
import { ExcaliburGraphicsContext } from '../../Graphics/Context/ExcaliburGraphicsContext';
import { RayCastHit } from './RayCastHit';
import { DeepRequired } from '../../Util/Required';
import { PhysicsConfig } from '../PhysicsConfig';
import { RayCastOptions } from './RayCastOptions';
import { BoundingBox } from '../BoundingBox';
import { createId } from '../../Id';

/**
 * Responsible for performing the collision broadphase (locating potential collisions) and
 * the narrowphase (actual collision contacts)
 */
export class DynamicTreeCollisionProcessor implements CollisionProcessor {
  private _dynamicCollisionTree: DynamicTree<Collider>;
  private _pairs = new Set<string>();

  private _collisionPairCache: Pair[] = [];
  private _colliders: Collider[] = [];

  constructor(private _config: DeepRequired<PhysicsConfig>) {
    this._dynamicCollisionTree = new DynamicTree<Collider>(_config.dynamicTree);
  }

  public getColliders(): readonly Collider[] {
    return this._colliders;
  }

  public query(point: Vector): Collider[];
  public query(bounds: BoundingBox): Collider[];
  public query(pointOrBounds: Vector | BoundingBox): Collider[] {
    const results: Collider[] = [];
    if (pointOrBounds instanceof BoundingBox) {
      this._dynamicCollisionTree.query(
        {
          id: createId('collider', -1),
          owner: null,
          bounds: pointOrBounds
        } as Collider,
        (other) => {
          results.push(other);
          return false;
        }
      );
    } else {
      this._dynamicCollisionTree.query(
        {
          id: createId('collider', -1),
          owner: null,
          bounds: new BoundingBox(pointOrBounds.x, pointOrBounds.y, pointOrBounds.x, pointOrBounds.y)
        } as Collider,
        (other) => {
          results.push(other);
          return false;
        }
      );
    }
    return results;
  }

  public rayCast(ray: Ray, options?: RayCastOptions): RayCastHit[] {
    const results: RayCastHit[] = [];
    const maxDistance = options?.maxDistance ?? Infinity;
    const collisionGroup = options?.collisionGroup;
    const collisionMask = !collisionGroup ? options?.collisionMask ?? CollisionGroup.All.category : collisionGroup.category;
    const searchAllColliders = options?.searchAllColliders ?? false;
    this._dynamicCollisionTree.rayCastQuery(ray, maxDistance, (collider) => {
      const owner = collider.owner;
      const maybeBody = owner.get(BodyComponent);

      if (options?.ignoreCollisionGroupAll && maybeBody.group === CollisionGroup.All) {
        return false;
      }

      const canCollide = (collisionMask & maybeBody.group.category) !== 0;

      // Early exit if not the right group
      if (maybeBody?.group && !canCollide) {
        return false;
      }

      const hit = collider.rayCast(ray, maxDistance);

      if (hit) {
        if (options?.filter) {
          if (options.filter(hit)) {
            results.push(hit);
            if (!searchAllColliders) {
              // returning true exits the search
              return true;
            }
          }
        } else {
          results.push(hit);
          if (!searchAllColliders) {
            // returning true exits the search
            return true;
          }
        }
      }
      return false;
    });
    return results;
  }

  /**
   * Tracks a physics body for collisions
   */
  public track(target: Collider): void {
    if (!target) {
      Logger.getInstance().warn('Cannot track null collider');
      return;
    }
    if (target instanceof CompositeCollider) {
      const colliders = target.getColliders();
      for (const c of colliders) {
        c.owner = target.owner;
        this._colliders.push(c);
        this._dynamicCollisionTree.trackCollider(c);
      }
    } else {
      this._colliders.push(target);
      this._dynamicCollisionTree.trackCollider(target);
    }
  }

  /**
   * Untracks a physics body
   */
  public untrack(target: Collider): void {
    if (!target) {
      Logger.getInstance().warn('Cannot untrack a null collider');
      return;
    }

    if (target instanceof CompositeCollider) {
      const colliders = target.getColliders();
      for (const c of colliders) {
        const index = this._colliders.indexOf(c);
        if (index !== -1) {
          this._colliders.splice(index, 1);
        }
        this._dynamicCollisionTree.untrackCollider(c);
      }
    } else {
      const index = this._colliders.indexOf(target);
      if (index !== -1) {
        this._colliders.splice(index, 1);
      }
      this._dynamicCollisionTree.untrackCollider(target);
    }
  }

  private _pairExists(colliderA: Collider, colliderB: Collider) {
    // if the collision pair has been calculated already short circuit
    const hash = Pair.calculatePairHash(colliderA.id, colliderB.id);
    return this._pairs.has(hash);
  }

  /**
   * Detects potential collision pairs in a broadphase approach with the dynamic AABB tree strategy
   */
  public broadphase(targets: Collider[], elapsed: number, stats?: FrameStats): Pair[] {
    const seconds = elapsed / 1000;

    // Retrieve the list of potential colliders, exclude killed, prevented, and self
    const potentialColliders = targets.filter((other) => {
      const body = other.owner?.get(BodyComponent);
      return other.owner?.isActive && body.collisionType !== CollisionType.PreventCollision;
    });

    // clear old list of collision pairs
    this._collisionPairCache = [];
    this._pairs.clear();

    // check for normal collision pairs
    let collider: Collider;
    for (let j = 0, l = potentialColliders.length; j < l; j++) {
      collider = potentialColliders[j];
      // Query the collision tree for potential colliders
      this._dynamicCollisionTree.query(collider, (other: Collider) => {
        if (!this._pairExists(collider, other) && Pair.canCollide(collider, other)) {
          const pair = new Pair(collider, other);
          this._pairs.add(pair.id);
          this._collisionPairCache.push(pair);
        }
        // Always return false, to query whole tree. Returning true in the query method stops searching
        return false;
      });
    }
    if (stats) {
      stats.physics.pairs = this._collisionPairCache.length;
    }

    // Check dynamic tree for fast moving objects
    // Fast moving objects are those moving at least there smallest bound per frame
    if (this._config.continuous.checkForFastBodies) {
      for (const collider of potentialColliders) {
        const body = collider.owner.get(BodyComponent);
        // Skip non-active objects. Does not make sense on other collision types
        if (body.collisionType !== CollisionType.Active) {
          continue;
        }

        // Maximum travel distance next frame
        const updateDistance =
          body.vel.magnitude * seconds + // velocity term
          body.acc.magnitude * 0.5 * seconds * seconds; // acc term

        // Find the minimum dimension
        const minDimension = Math.min(collider.bounds.height, collider.bounds.width);
        if (this._config.continuous.disableMinimumSpeedForFastBody || updateDistance > minDimension / 2) {
          if (stats) {
            stats.physics.fastBodies++;
          }

          // start with the oldPos because the integration for actors has already happened
          // objects resting on a surface may be slightly penetrating in the current position
          const updateVec = body.globalPos.sub(body.oldPos);
          const centerPoint = collider.center;
          const furthestPoint = collider.getFurthestPoint(body.vel);
          const origin: Vector = furthestPoint.sub(updateVec);

          const ray: Ray = new Ray(origin, body.vel);

          // back the ray up by -2x surfaceEpsilon to account for fast moving objects starting on the surface
          ray.pos = ray.pos.add(ray.dir.scale(-2 * this._config.continuous.surfaceEpsilon));
          let minCollider: Collider;
          let minTranslate: Vector = new Vector(Infinity, Infinity);
          this._dynamicCollisionTree.rayCastQuery(ray, updateDistance + this._config.continuous.surfaceEpsilon * 2, (other: Collider) => {
            if (!this._pairExists(collider, other) && Pair.canCollide(collider, other)) {
              const hit = other.rayCast(ray, updateDistance + this._config.continuous.surfaceEpsilon * 10);
              if (hit) {
                const translate = hit.point.sub(origin);
                if (translate.magnitude < minTranslate.magnitude) {
                  minTranslate = translate;
                  minCollider = other;
                }
              }
            }
            return false;
          });

          if (minCollider && Vector.isValid(minTranslate)) {
            const pair = new Pair(collider, minCollider);
            if (!this._pairs.has(pair.id)) {
              this._pairs.add(pair.id);
              this._collisionPairCache.push(pair);
            }
            // move the fast moving object to the other body
            // need to push into the surface by ex.Physics.surfaceEpsilon
            const shift = centerPoint.sub(furthestPoint);
            body.globalPos = origin
              .add(shift)
              .add(minTranslate)
              .add(ray.dir.scale(10 * this._config.continuous.surfaceEpsilon)); // needed to push the shape slightly into contact
            collider.update(body.transform.get());

            if (stats) {
              stats.physics.fastBodyCollisions++;
            }
          }
        }
      }
    }
    // return cache
    return this._collisionPairCache;
  }

  /**
   * Applies narrow phase on collision pairs to find actual area intersections
   * Adds actual colliding pairs to stats' Frame data
   */
  public narrowphase(pairs: Pair[], stats?: FrameStats): CollisionContact[] {
    let contacts: CollisionContact[] = [];
    for (let i = 0; i < pairs.length; i++) {
      const newContacts = pairs[i].collide();
      contacts = contacts.concat(newContacts);
      if (stats && newContacts.length > 0) {
        for (const c of newContacts) {
          stats.physics.contacts.set(c.id, c);
        }
      }
    }
    if (stats) {
      stats.physics.collisions += contacts.length;
    }
    return contacts;
  }

  /**
   * Update the dynamic tree positions
   */
  public update(targets: Collider[]): number {
    let updated = 0;
    const len = targets.length;

    for (let i = 0; i < len; i++) {
      if (this._dynamicCollisionTree.updateCollider(targets[i])) {
        updated++;
      }
    }
    return updated;
  }

  public debug(ex: ExcaliburGraphicsContext) {
    this._dynamicCollisionTree.debug(ex);
  }
}

1	import { CollisionProcessor } from './CollisionProcessor';
2	import { DynamicTree } from './DynamicTree';
3	import { Pair } from './Pair';
4
5	import { Vector } from '../../Math/vector';
6	import { Ray } from '../../Math/ray';
7	import { FrameStats } from '../../Debug';
8	import { Logger } from '../../Util/Log';
9	import { CollisionType } from '../CollisionType';
10	import { Collider } from '../Colliders/Collider';
11	import { CollisionContact } from '../Detection/CollisionContact';
12	import { BodyComponent } from '../BodyComponent';
13	import { CompositeCollider } from '../Colliders/CompositeCollider';
14	import { CollisionGroup } from '../Group/CollisionGroup';
15	import { ExcaliburGraphicsContext } from '../../Graphics/Context/ExcaliburGraphicsContext';
16	import { RayCastHit } from './RayCastHit';
17	import { DeepRequired } from '../../Util/Required';
18	import { PhysicsConfig } from '../PhysicsConfig';
19	import { RayCastOptions } from './RayCastOptions';
20	import { BoundingBox } from '../BoundingBox';
21	import { createId } from '../../Id';
22
23	/**
24	* Responsible for performing the collision broadphase (locating potential collisions) and
25	* the narrowphase (actual collision contacts)
26	*/
27	export class DynamicTreeCollisionProcessor implements CollisionProcessor {
28	private _dynamicCollisionTree: DynamicTree<Collider>;
UNCOV 29	private _pairs = new Set<string>();	×
30
UNCOV 31	private _collisionPairCache: Pair[] = [];	×
UNCOV 32	private _colliders: Collider[] = [];	×
33
UNCOV 34	constructor(private _config: DeepRequired<PhysicsConfig>) {	×
UNCOV 35	this._dynamicCollisionTree = new DynamicTree<Collider>(_config.dynamicTree);	×
36	}
37
38	public getColliders(): readonly Collider[] {
UNCOV 39	return this._colliders;	×
40	}
41
42	public query(point: Vector): Collider[];
43	public query(bounds: BoundingBox): Collider[];
44	public query(pointOrBounds: Vector \| BoundingBox): Collider[] {
45	const results: Collider[] = [];	×
46	if (pointOrBounds instanceof BoundingBox) {	×
47	this._dynamicCollisionTree.query(	×
48	{
49	id: createId('collider', -1),
50	owner: null,
51	bounds: pointOrBounds
52	} as Collider,
53	(other) => {
54	results.push(other);	×
55	return false;	×
56	}
57	);
58	} else {
59	this._dynamicCollisionTree.query(	×
60	{
61	id: createId('collider', -1),
62	owner: null,
63	bounds: new BoundingBox(pointOrBounds.x, pointOrBounds.y, pointOrBounds.x, pointOrBounds.y)
64	} as Collider,
65	(other) => {
66	results.push(other);	×
67	return false;	×
68	}
69	);
70	}
71	return results;	×
72	}
73
74	public rayCast(ray: Ray, options?: RayCastOptions): RayCastHit[] {
UNCOV 75	const results: RayCastHit[] = [];	×
UNCOV 76	const maxDistance = options?.maxDistance ?? Infinity;	×
UNCOV 77	const collisionGroup = options?.collisionGroup;	×
UNCOV 78	const collisionMask = !collisionGroup ? options?.collisionMask ?? CollisionGroup.All.category : collisionGroup.category;	×
UNCOV 79	const searchAllColliders = options?.searchAllColliders ?? false;	×
UNCOV 80	this._dynamicCollisionTree.rayCastQuery(ray, maxDistance, (collider) => {	×
UNCOV 81	const owner = collider.owner;	×
UNCOV 82	const maybeBody = owner.get(BodyComponent);	×
83
UNCOV 84	if (options?.ignoreCollisionGroupAll && maybeBody.group === CollisionGroup.All) {	×
UNCOV 85	return false;	×
86	}
87
UNCOV 88	const canCollide = (collisionMask & maybeBody.group.category) !== 0;	×
89
90	// Early exit if not the right group
UNCOV 91	if (maybeBody?.group && !canCollide) {	×
UNCOV 92	return false;	×
93	}
94
UNCOV 95	const hit = collider.rayCast(ray, maxDistance);	×
96
UNCOV 97	if (hit) {	×
UNCOV 98	if (options?.filter) {	×
UNCOV 99	if (options.filter(hit)) {	×
UNCOV 100	results.push(hit);	×
UNCOV 101	if (!searchAllColliders) {	×
102	// returning true exits the search
UNCOV 103	return true;	×
104	}
105	}
106	} else {
UNCOV 107	results.push(hit);	×
UNCOV 108	if (!searchAllColliders) {	×
109	// returning true exits the search
UNCOV 110	return true;	×
111	}
112	}
113	}
UNCOV 114	return false;	×
115	});
UNCOV 116	return results;	×
117	}
118
119	/**
120	* Tracks a physics body for collisions
121	*/
122	public track(target: Collider): void {
UNCOV 123	if (!target) {	×
124	Logger.getInstance().warn('Cannot track null collider');	×
125	return;	×
126	}
UNCOV 127	if (target instanceof CompositeCollider) {	×
UNCOV 128	const colliders = target.getColliders();	×
UNCOV 129	for (const c of colliders) {	×
UNCOV 130	c.owner = target.owner;	×
UNCOV 131	this._colliders.push(c);	×
UNCOV 132	this._dynamicCollisionTree.trackCollider(c);	×
133	}
134	} else {
UNCOV 135	this._colliders.push(target);	×
UNCOV 136	this._dynamicCollisionTree.trackCollider(target);	×
137	}
138	}
139
140	/**
141	* Untracks a physics body
142	*/
143	public untrack(target: Collider): void {
UNCOV 144	if (!target) {	×
145	Logger.getInstance().warn('Cannot untrack a null collider');	×
146	return;	×
147	}
148
UNCOV 149	if (target instanceof CompositeCollider) {	×
UNCOV 150	const colliders = target.getColliders();	×
UNCOV 151	for (const c of colliders) {	×
UNCOV 152	const index = this._colliders.indexOf(c);	×
UNCOV 153	if (index !== -1) {	×
UNCOV 154	this._colliders.splice(index, 1);	×
155	}
UNCOV 156	this._dynamicCollisionTree.untrackCollider(c);	×
157	}
158	} else {
159	const index = this._colliders.indexOf(target);	×
160	if (index !== -1) {	×
161	this._colliders.splice(index, 1);	×
162	}
163	this._dynamicCollisionTree.untrackCollider(target);	×
164	}
165	}
166
167	private _pairExists(colliderA: Collider, colliderB: Collider) {
168	// if the collision pair has been calculated already short circuit
UNCOV 169	const hash = Pair.calculatePairHash(colliderA.id, colliderB.id);	×
UNCOV 170	return this._pairs.has(hash);	×
171	}
172
173	/**
174	* Detects potential collision pairs in a broadphase approach with the dynamic AABB tree strategy
175	*/
176	public broadphase(targets: Collider[], elapsed: number, stats?: FrameStats): Pair[] {
UNCOV 177	const seconds = elapsed / 1000;	×
178
179	// Retrieve the list of potential colliders, exclude killed, prevented, and self
UNCOV 180	const potentialColliders = targets.filter((other) => {	×
UNCOV 181	const body = other.owner?.get(BodyComponent);	×
UNCOV 182	return other.owner?.isActive && body.collisionType !== CollisionType.PreventCollision;	×
183	});
184
185	// clear old list of collision pairs
UNCOV 186	this._collisionPairCache = [];	×
UNCOV 187	this._pairs.clear();	×
188
189	// check for normal collision pairs
190	let collider: Collider;
UNCOV 191	for (let j = 0, l = potentialColliders.length; j < l; j++) {	×
UNCOV 192	collider = potentialColliders[j];	×
193	// Query the collision tree for potential colliders
UNCOV 194	this._dynamicCollisionTree.query(collider, (other: Collider) => {	×
UNCOV 195	if (!this._pairExists(collider, other) && Pair.canCollide(collider, other)) {	×
UNCOV 196	const pair = new Pair(collider, other);	×
UNCOV 197	this._pairs.add(pair.id);	×
UNCOV 198	this._collisionPairCache.push(pair);	×
199	}
200	// Always return false, to query whole tree. Returning true in the query method stops searching
UNCOV 201	return false;	×
202	});
203	}
UNCOV 204	if (stats) {	×
205	stats.physics.pairs = this._collisionPairCache.length;	×
206	}
207
208	// Check dynamic tree for fast moving objects
209	// Fast moving objects are those moving at least there smallest bound per frame
UNCOV 210	if (this._config.continuous.checkForFastBodies) {	×
UNCOV 211	for (const collider of potentialColliders) {	×
UNCOV 212	const body = collider.owner.get(BodyComponent);	×
213	// Skip non-active objects. Does not make sense on other collision types
UNCOV 214	if (body.collisionType !== CollisionType.Active) {	×
UNCOV 215	continue;	×
216	}
217
218	// Maximum travel distance next frame
219	const updateDistance =
UNCOV 220	body.vel.magnitude * seconds + // velocity term	×
221	body.acc.magnitude * 0.5 * seconds * seconds; // acc term
222
223	// Find the minimum dimension
UNCOV 224	const minDimension = Math.min(collider.bounds.height, collider.bounds.width);	×
UNCOV 225	if (this._config.continuous.disableMinimumSpeedForFastBody \|\| updateDistance > minDimension / 2) {	×
UNCOV 226	if (stats) {	×
227	stats.physics.fastBodies++;	×
228	}
229
230	// start with the oldPos because the integration for actors has already happened
231	// objects resting on a surface may be slightly penetrating in the current position
UNCOV 232	const updateVec = body.globalPos.sub(body.oldPos);	×
UNCOV 233	const centerPoint = collider.center;	×
UNCOV 234	const furthestPoint = collider.getFurthestPoint(body.vel);	×
UNCOV 235	const origin: Vector = furthestPoint.sub(updateVec);	×
236
UNCOV 237	const ray: Ray = new Ray(origin, body.vel);	×
238
239	// back the ray up by -2x surfaceEpsilon to account for fast moving objects starting on the surface
UNCOV 240	ray.pos = ray.pos.add(ray.dir.scale(-2 * this._config.continuous.surfaceEpsilon));	×
241	let minCollider: Collider;
UNCOV 242	let minTranslate: Vector = new Vector(Infinity, Infinity);	×
UNCOV 243	this._dynamicCollisionTree.rayCastQuery(ray, updateDistance + this._config.continuous.surfaceEpsilon * 2, (other: Collider) => {	×
UNCOV 244	if (!this._pairExists(collider, other) && Pair.canCollide(collider, other)) {	×
245	const hit = other.rayCast(ray, updateDistance + this._config.continuous.surfaceEpsilon * 10);	×
246	if (hit) {	×
247	const translate = hit.point.sub(origin);	×
248	if (translate.magnitude < minTranslate.magnitude) {	×
249	minTranslate = translate;	×
250	minCollider = other;	×
251	}
252	}
253	}
UNCOV 254	return false;	×
255	});
256
UNCOV 257	if (minCollider && Vector.isValid(minTranslate)) {	×
258	const pair = new Pair(collider, minCollider);	×
259	if (!this._pairs.has(pair.id)) {	×
260	this._pairs.add(pair.id);	×
261	this._collisionPairCache.push(pair);	×
262	}
263	// move the fast moving object to the other body
264	// need to push into the surface by ex.Physics.surfaceEpsilon
265	const shift = centerPoint.sub(furthestPoint);	×
266	body.globalPos = origin	×
267	.add(shift)
268	.add(minTranslate)
269	.add(ray.dir.scale(10 * this._config.continuous.surfaceEpsilon)); // needed to push the shape slightly into contact
270	collider.update(body.transform.get());	×
271
272	if (stats) {	×
273	stats.physics.fastBodyCollisions++;	×
274	}
275	}
276	}
277	}
278	}
279	// return cache
UNCOV 280	return this._collisionPairCache;	×
281	}
282
283	/**
284	* Applies narrow phase on collision pairs to find actual area intersections
285	* Adds actual colliding pairs to stats' Frame data
286	*/
287	public narrowphase(pairs: Pair[], stats?: FrameStats): CollisionContact[] {
288	let contacts: CollisionContact[] = [];	×
289	for (let i = 0; i < pairs.length; i++) {	×
290	const newContacts = pairs[i].collide();	×
291	contacts = contacts.concat(newContacts);	×
292	if (stats && newContacts.length > 0) {	×
293	for (const c of newContacts) {	×
294	stats.physics.contacts.set(c.id, c);	×
295	}
296	}
297	}
298	if (stats) {	×
299	stats.physics.collisions += contacts.length;	×
300	}
301	return contacts;	×
302	}
303
304	/**
305	* Update the dynamic tree positions
306	*/
307	public update(targets: Collider[]): number {
308	let updated = 0;	×
309	const len = targets.length;	×
310
311	for (let i = 0; i < len; i++) {	×
312	if (this._dynamicCollisionTree.updateCollider(targets[i])) {	×
313	updated++;	×
314	}
315	}
316	return updated;	×
317	}
318
319	public debug(ex: ExcaliburGraphicsContext) {
320	this._dynamicCollisionTree.debug(ex);	×
321	}
322	}

excaliburjs / Excalibur / 14804036802

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