Many years ago, I came across the 20 Games Challenge. It gives a list of twenty games1 to replicate, in order of increasing complexity. To implement each game, you have to address a new set of problems with a new set of skills, which then carry forward to future games.
I really like the way this is structured. The “curriculum” provides a path, and suggests learning objectives, but leaves it to the student find the actual lessons. (Or to decide to skip over aspects.) The self-directed nature is very in line with the Recurse Center ideology, but having some structure addresses one of the hard parts of an RC-like experience: “I’m interested in this thing, but where do I even start?”
I put together Pong last spring, using the Bevy engine. But I got discouraged and distracted:
Using bevy_ecs for Replicant Space client was meant to be an alternative path to “learn game programming”, but it didn’t really fulfill that goal.
On a recent visit to New York, I paired with my Recurse batchmate Jeremy who was a little further along the 20 Games challenge–working on game 2, Breakout. We put together a collision visualizer to tune the paddle behavior.
Jeremy’s idea was to make the paddle act curved: a bounce on the center would bounce straight up, a bounce towards the edges would accentuate or negate the ball’s angle. The visualizer is a neat way to play with the dynamics and see which parameters look fun.
Working with Jeremy inspired me to pick up the challenge again. In particular, our discussions got me interested in an underlying math problem: ray-casting / shapecasting.
In principle, if the ball is travelling fast enough relative to the frame rate,
it could travel “through” a paddle/block within a frame.
For instance, if the ball’s velocity is 60 units per frame, the paddle is 30 units deep, and the ball has a radius of 10,
a naive calculation of the ball’s next position:
might send the ball to the other side of the paddle, without the ball and paddle overlapping.
One can avoid this by taking the position of the ball and obstacles throughout the current frame:
$$\vec{b}(t) = \vec{b}_{i} + \vec{v} t$$and solving if there is some \(t\) where the ball and obstacle collide.
I found some of Bevy’s builtins for this, as from this example. Bevy’s 2d libraries can cast:
and tell you where / when they collide. (“Ray” here is used in the Bevy sense: a half-line, starting at an origin and going in a direction.)
That’s all well and good… but what about a circle-to-rectangle collision, e.g. a ball to a paddle? There doesn’t appear to be a built-in for that.
As far as my partner and I were able to work out, this requires several tests. To collide a moving circle of radius \(r\) with a stationary rectangle, start with an equation representing the circle’s velocity in terms of time \(t\). Intersect that line with:
I normalized things so that \(\vec{b}_{0}\) is the ball’s position at the start of the frame, and \(0 \leq t \leq 1\) represents the duration of the frame. For edges, \(\vec{e}_{0}\) gives one corner, and \(\vec{e}_q m\) traces the edge over \(0 \leq m \leq 1\).
$$ \begin{align} \\ \vec{b}(t) &= \vec{b}_{0} + \vec{v}_{b} t \text{ (ball position)} \tag{1} \\ \vec{e}(m) &= \vec{e}_{0} + \vec{e}_{q} m \text{ (each edge)} \tag{2} \\ \vec{b}(t) - \vec{c} &\leq r \text{ (corner collision) } \tag{3} \\ \end{align} $$Equations 1 and 2 can be solved together for \(t\) and \(m\) to find an edge intersection. There will always be a solution unless the lines are exactly parallel; the solution only represents a collision if \(0 \leq m \leq 1\). (We’ll come back to \(t\) later.)
An intersection from (1) and (2) is against an “elevated” edge; it won’t necessarily detect if the ball comes in at an angle where the first point of collision is a corner. Equations 1 and 3 can also be combined and solved, and can produce zero, one, or two real solutions for (t).3
The smallest solution for \(t\) within \(0 \leq t \leq 1\) represents the first collision with this rectangle.4 (Negative \(t\) values mean the ball is headed away from the obstacle, and values greater than 1 indicate the collision will not occur during this frame.) The smallest such \(t\) value across all obstacles represents the time of the first collision overall, \(t_{c}\).
Plugging \(t\) back in to equation 1 gives the position of the ball at the time of collision. If you want to be really fancy (I do), you can then also compute the new velocity after the collision, and repeat the collision-detection with a smaller upper bound (\(t \leq 1 - t_{c}\) instead of \(t \leq 1\)) to find if a second collision occurs in the same frame.
Inspired by Jeremy’s work and the Bevy example, I decided to implement this mode of collision detection with a little vizualizer:
I wanted to understand the math behind collisions to build up my intuition, but didn’t actually want to implement a whole system for it myself, other than what was required for the visualizer.
So after prototyping the above, I pulled out Rapier and started my Breakout implementation in earnest. That’s the implementation at the top of the page; real(ish) physics!
My stumbling point in Pong had been that paddles did not collide with the edges of the screen, even when I thought I had configured them to. This time I more carefully read the docs and examples, and applied some manual event handling to “hold” the paddle within the screen area.5
I liked Jeremy’s idea of a “curved” paddle, but went for something easier to implement with Rapier: friction. If the paddle is in motion when it collides with the ball, it imparts a little horizontal velocity.6
In addition, each contact with the paddle adds a little overall velocity, making gameplay faster. I first tried treating the paddle’s added velocity as multiplicative rather than additive: having each bounce multiply the velocity by e.g. 105%. But a geometric progression meant the ball got too fast too fast!7
This was a nice little project! It was especially rewarding to get Rapier working after struggling with it previously.
Stepping back to the games challenge, and putting my Replicant Space client on pause, had me thinking more about learning goals.
I learned some about Bevy and ECS systems from my Replicant Space client; I picked up some tools like QueryData
and the bevy_tasks model that will help with other projects.
But overall I wasn’t learning much from it. Most of the effort was in the logic of automata, and figuring out how to synchronize state with the server. While the game is interesting, I don’t feel like I learned much from solving those problems.8
The 20 Games Challenge gives me a lot more control over what I’m learning. For instance, I could start “under the engine” and build my own, or with Godot or another engine; but I’ve chosen to focus on Bevy, because learning a new language or dealing with FFI is not one of my learning goals for this project. I can learn as much as I want about collision detection algorithms… or I can see, “what does a physics engine find important,” and start there.
Control over my learning goals is a great property to have in a project. Especially in an environment where there are a lot of shortcuts available – open-source libraries, free assets – it’s nice to be able to choose which ones I take, and where I take the long road.