Introduction
This article presents a simple algorithm and supporting data structures for implementing auto transitioning tiles in applications such as tile-based level editors like RPG Maker and the Starcraft level editor. When this functionality is implemented in a tile map editor, it significantly speeds up content generation and ensures consistent tile usage.
Background
Tile-based graphics (Figure 1) have been the hallmark of 2D games since the early days of video game development and serve as a means of presenting large 2D environment by reusing a relatively limited set of graphical blocks or tiles. The resulting graphics tend to be blocky and repetitive in nature. However, a skilful graphic artist can mitigate these problems through judicious design that aims to break such patterns.
Figure 1 - A sample tile map
One such technique entails the use of transition tiles, such as the grass-water and grass-dirt boundaries in the illustration above. However, manual and proper placement of these transitory tiles tends to be a tedious process. A sophisticated tile map editor allows the user to mark such tiles, enabling the editor application to automatically blend in a newly placed tile (for example, water) by placing the correct transitory tiles around it (such as the water-edge in Figure 1).
Auto-Tile Organisation
Most auto-tile sets consist of 14 tiles, that is, the interior and exterior tiles (full grass and full water tile, for example), top, bottom, left and right edges, four outer corners and four inner corners. The algorithm described here requires a further two tiles for a total of 16.
This algorithm considers a tile (transitory or otherwise) as consisting of four quadrants. Each of these quadrants or corners can belong to one side (grass) or the other (water), with the corresponding boundary lying within the tile. All the corner possibilities give rise to 2 x 2 x 2 x 2 = 16 possible tile combinations.
These 16 combinations can be indexed by composing a 4-bit binary number b3 b2 b1 b0 where each bit b i corresponds to a corner type. As a convention, the bits are mapped in order of increasing significance to the top-left, top-right, bottom-left and bottom-right corners respectively as per Figure 2.
Figure 2- Corner bit flags
Using this 4-bit index, the tiles would then be sorted in the following order:
Figure 3 - Auto-tiles ordered by 4-bit index
The process can also be reversed such that it is possible to determine the corner types from a given 4-bit index. This gives a means to implement auto-tiling as described in the next section. For the sake of simplicity, it is assumed that the map consists of only the 16 tiles above and that they can be directly referenced using the 4-bit corner index.
Auto-Tiling Algorithm
- When a new tile is placed in the map, the four corner bits are extracted from the 4-bit index of the tile and its 8 neighbours.
- For each of the four tiles (left, right, above, below) sharing an edge with the new tile, new 4-bit indices are constructed by reusing the 2 bits from the new tile closest to the shared edge, and the 2 bits in the neighbouring tile furthest from the edge. The new 4-bit indices effectively result in transitory tiles that blend correctly with the new tile.
- Similarly, for each of the four remaining neighbours (top-left, top-right, bottom-left, bottom-right) sharing a corner with the new tile, 4-bit indices are constructing using the bit from the new tile closest to the shared corner, and the 3 bits furthers from the shared corner in the neighbouring tile. These new 4-bit indices likewise result in four corner neighbours that blend correctly with the new tile.
- The neighbouring tiles are replaced with new tiles corresponding to the newly computed 4-bit indices.
Figure 4 - Corner-bit index matching
Considerations
Beyond the algorithm described above, a number of issues should be considered:
Care must be taken when handling tiles at the edge or corner of a map as these will have less than the usual 8 neighbouring tiles.
The algorithm above assumes that 4-bit indices correspond directly to tile indices. However, the auto-tile set may not necessarily start at index 0, nor be contiguous or in the order prescribed in Figure 3. To solve this issue, a two-way mapping must be maintained between arbitrary tile indices and 4-bit corner indices.
Despite the use of smoothly transitioning tiles, an observer can still be alienated by repeated patterns of the same tiles as can be seen in Figure 1. The algorithm can be improved by mapping each 4-bit index to more than one tile variant and have the algorithm select variants at random for the newly placed tile and for its neighbours.
Implementation
This article is of a theoretical nature and does not include sample source code. However, the reader is invited to study an implementation of this auto-tiling algorithm within the open-source tile map editor tIDE at http://tide.codeplex.com.
Figure 5 - Auto-tiling animation
History
- 3/Sep/2010 - Draft version
- 8/Sep/2010 - Minor formatting issues and clarifications
