# How do I handle collision detection so fast objects are not allowed to pass through walls?

I'm creating a 2d sidescrolling shooter, and I'm having a little trouble with collision detection for the bullets. Everything including the bullets are objects with their own polygons / update methods.

The trouble is that bullets go fast, and at 60 frames per second (what the game runs at) a bullet will often skip right through a wall -- since it moves more than the width of the wall during in the update interval -- and continue happily on its way since the polygons will never actually overlap.

What can I do about this? The only thing I've been able to come up with is to draw a line from the old position to the new position and do collision detection on that, but line drawing for collision detection is recommended against by the slick2d documentation. How can I solve this?

• Not a full answer, so a comment. I would never recommend graphically drawing a line but mathematically you can do this, its just a simple ray-plane intersection to see if the collision occured. You can then do a smaller fixed step detection to get the exact moment (and all the information that comes along with it) when the collision happened with out having to run at a constantly higher rate as suggested in the answers. Do a less costly check and then spend the time getting as precise of an answer as you need. May 9, 2018 at 22:31

The standard approaches are (pick one):

1. Increase your boundary width AND/OR reduce the maximum speed of your bullet so that it can never jump through a wall in a single update (requiers a bit of Pythagoras to figure out the maxium distances / minimum boundary widths);
2. Perform continuous collision detection (CCD), usually by raycasting to detect collision with linear (2) or planar (3D) surfaces ahead of the moving object. This is more expensive, but is a more well-rounded solution. Raycasting against 2D lines is pretty basic, but you do need to define all your boundaries as straight-edge polygons in this case.

For that matter, you can model your bullets as rays instead -- if that fits with the look & feel of your game, as in left4kdead. That way you don't need to approximate bullets as rays, because they already are rays. From the viewpoint of looks, this can look decent if you draw the line with a brighter spot on the bullet end, or just draw the line as a gradient from light (bullet end) to dark (tail end), giving it an appearance of motion.

I would agree that under most circumstances, using graphics for collision detection is a bit misguided, however pixel-perfect collision detection is exactly that, and is an accepted technique. I guess it all depends on what you want to achieve, and how quickly. If you don't need a very fast game with many bodies + action, go for it. Else better to use one of the approaches I outlined above.

• Thanks for the great answer - ideally i'd like it to be fast paced with many moving bodies. The reason I'm treating bullets as physical objects is so that they're affected by gravity like everything else (so arc down slightly, depending on the speed of the bullet, etc). Is this not a good way to do it? This is my first game, so I'm still hunting around for best practices. I could also use a parabolic equation, but I'm not sure how I'd set up the coefficients relating to the speed / aim angle of the bullet
– Mala
Oct 17, 2011 at 17:24
• It sounds like too much detail for bullets. In real life, when you fire a bullet, you are unlikely to ever find that slug due to the force of ricochet, unpredictability of the richochet angle, etc. Or else, it just enters a body and stays there (tree, person). I would just have them vanish or ricochet and then vanish shortly thereafter. Focus on your core gameplay, don't worry too much about these small details. Realism is best focused on the things that matter. Oct 17, 2011 at 17:32
• Yeah, I suppose I can just use straight lines for bullets and maybe find a way to make them curve downwards slightly later, if it seems important.
– Mala
Oct 17, 2011 at 17:45
• If the speed of the bullets is not too high (i.e. not so fast that you wouldn't be able to see them travel across the screen), then you can just apply gravity to their velocity while still modeling their collision detection using simple rays. The user is not going to notice that the bullet is moving as a series of straight lines anymore than he'll notice how all your other objects are also doing the same. For bullet trails, calculating and drawing a curved trail (spline) is not hard and will increase the illusion of a smooth curve to the bullet's trajectory. Oct 18, 2011 at 0:15

If you want your bullets to behave like realistic physical objects (eg. your bullets are more like arrows or stones from a catapult rather than gun-fire), then you could also try to increase the frequency of your physics-updates.

So while your game might run with 60 frames per second, your physic-simulation could run at 120 updates per second (here's the ubiquitous fix your timestep article that explains a good physics setup that can run at different speed than the render-loop).

Of course, increasing the update-interval on the physics-engine will put a bigger load on the CPU. So this approach is only sensible if your projectiles aren't very fast moving (which I was assuming since you are able to tell that your projectiles are moving in arc).

• Thanks! I'm effectively doing this (as well as using line-shaped projectiles) and am hoping it stays feasible as the game gets more complicated
– Mala
Oct 18, 2011 at 15:39