How Minkowski Played Flappy Bird

Introduction

Many people have tried playing Flappy Bird. Rarely does anyone manage to fly past 50 pipes, and very few reach a hundred or two. Some have tried building a bot. Surprisingly, even the most successful bot doesn't produce very impressive results — something around 160 points. A question arises: is it even possible to play Flappy Bird infinitely long? Or is there always some probability, however small, that a sequence of obstacles will appear that even an experienced player or a perfect bot cannot overcome?

This is where mathematics comes to the rescue. Let's find a winning strategy for Flappy Bird.

The Model

Let's describe a mathematical model of the game. Our playing field is a plane. There is a bird — a square with sides of length w, parallel to the coordinate axes. There are obstacles — pipes — vertical strips of width w_tube with horizontal gaps of height h_gap. The horizontal distance between two adjacent obstacles is fixed and equals Δ_tube. The position of the horizontal gap for each pipe is random (uniformly distributed within some range). Additionally, there is a floor — a horizontal line f. The floor is also an obstacle.

The bird's horizontal speed is constant and equals v_x. Gravity also acts on the bird, giving it a vertical acceleration g. Initially, the bird's vertical speed equals 0. At any moment, the player can tap — that is, set the bird's vertical speed to v_jump. Moreover, some semblance of air resistance acts on the bird — its vertical speed is bounded below by a constant v_fall. In practice, this means that after each tap the bird moves along a parabola that at some point transitions into a straight line. We will call the trajectory the bird follows after a tap a fallabola (a falling parabola).

The game ends when the bird touches an obstacle. The player's goal is to maximize the distance traveled.

Before moving on to the actual strategy, let's perform a trick. Analyzing intersections of a square bird with obstacles isn't very convenient. But it turns out we can easily switch to an equivalent model where the bird is a point. To do this, we "deflate" the bird to the size of a point (the center of the original square) while simultaneously "inflating" the obstacles. In this case, the original square intersects with obstacles if and only if the new point-bird lies within an inflated obstacle.

Scientifically, the result of "inflating" obstacles is called the Minkowski sum.

The Minkowski Sum

Wikipedia tells us: "The Minkowski sum of two subsets A and B of a linear space V is the set C consisting of all possible sums of vectors from A and B: C = {c | c = a + b, a ∈ A, b ∈ B}."

From an everyday perspective, the Minkowski sum of figures A and B is the figure obtained by attaching figure A to every point of B.

The Inverse Fallabola

Let's solve an auxiliary problem: where must the bird be located so that after a tap it flies through a given point A? More precisely, we need to find the geometric locus of points such that fallabolas drawn from them pass through a fixed point A.

Let v be an arbitrary vector connecting the beginning of a fallabola with one of its points. It is easy to see that after a tap at the point A − v, the bird will fly through point A. That is, A − v belongs to the desired geometric locus. Moreover, by taking all possible vectors v, we obtain all the desired points. But what is the set of points of the form A − v, where v is the radius vector to one of the points of a fallabola? It is a path that is centrally symmetric to the fallabola after reflection about point A.

We can generalize the problem: where must the bird tap to fly through a given region S? Based on everything above, the answer is the Minkowski sum of the region S and the inverse fallabola.

Upper Obstacles

Let's finally move to the main problem — finding a winning strategy. But first, let's solve it in a simplified case. Suppose the model has no lower halves of pipes and no floor. That is, we only have the upper parts of obstacles. Consider a standalone upper half of a pipe. Suppose the bird began its path somewhere far to the left of this obstacle. Assume that at some moment the bird crashed into the pipe. As we know from the previous section, this means a tap was performed in the region obtained by adding the inverse fallabola to the obstacle. Let's color this resulting region blue.

Note that if the player tapped at any point within the blue region, the corresponding fallabola first intersects the obstacle and only then leaves the blue region. In other words, the player will be forced to either lose or tap again within the blue region. And since any individual blue region is bounded on the right, it is impossible to fly within it indefinitely, and eventually the bird will die. Thus, a tap in the blue region always leads to defeat. Moreover, taps outside the blue region cannot lead to losing — without a tap in the blue region, you cannot crash into an upper obstacle, and there is nothing else to prevent the bird from flying.

As a result, for the case of only upper obstacles, we get the following statement:

Statement. If the bird began its flight outside the union of blue regions, then infinite winning strategies exist. All winning strategies are described as follows: outside the blue regions, the player can make arbitrary decisions; in the blue regions, the player must not tap.

Lower Obstacles

Now consider the case where only the lower halves of pipes are present in the model. That is, there are no upper halves and no floor. Again, consider a standalone lower obstacle. Draw a ray through its upper-left corner (point A) — ray AC — with an angle of inclination equal to atan(v_jump / v_x), that is, a ray directed along the bird's velocity at the moment immediately after a tap. Suppose the bird ends up below ray AC. Then regardless of the player's actions, it cannot rise with a vertical speed greater than v_jump. Combined with the constant horizontal speed v_x, this inevitably leads to a collision with the obstacle, i.e., a loss. Let's color the lower obstacle and the area below ray AC red.

It follows that under any winning strategy, the bird must not enter red regions. Moreover, if the bird is outside a red region at some moment in time, it can remain outside indefinitely. Indeed, as it approaches the boundary of the red region, the player can always start tapping frequently enough to avoid entering it.

Let's add the floor. It is easy to see that the floor can be treated as yet another red region in the shape of a lower half-plane.

Thus, if only lower obstacles and the floor are present, the following holds:

Statement. If the bird at the initial moment is outside the union of red regions, then infinite winning strategies exist. All winning strategies can be formulated as follows: outside the red region, the player can make any decisions; when approaching the red region, the player must tap.

All Obstacles Together

Consider the general situation. Suppose there are upper halves of pipes, lower halves, and a floor. The following is quite clear:

Statement. If the union of blue regions does not intersect with the union of red regions, and the bird initially is outside the blue and red regions, then winning strategies exist. Any winning strategy is described as follows: outside the blue and red regions, one can make any decisions; in the blue regions, one must not tap; when approaching the red regions, one must tap.

The absence of intersections between blue and red regions is essential for such a strategy to exist. Indeed, it may happen that a bird flying through a blue region closely approaches the boundary of a red region — in this case, if the player taps, they lose; if they don't tap, they also lose.

The question arises: do blue and red regions intersect in the actual game? It turns out that sometimes they do. And this happens in exactly one case: when there is a sufficiently large downward elevation change between the gaps of two adjacent pipes.

Let us analyze this situation. Suppose the bird managed to fly through these pipes. This means that at some moment it crossed the segment AB. But that means a tap was performed in the region between the inverse fallabolas drawn from points A and B. At the same time, this tap could not have been performed in either the blue or the red region. The only remaining area is the region shown in yellow in the figure.

That is, for a winning strategy to exist, we must be able to guarantee entering the yellow region. After that, all we need to do is tap, and the dangerous section will be overcome. To understand whether we can always reach the yellow region, we add the inverse fallabola to it — obtaining a region (shown in green in the figure) that is sufficient to reach in order to get to the yellow region in one tap.

Notice that if at some moment a tap is performed at a point lying above line Γ, we will no longer be able to reach the yellow region. Conversely, for any point below this boundary, we can always, by tapping enough times in succession, rise into the green region, then with one more tap reach the yellow region and, accordingly, overcome the obstacle. In other words, points lying above line Γ should, in our terminology, be colored blue. In fact, most of them are already blue, with the exception of the curvilinear triangle XYZ. Let's color XYZ blue as well. Now, to formulate the winning strategy, it remains to add the phrase: if the bird finds itself in the yellow region, it must tap at least once before leaving that region.

Note that coloring the additional triangle blue could not have added any intersections of red and blue regions, and therefore did not affect the analysis of the game's passability as a whole.

In summary, for the general case we get:

Statement. Suppose the bird at the initial moment is outside the blue and red regions. Then infinite winning strategies exist. All such strategies can be described as follows: outside the blue and red regions, one can tap at any moment; in the blue regions, one must not tap; when approaching the red regions, one must tap; upon entering the yellow region, one must tap at least once before leaving it.

Interestingly, a strategy of the form "start flying above some line and tap whenever the bird drops to that line" (for example, the upper boundary of the red regions shifted slightly upward would be a logical choice for such a line) is apparently not a winning strategy for any line.

Practice

All of this is well and good, but we would like some practical results. Hardware bots have already been featured on Habr, so we decided to make a software one. Quite by chance, we had at hand the code of our clone called Tappinator, whose physical model is quite close to the original game — we tried hard and measured carefully. Our bird is circular, though (it might be circular in Flappy Bird too, but the difference is small, and explaining with a square is simpler), and there are additional obstacles — diagonal ones. Here is how obstacles are "inflated" for a circular bird:

As a result, our blue and red regions look like this:

As for the yellow regions, they also arise for standard pipes, but additionally appear in the case of diagonal obstacles oriented from bottom to top (with their own curvilinear blue triangles and everything).

In the video, you can see 50 birds successfully reaching 1000 points, what the various colored regions look like from the bot's perspective, and what the game would look like if 1000 birds were flying simultaneously. In the uncolored areas, the bots behave randomly: each one has its own fixed probability of deciding to jump at each moment. You may notice that from the bot's perspective, the colored regions are somewhat larger than they are from the mathematical standpoint. This is because the bot can only make decisions 60 times per second, and the physical model is also updated discretely.

Conclusion

And so it turns out that even in a game as simple as Flappy Bird, there is room to develop a substantial mathematical theory. In reality, the most interesting part only begins from this point. Next comes the question of how to handle obstacles of arbitrary shape — here one has to introduce concepts such as the purple shadow, the maroon boundary, the right-linearly-connected region, right-linearly-connected closure, and so on. It is also interesting to determine what reaction time a human must have (that is, what the allowable timing error per tap should be) in order to play infinitely. Incidentally, this is an extremely non-trivial question, the rigorous answer to which remains unknown to us to this day.