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/SparseHashGrid.ts

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

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