What are grid colorings?

A grid coloring is a way to assign a color to each cell in a grid. Here we will only talk about periodic colorings – colorings that use repeating patterns. From the 30 games in our last project, 12 use grid colorings. We used to support only a few patterns, each individually coded. But we recently discovered a way to handle all repeating patterns; in this post I give some examples of what colorings can be used for, and give an overview of the method we use to color our grids.

What are colorings used for?

Aesthetics

Colorings make grids pretty. We colored almost all the grids on our site using one of these patterns, and many games use patterns to make their grids more attractive.

Visual Organization

Colorings make it easier to distinguish cells. In some games, such as chess or darts, these patterns can help make the game state easier to take in visually. In chess, it’s much easier to work out knight moves when you know a knight on black must always move to white.

(Image sourcce: http://www.chessvariants.org/hexagonal.dir/hexagonal.html)

Algorithms

Grid colorings are the basis of many interesting grid algorithms. The coloring algorithm does not return actual colors, but indices that we can use to access an array of colors that we can assign to cells in a grid if that is the goal. But the index also relays some structural information about a cell that can be exploited in algorithms to compute things that have nothing to do with colors. Let me give some examples.

Prim’s maze generation algorithm. This, and many other maze generation algorithms, work on edges. One way of implementing the algorithm is to represent edges and faces in the same grid, as we have done in this example with hex grids, and Game 6 for rect grids. You can use a coloring to decide which cells represent walls and which cells represent faces.

 

Here, yellow corresponds with definite openings; the other colors correspond with walls (that may be opened by the maze generation algorithm). The color also shows the orientation of the “edge”, for example, all red cells denote vertical edges.

Triangular grids. A single grid can be used to represent vertices and faces simultaneously. We can use this to assign coordinates to triangular grids that make them much easier to work with (we are investigating this as an alternative for our existing triangular grids, and I will write more on this topic later). In this case, the coloring tells you which cells correspond to faces, and which ones with vertices. It also tells you which cells have up triangles, and which ones have down triangles.

(You can use single grids to represent other combinations of faces, edges and vertices too; and again a coloring helps you decide which cells are which type).

Procedural content. In many games, these colors can help you generate interesting levels or puzzles. The game that inspired Grids uses colorings to generate many of the game’s puzzles.

Proving that puzzles have solutions. In some puzzle games, colorings can help you prove whether a given solution is solvable or not. For instance, our Game 10 is a simplified version of a packing problem, where the goal is to pack the entire grid with dominoes. There is a simple method using a checkerboard coloring to decide whether a given puzzle is solvable. This makes it easier to generate puzzles for these types of games. Here are a few examples of color arguments.

Sampling. Colorings are useful for low-res grid traversal, or sampling a grid evenly. This is the basis of many procedural algorithms: for instance, you could place elements at points of a regular sample offset by a random amount, giving you a fairly even distribution that is still somewhat unpredictable. Because colorings exist for any number of colors, you can also control the fraction precisely. If you want 20% of your world to be occupied by monsters, you simply use a 5-coloring.

Wrapped Grids. Grid colorings can be used for making look-up tables to wrap grids in non-standard ways. For example, a hex-grid can be wrapped as shown below:

(The interactive example on this page makes it a bit clearer how this wrapping works.) The method is to

• create a hexagon-shaped grid with the desired size,
• calculate the coloring index (for a suitable coloring) for each cell in this grid, and
• set the value at this index in an array to the associated point.

To find out how any point is wrapped, simply look up its coloring, and then the corresponding point in the array.

Implementing Colorings

Implementing a given pattern is relatively straightforward if you use an appropriate coordinate system for your grid. However, the general solution is not so straight-forward (we thought). Not because the problem itself is difficult, but because it is difficult to decide what input the user should give to the algorithm. And for a long time we did not have a solution.

(The microscopic explanation on Wikipedia is not clear, and does not seem so useful for game algorithms. It also deals with a narrower set of patterns than described here.)

The solution, when we found it, seems very obvious now. It follows from noting that any repeating pattern will always repeat in a parallelogram.

We can parameterize any such pattern by two non-parallel sides of the parallelogram. For the same pattern, more than one parallelogram is possible; any of these will do as long as we make sure that the color in the four corners is not inside the parallelogram, or intersects one of the sides anywhere other than at one of the corners. In the images below, the two parallelograms give the same coloring.

 

The maximum number of colors is given by the area of the parallelogram, which is always an integer, and moreover, given by the perp-dot product of the two sides $latex u$ and $latex v$:

$latex N = u_xv_y – u_yv_x$

To calculate the color, you simply translate the point to a canonical position, and note its offset from the origin. (The canonical parallelogram is easily indexed if the one side is parallel to the x-axis). The details are slightly messy, but it is similar to taking the remainder when doing division – only now in two dimensions.

It is easy to see what patterns are possible with any number of colors: it depends on the factorization of the number of colors.

Consider for example colorings with 6 colors.

We can factor 6 as 6 x 1, and 3 x 2 (we leave out 1 x 6 and 2 x 3, which we can obtain by flipping X and Y coordinates). This means two different parallelograms are possible (with additional constraints that one side must be parallel to the x-axis, and the other vector must have both coordinates positive). In the first case, there are 6 possibilities for this vector; in the second case, there are 3. This means, in total there are 6 + 3 = 9 possibilities.

  

  

  

We can find more colorings by considering the 1 x 6 and 2 x 3 parallelograms, but some of them duplicate the colorings above. One that does not is shown below. In general, it’s slightly tricky to calculate the exact number of unique patterns for a given number of colors.

This method works exactly the same for all uniform (hex and rect) grids. What is different on different grids is how neighbors relate to each other (so patterns look different visually, and have different “meanings” algorithmically).

Spliced grids (such as triangular, rhombille, and Cairo pentagon grids) are all based on uniform grids, where each cell is spliced into more cells. Each splice has an index; the coordinate is made from the coordinate of the cell in the base grid, plus this index. Coloring these grids combine the coloring in the base grid with the index. For instance, to get the Cairo 12-coloring below, we used a 3-coloring of the base (c), and combined it with the index (i) using the following:

$latex 4c + i$

 

(These algorithms will be available in Grids 1.7 🙂 )