Let Me Tell You About WANG TILES

Recently, at work, I had a problem for which Wang tiles were the suggested answer. I’d never had a chance to use them for something before but after seeing them in operation, I now want to use them for everything, forever. (Disclaimer: I started this article a couple of months ago and shelved it. I’m no longer quite so excited about Wang tiles but they’re pretty good)

So what are they? As their Wikipedia page says, they’re simply square, unrotatable tiles with restrictions on which edges can be placed next to one another, often represented by colours or jigsaw-piece edges. The specific sets of tiles that interested Hao Wang and other mathematicians are the ones that force a non-periodic tiling of a plane. For graphics, that’s just inconvenient so we use a set of tiles that has every permutation of edge colours and would bore a mathematician senseless.

What they’re used for is to hide a shortage of resources. When you’re designing a tiling texture, you’re in an uncomfortable place – if you add any feature that stands out the player’s eye will lock onto it and the tiling will become obvious, but if you make the texture too bland, things start to look unnaturally uniform. Here are some hills covered in silver worms:

The picture on the right is using the same size of texture, and the tiles are a quarter of the size, but they’re selected using the following procedure (based on Li-Yi Wei’s paper):
For each pixel:

  1. Multiply the texture coordinates by the tiling rate, then round down to get a unique X,Y coordinate for the current tile (save the remainder for later)
  2. Run the tile’s coordinates through a hash function to get a random-looking choice of colour for the top and left edge. Also hash the left edge of the tile to the right and the top edge of the tile below, to set the colour for the right and bottom edges (this guarantees the edges will always match between tiles).
  3. Look up the tile in the source texture that has the correct combination of edge colours.

(alternatively, steps 2 and 3 can be done ahead of time and put in a large lookup table)


Visualisation of the tiles and their edge colours

One concern about using Wang tiles is that authoring textures for them can be harder than authoring a standard tileable texture, so I decided to have a go (on the basis that if a programmer can do it, it can’t be that hard). Apologies in advance to any artists tearing their hair out at my inefficient ways of doing things.

First, I take the cracked mud texture that I’ve been using for the land previously (originally by HHH316) and place a 4×4 grid over it. This defines the scale of the features and provides unique detail for each tile.
Next, I find four different spans (two horizontal and two vertical) that are as visually unexciting as possible, each the length of a tile edge. I cut out a diamond around each and place it in a new layer, duplicated across every instance of a particular edge colour.
Over this, I place some small (1-2 pixel) dots of an identical colour at each corner. Wei describes a very involved way of fixing texture filtering across the corners of tiles, but it’s expensive. Guaranteeing that all corners are the same colour solves the problem at least for the first couple of mip levels, beyond which the texture will be looking mucky anyway.
Finally, I place the original texture over the top again, add a layer mask to it and, at a high zoom level, experimentally paint away sections with a fairly hard brush, trying to maintain a believable join. Once I’ve painted away a border around every tile, the only remaining discontinuities should be short stretches of the diagonal boundary between the diamonds that I’ve exposed near tile corners. I check them by eye and fix them with whatever works, usually painting small areas of the top layer back in over them.

It's easier to see if you colourise it a bit

It’s easier to see if you colourise it a bit

For the grass mask texture I had an additional problem – it’s created by extracting the darker lines from the mud texture and blurring them, but the blur is dozens of pixels wide and will ruin the continuity across tile edges. To fix this I just cheated, copying one tile edge for each “colour”, adding a transparency gradient across it and at each end, then pasting it back down over all the others of that “colour”. Anyway, long story short, it all works just fine:

And that's all I have to say about that

And that’s all I have to say about that


Leave a Reply