Hacker News Reader

Comment by aappleby | Hacker News Reader

If you want to do collision detection in something like a game and you don't want to be constantly debugging collision issues, you have to be way way more aware of numerical precision issues than this article is.

For example, even a basic "point in sphere" test can return logically inconsistent results if the point is right on the surface of the sphere and you swap the x and z coordinates.

Ignoring issues like precision can result in players falling through the world or walking through walls.

View on HN

One of my favorite books is Real-Time Collision Detection[1] which covers this and other adjacent topics(like cache line aware data structures!). I generally refer to it as "data structures for 2D/3D" and I think only the Art of Electronics has more value on a page-by-page basis for the domains I've enjoyed.

[1] https://realtimecollisiondetection.net/books/rtcd/

I'm surprised there was never a 2nd edition in the past 20 years.

I think the advice and mechanics are timeless. This is robust CS and Math stuff which stood the test of time. And this makes the book itself so valuable. I own it.

Note that there may be a 2nd edition coming but any release is against Christer Ericson's wishes and he's not involved: https://twitter.com/ChristerEricson/status/10504887470100602...

Nice, I literally just asked the OP to provide a link! Thank you!

Yep that's the book.

NB: there is a planned 2nd edition without the involvement and against the wishes of the author :(

https://x.com/christerericson/status/1050488747010060288?s=4...

This is a damn good book. I always recommend it to colleagues.

https://www.realtimerendering.com/intersections.html

Speedrunners will not appreciate it. ;)

Also, in my experience, right from the beginning you should be aware of performance issues and should be familiar with a quad tree.

I build shooters for Android mobile in 2016 and heavy action and lots of screen fun was impossible without quad trees.

Even logic with line intersection has to be careful! I wrote some code to use line intersection tests for 2D platforming. Turns out "find a line this line collides with, move to that point, and repeat" is easy to mess up due to FP precision.

I second Real Time Collision Detection. I used its section on line segment intersection to get my code working.

If the simulation hypothesis of reality is correct, does this mean we might encounter such edge cases in physics? Where should we look?

Sure, you'd look for division-by-zero issues, like black holes.

Or notice that 256-bit numbers floats are used (with 237-bit mantissas), which give roughly 10^71 distinct full-precision values: about the same as the width of the universe in plank lengths.

At the edge of the universe, you'd expect the lack of precision to turn the simulation into garbage, noise, or just heat. We call that the cosmic event horizon, which is sort-of what happens when you go too far in Minecraft. The heat we call the cosmic microwave background.

Similarly, you could notice that the simulation uses fixed-precision numbers for the simulation of local fields. You would expect this to manifest as a whole range of "minimum" values below which no physical process can go. Quantums of action, as it were. We call the study of this: Quantum Mechanics.

One could also envisage the universe being simulated on clusters of computers, but then you run into issues with data transfer bandwidth between nodes -- the ones simulating lots of complicated stuff will have trouble sending their data to other nodes fast enough. So a simple fix is to slow them down so that they don't overwhelm their neighbours. This temporal distortion is what we call gravity, and its study is general relativity.

Each cluster node running the simulation exchanges its state with its neighbours at each time step. It takes two time steps for the nodes one step further than that to receive an update. Three time steps for three nodes, and so forth. This limits the speed at which all information (causality) can flow through the grid of cluster nodes. We call this the speed of light, and its study we've named special relativity.

I enjoyed this :)

Meh... saying cosmic event horizon is like far lands is flat earthing at cosmic scale.

You can't physically get there, it's always the same distance from where you are (though it's shrinking over time they say)

You don't have to get there, it will eventually come to you. https://youtu.be/eVoh27gJgME?si=ld9M-ZAfK37XdyJL

This is super interesting, what further reading would you recommend for a complete beginner in collision detection? Thank you.

Not only collision detection, but everything that uses floats like graphic does. I would recommend introductions to numerics and linear algebra, which should cover everything needed (the theory and how to actually use floats in programs) but not be overly "mathematical" formulated. But as I am a mathematician (who learned that 25 years ago) I don't háve any concrete recommendations of books or videos of lectures and you would not be able to read my handwriting, as I would have problems reading what I wrote back then ;).

I ask this because I speculate that I discovered "new math". It is unlikely, because I failed math in school, but I dared to imagine 0=1 like many others. But the complete line of math I am trying to prove is -1=1=0=∞. It does sound crazy, I know. But I honestly think this line of math is what separates us from actual, working fusion. Of course, I realize how insane I sound, and that is why I am looking for ways to probe my hypothesis. I think I am getting closer, but literally every single person I talked to about this told me I should visit a psychiatrist :')

Reply on news.ycombinator.com