Collision Detection, Oh How Elusive
Collision detection is still a significant issue in programming even to this day. Initially it may seem straightforward: if two objects occupy the same space make them move away. However this becomes increasingly difficult to do when the work space isn’t just two 2D objects in the same space, and it’s often complex 3D objects in 3D space. Beyond just properly detecting that there was a collision the extended difficulty comes when programming the collision response.
A Simple Example
Here is a simple collision model I have created using p5.js with their 2D collision library. p5.js will redraw the ball’s position 60 times every second, and has a built in collision detection function will output true whenever the pixels of the ball occupy the same coordinates as the pixels of the line. The ball is only moving on the y-axis and has no speed in the x-direction.
When the line-circle-collision function returns true, the speed of the ball in the y-direction will be reversed.
The ball also has collision detection for the walls of the grid, such that when the pixels of the ball occupy the same coordinates of the walls, its speed reverses.
And this works for the most part, but it is very easy to break.
After drawing just a few lines in a very dense, small area, the collision equations simply cannot keep up with both the position of the ball, and the positions of the lines. This allows the ball to clip through the lines making our boundaries useless.
This sort of clip doesn’t even require that you overwhelm the grid with large number of lines. This can be done using a smaller ball. This occurs because when the code redraws the location of the ball, its possible that the individual frames of the balls location never actually have it come into contact with the line.
This is an incredibly simple example, and it’s still very easy break.
Things Get Very Complex Very Fast
Physics simulations take a very precise, and detailed approach to collision detection. They usually incorporate physical models and equations into their code along with their collision detection. A common practice for small, controlled simulations such as the one above is to check frame by frame, at an incredibly high frame rate, the entire list of intersecting bodies, put these into physical models, and obtain new position data bases off of that. There are sub-types of collision models within physics simulation but they all follow this general idea.
And this is precise. But this method is incredibly inefficient and requires a huge amount of power to accomplish.
Maybe We Should Take a Step Back
Video games are perhaps the most common instance of programmers needing to detect and respond to collisions. And today, video games are rarely as simple as a ball and some lines. Objects in video games are often times 3D polygons with very detailed surfaces that have to interact with other objects, lighting, particle effects, and so much more. They have their own animation cycles that can also affect their collision detection.
Video games do not have access to the same computational power that a physics simulation would, so it does not have the time or power to go every single point of interaction. So a near universal practice is through hitboxes.
Hitboxes are simple 3D polygons that follow a much more detailed model. Seen in the gif above, the yellow and red areas indicate where the detection data would be tested. In this case if the red from one model were to collide with the yellow from another model, it would detect that the attack connected. The collision data does not need to be nearly as precise as compared to if it was testing the character model.
There are some issues with this method. The hitbox and the character model are not perfectly synced up, so collision data does not always much with what is on screen. A character may appear as though they should be hit, but their hitbox is off enough that it does not detect any collision.
A Long Way to Go
Collision detection is still being studied and advanced upon, with many new and different models for calculating position, collision, and response. A major limiting factor as of right now is computational power, so it may be some time before it feels seamless.
I recommend reading these articles for more info: