Building Smooth Curves from Waypoints in 2D Games

When developing a 2D shoot 'em up (shmup) or path-based level editor, having entities fly across rigid, linear segments quickly feels unnatural. To give enemies that fluid, classic arcade flight path, you need interpolation techniques that generate smooth curves passing cleanly through arbitrary waypoints.

While Bézier curves are often the first recommendation, they present a significant challenge: standard Bézier curves do not naturally pass through their intermediate control points. Instead, they are pulled toward them. For level designers who place waypoints expecting an enemy to hit each point directly, Catmull-Rom splines are typically the superior choice.

Why Catmull-Rom Splines are Ideal for Path Following

A Catmull-Rom spline is a type of cubic Hermite spline where the curve is guaranteed to pass directly through every control point. It calculates tangents automatically based on adjacent points, eliminating the need to manually compute control handles.

Key advantages include:

  • Precision: Enemies hit every waypoint specified in the level editor.
  • Local Control: Adjusting one point only affects the adjacent curve segments, leaving the rest of the path intact.
  • Simplicity: You don't need complex control handle math like you would with composite Bézier paths.

Implementing Catmull-Rom Interpolation in C/C++

Given four consecutive control points p0, p1, p2, and p3, the position between p1 and p2 can be calculated using a normalized parameter t (where 0 <= t <= 1):

struct position {\n    double x;\n    double y;\n};\n\nstruct position get_catmull_rom_position(double t, struct position p0, struct position p1, struct position p2, struct position p3) {\n    double t2 = t * t;\n    double t3 = t2 * t;\n\n    struct position result;\n    result.x = 0.5 * ((2.0 * p1.x) +\n                      (-p0.x + p2.x) * t +\n                      (2.0 * p0.x - 5.0 * p1.x + 4.0 * p2.x - p3.x) * t2 +\n                      (-p0.x + 3.0 * p1.x - 3.0 * p2.x + p3.x) * t3);\n\n    result.y = 0.5 * ((2.0 * p1.y) +\n                      (-p0.y + p2.y) * t +\n                      (2.0 * p0.y - 5.0 * p1.y + 4.0 * p2.y - p3.y) * t2 +\n                      (-p0.y + 3.0 * p1.y - 3.0 * p2.y + p3.y) * t3);\n\n    return result;\n}

Handling Curve Endpoints

Because Catmull-Rom requires four points to evaluate a segment (two segment endpoints and one neighbor on each side), handling the start and end of the path requires special consideration. You can solve this by duplicating the edge points:

  • To interpolate between points[0] and points[1], use: p0 = points[0], p1 = points[0], p2 = points[1], p3 = points[2].
  • For closed loops, wrap the indices modulo the array length.

Achieving Constant Speed: Arc-Length Parameterization

One major pitfall with spline evaluation is that incrementing t at a constant rate does not produce constant physical speed. When control points are far apart, the entity speeds up; when they are close, it slows down.

To make an entity travel at a steady velocity v:

  1. Pre-sample the Curve: Subdivide the spline into tiny linear segments (e.g., sample 50–100 points along each segment) and compute the Euclidean distances between them.
  2. Build an Arc-Length Lookup Table: Store pairs of (distance, t).
  3. Advance by Distance: In your update loop, increase the entity's traveled distance by speed * delta_time, then binary search the lookup table to retrieve the exact t value corresponding to that distance.

Alternative Methods Worth Considering

  • Chaikin's Algorithm: A corner-cutting subdivision technique. It is extremely fast and easy to compute, but it smoothens corners by rounding inwards rather than crossing the exact points.
  • B-Splines: Great for very smooth curves (C2 continuity), but like standard Bézier curves, they approximate rather than interpolate the control points.
  • Steering Behaviors (Reynolds' Path Following): Instead of locking the entity's coordinates directly to a mathematical equation, use kinematic forces. Calculate a target point along the curve slightly ahead of the entity and apply steering acceleration. This works particularly well if you want enemies to dynamically react to collisions, knockback, or varying physics forces.