Understanding Polar Grids

Introduction

At this point, if someone were to ask us for a “circle maze,” we could oblige them by making a template image of a circle and then using it as a mask to generate the corresponding maze. We’d get something like the following:

While this works, it’s not very attractive. The jagged, pixelated edges of the mask are merely approximating the circle we want and are translated one-to-one onto our grid’s rigid, rectangular cells. This arrangement of perpendicular rows and columns is called a regular or orthogonal grid, and though it has some advantages (easy to understand, easy to implement), it is a little inefficient when we try to represent non-orthogonal lines like diagonals or curves.

There happens to be a class of grid that works really well for circles, though. It’s called a polar grid, and the mazes we build with it are called theta or circle mazes. Let’s see how to use these grids to make circle mazes that look a lot like the one shown below:

Polar grids explained

Whereas the orthogonal grids we’re used to are composed of rows and columns of cells, polar grids are composed of rings of concentric circles, each divided into cells like the spokes of a wagon wheel, as shown below.

There are going to be lots of ways we could represent one of these in code, but it turns out that we can reuse our existing Grid class with just a few changes. We’ll work through them in stages, starting with what it will take to draw a polar grid.

In the beginning, we start with a few given values. These include the height of each ring (we’ll call it ring_height), and how many cells exist in the ring (or cell_count). With those, we can then define the geometry of a given cell like this:

theta = 2 * Math::PI / cell_count

inner_radius = cell.row * ring_height

outer_radius = (cell.row + 1) * ring_height

theta_ccw = cell.col * theta

theta_cw = (cell.col + 1) * theta

The theta variable describes the angular size of every cell in the ring. If a complete circle describes an angle of 2 * Math::PI radians, then we can simply divide that by the number of cells in the ring to see how many radians are covered by a single cell.

The inner_radius and outer_radius variables tell us how far the cell is from the origin, with the inner value describing the distance of the inward wall and the outer value describing the distance of the outward wall.

The last two variables are used to describe where the counterclockwise and clockwise walls of the cell are in radians. The counterclockwise wall is described by theta_ccw, which is simply the angle around the circle to that wall. Likewise, theta_cw describes the angle to the clockwise wall.

Let’s put these on a diagram and see if they make more sense. The following diagram zooms in on our polar grid, looking at one arbitrary cell whose corners are $A$ ...