Marching Squares

The marching squares algorithm is used to approximate the shape of a 2D object. In this example, we have a variety of balls floating around the screen. The goal is to implement the marching squares algorithm to approximate the shape of each ball and create a blobby effect when the balls collide with each other.

Essentially, we want to create a grid (depending on the size of your screen). The size of each square in the grid will determine how well the shape approximation is displayed (i.e. smaller squares yield tighter approximations).

In order to draw each square, we need to consider how a ball is intersecting it. For instance, each square has 4 corners and the ball can intersect one, two, three, or all four corners. All together, 16 scenarios are possible. Each configuration can be hardcoded and each can be stored in a data structure. Depending which corners are intersected, a specific square will be displayed on the grid.

Now how do we detect when a ball has intersected a square? To answer this question, we need two things: we need to keep track of the position of each square in the grid, and we need the ball’s center (x, y) location at all times. By having these variables, we can determine the square intersection by using euclidean distances.

Key point:

If the square’s corner lies between the center and outer edge of the ball, then the corner has been intersected.

Euclidean distance can be used to find the distance between the ball’s center location and the squares center location (+ or – corner distance) to find whether or not a corner has been intersected.

d = sqrt((x2 – x1)^2 + (y2 – y1)^2)

From here, we can loop the same process for all squares in the grid and all floating balls to create the effect seen above.