Howling Moon Software

With the large and dynamic scale that we have planned for Solaro, the game is going to need to work with relatively high velocities. We’ll want to allow ships to travel fairly fast so that they can get around the world, and bullets will have to travel even faster so that you can hit things. This means that we will need to support swept collisions, the bane of collision detection.

The easy implementation of collision detection is to move all the objects in the system and then check to see if they are overlapping. This simple but effective algorithm has worked great for decades. As long as your objects are relatively big or slow, the player isn’t going to notice that Mario overlapped a goomba by 2 pixels when he dies right away anyway. The problem with this technique is that if you have very fast moving objects (like a railgun bullet fired from your ship) it could move a huge distance in between individual timesteps. So on one frame, the bullet might be 100 meters in front of a ship and the next frame 100 meters behind it. This won’t do for Solaro.

While the Unity3D engine that we are building Solaro in has very nice built in collision detection and physics, it doesn’t support swept collisions. This means that we are on our own to implement them. Fortunately, swept collisions between spheres is very easy, and the fast paced gameplay of a shoot-em-up game means that a player is not going to notice if the collisions are 100% perfect. Games such as Halo 1 and Mechwarrior used a bunch of spheres to represent the collision shapes nobody really noticed. Additionally, spheres are easy to group into trees for efficient heirarchical culling of collisions.

So how easy is swept sphere collisions? A simple quadratic formula will do! What we are trying to solve for is the first point it time when their surfaces touch. Let’s start by simplifying the problem. Checking for a collision between two moving spheres is actually equivalent to checking if a line segment based on the relative position and motion of the spheres intersects a sphere with a radius that is the sum of the two sphere’s radii. This is a much easier way to think about the problem because we can just treat the line segment as a parametric equation for a line based on time, and check when the distance is equal to the radius of the sphere. Solving that, you end up with a simple quadratic equation that you can solve using the quadratic formula.

The following C# Unity3D code checks if two projectiles hit. v0 and v1 are the endpoints of the line segment we are checking. The rest is solving for the quadratic coefficients and solving the equation. The final t value is the percentage of the timestep that passed when the collision first occurred. It’s as simple as that!

  protected bool Sweep(SweptProjectile p0, SweptProjectile p1, ref HitInfo info){
    Vector3 v0 = p1.rb.position - p0.rb.position;
    Vector3 v1 = v0 + (p1.rb.velocity - p0.rb.velocity)*Time.fixedDeltaTime;
    float r = (p0.radius + p1.radius);

    float dot00 = Vector3.Dot(v0, v0);
    float dot01 = Vector3.Dot(v0, v1);
    float dot11 = Vector3.Dot(v1, v1);

    float a = dot00 - 2f*dot01 + dot11;
    float b = 2f*(dot01 - dot00);
    float c = dot00 - r*r;

    float det = b*b - 4f*a*c;

    if(det > 0f){
      float t = -(b + Mathf.Sqrt(det))/(2f*a);
      if(0f <= t && t <= 1f){
        info.t = t;
        info.projectile = p1;
        return true;
      }
    }

    return false;
  }