120 lines
4.3 KiB
TypeScript
120 lines
4.3 KiB
TypeScript
import { Data, Location, Polygon, CollisionClass } from "./Components";
|
|
import { Id, Join } from "./Data";
|
|
import { TfPolygon } from "./Location";
|
|
|
|
interface Candidate {
|
|
id: Id;
|
|
class: CollisionClass;
|
|
poly: Polygon;
|
|
};
|
|
|
|
function hash(minX: number, minY: number, maxX: number, maxY: number, cellSize: number): string[] {
|
|
let minXCell = Math.floor(minX/cellSize);
|
|
let minYCell = Math.floor(minY/cellSize);
|
|
let maxXCell = Math.floor(maxX/cellSize);
|
|
let maxYCell = Math.floor(maxY/cellSize);
|
|
const results = [];
|
|
for(let xCell = minXCell; xCell <= maxXCell; xCell++) {
|
|
for(let yCell = minYCell; yCell <= maxYCell; yCell++) {
|
|
results.push(`${xCell},${yCell}`);
|
|
}
|
|
}
|
|
return results;
|
|
}
|
|
|
|
function hashPolygon({points}: Polygon, cellSize: number): string[] {
|
|
let minX = 1/0;
|
|
let minY = 1/0;
|
|
let maxX = -1/0;
|
|
let maxY = -1/0;
|
|
for(let i = 0; i < points.length; i += 2) {
|
|
minX = Math.min(minX, points[i]);
|
|
minY = Math.min(minY, points[i+1]);
|
|
maxX = Math.max(maxX, points[i]);
|
|
maxY = Math.max(maxY, points[i+1]);
|
|
}
|
|
return hash(minX, minY, maxX, maxY, cellSize);
|
|
}
|
|
|
|
function projectPolygonToAxis(axisX: number, axisY: number, points: number[]): [number, number] {
|
|
let min = 1/0;
|
|
let max = -1/0;
|
|
for(let i = 0; i < points.length; i += 2) {
|
|
// dot product doesn't need normalizing since we only compare magnitudes
|
|
const value = (axisX * points[i]) + (axisY * points[i+1]);
|
|
min = Math.min(min, value);
|
|
max = Math.max(max, value);
|
|
}
|
|
return [min, max];
|
|
}
|
|
|
|
/**
|
|
* Return true if the axis contains a gap between the two polygons
|
|
*/
|
|
function testPolygonSeparatingAxis(axisX: number, axisY: number, aPoints: number[], bPoints: number[]): boolean {
|
|
const [minA, maxA] = projectPolygonToAxis(axisX, axisY, aPoints);
|
|
const [minB, maxB] = projectPolygonToAxis(axisX, axisY, bPoints);
|
|
return !((minA < maxB) && (minB < maxA));
|
|
}
|
|
|
|
function halfCollideConvexPolygons(aPoints: number[], bPoints: number[]): boolean {
|
|
for(let i = 2; i < aPoints.length; i += 2) {
|
|
const dx = aPoints[i] - aPoints[i-2];
|
|
const dy = aPoints[i+1] - aPoints[i-1];
|
|
if(testPolygonSeparatingAxis(-dy, dx, aPoints, bPoints)) {
|
|
return false;
|
|
}
|
|
}
|
|
const dx = aPoints[0] - aPoints[aPoints.length-2];
|
|
const dy = aPoints[1] - aPoints[aPoints.length-1];
|
|
if(testPolygonSeparatingAxis(-dy, dx, aPoints, bPoints)) {
|
|
return false;
|
|
}
|
|
|
|
// no gaps found in this half
|
|
return true;
|
|
}
|
|
|
|
function collideConvexPolygons({points: aPoints}: Polygon, {points: bPoints}: Polygon): boolean {
|
|
return halfCollideConvexPolygons(aPoints, bPoints) && halfCollideConvexPolygons(bPoints, aPoints);
|
|
}
|
|
|
|
export function FindCollisions(data: Data, cellSize: number, callback: (className: string, sourceId: Id, targetId: Id) => void) {
|
|
const spatialMap: Record<string, Candidate[]> = {};
|
|
|
|
Join(data, "collisionTargetClass", "location", "bounds", "id").map(
|
|
([targetClass, location, poly, id]) => {
|
|
const workingPoly = TfPolygon(poly, location);
|
|
const candidate = {
|
|
id, class: targetClass, poly: workingPoly
|
|
};
|
|
hashPolygon(workingPoly, cellSize).forEach(key => {
|
|
if(!spatialMap[key]) spatialMap[key] = [];
|
|
spatialMap[key].push(candidate);
|
|
});
|
|
}
|
|
);
|
|
|
|
Join(data, "collisionSourceClass", "location", "bounds", "id").map(
|
|
([sourceClass, location, poly, id]) => {
|
|
const workingPoly = TfPolygon(poly, location);
|
|
const candidates: Record<string, Candidate> = {};
|
|
hashPolygon(workingPoly, cellSize).forEach(key => {
|
|
if(spatialMap[key]) {
|
|
for(const candidate of spatialMap[key]) {
|
|
// dedup targets to test
|
|
candidates[candidate.id[0]] = candidate;
|
|
}
|
|
}
|
|
});
|
|
for(const bareId in candidates) {
|
|
const target = candidates[bareId];
|
|
if(collideConvexPolygons(workingPoly, target.poly)) {
|
|
const className = `${sourceClass.name}>${target.class.name}`;
|
|
callback(className, id, target.id);
|
|
}
|
|
}
|
|
}
|
|
);
|
|
}
|