Better Know An Algorithm: Marching Squares

There are a number of useful algorithms that every game programmer should be aware of and know how to code. One of my goals is to explain how these algorithms work and provide code samples. If the algorithms have a cool visualization, than I’ll try to provide one of those as well.

Without further ado, let’s start with our first Better Know An Algorithm (BKAA) with The Marching Squares Algorithm – THE FIGHTIN' SQUARES!

What does it do?

You’ve seen the output of this algorithm all over the place. When you use the magic wand tool in Adobe Photoshop, it produces the ‘ants marching’ perimeter of a colored area. Marching Squares gets its name from the way it works – it takes a square area of an image and marches around the perimeter of an object.

For example, if you wanted to select the first big sprite from this Tyrian sprite sheet from Lost Garden:

Example Tyrian Sprite Sheet

Example Tyrian Sprite Sheet

And produce an outline (with the sprite sheet on the top, and without on the bottom):

First Outline

Marching Squares Outline

Outline With No Sprite

Points Produced by the Marching Squares Algorithm

Pretty cool, huh? Well, maybe not yet. The application isn’t immediately obvious. You could (and I’m not saying you should) use this algorithm to do things like trace topographies in heightmaps, determine interior/exterior spaces, or route some pathfinding. So you’ve seen what it does, but…

How does it work?

The algorithm is actually very simple. Essentially, we will be running a loop where we look at 4 pixels at a time. Depending on the state of those pixels, we move in 1 of four directions. To begin, we start from the upper left pixel in the image and we progress to the right until we reach a border. Once there, we look at the state of our four pixels, and move accordingly. The diagram below shows the 16 possible states, and the resulting move they cause.

Marching States

States of Marching Squares

To see the algorithm in action, I’ve made a simple excerpt of it in this animation. The green square represents the current 4 pixels, and their state is also shown in the lower right. As you can see, in this case we are simply checking if the pixels are white or colored to determine the state of the four pixels. You could easily use transparency to run your algorithm, or any other color. You’ll see more about that in the code.

Marching Squares on Mario

Marching Squares working on Mario

I’ve reversed the direction of the algorithm in this example to demonstrate that it does work either direction. Just reverse the arrows in the diagram above to travel clockwise. Alright, enough talk, let’s code!

The Code

Let’s go ahead and create a simple class, MarchingSquare, that will do our heavy lifting. It will have one public method that takes in a texture and return a list of points that defines the perimeter, and a number of smaller worker functions.

using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;
using Systems.Collections.Generic;
 
public class MarchingSquare
{
  // A simple enumeration to represent the direction we
  // just moved, and the direction we will next move.
  private enum StepDirection
  {
    None,
    Up,
    Left,
    Down,
    Right
  }
 
  // Some variables to make our function
  // calls a little smaller, probably shouldn't
  // expose these to the public though.
 
  // Holds the color information for our texture
  private Color[] colorData;
 
  // Our texture
  private Texture2D texture;
 
  // The direction we previously stepped
  private StepDirection previousStep;
 
  // Our next step direction:
  private StepDirection nextStep;
 
  // Takes a texture and returns a list of pixels that
  // define the perimeter of the upper-left most
  // object in that texture, using alpha==0 to determine
  // the boundary.
  public List<Vector2> DoMarch(Texture2D target)
  {
    // Nothing to see... yet
  }
 
  // Finds the first pixel in the perimeter of the image
  private Vector2 FindStartPoint()
  {
    // Nothing to see... yet.
  }
 
  // Performs the main while loop of the algorithm
  private List<Vector2> WalkPerimeter(int startX, int startY)
  {
    // Nothing to see... yet.
  }
 
  // Determines and sets the state of the 4 pixels that
  // represent our current state, and sets our current and
  // previous directions
  private void Step(int x, int y)
  {
   // Nothing to see... yet.
  } 
 
  // Determines if a single pixel is solid (we test against
  // alpha values, you can write your own test if you want
  // to test for a different color.)
  private bool IsPixelSolid(int x, int y)
  {
    // Nothing to see... yet.
  }
}

Alright, we’ve laid some ground work, let’s look at these functions in a little more depth. Starting with the easiest of the bunch IsPixelSolid which just checks to see if a single pixel (given x and y coordinates) is solid.

// Determines if a single pixel is solid (we test against
// alpha values, you can write your own test if you want
// to test for a different color.)
private bool IsPixelSolid(int x, int y)
{
  // Make sure we don't pick a point outside our
  // image boundary!
  if (x < 0 || y < 0 ||
      x >= texture.Width || y >= texture.Height)
      return false;

  // Check the color value of the pixel
  // If it isn't 100% transparent, it is solid
  if (colorData[x + y * texture.Width].A > 0)
      return true;

  // Otherwise, it's not solid
  return false;
}

Next, let’s take care of another simple function, FindStartPoint, which is responsible for finding the coordinates of the first point on the perimeter of the sprite we are tracing. In this example, I start in the upper left and continue scanning to the right until I hit a non-empty pixel.

// Locates the perimeter of a sprite within the texture
    // starting from the upper left and moving right.
    private Vector2 FindStartPoint()
    {
      // Scan along the whole image
      for (int pixel = 0; pixel < colorData.Length; pixel++)
      {
        // If the pixel is not entirely transparent
        // we've found a start point
        if (colorData[pixel].A > 0)
          return new Vector2(pixel % texture.Width,
                  pixel / texture.Width);
      }
   
      // If we get here
      // we've scanned the whole image and found nothing.
      return Vector2.Zero;
    }

Here’s the code for Step, we’ll break it down a little.

// Determines and sets the state of the 4 pixels that
    // represent our current state, and sets our current and
    // previous directions
    private void Step(int x, int y)
    {
      // Scan our 4 pixel area
      bool upLeft = IsPixelSolid(x-1, y-1);
      bool upRight = IsPixelSolid(x, y-1);
      bool downLeft = IsPixelSolid(x-1, y);
      bool downRight = IsPixelSolid(x, y);
   
      // Store our previous step
      previousStep = nextStep;
   
      // Determine which state we are in
      int state = 0;
   
      if (upLeft)
         state |= 1;
      if (upRight)
         state |= 2;
      if (downLeft)
         state |= 4;
      if (downRight)
         state |= 8;
   
      // State now contains a number between 0 and 15
      // representing our state.
      // In binary, it looks like 0000-1111 (in binary)
   
      // An example. Let's say the top two pixels are filled,
      // and the bottom two are empty.
      // Stepping through the if statements above with a state
      // of 0b0000 initially produces:
      // Upper Left == true ==>  0b0001
      // Upper Right == true ==> 0b0011
      // The others are false, so 0b0011 is our state
      // (That's 3 in decimal.)
   
      // Looking at the chart above, we see that state
      // corresponds to a move right, so in our switch statement
      // below, we add a case for 3, and assign Right as the
      // direction of the next step. We repeat this process
      // for all 16 states.
   
      // So we can use a switch statement to determine our
      // next direction based on
      switch (state )
      {
        case 1: nextStep = StepDirection.Up; break;
        case 2: nextStep = StepDirection.Right; break;
        case 3: nextStep = StepDirection.Right; break;
        case 4: nextStep = StepDirection.Left; break;
        case 5: nextStep = StepDirection.Up; break;
        case 6:
          if (previousStep== StepDirection.Up)
          {
            nextStep = StepDirection.Left;
          }
          else
          {
            nextStep = StepDirection.Right;
          }
          break;
        case 7: nextStep = StepDirection.Right; break;
        case 8: nextStep = StepDirection.Down; break;
        case 9:
          if (previousStep== StepDirection.Right)
          {
            nextStep = StepDirection.Up;
          }
          else
          {
            nextStep = StepDirection.Down;
          }
          break;
        case 10: nextStep = StepDirection.Down; break;
        case 11: nextStep = StepDirection.Down; break;
        case 12: nextStep = StepDirection.Left; break;
        case 13: nextStep = StepDirection.Up; break;
        case 14: nextStep = StepDirection.Left; break;
        default:
          nextStep = StepDirection.None;
          break;
        }
    }

Now, the astute among you will notice that there are two states that don’t follow a simple pattern. States 6 and 9, the two diagonal states (0110 and 1001 respectively, also the middle two states in the far right column in the image above) have a small quirk. If you always travel a single direction when you encounter these states you will occasionally get caught in a loop. Here’s an example:

Marching Squares on Mario

Marching Squares Problem

Look at the two red squares, let’s say we were tracing along from the left when we encountered them. The diagram above would have us travel up into the hollowed out center area, which is probably what we want to do. So we travel up, then follow along the perimeter of the interior blank area until we hit the two red squares again. The algorithm says to go up, so we go up again, back into the center area. If we don’t account for this, we’ll get stuck in a loop forever tracing the interior shape. So we just watch where we came from. If we came from the left, we go up, otherwise we go down. Problem solved.

Now that we can actually take single steps, WalkPerimeter simply takes a starting point and keeps taking steps until we’ve walked the entire perimeter. Take note, this method requires initX and initY to be a point on the perimeter of the object we are tracing, or else it will never return.

public List<Vector2> WalkPerimeter(int startX, int startY)
    {
      // Do some sanity checking, so we aren't
      // walking outside the image
      if (startX< 0)
        startX= 0;
      if (startX> texture.Width)
        startX= texture.Width;
      if (startY< 0)
        startY= 0;
      if (startY> texture.Height)
        startY= texture.Height;
     
      // Set up our return list
      List<Vector2> pointList = new List<Vector2>();
     
      // Our current x and y positions, initialized
      // to the init values passed in
      int x = startX;
      int y = startY;
     
      // The main while loop, continues stepping until
      // we return to our initial points
      do
      {
        // Evaluate our state, and set up our next direction
        Step(x, y);
     
        // If our current point is within our image
        // add it to the list of points
        if (x >= 0 &&
            x < texture.Width &&
            y >= 0 &&
            y < texture.Height)
          pointList.Add(new Vector2(x, y));
     
        switch (nextStep)
        {
          case StepDirection.Up:    y--; break;
          case StepDirection.Left:  x--; break;
          case StepDirection.Down:  y++; break;
          case StepDirection.Right: x++; break;
          default:
            break;
        }
      } while (x != startX|| y != initY);
     
      return pointList;
    }

Finally, we just have DoMarch, our public facing method responsible for putting everything together.

// Takes a texture and returns a list of pixels that
    // define the perimeter of the upper-left most
    // object in that texture, using alpha==0 to determine
    // the boundary.
    public static List<Vector2> DoMarch(Texture2D target)
    {
      texture = target;
      // Create an array large enough to hold our texture data
      colorData = new Color[texture.Height * texture.Width];
   
      // Get our color information out of the texture and
      // into our traversable array
      texture.GetData
  (colorData);
   
      // Find the start points
      Vector2 perimeterStart = FindStartPoint();
   
      // Return the list of points
      return WalkPerimeter((int)perimeterStart.X, (int)perimeterStart.Y);
    }

And we’re done!