15354777440

Committed 30 May 2025 08:03PM UTC coverage: 87.858% (-1.5%) from 89.344%

Build # 15354777440

Build Type

Pull #3385

github

Committed by

web-flow

Commit Message

Merge a00f57733 into e6ec66358

Pull Request Pull Request #3385: updated Meet action to add tolerance

Run Details

5002 of 6948 branches covered (71.99%)

3 of 5 new or added lines in 2 files covered. (60.0%)

872 existing lines in 83 files now uncovered.

13661 of 15549 relevant lines covered (87.86%)

25187.01 hits per line

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

91.13

/src/engine/Collision/Detection/SparseHashGrid.ts

import { Color } from '../../Color';
import type { ExcaliburGraphicsContext } from '../../Graphics/Context/ExcaliburGraphicsContext';
import type { Vector } from '../../Math/vector';
import { vec } from '../../Math/vector';
import { RentalPool } from '../../Util/RentalPool';
import { BoundingBox } from '../BoundingBox';

export class HashGridProxy<T extends { bounds: BoundingBox }> {
  id: number = -1;
  /**
   * left bounds x hash coordinate
   */
  leftX: number;
  /**
   * right bounds x hash coordinate
   */
  rightX: number;
  /**
   * bottom bounds y hash coordinate
   */
  bottomY: number;
  /**
   * top bounds y hash coordinate
   */
  topY: number;

  bounds: BoundingBox;

  cells: HashGridCell<T>[] = [];
  hasZeroBounds = false;
  /**
   * Grid size in pixels
   */
  readonly gridSize: number;
  constructor(
    public object: T,
    gridSize: number
  ) {
    this.gridSize = gridSize;
    this.bounds = object.bounds;
    this.hasZeroBounds = this.bounds.hasZeroDimensions();
    this.leftX = Math.floor(this.bounds.left / this.gridSize);
    this.rightX = Math.floor(this.bounds.right / this.gridSize);
    this.bottomY = Math.floor(this.bounds.bottom / this.gridSize);
    this.topY = Math.floor(this.bounds.top / this.gridSize);
  }

  /**
   * Has the hashed bounds changed
   */
  hasChanged(): boolean {
    const bounds = this.object.bounds;
    const leftX = Math.floor(bounds.left / this.gridSize);
    const rightX = Math.floor(bounds.right / this.gridSize);
    const bottomY = Math.floor(bounds.bottom / this.gridSize);
    const topY = Math.floor(bounds.top / this.gridSize);
    if (this.leftX !== leftX || this.rightX !== rightX || this.bottomY !== bottomY || this.topY !== topY) {
      return true;
    }
    return false;
  }

  /**
   * Clears all collider references
   */
  clear(): void {
    for (const cell of this.cells) {
      const index = cell.proxies.indexOf(this);
      if (index > -1) {
        cell.proxies.splice(index, 1);
      }
      // TODO reclaim cell in pool if empty?
    }
  }

  /**
   * Update bounds of the proxy
   */
  updateBounds(): void {
    this.bounds = this.object.bounds;
  }

  /**
   * Updates the hashed bounds coordinates
   */
  update(): void {
    this.bounds = this.object.bounds;

    this.leftX = Math.floor(this.bounds.left / this.gridSize);
    this.rightX = Math.floor(this.bounds.right / this.gridSize);
    this.bottomY = Math.floor(this.bounds.bottom / this.gridSize);
    this.topY = Math.floor(this.bounds.top / this.gridSize);
    this.hasZeroBounds = this.object.bounds.hasZeroDimensions();
  }
}

export class HashGridCell<TObject extends { bounds: BoundingBox }, TProxy extends HashGridProxy<TObject> = HashGridProxy<TObject>> {
  proxies: TProxy[] = [];
  key: string;
  x: number;
  y: number;

  configure(x: number, y: number) {
    this.x = x;
    this.y = y;
    this.key = HashGridCell.calculateHashKey(x, y);
  }

  static calculateHashKey(x: number, y: number) {
    return `${x}+${y}`;
  }
}

export class SparseHashGrid<TObject extends { bounds: BoundingBox }, TProxy extends HashGridProxy<TObject> = HashGridProxy<TObject>> {
  readonly gridSize: number;
  readonly sparseHashGrid: Map<string, HashGridCell<TObject, TProxy>>;
  readonly objectToProxy: Map<TObject, TProxy>;

  public bounds = new BoundingBox();

  private _hashGridCellPool = new RentalPool<HashGridCell<TObject, TProxy>>(
    () => new HashGridCell(),
    (instance) => {
      instance.configure(0, 0);
      instance.proxies.length = 0;
      return instance;
    },
    1000
  );

  private _buildProxy: (object: TObject) => TProxy;

  constructor(options: { size: number; proxyFactory?: (object: TObject, gridSize: number) => TProxy }) {
    this.gridSize = options.size;
    this.sparseHashGrid = new Map<string, HashGridCell<TObject, TProxy>>();
    this.objectToProxy = new Map<TObject, TProxy>();
    if (options.proxyFactory) {
      this._buildProxy = (object: TObject) => options.proxyFactory(object, this.gridSize);
    } else {
      this._buildProxy = (object: TObject) => new HashGridProxy(object, this.gridSize) as TProxy;
    }

    // TODO dynamic grid size potentially larger than the largest collider
    // TODO Re-hash the objects if the median proves to be different
  }

  query(point: Vector): TObject[];
  query(bounds: BoundingBox): TObject[];
  query(boundsOrPoint: BoundingBox | Vector): TObject[] {
    const results = new Set<TObject>();
    if (boundsOrPoint instanceof BoundingBox) {
      const bounds = boundsOrPoint;
      const leftX = Math.floor(bounds.left / this.gridSize);
      const rightX = Math.floor(bounds.right / this.gridSize);
      const bottomY = Math.floor(bounds.bottom / this.gridSize);
      const topY = Math.floor(bounds.top / this.gridSize);
      for (let x = leftX; x <= rightX; x++) {
        for (let y = topY; y <= bottomY; y++) {
          const key = HashGridCell.calculateHashKey(x, y);
          // Hash bounds into appropriate cell
          const cell = this.sparseHashGrid.get(key);
          if (cell) {
            for (let i = 0; i < cell.proxies.length; i++) {
              cell.proxies[i].updateBounds();
              if (cell.proxies[i].bounds.intersect(bounds)) {
                results.add(cell.proxies[i].object);
              }
            }
          }
        }
      }
    } else {
      const point = boundsOrPoint;
      const key = HashGridCell.calculateHashKey(Math.floor(point.x / this.gridSize), Math.floor(point.y / this.gridSize));
      // Hash points into appropriate cell
      const cell = this.sparseHashGrid.get(key);
      if (cell) {
        for (let i = 0; i < cell.proxies.length; i++) {
          cell.proxies[i].updateBounds();
          if (cell.proxies[i].bounds.contains(point)) {
            results.add(cell.proxies[i].object);
          }
        }
      }
    }
    return Array.from(results);
  }

  get(xCoord: number, yCoord: number): HashGridCell<TObject> {
    const key = HashGridCell.calculateHashKey(xCoord, yCoord);
    const cell = this.sparseHashGrid.get(key);
    return cell;
  }

  private _insert(x: number, y: number, proxy: TProxy): void {
    const key = HashGridCell.calculateHashKey(x, y);
    // Hash collider into appropriate cell
    let cell = this.sparseHashGrid.get(key);
    if (!cell) {
      cell = this._hashGridCellPool.rent();
      cell.configure(x, y);
      this.sparseHashGrid.set(cell.key, cell);
    }
    cell.proxies.push(proxy);
    proxy.cells.push(cell); // TODO dupes, doesn't seem to be a problem
    this.bounds.combine(proxy.bounds, this.bounds);
  }

  private _remove(x: number, y: number, proxy: TProxy): void {
    const key = HashGridCell.calculateHashKey(x, y);
    // Hash collider into appropriate cell
    const cell = this.sparseHashGrid.get(key);
    if (cell) {
      const proxyIndex = cell.proxies.indexOf(proxy);
      if (proxyIndex > -1) {
        cell.proxies.splice(proxyIndex, 1);
      }
      const cellIndex = proxy.cells.indexOf(cell);
      if (cellIndex > -1) {
        proxy.cells.splice(cellIndex, 1);
      }
      if (cell.proxies.length === 0) {
        this._hashGridCellPool.return(cell);
        this.sparseHashGrid.delete(key);
      }
    }
  }

  track(target: TObject): void {
    const proxy = this._buildProxy(target);
    this.objectToProxy.set(target, proxy);
    for (let x = proxy.leftX; x <= proxy.rightX; x++) {
      for (let y = proxy.topY; y <= proxy.bottomY; y++) {
        this._insert(x, y, proxy);
      }
    }
  }

  untrack(target: TObject): void {
    const proxy = this.objectToProxy.get(target);
    if (proxy) {
      proxy.clear();
      this.objectToProxy.delete(target);
    }
  }

  update(targets: TObject[]): number {
    let updated = 0;
    // FIXME resetting bounds is wrong, if nothing has updated then
    // the bounds stay 0
    // this.bounds.reset();
    for (const target of targets) {
      const proxy = this.objectToProxy.get(target);
      if (!proxy) {
        continue;
      }
      if (proxy.hasChanged()) {
        // TODO slightly wasteful only remove from changed
        for (let x = proxy.leftX; x <= proxy.rightX; x++) {
          for (let y = proxy.topY; y <= proxy.bottomY; y++) {
            this._remove(x, y, proxy);
          }
        }
        proxy.update();
        // TODO slightly wasteful only add new
        for (let x = proxy.leftX; x <= proxy.rightX; x++) {
          for (let y = proxy.topY; y <= proxy.bottomY; y++) {
            this._insert(x, y, proxy);
          }
        }
        updated++;
      }
    }
    return updated;
  }

  debug(ex: ExcaliburGraphicsContext, elapsed: number): void {
    const transparent = Color.Transparent;
    const color = Color.White;
    for (const cell of this.sparseHashGrid.values()) {
      ex.drawRectangle(vec(cell.x * this.gridSize, cell.y * this.gridSize), this.gridSize, this.gridSize, transparent, color, 2);
    }
  }
}

1	import { Color } from '../../Color';
2	import type { ExcaliburGraphicsContext } from '../../Graphics/Context/ExcaliburGraphicsContext';
3	import type { Vector } from '../../Math/vector';
4	import { vec } from '../../Math/vector';
5	import { RentalPool } from '../../Util/RentalPool';
6	import { BoundingBox } from '../BoundingBox';
7
8	export class HashGridProxy<T extends { bounds: BoundingBox }> {
9	id: number = -1;	850✔
10	/**
11	* left bounds x hash coordinate
12	*/
13	leftX: number;
14	/**
15	* right bounds x hash coordinate
16	*/
17	rightX: number;
18	/**
19	* bottom bounds y hash coordinate
20	*/
21	bottomY: number;
22	/**
23	* top bounds y hash coordinate
24	*/
25	topY: number;
26
27	bounds: BoundingBox;
28
29	cells: HashGridCell<T>[] = [];	850✔
30	hasZeroBounds = false;	850✔
31	/**
32	* Grid size in pixels
33	*/
34	readonly gridSize: number;
35	constructor(
36	public object: T,	850✔
37	gridSize: number
38	) {
39	this.gridSize = gridSize;	850✔
40	this.bounds = object.bounds;	850✔
41	this.hasZeroBounds = this.bounds.hasZeroDimensions();	850✔
42	this.leftX = Math.floor(this.bounds.left / this.gridSize);	850✔
43	this.rightX = Math.floor(this.bounds.right / this.gridSize);	850✔
44	this.bottomY = Math.floor(this.bounds.bottom / this.gridSize);	850✔
45	this.topY = Math.floor(this.bounds.top / this.gridSize);	850✔
46	}
47
48	/**
49	* Has the hashed bounds changed
50	*/
51	hasChanged(): boolean {
52	const bounds = this.object.bounds;	3,443✔
53	const leftX = Math.floor(bounds.left / this.gridSize);	3,443✔
54	const rightX = Math.floor(bounds.right / this.gridSize);	3,443✔
55	const bottomY = Math.floor(bounds.bottom / this.gridSize);	3,443✔
56	const topY = Math.floor(bounds.top / this.gridSize);	3,443✔
57	if (this.leftX !== leftX \|\| this.rightX !== rightX \|\| this.bottomY !== bottomY \|\| this.topY !== topY) {	3,443✔
58	return true;	222✔
59	}
60	return false;	3,221✔
61	}
62
63	/**
64	* Clears all collider references
65	*/
66	clear(): void {
67	for (const cell of this.cells) {	32✔
68	const index = cell.proxies.indexOf(this);	52✔
69	if (index > -1) {	52!
70	cell.proxies.splice(index, 1);	52✔
71	}
72	// TODO reclaim cell in pool if empty?
73	}
74	}
75
76	/**
77	* Update bounds of the proxy
78	*/
79	updateBounds(): void {
80	this.bounds = this.object.bounds;	92✔
81	}
82
83	/**
84	* Updates the hashed bounds coordinates
85	*/
86	update(): void {
87	this.bounds = this.object.bounds;	222✔
88
89	this.leftX = Math.floor(this.bounds.left / this.gridSize);	222✔
90	this.rightX = Math.floor(this.bounds.right / this.gridSize);	222✔
91	this.bottomY = Math.floor(this.bounds.bottom / this.gridSize);	222✔
92	this.topY = Math.floor(this.bounds.top / this.gridSize);	222✔
93	this.hasZeroBounds = this.object.bounds.hasZeroDimensions();	222✔
94	}
95	}
96
97	export class HashGridCell<TObject extends { bounds: BoundingBox }, TProxy extends HashGridProxy<TObject> = HashGridProxy<TObject>> {
98	proxies: TProxy[] = [];	3,176,000✔
99	key: string;
100	x: number;
101	y: number;
102
103	configure(x: number, y: number) {
104	this.x = x;	3,774✔
105	this.y = y;	3,774✔
106	this.key = HashGridCell.calculateHashKey(x, y);	3,774✔
107	}
108
109	static calculateHashKey(x: number, y: number) {
110	return `${x}+${y}`;	8,945✔
111	}
112	}
113
114	export class SparseHashGrid<TObject extends { bounds: BoundingBox }, TProxy extends HashGridProxy<TObject> = HashGridProxy<TObject>> {
115	readonly gridSize: number;
116	readonly sparseHashGrid: Map<string, HashGridCell<TObject, TProxy>>;
117	readonly objectToProxy: Map<TObject, TProxy>;
118
119	public bounds = new BoundingBox();	3,176✔
120
121	private _hashGridCellPool = new RentalPool<HashGridCell<TObject, TProxy>>(	3,176✔
122	() => new HashGridCell(),	3,176,000✔
123	(instance) => {
124	instance.configure(0, 0);	×
125	instance.proxies.length = 0;	×
UNCOV 126	return instance;	×
127	},
128	1000
129	);
130
131	private _buildProxy: (object: TObject) => TProxy;
132
133	constructor(options: { size: number; proxyFactory?: (object: TObject, gridSize: number) => TProxy }) {
134	this.gridSize = options.size;	3,176✔
135	this.sparseHashGrid = new Map<string, HashGridCell<TObject, TProxy>>();	3,176✔
136	this.objectToProxy = new Map<TObject, TProxy>();	3,176✔
137	if (options.proxyFactory) {	3,176✔
138	this._buildProxy = (object: TObject) => options.proxyFactory(object, this.gridSize);	1,902✔
139	} else {
140	this._buildProxy = (object: TObject) => new HashGridProxy(object, this.gridSize) as TProxy;	1,274✔
141	}
142
143	// TODO dynamic grid size potentially larger than the largest collider
144	// TODO Re-hash the objects if the median proves to be different
145	}
146
147	query(point: Vector): TObject[];
148	query(bounds: BoundingBox): TObject[];
149	query(boundsOrPoint: BoundingBox \| Vector): TObject[] {
150	const results = new Set<TObject>();	91✔
151	if (boundsOrPoint instanceof BoundingBox) {	91✔
152	const bounds = boundsOrPoint;	1✔
153	const leftX = Math.floor(bounds.left / this.gridSize);	1✔
154	const rightX = Math.floor(bounds.right / this.gridSize);	1✔
155	const bottomY = Math.floor(bounds.bottom / this.gridSize);	1✔
156	const topY = Math.floor(bounds.top / this.gridSize);	1✔
157	for (let x = leftX; x <= rightX; x++) {	1✔
158	for (let y = topY; y <= bottomY; y++) {	2✔
159	const key = HashGridCell.calculateHashKey(x, y);	4✔
160	// Hash bounds into appropriate cell
161	const cell = this.sparseHashGrid.get(key);	4✔
162	if (cell) {	4!
163	for (let i = 0; i < cell.proxies.length; i++) {	4✔
164	cell.proxies[i].updateBounds();	6✔
165	if (cell.proxies[i].bounds.intersect(bounds)) {	6!
166	results.add(cell.proxies[i].object);	6✔
167	}
168	}
169	}
170	}
171	}
172	} else {
173	const point = boundsOrPoint;	90✔
174	const key = HashGridCell.calculateHashKey(Math.floor(point.x / this.gridSize), Math.floor(point.y / this.gridSize));	90✔
175	// Hash points into appropriate cell
176	const cell = this.sparseHashGrid.get(key);	90✔
177	if (cell) {	90✔
178	for (let i = 0; i < cell.proxies.length; i++) {	55✔
179	cell.proxies[i].updateBounds();	86✔
180	if (cell.proxies[i].bounds.contains(point)) {	86✔
181	results.add(cell.proxies[i].object);	71✔
182	}
183	}
184	}
185	}
186	return Array.from(results);	91✔
187	}
188
189	get(xCoord: number, yCoord: number): HashGridCell<TObject> {
190	const key = HashGridCell.calculateHashKey(xCoord, yCoord);	×
191	const cell = this.sparseHashGrid.get(key);	×
UNCOV 192	return cell;	×
193	}
194
195	private _insert(x: number, y: number, proxy: TProxy): void {
196	const key = HashGridCell.calculateHashKey(x, y);	4,359✔
197	// Hash collider into appropriate cell
198	let cell = this.sparseHashGrid.get(key);	4,359✔
199	if (!cell) {	4,359✔
200	cell = this._hashGridCellPool.rent();	3,774✔
201	cell.configure(x, y);	3,774✔
202	this.sparseHashGrid.set(cell.key, cell);	3,774✔
203	}
204	cell.proxies.push(proxy);	4,359✔
205	proxy.cells.push(cell); // TODO dupes, doesn't seem to be a problem	4,359✔
206	this.bounds.combine(proxy.bounds, this.bounds);	4,359✔
207	}
208
209	private _remove(x: number, y: number, proxy: TProxy): void {
210	const key = HashGridCell.calculateHashKey(x, y);	646✔
211	// Hash collider into appropriate cell
212	const cell = this.sparseHashGrid.get(key);	646✔
213	if (cell) {	646!
214	const proxyIndex = cell.proxies.indexOf(proxy);	646✔
215	if (proxyIndex > -1) {	646!
216	cell.proxies.splice(proxyIndex, 1);	646✔
217	}
218	const cellIndex = proxy.cells.indexOf(cell);	646✔
219	if (cellIndex > -1) {	646!
220	proxy.cells.splice(cellIndex, 1);	646✔
221	}
222	if (cell.proxies.length === 0) {	646✔
223	this._hashGridCellPool.return(cell);	527✔
224	this.sparseHashGrid.delete(key);	527✔
225	}
226	}
227	}
228
229	track(target: TObject): void {
230	const proxy = this._buildProxy(target);	850✔
231	this.objectToProxy.set(target, proxy);	850✔
232	for (let x = proxy.leftX; x <= proxy.rightX; x++) {	850✔
233	for (let y = proxy.topY; y <= proxy.bottomY; y++) {	1,366✔
234	this._insert(x, y, proxy);	3,741✔
235	}
236	}
237	}
238
239	untrack(target: TObject): void {
240	const proxy = this.objectToProxy.get(target);	45✔
241	if (proxy) {	45✔
242	proxy.clear();	32✔
243	this.objectToProxy.delete(target);	32✔
244	}
245	}
246
247	update(targets: TObject[]): number {
248	let updated = 0;	3,606✔
249	// FIXME resetting bounds is wrong, if nothing has updated then
250	// the bounds stay 0
251	// this.bounds.reset();
252	for (const target of targets) {	3,606✔
253	const proxy = this.objectToProxy.get(target);	3,443✔
254	if (!proxy) {	3,443!
UNCOV 255	continue;	×
256	}
257	if (proxy.hasChanged()) {	3,443✔
258	// TODO slightly wasteful only remove from changed
259	for (let x = proxy.leftX; x <= proxy.rightX; x++) {	222✔
260	for (let y = proxy.topY; y <= proxy.bottomY; y++) {	360✔
261	this._remove(x, y, proxy);	646✔
262	}
263	}
264	proxy.update();	222✔
265	// TODO slightly wasteful only add new
266	for (let x = proxy.leftX; x <= proxy.rightX; x++) {	222✔
267	for (let y = proxy.topY; y <= proxy.bottomY; y++) {	348✔
268	this._insert(x, y, proxy);	618✔
269	}
270	}
271	updated++;	222✔
272	}
273	}
274	return updated;	3,606✔
275	}
276
277	debug(ex: ExcaliburGraphicsContext, elapsed: number): void {
278	const transparent = Color.Transparent;	×
279	const color = Color.White;	×
280	for (const cell of this.sparseHashGrid.values()) {	×
UNCOV 281	ex.drawRectangle(vec(cell.x * this.gridSize, cell.y * this.gridSize), this.gridSize, this.gridSize, transparent, color, 2);	×
282	}
283	}
284	}

excaliburjs / Excalibur / 15354777440

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