Wang Tiling

Wang tiling is a really cool concept… it’s a good way to use 2d tiled graphics in such a way that can look very organic, without discernable patterns.

The basic idea of how they work is that each tile has a type of edge. You start by placing a random tile, and then you start putting down it’s neighboring tiles. When you place a tile, the rule is you can only put down a tile that has compatible edge types (aka the tiles can go together seamlessly). Rinse and repeat and pretty soon you have tile based graphics that don’t look tiled at all.

Specifically here is a strategy I like to use for filling a grid with wang tiles:

  1. Place any random tile in the upper left corner
  2. Put a tile below it that has an edge on it’s top that is compatible with the already placed tile’s bottom edge
  3. Continue placing tiles downward until you reach the bottom of the column
  4. Now, move back to the top, move over to the next column, and now place a tile such that the left edge is compatible with the right edge of the tile it is next to.
  5. Moving down, you now have to find a tile which is compatible with both the tile above it, and the tile to the left. Since there are going to be multiple tiles that fit these constraints, just choose randomly from the ones that do.
  6. Rinse and repeat until the grid is filled

However, if you are in a situation where you need “random access” to know what tile to use at a specific grid cell (x,y) there is another option that I like a lot more.

In this situation, if you have 2 edge types for each of the 4 edges, that means that you need 4 bits to describe a specific tile (each bit says which type to use for an edge).

Because of this, you can generate four random bit values (0 or 1), using a pseudo random number generator that takes two numbers in and gives one number as output.

You would generate the random numbers for the coordinates:

  • (x,y)
  • (x+1,y)
  • (x,y+1)
  • (x+1,y+1)

And then use those bits as edge selections. The 4 bit number (0 to 15) then could tell you which tile to use.

The result is that you generate tiles which are compatible with their neighbors, and you don’t have to generate the whole wang tiled grid up to that point.

You get “random access” views into the field of wang tiles, and this is the technique I used in the shader toy demos below.

There is a lot more info out there (links at bottom of post) so I’ll leave it at that and show you some results I got with some simple tiles.

The tiles I used are very geometric, but if you have more organic looking tiles, the resulting tile grid will look a lot more organic as well.

Also, as the links at the bottom will tell you, if you have wang tiles where each axis has only 2 edge types, even though the number of permutations of tiles in that situation is 16 (XVariation^2 * YVariation^2), you can actually get away with just using 8 tiles (XVariation * YVariation * 2). In my example below I had to use all 16 though because I’m just generating edge types in a pixel shader without deeply analyzing neighboring tiles, and it would be a lot more complex to limit my generation to just the 8 tiles. If you can think of a nice way to generate a wang tile grid using only the 8 tiles though, please let me know!

The 16 wang tiles used:

A resulting grid:

Here’s a more complex set of 16 wang tiles:

And a resulting grid:

Links For More Info

ShaderToy: Wang Tiling
ShaderToy: Circuit Board

Wang Tiling Research Paper

Introduction to Wang Tiles

By the way… something really crazy about wang tiles is that apparently they can be used to do computation and they are turing complete. Seriously? Yes! Check out the link below:

Computing with Tiles

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s