There is a trick commonly used to draw terrain in RPG games, walls in maze games, islands and continents in world-map type games, and much more. It’s a type of auto-tiling known as Wang 2-corner tiles, and until recently, the best explanation on the internet was found here. But that website is now dead, alas.
You can still view it on the Wayback Machine here, but perhaps it’s time for a fresh explanation. This blog post is meant to be that — a quick, concise explanation of this simple yet brilliant idea.
Wang Tilesets
Wang tiles were dreamt up by a mathematician named Hao Wang in the 1960s. The basic idea of is this: make tiles that match their neighbors, either on the edges (edge-matching Wang tiles) or on their corners (corner-matching Wang tiles). You need only a limited set of such tiles; if each corner has two possible variations — for example, each corner is either “land” or “water” — and 4 corners, then the minimum number of tiles is 2^4, or 16 tiles.
In computer games, corner-matching Wang tiles seem to be more common. If there are 2 possible types for each corner, this is known as a Wang 2-corner tileset. If there are 3 (for example: water, sand, and jungle), then you need 3^4 = 81 different tiles, which is considerably more work to make. For this reason, 2-corner tilesets are the most common of all.
Selecting the Right Tile
We can assign each of the 16 tiles in a 2-corner tileset an index number from 0 to 15. Then, we can find the correct index by simply adding up a number assigned to each corner:
So here we’re giving the northeast corner a value of 1, the southeast corner a value of 2, 4 for the southwest, and 8 for the northwest. Add up the values of the corners where you want land (or whatever your tileset represents) to find the tile index.
Here are four examples of Wang 2-corner tilesets that follow this indexing scheme. (These are from the now-defunct site mentioned at the top of this article.)
Choose Your Thickness
The artist draws each tile so that the division between the two types (e.g. land/water) happens at the same location on the tile edge, so it will meet up perfectly with whatever tile is next to it. On the interior of the tile, that dividing line can wander around however the artist wants, as long as it lands at the standard spot on the other edge of the tile.
That point on the edge where the dividing line lands determines how “thick” your tiles appear. In the following examples, we have “bright” (green) and “dark” (black) corners. Let’s think of the dark corners as background, and the bright ones as foreground. If the dividing line on the edge of each tile is very close to the foreground corner, then you get thin walls, suitable for something like a Pac-Man maze. In a game, the player or enemy sprites would probably be playing mainly in the background area.
If the dividing line is right in the middle of each tile, then you have an even balance between foreground and background. You might use this if the player can move equally well on both, for example, if your two types represent rock and grass, but this is mere decoration and doesn’t affect gameplay.
If the dividing line is closer to the background corner, then you have a lot of foreground area on each tile. This makes fat, chunky foreground areas.
These examples used this Clean 2-Corner tileset. But just to show that tiles don’t need to be boring round-rects, I quickly banged out a little island tileset that looks like this (with indexes added):
The same layout as above, but using this tileset, makes nice little islands. Pirate game, anyone?
Auto-Tiling
The term “auto-tiling” has come to mean any scheme in which the player (or an algorithm) can easily paint with a tileset, and the appropriate indexes are automatically chosen, rather than the designer having to individually say “put tile 7 here, tile 13 there, and tile 5 next to that”.
Auto-tiling with Wang 2-corner tiles is easy: you only need to realize that what you are painting are the corners, not the squares. Because tiles are chosen based on the type of the four corners, what you do with the mouse is toggle the terrain type at the corners. Then the code can recalculate the tile indexes for the four tiles around each corner.
Try it! Mini Micro has a demo of this at /sys/demo/maze.ms, and you can try it online right now.
Tile Variations
If you use the bare minimum 16 tiles, and your tiles are meant to represent natural features like coastlines, grass, or rocks, then the tiling will become pretty obvious in large areas. You can break up this obvious tiling by having multiple versions for each Wang value. For example, you could have two versions of each, for 32 tiles total. Then, when selecting tiles to display based on the state of the four corners, just add a random offset (0 or 16) after calculating your index as above.
Other Types of Wang Tiles
As noted above, it’s possible to have more than just two types for each corner. 3-corner Wang tiles would come in 3^4 = 81 variations; you could even go for 4-corner Wang tiles like these, which require 4^4 = 256 different tiles.
If your game uses a hexagonal map, you can still use corner-matching Wang tiles. But in this case, 2 terrain types would mean 2^6 = 64 different hexagonal tiles. (And let’s not even think about what 3-corner or 4-corner variations would mean in this case!)
You could also consider edge-matching Wang tiles, where the two terrain types match up along the edge rather than the corner. The trouble with this is, you have no choice about where the dividing line between the two terrain types falls; it has to be right at the corner. And if you have any visible “border” around your terrain, like the sand in my island tileset above, you won’t be able to hide a visible notch at the tile corners. So, edge-matching Wang tiles are not as generally useful, but they can work in special cases.
Finally, there’s nothing that says Wang tiles have to be flat 2D images. If you’re working in a 3D environment, you can have fully modeled 3D tiles that fit neatly together, using this same Wang index calculation.
Go Forth and Wangify
Wang tiles are a brilliant invention. Now that you know what to look for, you will spot them in almost any game with editable or procedurally-generated maps. And if you’re a game developer (or would like to be one!), consider applying this technique to your own games!
