I am making my own tilemap procedural generation system in Python. It would be awesome if I could use the terrain transition rules from the .tmx tilemaps. I want to reproduce the behavior of the Tiled terrain brush, particularly for local neighborhood analysis as shown in the following picture.
Can someone explain the algorithm of this smart brush?
Until now, here is what I am doing:
I create a 2D matrix representing my futur tilemap. I populate it with terrain names like “ground”, "water, etc. as defined in the .tmx tileset I am using. Thus an element of this matrix is a string representing the terrain. This step is the procedural generation in itself. It works as expected.
From this 2D matrix containing terrain names, I create a new matrix of terrain ids.
On each element of this new 2D matrix, I am applying my partly working brush to replace the tiles which are transition between terrains. For the (x, y) element, I look at its corners (top-left, top-right, bottom-left and bottom-right), and I find the corresponding tile in the tileset. Thus I am only looking to the 8 closest tiles.
I won’t go into too much detail here, since for that you can just browse the source code here:
(yes, I’m afraid this is a huge function, but the logic of it is not very complicated)
As explained in the manual, a tileset can define a list of terrain types and then for each tile you can define which terrain type each of its 4 corners has. With this information, and given a list of initial tiles (the ones the user actually tries to modify), the brush works as follows:
Look at the next tile to consider and find a tile matching the desired terrain pattern in the tileset. While looking matching tiles in the tileset, a mask is used so you can for example search all tiles that have a certain terrain type in the top-left and top-right, but not caring what their terrain type is in the other corners. If there are multiple options, they are ordered by priority and from the best options it chooses by probability (see findBestTile).
If a tile was found, it is placed in the preview tile stamp and then all 4 direct neighbors are checked to see whether the terrain at their sides matches with the tile we just chose. Each neighbor that doesn’t match is added to the list of tiles to find an alternative tile for. Once these new tiles to consider are being processed at the previous step, the mask is used to force it to find tiles matching the already chosen tiles.
To make sure this does not fill the entire map with random transitions, it is important that the algorithm works towards a shortest possible solution. This is why in the first step, it takes into account the “distance” between terrain types when prioritizing matching tiles. The distance between terrain types is the number of transitions necessary to go from one terrain type to another, and this information is calculated and cached within the tileset.
Note that this algorithm is by no means perfect. A few shortcomings:
It only considers each point once. While this is good for performance, it means it can get stuck due to earlier choices even though there may have been a solution.
In the past it could go crazy when the terrain definitions were incomplete. In Tiled 1.1 this was fixed by limiting the area processed by the tool based on the maximum terrain distance.
Finding matching tiles is done using a linear search, which is slow for tilesets with lots of tiles (#1632).
I would guess though, that since you’re using it for procedural generation, that you won’t need to deal with most of the complexity, which really comes from the need to modify an existing tilemap.
