Lately, I’ve been experimenting with music visualizers. One of my favorites is inspired by the classic arcade game Pong. In classic Pong, a ball bounces off paddles in a steady rhythm. What if we synchronize the bounces to the beat of a song, making the paddles dance? To make this possible, we alter the physics of the game so that the ball moves at a constant speed, and paddles can move anywhere on their respective halves of the screen. We also retain these rules from the classic game:
The contact point of the ball on the paddle determines its angle of reflection.
Paddles have no speed limit.
The ball bounces off the top and bottom of the screen.
These physics give us the necessary degrees of freedom to move the paddles to hit the ball at any desired times. One simple strategy to satisfy any timing requirements is to keep both paddles close to the center. This gives us little horizontal space, but vertical space is effectively infinite since the ball can bounce off the top and bottom edges of the screen. For any desired shot duration, we can slow the horizontal velocity to match it by hitting the ball more vertically. While this argument shows a solution exists for any input, it certainly isn't exciting to watch.
What Makes a Visualization Appealing?
One desirable property is the utilization of screen space; a game stuck in a small region feels cramped and underwhelming. Closely related is dynamism of movement; spectators enjoy watching players make heroic efforts to hit a ball just within reach. Unfortunately, it's difficult to write an algorithm to maximize screen usage while guaranteeing a valid game. If a paddle hits the ball far from the screen's center, the ball may not have time to cross the screen for the next beat. Any movement of the paddles must account for the potential impact on future moves. This is the crux of the problem: while respecting the beat of the song and the physics of the game, where should the paddles hit the ball on each beat to maximize screen utilization?
Constrained Optimization
Fortunately, there is a mature field dedicated to optimizing an objective (screen utilization) with respect to variables (the locations of bounces) in the presence of constraints on those variables (physics and the beats of the song). If we write our requirements as a constrained optimization problem, we can use an off-the-shelf solver to compute optimal paddle positions instead of designing an algorithm ourselves.
Formulating the task as a constrained optimization problem has several advantages. If we change the physics, we simply need to update our constraints, while an algorithm may need to be rewritten. In a similar vein, it lets us easily experiment with objectives. Developing appealing animations is an iterative process, which the declarative style of constrained optimization facilitates.
Simplifying the Problem
That sounds great, but modeling 2D constraints is hard; is our game truly two-dimensional? It turns out modeling only the horizontal component is sufficient! In our ruleset, the ball moves at a constant speed, so its vertical velocity is exactly determined by its horizontal velocity. By simulating the game, we can compute the ball's vertical position at any time. Knowing the ball's vertical position also gives us the vertical position of the paddles since it must match the ball's position to hit it (plus a small delta to achieve the desired angle). Between hits, we simply linearly interpolate positions to achieve smooth movement. Thus, we only need our solver to compute the horizontal positions and velocities at the times when the paddles hit the ball; the rest follows from the physics of the game.
Defining Parameters and Variables
Let's start by defining the hardcoded parameters of the game. Next, we have the beat times we’d like to synchronize. Each t represents the time when the ball should hit a paddle. We obtain these times from MIDI files, though in the future I’d like to explore more automated ways of extracting them from audio. We take the differences between adjacent times to get the duration the ball should travel each shot. Each d represents the time interval between two consecutive hits of the ball. These are all the fixed inputs we provide to the solver.
Now we’ll define the variables we’d like to optimize and their relationships to other quantities. Remember, we only need to optimize horizontal positions and velocities. Each p_i represents the horizontal distance of the paddle from the center when it hits the ball for the i-th time. Even indices (p_0, p_2, …) represent the left paddle, while odd indices (p_1, p_3, …) represent the right paddle. The set of ball horizontal velocities. Each v_i represents the horizontal velocity of the ball after the i-th hit. To make it easier to construct constraints, we define these to always be positive no matter if the ball is moving left or right.
First, we constrain paddles to stay on their respective halves of the screen. We defined p as the distance from the center, so it’s nonnegative no matter which side of the screen it’s on. Next, we constrain the magnitude of the ball's horizontal velocity to be positive and not exceeding its total speed S. These two constraints fully define the physics of our game. We add one final constraint to enforce beat synchronization. This ensures that the ball reaches the next paddle at the correct time. The left-hand side represents the total horizontal distance traveled (sum of distances from the center for two consecutive paddle hits), which must equal the product of the duration of the shot and the ball's horizontal velocity.
Solving the Problem
We know there is a degenerate solution in which the paddles are stuck in the center. A natural thought is to encourage the opposite; maximize the distance from the center. Our objective, then, is to maximize the sum of the paddle’s distances from the center.
With our mathematical formulation in hand, all that’s left is to solve it. All of our constraints are linear, so any linear programming (LP) solver will suffice. I chose CVXPY for its simplicity and generality. CVXPY solves convex optimization problems, of which LP problems are a subset. While we don’t require its full feature set for this task, the flexibility to support more complex objectives and constraints facilitates creative exploration.
With CVXPY, we can express the constraints enumerated above as follows. Sure enough, the code closely matches the formulas. I actually find the code easier to follow than the formulas due to the descriptive variable names. The solver returns the horizontal positions where the paddles should hit the ball as well as the horizontal velocities of the ball, from which we can easily compute the angles of reflection. This is enough to compute the vertical positions via simulation. To animate the final result, we use the positions of the ball and paddles at the time of each hit as keyframes. Between hits, we interpolate the positions to create a smooth animation.
Conclusion
Visualization is an extremely open-ended problem, and ultimately the only judges are our own eyes. More often than not, the results depend on which algorithms we know. I suspect there are many more visualizers powered by constrained optimization waiting to be discovered; I’d love to hear about them!
Remember these 3 key ideas for your startup:
Leverage Constrained Optimization: By framing problems as constrained optimization tasks, you can use existing solvers to find optimal solutions without designing algorithms from scratch. This approach is flexible and adaptable to changing requirements.
Utilize Screen Space Effectively: In any visual or interactive application, maximizing the use of available space can make the experience more engaging and dynamic. This principle can be applied to UI/UX design in your products.
Iterative Development: Developing appealing visualizations or products is an iterative process. Experiment with different objectives and constraints to find the most effective solutions. Tools like CVXPY can facilitate this creative exploration.
Edworking is the best and smartest decision for SMEs and startups to be more productive. Edworking is a FREE superapp of productivity that includes all you need for work powered by AI in the same superapp, connecting Task Management, Docs, Chat, Videocall, and File Management. Save money today by not paying for Slack, Trello, Dropbox, Zoom, and Notion.
For more details, see the original source.
