Pixel-perfect 2D collision detection in SDL.

game.cc

#include <assert.h>
#include <stdio.h>
#include <stdint.h>

#include <SDL.h>

typedef uint32_t u32;
typedef int32_t i32;
typedef uint64_t u64;
typedef int64_t i64;
typedef float f32;
typedef double f64;

i32 Sign(i32 Value) {
  if (Value >= 0) {
    return 1;
  }

  return -1;
}

typedef union v2i_t {
  struct {
    i32 X, Y;
  };
  struct {
    i32 W, H;
  };
  i32 V[2];
} v2i;

inline v2i operator + (v2i Left, v2i Right) {
  v2i Result = { Left.X+Right.X, Left.Y+Right.Y };
  return Result;
}

typedef union v2_t {
  struct {
    f32 X, Y;
  };
  struct {
    f32 W, H;
  };
  f32 V[2];
} v2;

inline v2 operator + (v2 Left, v2 Right) {
  v2 Result = { Left.X+Right.X, Left.Y+Right.Y };
  return Result;
}

inline v2 operator * (v2 Left, v2 Right) {
  v2 Result = { Left.X*Right.X, Left.Y*Right.Y };
  return Result;
}

inline v2 operator * (v2 Left, f32 Scalar) {
  v2 Result = { Left.X*Scalar, Left.Y*Scalar };
  return Result;
}

inline v2 operator * (f32 Scalar, v2 Right) {
  v2 Result = { Right.X*Scalar, Right.Y*Scalar };
  return Result;
}

inline void operator += (v2& Left, v2 Right) {
  Left.X += Right.X;
  Left.Y += Right.Y;
}

typedef struct aabb_t {
  v2i Min;
  v2i Max;
} aabb;

typedef struct entity_t {
  v2i Pos;
  v2i Dim;
  v2 Vel;
  v2 Acc;
  // We store the fractional remainders from movement so we can get sub-pixel
  // accuracy.
  v2 Rem;
  aabb Box;
} entity;

entity BuildEntity(i32 X, i32 Y, i32 W, i32 H) {
  entity Result;
  Result.Pos = { X, Y };
  Result.Dim = { W, H };
  Result.Vel = { 0.0f, 0.0f };
  Result.Acc = { 0.0f, 0.0f };
  Result.Rem = { 0.0f, 0.0f };
  Result.Box = { { X, Y }, { X + W, Y + H }};

  return Result;
}

typedef struct game_input_t {
  bool MoveLeft;
  bool MoveRight;
  bool ActionDown;

  f32 DeltaTimeSecs;
  v2i MouseP;
} game_input;

typedef struct game_state_t {
  bool Running;

  entity Player;
  entity PlayerFeet;
  bool Grounded;

  u32 JumpPresses;

  u32 NumObjects;
  entity Objects[100];

  SDL_Renderer* Renderer;
} game_state;

void PushObject(game_state* State, entity Object) {
  assert(State->NumObjects < 100);
  State->Objects[State->NumObjects++] = Object;
}

bool HasCollision(aabb* A, aabb* B) {
  bool Result = false;

  if ((A->Min.X <= B->Max.X && A->Max.X >= B->Min.X) &&
      (A->Min.Y <= B->Max.Y && A->Max.Y >= B->Min.Y)) {
    Result = true;
  }

  return Result;
}

bool HasCollision(game_state* State, entity* Entity, v2i Pos) {
  aabb EntityBox = {
    { Pos.X, Pos.Y },
    { Pos.X + Entity->Dim.W, Pos.Y + Entity->Dim.H }
  };

  for (u32 I = 0; I < State->NumObjects; ++I) {
    if (HasCollision(&EntityBox, &State->Objects[I].Box)) {
      return true;
    }
  }

  return false;
}

void MovePlayerX(game_state* State, entity* Player, v2 Disp) {
  Player->Rem.X += Disp.X;
  i32 Move = (i32)round(Disp.X);

  if (Move != 0) {
    Player->Rem.X -= Move;
    int sign = Sign(Move);

    while (Move != 0) {
      if (!HasCollision(State, Player, Player->Pos + v2i{sign, 0})) {
        Player->Pos.X += sign;
        Move -= sign;
      } else {
        Player->Vel.X = 0;
        break;
      }
    }
  }
}

void MovePlayerY(game_state* State, entity* Player, v2 Disp) {
  Player->Rem.Y += Disp.Y;
  i32 Move = (i32)round(Disp.Y);

  if (Move != 0) {
    Player->Rem.Y -= Move;
    int sign = Sign(Move);

    while (Move != 0) {
      if (!HasCollision(State, Player, Player->Pos + v2i{0, sign})) {
        Player->Pos.Y += sign;
        Move -= sign;
      } else {
        Player->Vel.Y = 0;
        break;
      }
    }
  }
}

void DrawEntity(game_state* State, entity* Entity) {
  SDL_Rect Rect = {
    .x = Entity->Pos.X,
    .y = Entity->Pos.Y,
    .w = Entity->Dim.W,
    .h = Entity->Dim.H
  };
  SDL_SetRenderDrawColor(State->Renderer, 255, 255, 255, SDL_ALPHA_OPAQUE);
  SDL_RenderFillRect(State->Renderer, &Rect);
}

void DrawPlayer(game_state* State, entity* Player) {
  SDL_Rect Rect = {
    .x = Player->Pos.X,
    .y = Player->Pos.Y,
    .w = Player->Dim.W,
    .h = Player->Dim.H
  };
  SDL_SetRenderDrawColor(State->Renderer, 0, 0, 255, SDL_ALPHA_OPAQUE);
  SDL_RenderFillRect(State->Renderer, &Rect);
}

f32 Square(f32 V) {
  return V*V;
}

void GameUpdateAndRender(game_state* State, game_input* Input) {
  v2 ddPlayerP = { 0.0f, 10.0f };
  v2 Disp = { 0.0f, 0.0f };

  if (Input->MoveLeft && Input->MoveRight) {
    // Do nothing
  } else if (Input->MoveLeft) {
    if (State->Player.Vel.X > 0) {
      State->Player.Vel.X = -1;
      State->Player.Rem.X = 0;
    }
    ddPlayerP.X = -1.0f;
  } else if (Input->MoveRight) {
    if (State->Player.Vel.X < 0) {
      State->Player.Vel.X = 1;
      State->Player.Rem.X = 0;
    }
    ddPlayerP.X = 1.0f;
  }

  if (State->Grounded) {
    // Gravity stops when grounded
    ddPlayerP.Y = 0.0f;
  }

  if (Input->ActionDown && (State->Grounded || State->JumpPresses < 20)) {
    State->Player.Vel.Y += -50.0f;
    State->JumpPresses++;
  }

  // NOTE: Prevent uses from doing mid-air jumps because they haven't hit their
  // jump count.
  if (!Input->ActionDown && !State->Grounded && State->JumpPresses < 20) {
    State->JumpPresses = 20;
  }

  ddPlayerP.X = ddPlayerP.X * 600.0f;
  ddPlayerP.Y = ddPlayerP.Y * 300.0f;
  if (State->Grounded && !Input->MoveRight && !Input->MoveLeft) {
    ddPlayerP.X += -4.0f*State->Player.Vel.X;
  }
  Disp = 0.5f * ddPlayerP * Square(Input->DeltaTimeSecs) + State->Player.Vel * Input->DeltaTimeSecs;
  State->Player.Vel += ddPlayerP * Input->DeltaTimeSecs;

  MovePlayerX(State, &State->Player, Disp);
  MovePlayerY(State, &State->Player, Disp);

  DrawPlayer(State, &State->Player);
  for (u32 I = 0; I < State->NumObjects; I++) {
    DrawEntity(State, &State->Objects[I]);
  }

  v2i FeetPos = State->Player.Pos;
  FeetPos.Y += 32;

  // Check if the 32x1 invisible tile just below the player has collided with something.
  // If so, then we say the player has hit the ground and become "grounded".
  if (HasCollision(State, &State->PlayerFeet, FeetPos)) {
    if (!State->Grounded) {
      printf("Grounded\n");
    }
    State->Grounded = true;
    State->JumpPresses = 0;
  } else {
    State->Grounded = false;
  }
}

int main() {
  game_input Input = {
    .MoveLeft = false,
    .MoveRight = false,
    .ActionDown = false,
    .DeltaTimeSecs = 0.0f,
    .MouseP = { 0, 0 }
  };
  game_state State = {
    .Running = true,
    .Player = BuildEntity(1 * 32, 0, 32, 32),
    .PlayerFeet = BuildEntity(1 * 32, 32, 32, 1),
    .NumObjects = 0
  };
  State.JumpPresses = 0;
  State.Grounded = false;

  // Push the ground and platforms for the player to collide with
  PushObject(&State, BuildEntity(0 * 32, 14 * 32, 32, 32));

  PushObject(&State, BuildEntity(24 * 32, 14 * 32, 32, 32));
  PushObject(&State, BuildEntity(5 * 32, 13 * 32 - 2, 2 * 32, 32));

  PushObject(&State, BuildEntity(0, 15 * 32, 25 * 32, 32));

  SDL_Init(SDL_INIT_EVERYTHING);
  SDL_Window* Window = SDL_CreateWindow(
    "Collisions Test",
    SDL_WINDOWPOS_CENTERED,
    SDL_WINDOWPOS_CENTERED,
    800,
    600,
    0
  );
  SDL_Renderer* Renderer = SDL_CreateRenderer(
    Window,
    -1,
    SDL_RENDERER_ACCELERATED | SDL_RENDERER_PRESENTVSYNC
  );

  State.Renderer = Renderer;

  SDL_Event Event;
  u32 LastTime = SDL_GetTicks();
  while (State.Running) {
    while (SDL_PollEvent(&Event)) {
      if (Event.type == SDL_QUIT) {
        State.Running = false;
      }

      if (Event.type == SDL_KEYDOWN) {
        switch(Event.key.keysym.sym) {
        case SDLK_ESCAPE:
          State.Running = false;
          break;
        case SDLK_LEFT:
          Input.MoveLeft = true;
          break;
        case SDLK_RIGHT:
          Input.MoveRight = true;
          break;
        case SDLK_SPACE:
          Input.ActionDown = true;
          break;
        default:
          break;
        }
      }

      if (Event.type == SDL_KEYUP) {
        switch(Event.key.keysym.sym) {
        case SDLK_LEFT:
          Input.MoveLeft = false;
          break;
        case SDLK_RIGHT:
          Input.MoveRight = false;
          break;
        case SDLK_SPACE:
          Input.ActionDown = false;
          break;
        default:
          break;
        }
      }

      if (Event.type == SDL_MOUSEMOTION) {
        Input.MouseP.X = Event.motion.x;
        Input.MouseP.Y = Event.motion.y;
        printf("%d, %d\n", Input.MouseP.X, Input.MouseP.Y);
      }

      if (Event.type == SDL_MOUSEBUTTONDOWN) {
        // Left-mouse clicks insert a new 32x32 collidable tile onto the screen. Useful
        // for drawing more collidable stuff to test collisions in different ways.
        if (Event.button.button == SDL_BUTTON_LEFT) {
          u32 TileX = Input.MouseP.X / 32;
          u32 TileY = Input.MouseP.Y / 32;
          printf("%d, %d - %d, %d\n", TileX, TileY, TileX * 32, TileY * 32);
          PushObject(&State, BuildEntity(TileX * 32, TileY * 32, 32, 32));
        }
      }
    }

    SDL_SetRenderDrawColor(Renderer, 0, 0, 0, SDL_ALPHA_OPAQUE);
    SDL_RenderClear(Renderer);

    u32 CurrentTime = SDL_GetTicks();
    Input.DeltaTimeSecs = (f32)(CurrentTime - LastTime) / 1000.0f;
    GameUpdateAndRender(&State, &Input);
    LastTime = CurrentTime;

    SDL_RenderPresent(Renderer);
  }

  SDL_DestroyRenderer(Renderer);
  SDL_DestroyWindow(Window);
  SDL_Quit();
  return 0;
}

Makefile

.PHONY: run

CXXFLAGS=-Wall -g -fno-exceptions -fno-rtti $(shell pkg-config sdl2 --cflags)
LDFLAGS=-lm $(shell pkg-config sdl2 --libs)

game: game.cc
	$(CXX) $(CXXFLAGS) -o game game.cc $(LDFLAGS)

run: game
	./game

clean:
	rm -rf *~ game

What if the velocity of the player is greater than the size (width or height) of the object?