Collisions in Gothic Survival

27 Oct 2023

This post explains how my reverse bullet hell game Gothic Survival (iOS, Android) implements collisions for a large number of on-screen objects.

There’s a lot going on!

Gothic Survival is implemented in Flutter using the 2D game engine Flame. Both Flutter and Flame are constantly changing, so the code in this post may not line up with existing APIs. The general idea should be the same, so take what you will.

This post is split into roughly two parts:

Architecture, in which we discuss the requirements, options, and decision of how to implement collisions.
Implementation, in which I provide the actual Flutter and Flame code for collisions in Gothic Survival.

Architecture

There are a handful ways to get this done. We want to achieve a rapid development speed by keeping the code small and reusing parts of Flame where possible. Another hard requirement is performance: the game can easily have over 100-200 moving objects on the screen at once.

Notably, the game does not require true physics. It’s sufficient for things to sort of bunch up and move around each other somehow. It might take some experimentation to get this to “feel” right no matter how we implement it.

Architecture: Options

One option is Box2D, via its Flame integration plugin. Box2D will allow us to avoid any complex mathematical calculations. Unfortunately, the performance on a mobile device with hundreds of objects is not great. Moreover, it introduces complexity because physics only behaves “as expected” within realistic bounds.

Another option is to use Flame’s built-in collision system, called StandardCollisionSystem. This does not handle the collisions, so we need to implement how objects are displaced based on their properties, but the actual process of generating collisions is taken care of.

Lastly, we can ditch everything and throw every position of every collidable component into our own engine and implement collisions and their effects on component position. With enough time and effort, this could be the most performant, custom solution.

Architecture: Decision

Box2D would be excessively complex and likely fail to satisfy our performance requirements. Writing an engine to handle everything from scratch would take too long. As a result, the option that best satisfies our requirements is using Flame’s built-in collision system.

Although we need to write a little math for collision resolution, we can successfully reuse a large chunk of Flame’s code. The system’s performance is already quite good thanks to its use of quadtrees. As long as we don’t write any incredibly poor intersection testing functions, execution time will be solved.

Implementation

The collision system in Gothic Survival resolves two, primary concerns:

Solid Collision Detection: The built-in collision system detects collisions of the borders of shapes, but in Gothic Survival, there may be small objects completely contained within larger objects. These must collide as well.
Collision Resolution: The built-in collision system detects collisions and then passes that information to us via a callback. We need to compute how those objects are displaced based on this collision data.

Implementation: Solid Collision Detection

Flame allows you to completely replace the set of intersection tests used by its built-in collision system, and that’s precisely what we’ll do:

final List<Intersections> _solidIntersections = [
  SolidCircleCircleIntersections(),
  SolidCirclePolygonIntersections(),
  SolidPolygonPolygonIntersections(),
];

Set<Vector2> solidIntersections(ShapeComponent shapeA, ShapeComponent shapeB) {
  final intersectionSystem = _solidIntersections.firstWhere(
    (system) => system.supportsShapes(shapeA, shapeB),
    orElse: () => throw 'Unsupported shape detected',
  );

  return intersectionSystem.unorderedIntersect(shapeA, shapeB);
}

class SolidCollisionDetection extends StandardCollisionDetection {
  @override
  Set<Vector2> intersections(ShapeHitbox hitboxA, ShapeHitbox hitboxB) {
    return solidIntersections(hitboxA, hitboxB);
  }
}

A SolidCollisionDetection instance can then be inserted directly into Flame’s API.

Implementation: Solid Intersection Algorithms

The actual intersection algorithms are as follows. They are not particularly optimized - the goal is to release, measure, then optimize. After release, performance was completely sufficient, so I never went back.

// These methods don't really return the true intersection points.
// The game never uses intersection points, so it's wasted time.
final _NO_INTERSECTION_POINTS = Set.unmodifiable(Set<Vector2>.identity());
final _HAS_INTERSECTION_POINTS = Set.unmodifiable({Vector2.zero()});

class SolidPolygonPolygonIntersections extends PolygonPolygonIntersections {
  @override
  Set<Vector2> intersect(
    PolygonComponent polygonA,
    PolygonComponent polygonB, {
    Rect? overlappingRect,
  }) {
    for (final vertex in polygonA.globalVertices()) {
      if (polygonB.containsPoint(vertex)) {
        return _HAS_INTERSECTION_POINTS;
      }
    }

    for (final vertex in polygonB.globalVertices()) {
      if (polygonA.containsPoint(vertex)) {
        return _HAS_INTERSECTION_POINTS;
      }
    }

    return _NO_INTERSECTION_POINTS;
  }
}

class SolidCirclePolygonIntersections extends CirclePolygonIntersections {
  @override
  Set<Vector2> intersect(
    CircleComponent circle,
    PolygonComponent polygon, {
    Rect? overlappingRect,
  }) {
    // Should optimize this to stop producting intersection points too.
    // But it won't yield much benefit - most interactions are circle-circle.
    final intersectionPoints = super.intersect(
      circle,
      polygon,
      overlappingRect: overlappingRect,
    );

    if (intersectionPoints.isEmpty) {
      for (final vertex in polygon.globalVertices()) {
        if (circle.containsPoint(vertex)) {
          intersectionPoints.add(vertex);
        }
      }

      // Too lazy to implement a real polygon-circle intersection.
      final circleGlobalVertices = [
        circle.absoluteCenter + Vector2(circle.radius, 0),
        circle.absoluteCenter + Vector2(0, -circle.radius),
        circle.absoluteCenter + Vector2(-circle.radius, 0),
        circle.absoluteCenter + Vector2(0, circle.radius),
      ];

      for (final vertex in circleGlobalVertices) {
        if (polygon.containsPoint(vertex)) {
          intersectionPoints.add(vertex);
        }
      }
    }

    return intersectionPoints;
  }
}

class SolidCircleCircleIntersections extends CircleCircleIntersections {
  @override
  Set<Vector2> intersect(CircleComponent shapeA, CircleComponent shapeB) {
    final distance = shapeA.absoluteCenter.distanceTo(shapeB.absoluteCenter);
    final radiusA = shapeA.radius;
    final radiusB = shapeB.radius;

    if (distance > radiusA + radiusB) {
      return _NO_INTERSECTION_POINTS;
    }

    return _HAS_INTERSECTION_POINTS;
  }
}

After insertion, Flame’s collision detection system will report on solid intersections correctly. All that’s left is to handle the actual collisions themselves.

Implementation: Collision Resolution

If you’re not mathematically-inclined, you’re probably dreading this part. Fortunately, what we want to do isn’t particularly complicated.

Gothic Survival implements collision resolution without factoring in mass or momentum. Instead, it just tries to prevent things from moving into its physical body.

The actual in-game architecture for entities abuses mixins to put together special behavior, and collisions were no different. The HasMovement mixin is responsible for modifying position based on a movement vector, while HasCollisions provides access to a list of active collisions for processing.

The HasMovementCollisions combines these to modify the movement vector based on any active collisions. Here’s the actual code:

/// Handles modifying movement when colliding with blocking entities.
mixin HasMovementCollisions on HasMovement, HasCollisions {
  @override
  void onMove(
    EntityMovement movement,
    Vector2 target,
    Vector2 offset,
  ) {
    if (activeCollisions.isNotEmpty) {
      var blocked = false;

      for (final other in activeEntityCollisions) {
        if (other.collisions?.shouldBlock?.call(this as Entity) ?? false) {
          blocked = true;

          // This is a special case of vector rejection where the entity
          // rejects any movement into its area - ie. clamping.
          var destination = position + offset;

          // Easier to interact with a Rect instance for bounds-checking.
          final bounds = other.toRect();

          // Coming from the right: clamp destination to obstacle's left.
          if (position.x <= bounds.left) {
            destination.x = min(destination.x, bounds.left);
          }

          // Coming from the left: clamp destination to obstacle's right.
          if (position.x >= bounds.right) {
            destination.x = max(destination.x, bounds.right);
          }

          // Coming from the bottom: clamp destination to obstacle's top.
          if (position.y >= bounds.bottom) {
            destination.y = max(destination.y, bounds.bottom);
          }

          // Coming from the top: clamp destination to the obstacle's bottom.
          if (position.y <= bounds.top) {
            destination.y = min(destination.y, bounds.top);
          }

          // The permitted offset is only up until the clamped destination.
          offset = destination - position;
        }
      }
    }

    super.onMove(movement, target, offset);
  }
}

That wasn’t too bad! The result is performant and looks good, too.

Conclusion

Looking at the final result it may not be obvious, but this took experimentation. I iterated on how things behaved for several days before settling on this implementation. In between, I had several “more correct” displacement calculations, but somehow the simplest one produced the most aesthetic effect.

In the end, I believe the collision implementation in Gothic Survival is about as complex as it needs to be for the game to work. I’m pretty happy with it, which is quite the rare outcome! Feel free to reuse the code if you find it useful.