Click here to Skip to main content
15,867,686 members
Articles / General Programming / Algorithms

Implementing Auto-tiling Functionality in a Tile Map Editor

Rate me:
Please Sign up or sign in to vote.
5.00/5 (19 votes)
7 Sep 2010CPOL4 min read 158.7K   41   15
This article presents an algorithm and data structures to implement auto-tiling as seen in RPG Maker, the Starcraft level editor, etc.

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.

TileMapExample.png

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.

CornerBitFlags.png

Figure 2- Corner bit flags

Using this 4-bit index, the tiles would then be sorted in the following order:

AutoTileSequence.png

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

  1. 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.
  2. 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.
  3. 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.
  4. The neighbouring tiles are replaced with new tiles corresponding to the newly computed 4-bit indices.

CornerMatch.png

Figure 4 - Corner-bit index matching

Considerations

Beyond the algorithm described above, a number of issues should be considered:

  • Edge tiles

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.

  • Tile Organisation

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.

  • Variety

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.

Animation.gif

Figure 5 - Auto-tiling animation

History

  • 3/Sep/2010 - Draft version
  • 8/Sep/2010 - Minor formatting issues and clarifications

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer (Senior)
Malta Malta
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
QuestionThank you! Pin
Ol' Smaug11-Dec-16 10:23
Ol' Smaug11-Dec-16 10:23 
QuestionElegance! Pin
Member 84964275-Sep-15 15:56
Member 84964275-Sep-15 15:56 
NewsPractical Implementation Done Pin
Kyle Stone5-Aug-14 23:53
Kyle Stone5-Aug-14 23:53 
Hi!

Found this article incredibly useful. We use this article in the games programming class that I give.
Here you can see the practical implementation:

http://stonium.co.za/smoothing/[^]


It helps sometimes to be able to do something practically before trying to implement it.

Info about the implementation:

http://stonium.co.za/2014/02/25/map-editor/[^]
GeneralRe: Practical Implementation Done Pin
Colin Vella6-Aug-14 1:52
Colin Vella6-Aug-14 1:52 
QuestionMore than 2 terrain types? Pin
c_takov5-Sep-13 15:11
c_takov5-Sep-13 15:11 
AnswerRe: More than 2 terrain types? Pin
Colin Vella6-Sep-13 8:34
Colin Vella6-Sep-13 8:34 
GeneralRe: More than 2 terrain types? Pin
c_takov6-Sep-13 21:26
c_takov6-Sep-13 21:26 
GeneralRe: More than 2 terrain types? Pin
Colin Vella8-Sep-13 2:25
Colin Vella8-Sep-13 2:25 
GeneralRe: More than 2 terrain types? Pin
c_takov8-Sep-13 12:53
c_takov8-Sep-13 12:53 
GeneralMy vote of 5 Pin
Arthur F Souza4-Jul-12 8:15
Arthur F Souza4-Jul-12 8:15 
GeneralMy vote of 5 Pin
Manoj Kumar Choubey28-Mar-12 0:44
professionalManoj Kumar Choubey28-Mar-12 0:44 
GeneralMy vote of 5 Pin
paladin_t14-Oct-10 18:27
paladin_t14-Oct-10 18:27 
GeneralMy vote of 5 Pin
fi396828-Sep-10 22:47
fi396828-Sep-10 22:47 
GeneralMy vote of 5 Pin
catbertfromgilead7-Sep-10 1:45
catbertfromgilead7-Sep-10 1:45 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.