Better Know An Algorithm 1: 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):

Marching Squares Outline

Marching Squares Outline

Points Produced by the Marching Squares Algorithm

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.

States of Marching Squares

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 working 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
  // 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
  // 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
  // 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 Problem

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
  // 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. The complete file can be downloaded from my code dump. (Right-click, save as.)

If you enjoyed reading this, or found it useful, please leave a comment so I know to keep doing these. In the next installment, I’ll be tackling the Douglas Peucker Algorithm to turn the output of what we just generated into a simplified polygon for use in a physics engine.

Category: Better Know An Algorithm, Design and Data Structures | Tags: , , , , , , , 9 comments »

9 Responses to “Better Know An Algorithm 1: Marching Squares”

  1. Cloud Bright

    I do not believe I’ve seen this described that way before. You actually have made this so much clearer for me. Thanks!

  2. Morto

    Hi,
    thank you for the article. I want to try to use the March S. code and combine it in a sort of graphical editor that would create bounding outlines for physic demos (in Farseer).
    Anyway – very helpful

  3. Max Loh

    I would like to personally thank you for this very well-written, easy to follow article about marching squares. It helped me finish my task for work with ease.

  4. massadop

    Thanks. It has been very useful and easy to follow.
    Looking forward the Douglas Peucker Algorithm

  5. Phill Spiess

    @Morto: I’m working on the post showing off the Douglas Peucker Algorithm that will do exactly that! Should be up shortly!

  6. Deram Scholzara

    Thank you so much for writing this up! It’s the most this algorithm has ever made sense to me, however I’m having some trouble with one aspect of it.

    I’m a little confused on this part – wouldn’t this algorithm produce a set of points that overlaps the perimeter of the up-left edges of the shape, but is offset down-right for the down-right edges of the shape?

    I’m assuming this would be the case because you are adding the current pixel to pointList, which is always the down-right pixel of the current step’s 4 pixels.

    Am I missing something?

  7. Rajiv

    This is basic explanation but nice. Here you are working to move for points. Never told anything how is it useful in surface mapping means can we draw any surface represented by a mathematical equation and trace it from square.

  8. Justin

    Thanks for the article. Great Stuff!

  9. Andrea Portale

    Great read. Algorithms are shown in a pretty cryptic way most of the time, making it moderately hard for inexperienced programmers to get what those do in an enjoyable fashion.

    I’m pretty sure these will be of great help to lots of people! Keep hem coming ;)


Leave a Reply



 

Back to top