In my experience, collision detection is the easy piece (partly due to the prevalence of resources like this one); collision resolution is where you start having to make compromises (and there aren’t always clean solutions).
CD is an unsolved problem. CD is actually where you make the bigger compromises. Even we had analytical solutions to every collision scenario (we are nowhere near that) still we have "floating point issue". Everything that touches FP is corrupted and it gets much worse for CD. Issues with the collision response partly the after effects.
I think the main difference is that it's not hard to get approximate detection methods working with some high school geometry(and for games with simple physical behavior, you can usually stop at those) but finding any kind of approximate solution to collision response is not something students are ordinarily given any theoretical background in until undergraduate education, and then mostly indirectly through calculus, not crossing into the general CS classes where it would directly connect.
If you study physics specifically and are plugged into the theory driving iterative solvers, or perhaps you study math and spot the connection between constraint problems generally and the specific case of collision, you can find your way to answers about engineering satisfying non-realistic behaviors, but that's describing a subset of game programmers. Many still stumble through a sea of hacks and reliance on libraries because the conceptual knowledge hasn't been directed at them.
Very nice! A very good resource on collision detection is the book by Christer Ericson (2005). However it is more geared towards c++ realtime games.
https://realtimecollisiondetection.net/
I appreciate this nice site too.
I learned a tremendous amount of information from that book. It's _the_ book to get if you're interested in collision and related spatial data structures.
It's a very basic intro. Polygon/polygon is brute force, O(N^2). There's no coarse filtering so that only nearby objects are checked. There's nothing that points out that concave objects are much harder to check efficiently than convex ones. Plus it's 2D only.
An intro is nice, but this is like writing about sorting and only showing bubble sort.
This is beautiful, but it seems to be missing two pretty common cases:
1. Off-axis rectangles, which are common for things like fighting games
2. Efficient convex polygon to convex polygon collision (GJK being the most popular algorithm), which is sort of the “most general” 2d collision detection problem.
I have brief look at this book and it looks nice and easy to read, however I noted the author works with floating point numbers and in some places, you can see snippets like this:
// are the two points in the same location?
if (x1 == x2 && y1 == y2) {
return true;
}
You should never compare two floating-point numbers for equality.
Use interval and < > to determine if two numbers are close.
> You should never compare two floating-point numbers for equality.
... when their values come from an arithmetic computation.
Here's a counter example: Quake's collision code makes extensive use of `if(trace.fraction == 1.0f)`, which basically means "could the whole move be done without colliding?". This makes sense, because `fraction` is explicitly initialized to `1.0f`, and gets potentially overwritten with lower values in case the ray intersects colliders.
This could also make sense when dealing with clamped values, e.g:
```
const float ratio = clamp(some_computation, 0.0f, 1.0f);
if (ratio == 0.0)
{
// ...
}
```
In both cases, the zero or one being compared to isn't a result of an arithmetic computation ; it comes from an assignment with a known constant (e.g inside `clamp`).
Like a lot of things, the “don’t compare floats for equality” is a rule you should follow unless you understand it well enough to know when you can break it.
In particular, in many cases, you want to consider alternatives to comparing against a fixed epsilon: the relative epsilon approach, and the ULP (Units in the Last Place) method, which tests for how many other floats/doubles are representable between two values you're comparing. The benefit of these two methods is that they scale with the compared numbers.
Thanks all for the love and suggestions! I made this site more than five years ago and am so happy it helps folks daily. This is a project that can always be expanded and what's there is never enough. Super helpful to hear from y'all on some low-hanging next steps. Happy to hear more suggestions on what next steps and/or can't-be-left-out topics. (With the eye towards beginners and folks without a ton of math background – the goal isn't to be a drop-in for Box2D or Unity or whatever but to outline the fundamentals and get folks started.)
I am positively in love with this website. It’s simple. Looks great. Works on mobile. It’s well organized with exactly the right amount of data. When dealing with algorithms you need to get right to the point. Don’t make it a dense read. And because of all these successes, this website is also a good reference.
No, it’s not premature. Skipping sqrt operations in the inner loops, which collision detection often is, is a generally good idea because the sqrt operation isn’t cheap.
My 8-bit games just used rectangles; for circles I just overlapped two inside the geometry in a fat "+" shape. This was on a platform with pixel-accurate collision detection in hardware, and I always thought that the sloppy geometry-based detection was more fun for players.
N-squared for single-digit N worked just fine, too.
Historial note: To avoid sqrt, the Atari baseball cartridge went the 1897 Indiana legislature one better, using octagons as circles.
π ~= 3,314?
Unte im finyish du kaxa okwa bik, 4 600 mm bi wit dek xante im. Na desh kuwang, unte im 2 300 mm gova bik, unte 14 000 mm fo imim du gang im.
- 1 Da Bosmang Da Bik Imalowda 7:23
I found the OOP chapter to be very questionable and against industry practice. Even for simple software you don't want to clobber rendering and collision detection together into the same object. The algorithms also naturally become O(n^2) and it's not possible to fix that without major rewrites, undoing the OOP. OOP is notoriously bad for CD. I'd suggest a simple data oriented design approach here, e.g. pushing collisions into a new container instead of setting flags in some object that the rendering code then uses.
First sort by one axis, then take the items that are close enough and sort them by another axis, then take the ones that are close enough and do the expensive square root or intersect calculations which are much slower then sorting.
