on dominoes
This post is a part of a series of logs on the development of the joegame world. Look out for the other parts:
- Tiling, dominoes
- Noise, generation
- Size, google maps
- Constraints, objects
- Machines, animals
O God! I could be bounded in a nut-shell, and count myself a king of infinite space, were it not that I have bad dreams.
– Shakespeare, Hamlet, Act 2, Scene
.svg)
Figure 1: We must imagine the tiles periodic. Wikipedia.
.svg){kind=link}
In this first entry concerning the generation of the joegame world, the discussion will be about tessellation. The idea of tiling things in general is naturally connected to game development and computer graphics because it is a way of making more than the simple sum of your parts, and parts are expensive. A graphics card, in part, deals with textures. A texture in essence is simply some bulk of information that you push/upload to your GPU. Most of the time this is, to make things very simple, some image. I am desinging a field for my video game (its called joegame), how do I go about this? That is, lets say I want to cover 1024x1024 pixels with grass. I could simply push a 1024x1024 picture of grass to my GPU and call it a day, but once I start thinking about adding water, or maybe some different grass, these big pictures will start to stack up in cost for the GPU to handle or contain at a given time.
Figure 2: Lovely unmowed grass
This entire situation somewhat directly leads to the concept of tessellation. Instead of pushing over a large texture, I can push a small one, and if I can work it out such that tiling the small texture in particular ways looks seamless, looks close enough to the full image, that can be a win; I can do more with less. In many, many games, this insight is taken to its ultimate conclusion: the idea of tilemaps. One way to conceive of the "world" of a game is as some regular grid on which to place different tiles. In this, "tilesheets" become the things passed to the graphics card, which are be compact textures organized in tiles that are the same dimensions of the world. To populate the world with color and detail, one only needs to works to place tiles at certain coordinates.
tiling the plane ATTACH
Figure 3: The Tiled Map Editor
While tilemaps are efficient for the computer, they can be hard on the human. Specifically, the work around placing tiles on the grid can be tedious. Tools work the best they can to ease the pain of placing certain squares on large grids. The main issue one deals with is that some tiles are meant to be placed by each other, and some aren't. The power of tiling is fundamentally related to just how well your tiles go together. The issue of seams and connecting differing areas becomes a major task in this way of doing things. And if you are just placing tiles down, it can take a lot of time and be very error prone.
Figure 4: Some badly placed tiles
One common tool to help with placing tiles comes from certain mathematical problem around decidability. Mathematician Hao Wang proposed a construction where there is some set of tiles, each tile gives prescribes itself specific neighbors for each of its sides, and we ask "can we use these tiles to tile an entire plane"? Hao conjectured that if one could tile the plane, then it would be a "periodic" tiling. Etc etc
Figure 5: Hao's original experiment
As it were though, for video games we don't need to do the homework. All we really take from Hao is the nature of the game: tiles which assert their own edges/seams. In the Tiled map editor, this fundamental idea is utilized in "terrain sets". Given a tileset with various seams, we call "terrain" that which
Figure 6: Setting up wang tiles in Tiled
Figure 7: Seamless Wang-ed tiles in tiled
Figure 8: We must imagine the tiles periodic.