How do I represent projectiles in a video game?

Question

I'm making a simple fixed shooter game, similar to "Galaga",) as part of a presentation I'm doing. I'm wondering what strategies and data structures would people use for tracking projectiles, like lasers fired from the spaceship. A super simple implementation that I've used, before, is to just represent each projectile as a point, and check for collisions with all objects in the scene.

However, this seems costly, in large scenes with many projectiles; I'm wondering what other types of strategies or implementations are used for this type of use case. What do games like FPS use for tracking projectiles (bullets, tank shells, etc)?

Answer 1

For very fast projectiles (such as lasers or bullets), you could use, a Ray.

A ray has a start point and an end point. A (very minimal) data structure for a ray is:

struct Ray
{
  Vector3f start, end ;
} ;

Looks like this:

(You could also cache the direction vector and length, but I used a very simple defn above).

If the ray is a laser beam that travels at the speed of light, you would just persist the ray (as starting at the gun nozzle and ending on a wall somewhere) for a couple of frames. Anything intersecting the ray each frame takes damage.

If the ray is a slower projectile (like a bullet, for example), the distance the bullet travelled over a timestep is modelled by the ray. The start point is where the ray is at the beginning of the frame, and the end point is where the ray will be after the frame is done. Anything in the bullet's ray's way is damaged by the bullet.

Rays can be efficiently collided with spheres, aabbs, convex hulls etc. Check out my Hullinator project for an actual running program (CTRL+Click to fire rays)

Answer 2

Using a ray works well for instantaneously travelling projectiles such as bullets. For projectiles which have slower speed such as the type you'll make use of for your space game it makes sense to simply track their position in the game world like you would any other entity. What I often do is have a base class called Entity which contains properties of any lasting game object — position, rotation, collision box, etc. My player driven and projectiles then inherit off this and my game world only needs to know how to deal with the super class Entity, not each individual type of entity.

To increase performance it's very common to keep a pool around for any objects you'll be creating and destroying often. When you need a new projectile you'd pull from this pool, modify the new projectile as needed and return it back to the pool when it's expired.

Answer 3

When you want to optimize for collision detection, you could store all game objects in a two- or three-dimensional tree. This data structure makes it very efficient to retrieve all objects in a certain area.

Binary trees do however have the disadvantage that they degenerate easily when objects are added, removed and change their positions, so you will need to auto-balance it.

A compromise which would be easier to implement but not be quite as efficient would be to use a chunk-based approach. Divide the playing field into cubes and keep track of which objects are touching each cube. When you check for collisions with an object, you only need to check it against the object lists of the cubes it is touching (replace "cube" with "rectangle" for a 2d-game).