excaliburjs / Excalibur

🎮 Your friendly TypeScript 2D game engine for the web 🗡️
https://excaliburjs.com
BSD 2-Clause "Simplified" License
1.82k stars 189 forks source link

fix: rewrite ClosestLine and PolygonPolygonClosestLine logic for improved accuracy on sloped polygons #3124

Closed mattjennings closed 4 months ago

mattjennings commented 4 months ago

===:clipboard: PR Checklist :clipboard:===

==================

Improves accuracy of PolygonPolygonClosestLine and ClosestLine functions. Big disclaimer, I heavily relied on ChatGPT for the math logic here... extra eyes greatly appreciated. I myself plan to do a deeper review on the math here before merging.

Before:

https://github.com/user-attachments/assets/a0d9d5d5-76e9-4e05-8459-15b6a48b0dcb

After:

https://github.com/user-attachments/assets/85d4410b-2bf2-4f51-90e2-4ee828a9693b

I also think there's a faster way to do the PolygonPolygonClosestLine logic. Right now it iterates over each side of the polygon, draws a line, and returns the shortest result. Potentially it could use SAT to determine the closest sides, but I had unexpected results

PolygonPolygonClosestLine(polygonA: PolygonCollider, polygonB: PolygonCollider) {
    const aSat = SeparatingAxis.findPolygonPolygonSeparation(polygonA, polygonB);
    const bSat = SeparatingAxis.findPolygonPolygonSeparation(polygonB, polygonA);

    return ClosestLine2(aSat.side, bSat.side);
}

https://github.com/user-attachments/assets/be6460cb-7786-4864-93aa-d8053478aa53

eonarheim commented 4 months ago

@mattjennings Thanks again! Bravo!