July 3rd, 2018 (back)

RAPTR - Collision Sprites and Static Meshes

Static Meshes and Alpha Channel Collisions

Lots of progress! I've added multiple modes of collision testing. Static meshes now can go into a precise pixel check after a coarse bounding box test. This is done by specifying a collision channel where the alpha channel denotes collisions. This is pretty neat and has some good results.

SDL Surface and Pixel Tests

This was actually fairly straight-forward. Our animation system presents itself as frames with particular offsets into the sprite-sheet. So, all that is really required is to pull the collision sprite and read the surface offsets, then compare that to the bounding box of the object we are testing.

bool StaticMesh::intersect_slow(const Rect& other_box) const
  const auto& surface = sprite->surface;
  const uint8_t* pixels = reinterpret_cast<uint8_t*>(surface->pixels);
  int32_t bpp = surface->format->BytesPerPixel;

  auto& pos = this->position();
  auto& frame = collision_frame;

  // x0 position
  int32_t x0_min = static_cast<int32_t>(std::max(other_box.x, pos.x));
  int32_t x0_max = static_cast<int32_t>(std::min(other_box.x + other_box.w,
                                                 pos.x + frame->w - 1));

  // y0 position
  int32_t y0_min = static_cast<int32_t>(std::max(other_box.y, pos.y));
  int32_t y0_max = static_cast<int32_t>(std::min(other_box.y + other_box.h,
                                                 pos.y + frame->h - 1));

  for (int32_t x0 = x0_min; x0 <= x0_max; ++x0) {
    for (int32_t y0 = y0_min; y0 <= y0_max; ++y0) {
      int32_t idx = ((frame-<y + y0) * surface-<pitch) + (x0 + frame->x) * bpp;
      const uint8_t* px = pixels + idx;
      if (*px > 0) {
        return true;
  return false;

Now, our collision system is as follows:

  1. An entity states that it wants to move to a certain location described by a bounding box.
  2. It requests from the world if there are any entities that will cause problems with this
  3. The world does a coarse R-Tree intersection and finds candidates
  4. Then for each candidate, it asks those entities if the first object will intersect with them

Entity wants to move

Rect fall_check = this->want_position_y(delta_ms);
fall_check.y += 0.1;
auto intersected_entity = game->intersect_world(this, fall_check);

World checks for intersections

std::shared_ptr<Entity> Game::intersect_world(Entity* entity, const Rect& bbox)
  double min_bounds[2] = {bbox.x, bbox.y};
  double max_bounds[2] = {bbox.x + bbox.w, bbox.y + bbox.h};

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

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

  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 (found->intersects(condition->bbox)) {
      condition->intersected = true;
      condition->found = found;
      return false;

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

  if (condition_met.intersected) {
    return entity_lut[condition_met.found->id()];

  return nullptr;