20275897578

Committed 16 Dec 2025 04:52PM UTC coverage: 88.649% (+0.02%) from 88.63%

Build # 20275897578

Build Type

Pull #3622

github

Committed by

web-flow

Commit Message

Merge 493498a8e into 97bb68b86

Pull Request Pull Request #3622: feat: Add better debug settings

Run Details

5324 of 7269 branches covered (73.24%)

19 of 20 new or added lines in 4 files covered. (95.0%)

1 existing line in 1 file now uncovered.

14729 of 16615 relevant lines covered (88.65%)

24677.91 hits per line

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

91.87

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

import { Color } from '../../Color';
import type { ExcaliburGraphicsContext } from '../../Graphics/Context/ExcaliburGraphicsContext';
import type { Vector } 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 color = Color.White;
    for (const cell of this.sparseHashGrid.values()) {
      ex.debug.drawRect(cell.x * this.gridSize, cell.y * this.gridSize, this.gridSize, this.gridSize, { color, lineWidth: 2 });
    }
  }
}

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

excaliburjs / Excalibur / 20275897578

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