Marching Squares and Quadtrees - A Primer

In the world of computer graphics and game development, an algorithm that comes up often is Marching Squares. Quadtrees are also used often in the same fields, to optimize spatial queries. These two contents are fundamental for terrain generation, collision detection, and more.

This post focuses on understanding Marching Squares, and implementing it in JavaScript using p5.js. We’ll cover on optimizing this approach using Quadtrees in a follow up blog post.

But first, let’s build some motivation for why we need marching squares.

Motivation

Say we want to draw a mathematical function, for example, $y = sin(x)$. The most intuitive way of doing so, would be calculating the value of $y$ at each point, and connecting them with lines. Let’s take a look at this approach in the animation below:

Loading animation...

Resolution

Frequency

Show Lines

Show Axes

Show Lines

Show Axes

You can play around with the function to see how it changes with frequency and resolution. Try doing the following things:

1. Decrease the resolution all the way down and see how it gets janky.
2. Max-out the resolution, and try increasing the frequency. You’ll notice how the function gets more hilly and complex.
3. Turn down both of them, and see how the function doesn’t even look close to the actual sin function.
4. Turn off the show lines option, and play around with the resolution. Notice how the number of points to each other as the resolution increases.
5. Turn on the show axes option, and repeat the steps above.

This changing of the graph is due to the changes in how we draw the function. As the resolution increases, we calculate and draw more and more points, in the same space. This makes the function look more accurate.

The Problem

We calculate the value of $y$, as per $y = sin(x)$ at each of these points. Then, we connect them all by lines which is the graph of the function.

Let’s take a look at the code for this approach.

// The equation we are trying to draw
const equation = x => sin(x)

// How often we'll be calculating the value of y
const resolution = 100
let points = []

function setup () {
  createCanvas(400, 225)

  // Caluclate the values of x, and y
  // and store them in the points array
  for (let i = 0; i < resolution; i++) {
    let x = (width / resolution) * i
    let y = (height / 2) * sin(2 * PI * (i / resolution))
    points.push(createVector(x, y))
  }
}

function draw() {
  background(220);
  translate(0, height / 2)
  
  // D
  for (let i = 0; i < points.length - 2; i++) {
    let p1 = points[i]
    let p2 = points[i + 1]
    line(p1.x, p1.y, p2.x, p2.y)
  }
}

You can install p5.js, and try out above code, or simply use the p5.js web editor.

This approach works well to a certain extent, however it has a very serious pitfall! Can you try to guess it? Here’s a hint - try to think about a function that gives two values of $y$ for any given $x$!

The Pitfall

It turns out that this approach does not work for implicit functions. Implicit functions are those that do not have a direct mapping between $x$ and $y$. Instead, they express a relationship between $x$ and $y$ in the form of an equation.

Consider the equation of a circle: $x^2 + y^2 = r^2$ where $r$ is the radius of the circle. Let’s try to draw this circle using the same approach as above.

// The equation we are trying to draw
const equation = x => sin(x) 
const r = 5
const equation = x => sqrt(r**2 - x**2) 

// How often we'll be calculating the value of y
const resolution = 100
let points = []

function setup () {
  createCanvas(400, 225)

  // Caluclate the values of x, and y
  // and store them in the points array
  for (let i = 0; i < resolution; i++) {
    let frac = i / resolution
    let x = width * frac
    let y = equation(x)
    points.push(createVector(x, y))
  }
}

function draw() {
  background(220);
  translate(0, height / 2)
  
  // D
  for (let i = 0; i < points.length - 2; i++) {
    let p1 = points[i]
    let p2 = points[i + 1]
    line(p1.x, p1.y, p2.x, p2.y)
  }
}

Replace the equation with the one above, and try running the code. You’ll notice that it doesn’t draw a circle, but instead a weird shape.

Contouring

Marching Squares is a computer graphics algorithm used for contouring in two-dimensional scalar fields. It’s often used in terrain generation in games, where it helps create more realistic and complex landscapes.

The algorithm works by dividing the terrain into a grid of squares. Each corner of a square is assigned a value based on the height of the terrain at that point. The algorithm then determines where the contour line should pass through the square, creating a more detailed and realistic terrain.

fn main () {
  println!("Hello World")
}

Quadtrees

Quadtrees, on the other hand, are a tree data structure used in computer graphics and game development for spatial partitioning. They’re often used for collision detection, where they help determine which objects might collide without having to check every single object.

The algorithm works by dividing the space into four quadrants. Each quadrant can be further divided into four smaller quadrants, and so on. This creates a tree structure where each node represents a quadrant of space, making it easier to check for potential collisions.

# Pseudocode for Quadtrees
def quadtree(space):
    divide space into quadrants
    for each quadrant:
        if quadrant contains more than one object:
            quadtree(quadrant)

Conclusion

Marching Squares and Quadtrees are powerful tools in computer graphics and game development. Understanding these algorithms and how they work together can help you create more complex and efficient games. So, start experimenting with these algorithms and see what you can create!