June 21st, 2018 (back)

RAPTR - Collisions and Trees

Progress Today

Today I reworked the controller interface, added a spatial tree for tracking entities, and integrated some collision.

Controller Dispatch

I reworked the controller dispatch so that both axis are sent to the callbacks. This makes it much easier to treat the joystick on the controller as a single object, then handling both axis independently.

int16_t axis = static_cast(e.caxis.axis);

int16_t primary_axis = axis / 2; // ugh... well, it's a safe assumption for now

float mag[2] = {0, 0};
float angle = 0.0;

for (int i = primary_axis; i <= primary_axis + 1; ++i) {
    SDL_GameControllerAxis axis = static_cast<SDL_GameControllerAxis>(i);
    const int16_t deadzone = 8000; // hardcoded for now
    const int16_t value = SDL_GameControllerGetAxis(sdl.controller, axis);
    if (value < -deadzone || value > deadzone) {
      mag[i] = std::max(-1.0f, std::min(value / float(std::numeric_limits<int16_t>::max()), 1.0f));

float x = mag[0], y = mag[1]; 
float magnitude = sqrt(x * x + y * y);
angle = atan2(y, x)  * 180.0f / M_PI;
angle += angle < 0 ? 360.0f : 0.0f;

for (auto& callback : right_joy_callbacks) {
    callback(primary_axis, angle, magnitude, x, y);


My plans are to do a 3-stage collision system. This is probably some slight over-engineering, but I am curious about doing pixel-perfect collisions and accounting for transparent pixels as no-hits. The idea:

  1. Create a spatial tree of the objects in the scene
  2. Store a table of last known locations so we have a way to update the spatial tree with remove / adds in a sane fashion
  3. On movement, the entity requests from the game permission to go to a location
  4. A coarse check (fast) is done on the spatial tree to determine if there is any candidate intersections to watch out for
  5. A bounding-box (fast) intersection test is done on candidates to find any that we need to check precisely
  6. The intersection rectangle is used as mask on both objects to see if there are pixel overlaps. If so, then it is an intersection

Spatial Tree: R-Tree

I am not writing my own R-Tree. Been there, done that. We need to know when to update the tree. So, a simple loop does the trick for right now:

for (auto& entity : entities) {

  const SDL_Rect& old_bbox = last_known_entity_loc[entity];
  SDL_Rect new_bbox = character->bbox();
  if (!SDL_RectEquals(&new_bbox, &old_bbox)) {
    float new_min_bounds[2] = {new_bbox.x, new_bbox.y};
    float new_max_bounds[2] = {new_bbox.x + new_bbox.w, new_bbox.y + new_bbox.h};
    float old_min_bounds[2] = {old_bbox.x, old_bbox.y};
    float old_max_bounds[2] = {old_bbox.x + old_bbox.w, old_bbox.y + old_bbox.h};
    rtree.Remove(old_min_bounds, old_max_bounds, entity);
    rtree.Insert(new_min_bounds, new_max_bounds, entity);
    last_known_entity_loc[entity] = new_bbox;

Then, when the entity wants to move:

SDL_Rect desired;
const auto& frame = sprite->current_animation->current_frame();
desired.x = want_x;
desired.y = want_y;
desired.w = frame.w * sprite->scale;
desired.h = frame.h * sprite->scale;

if (game->entity_can_move_to(this, desired)) {

We just follow our collision path from above:

bool Game::entity_can_move_to(Entity* entity, const SDL_Rect& bbox)
  float min_bounds[2] = {bbox.x, bbox.y};
  float max_bounds[2] = {bbox.x + bbox.w, bbox.y + bbox.h};

  struct ConditionMet {
    Entity* check;
    SDL_Rect bbox;
    bool intersected;
  } condition_met;

  condition_met.check = entity;
  condition_met.intersected = false;
  condition_met.bbox = bbox;

  rtree.Search(min_bounds, max_bounds, [](Entity* found, void* context) -> bool {
    ConditionMet* condition = reinterpret_cast<ConditionMet*>(context);
    Entity* self = condition->check;
    if (self->id() == found->id()) {
      return true;

    if (SDL_HasIntersection(&condition->bbox, &found->bbox())) {
      condition->intersected = true;
      return false;

    return true;
  }, reinterpret_cast<void*>(&condition_met));

  return !condition_met.intersected;