I am programming a game in the spirit of Wolfenstein 3D (2D grid map, 1 cell = 1 cube) and I wanted to implement shootings. I didn't want the shootings to happen in one frame so, I wanted to see the beams flying everywhere.

So this gets a bit complicated for me to test for impacts. To be fair, I'm not really sure how I'm supposed

This is how I used to do it : I took the position of the beam and checked on the map to see if there is a wall at said position. It works great when the beam is moving very slowly. But when they go extremely fast, naturally, as you would expect, they clip through walls.

Here you can have an idea of what I'm looking for. 2D grid with white cells being air and grey cells being walls. Player is green, beam is red and dotted lines represent the beam on next frames. And orange is the collision

So I'm not exactly sure when and what to test for collisions here, as well as how to find the impact's position. What would be the most optimised way to test for collisions ?


The problem is that your bullet is flying so quick that it passes between two game loops the collision check, in particular when it is directed towards a corner. There are a few solutions to that:

Use Matrix algebra if you have a gamemath class in place. See this solution here on stackoverflow (here). As you can see, there are quite some calculations where matrix algebra can help you if you really need a clean solution!

I use a simplified algorithm that uses real time determination for fast projectiles. The idea is to run a pre-check that simulates a slow bullet near the corner in question. This is not a mathematical solution--and could be considered more dirty than my first proposition--but should do the trick if you do not plan to have 10000 bullets to fly around at the same time. Here is how it goes.

  1. Determine how much your bullet in general traverses per game loop. Call it r which is simply the length of your bullet's speed vector times delta t (or your framespeed etc.).

  2. At each corner of the wall at the time of the bullet getting out, construct around a maximum distance to the bullet's maximum range circles around all corners. See pic.enter image description here. You can even simplify this by only considering corners that are in direction of the bullet's flight path etc.

  3. Determine during the bullet's flight if the bullet hits a circle (=is inside!). Now you know which corner is the one you need to be carefully looking at to start a refined algorithm. Note down the corner's coordinates <cx,cy> and where it had a positive collision check <hitx, hity>

  4. This is the corner you have to zoom into. Construct a mathematical infinite line from the player's position and the speed vector of the bullet. (blue line).

  5. Determine the intersection with the circle of this line. To do so, get the get the intersection point within the circle and move in direction to the player by distance r at an angle determined of the (negative) bullet's speed vector <hitx-cos(angle)*r, hity-sin(angle)*r>. (Now you calculated the position of the green dot in the pic or a bit prior to that along the flightpath).

  6. Here you need to slow down in theoretical pre-test algorithm. Move pixel by pixel in direction of the bullet's speed vector until you reach the other side of the circle. For this, create a loop that moves with very small t or pixel-wise and do a point-in-rectangle-check, that is, you test whether any point along this path is inside the rectangle (wall). You can find an algorithm for this (see post here: How do I efficiently check if a point is inside a rotated rectangle?). The test is very fast, as in reality the circle buffer size around a corner is quite small and the loop could have around 20-30 iterations, which doesn't budge the performance.

  • \$\begingroup\$ Thank you for your input. I actually ended up cutting the ray in smaller rays and testing collisions that way. It surprisingly works better than I expected \$\endgroup\$ – Gaktan Oct 27 '15 at 21:21
  • \$\begingroup\$ Well cone! This solution it is based on that, but this algorithm is slightly more efficient as the smaller cuts start to be implemented when it hits the circle. \$\endgroup\$ – Majte Oct 27 '15 at 22:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.