How do I check collision when firing bullet?

Question

I'm currently creating 2D game from top perspective. I'm having problems with bullets. Yes, I currently simulate their movement so user can see them (about 2x ). Moving them with

// this is static
Direction = new Vector2(mouse.X, mouse.Y) - new Vector2(player.x, player.y);
Direction.Normalize();
Speed = 900f;

//this is called in Draw(GameTime gameTime) 
Position += Direction * 9f * Speed * (float)gameTime.ElapsedGameTime.TotalSeconds;

actually it's working perfectly, however, they're too fast so I can't check their collision each frame and I need to re-play their way each frame. How would I do it? And how would I do this available for both server (which doesn't use XNA as I want to port it to Linux later) and client (using XNA)?

Here's an image which shows the problem (1. bullet is before target 2. bullet is behind target, so it can no longer intersect the target. My goal is to calculate whether it intersected the target before)

I have almost forgot to mention! These objects are moving, these are player, that means that user can get out of the bullet's trace

Answer 1

The simplest way to solve this problem is to use fixed time steps in XNA and tell it you want more fps for your update method, this makes your update code run more often and with smaller time steps which in turn means that your bullet will travel a shorter distance each time you check for collisions. This is essentially what Nick mentioned above, but with less changes needed to your code.

In the constructor for your Game class put the following two lines of code:

base.IsFixedTimeStep = true;
base.TargetElapsedTime = new TimeSpan((long)(TimeSpan.TicksPerSecond / 600f));

600f Is the number of frames per second you want, most likely your already running with fixed time step (this is the default in XNA) at 60fps, by changing it to 600 your bullets will be checked 10 times more often.

Once you understood how this works in practice however I would recommend that you do this manually by dividing the ElapsedGameTime you receive in your update with the speed of your bullet and then update the bullet multiple times per update, this way you don't force your entire game to run at higher frames per second just to accommodate your bullets moving fast. Hope this helps.

---

PS. Swept objects is an interesting solution to this problem, while probably overkill for your scenario, it involves sweeping the object (the bullet) along its movement vector and then comparing this new shape to the other objects for collision. Sweeping a circle would give you a capsule for instance. You would normally do this with the bounding boxes of the sprites since its easier to calculate, but using algorithms like GJK you can do it with arbitrary shapes as well (in both 2D and 3D).

Answer 2

There are two methods of collision detection.

---

Discrete stepping

Use basic calculus to step an object A through space by some (typically fixed) distance per step. At each step, check object A for colocation with other objects B in the same space.

Pros: Cheap to process.

Cons: Can miss objects through penetration, which occurs because your physics timestep (need not necessarily be your gameloop timestep!) is not small enough to catch those cases where a bullet would have hit another object. Either (a) reduce your timestep to a smaller value and iterate your physics more frequently, or (b) reduce and cap maximum velocities, or (c) opt for CCD, below.

---

Continuous Collision Detection (CCD) AKA raycasting

This uses linear algebra to determine whether a line (or lines) representing body A's trajectory, is intersected by another line representing the boundary of some other solid body B. .

Pros: 100% accurate.

Cons: Costly to process, as you have to check the line against everything within your scene, or at least your area of interest (AoI) near to the player.

---

A number of physics engines allow a choice between these, for given types of bodies. For instance, while it may be prudent to use CCD for very fast moving, small objects like bullets, it may be perfectly acceptable to use stepping for other objects, since the timestep is small enough, and they are large and slow-moving enough, that there is no way they could overshoot/penetrate.

Answer 3

If the bullet is moving very fast then I believe that you would use raycasting (at least that is what I think it is usually called) in order to determine collision. In this example you would have the old position, you would calculate the new position. Then you would represent this movement by a line/ray between these two positions. If this line intersects with any geometry in your scene, then the bullet has hit something.

While I am not familiar with XNA, I would be surprised if it doesn't have built-in support for performing raycasting checks.

Some links that may be useful:

http://www.synapsegaming.com/forums/p/825/3684.aspx

http://www.youtube.com/watch?v=o9E1AhpcXWg