Refactor Terrain Tile Matching Algorithm for Accuracy and Determinism

Describe the project you are working on

2D game with a procedurally generated tile-based world.

Describe the problem or limitation you are having in your project

Godot 4's terrain tiles represented a large step forward from 3.x in terms of flexibility and power. However, it shipped with an algorithm that isn't built to handle the complexity of the underlying system. This has resulted in a high failure rate when selecting tiles (choosing tiles that don't match) as well as choosing tiles that might match but may be unwanted or unexpected. In this proposal, I'm defining the first situation as a lack of accuracy and the second as a lack of determinism.

While these errors can be fixed in the editor, they are a prohibitive limitation for user-facing situations. Due to this, it has been stated that terrain tiles are not meant to be used for procedural generation. This represents a significant regression from Godot 3.x's autotiles.

And it is not just procedural generation that is affected. Any need to place terrain tiles during gameplay is compromised by this limitation, from building roads in a strategy game, to tilling soil in a farming game, to building walls in a base-builder, or dynamically destroying terrain tiles in a mining game. As far as that last example, a game like Dome Keeper, which was made in Godot 3, would not currently be possible using Godot 4 terrains due to the lack of accuracy (as well as the regression in ability to merge autotiles).

There are multiple open issues regarding this, including: https://github.com/godotengine/godot/issues/64300, https://github.com/godotengine/godot/issues/76493, https://github.com/godotengine/godot/issues/70218, https://github.com/godotengine/godot/issues/73903. There have also been discussions in multiple other proposals about ways to fix it, including https://github.com/godotengine/godot-proposals/issues/5575, https://github.com/godotengine/godot-proposals/issues/6415, https://github.com/godotengine/godot-proposals/discussions/5425.

Describe the feature / enhancement and how it helps to overcome the problem or limitation

Implementing a terrain tile matching algorithm with increased accuracy and determinism would allow use of terrain tiles in user-facing situations.

There are two main situations the algorithm faces when it needs to select a tile.

(1) Surrounding tiles are already placed. As long as a tile exists that matches all the bits of the surrounding tiles, this is a quick and easy task for the algorithm.

(2) Surrounding tiles are not already placed. In this case, you know the terrain (or center bit) of the tiles in the adjacent cells, but you don't know what their peering bits are.

If you only have two possible terrains and there is a full set of transition tiles to choose from (an autotile with no missing tiles), this is relatively simple problem to solve. This is, for the most part, the problem that Godot 3's autotiling algorithm solves. And the code referenced in https://github.com/godotengine/godot/issues/80635 demonstrates that when you are guaranteed to have no missing tiles, you can solve it extremely efficiently.

However, when there are multiple possible peering terrains that could be used to transition between these tile terrains, this problem becomes what I believe is considered NP-Hard.

I have found that in order to consistently solve this situation with accuracy and determinism, you need a global solver with a large scope, sorted update order, deterministic peering terrain selection and the ability to backtrack. The current Godot 4 algorithm has a high failure rate because it is a local solver with a small scope, a linear update order, it only deterministically matches peering terrains that are the same as the tile terrain, and it cannot backtrack.

Note: For anyone reading this who is not familiar with how terrain tiles match to each other, see the Understanding how terrains work section from https://github.com/godotengine/godot-docs/pull/7789.

Describe how your proposal will work, with code, pseudo-code, mock-ups, and/or diagrams

I have successfully implemented the solver described above in a GDScript plugin (Terrain Autotiler - github repo). This plugin also integrates feature regressions from Godot 3.x (full 256 Wang tile matching, ignore bits, merging terrains), but in order not to distract from the main feature proposal here, I'll discuss those separately in a comment below.

This solver, as implemented by Terrain Autotiler, can fix all the issues referenced in the above section (examples here). I would love to offer it as an engine contribution, but I am not experienced in C++ and, given that this is already a complex part of the codebase, I think it would be best done by someone with more familiarity.

So, instead, I wanted to provide a general roadmap to creating a solver like this, and open a general discussion about it. I am happy to go into more detail and provide code samples for any of these points.

Here are the things it has to do:

Deterministic peering terrain selection.

This is the core of Terrain Autotiler's ability to deterministically match tiles.

It does this by scoring all the possible peering terrains that can transition between up to 4 different terrains (the greatest number that can influence a single peering bit). It does this at the time it loads terrain tiles into memory, so the result is cached for speed.

It first prioritizes the "primary" peering terrains, or the peering terrains that match any of the tile terrains. Then the "secondary" peering terrains, which don't match the tile terrains, but which are used as peering terrains for all the tile terrains. Inside the "primary" and "secondary" categories, it ranks each possible peering terrain by their order in the terrain set, with a lower index having a higher priority. It does not rank any peering terrain that cannot match to all the tile terrains.

In Terrain Autotiler, it uses a base value of 10000 for primary and 1000 for secondary, and then subtract's the terrain index from that number. (These are large numbers chosen to prevent overlap because Terrain Autotiler uses a multiplier of 10 due to Alternative Terrains.)

Due to the possibility of incomplete autotiles, this does not guarantee a solution. But this does prevent choosing peering terrains that are guaranteed to have no solution. It also ensures that cells are making the same decisions in choosing tiles regardless of time or space.

Here are some examples using the following tiles, with 4 terrains arranged with the indexes Water (0), Grass (1), Dirt (2), Sand (3).

transition_examples_tileset

(1) Dirt cells adjacent to each other.

Dirt (2) <-> Dirt (2)
    Dirt (2) - 9980
    Water (0) - 1000
    Grass (1) - 990

(2) Grass adjacent to Dirt.

Dirt (2) <-> Grass (1)
    Grass (1) - 9990
    Water (0) - 1000

In this case, there are no tiles with Grass as the tile's terrain that have peering bits assigned to Dirt. This means that, even though Dirt is a primary peering terrain, it will never be chosen, regardless of which tile is updated first.

(3) Water adjacent to Dirt.

Water (0) <-> Dirt (2)
    Water (0) - 10000

There is only one possibility here, so any time that Dirt is adjacent to Water, it will only choose Water as its peering terrain.

(4) Add Grass in an adjacent cell, and the result is the same:

Water (0) <-> Grass (1) <-> Dirt (2)
    Water (0) - 10000

(5) Sand adjacent to Dirt.

Sand (3) <-> Dirt (2)
    Water (0) - 1000
    Grass (1) - 990

Because there are no tiles with Sand as the tile's terrain and Dirt as a peering bit, or vice versa, neither of the primary terrains will work here. So they are not considered as possibilities.

Water and Grass are both possible, however. Water is ranked higher because it is listed first in the terrain set. This is a deterministic choice that is under the user's control. If a user prefers Grass to be used, they can move it above Water in the terrain set.

(6) Sand adjacent to Dirt (with Grass above Water in the terrain set).

Large update scope.

In order to fix errors and deterministically update neighbors, you need to be able to freely update a tile's neighbors. In order to do that, you need to be able to change cells 2 tiles away from a specific update.

Godot 4 currently can only change half of its immediately adjacent tiles. The peering terrains not adjacent to the update are fixed. This causes persistent errors, particularly in Corners mode, and the inability to solve problems like the bridge problem in the comment on https://github.com/godotengine/godot-proposals/issues/5575#issuecomment-1278885451.

In addition, sometimes you will run into a problem that requires changing a cell an arbitrary number of cells away. This generally occurs when painting three adjacent terrains that don't have a tile that can transition all three. But it can also happen in cases of incomplete autotiles.

Backtracking can solve this. Because backtracking is slow, and the tile that needs to be changed is not guaranteed to even be within the scope of the current update, Terrain Autotiler switches to updating the entire layer (or a 64x64 tile area, whichever is smaller) when it realizes that it cannot solve the problem with a single level of backtracking.

Here is an example using Terrain Autotiler:

third_terrain_01

And here is how Godot currently solves the same problem:

third_terrain_01_godot

Terrain Autotiler's outcome doesn't necessarily look better, even if it is the technically accurate solution. You might prefer a single non-matching tile to such a large change. However, opting out of handling this situation is also a decision, and results in handling it inconsistently based on which tile you happen to update first. And, if you de-prioritize finding an accurate solution in this case, you compromise your ability to handle other situations accurately.

Here is a similar situation where the same solution is more likely the desired outcome:

third_terrain_02

For Terrain Autotiler, I preferred the solution with the most accurate and consistent results. I consider it a matter of user education. If a user knows that this will happen when painting adjacent terrains that don't have a single tile that matches them all, then they can take measures avoid it.

A different solution to this specific problem may be preferred for Godot 4, but it needs to be addressed intentionally in order to have deterministic results.

Sorting.

Sorting is expensive, but it is less expensive than backtracking, so Terrain Autotiler uses it to a limited extent when it identifies complex situations (3+ terrains influencing a single bit, or incomplete autotiles).

In many constraint solvers, you want to update the most constrained item first. In this case, however, that actually does not mean updating the cell with the most neighbor tiles already chosen, or the fewest possible tiles that will fit into its constraints. Even if a cell only has 2 possible tiles to choose from, that's a 50% chance it will choose poorly if doesn't have the information needed to make a good decision.

In this case, it means updating the cell with with the hardest decision to make, and the best ability to make that decision. This means the cell with the greatest number of unique top peering terrains needed to transition to its neighbors (3 or more). And, among those cells, the cell with the greatest number of tiles it can choose from.

Once this cell has chosen a tile, some of its neighbors may now fit into a more complex category than they did before, so it then checks its neighbors and updates them next if they also now have 3+ top peering terrains.

Handling non-matching tiles.

When Terrain Autotiler encounters a situation where there are no matching tiles for a cell, it first checks to see if there is any possibility of a matching tile by mocking removal of all adjacent tiles that are reasonable to remove. This does not guarantee a solution, but instead guarantees that if there is still no tile, that there is no solution.

If there is a possible solution, it will try backtracking, and then expanding the update size if necessary.

If this fails, or if there was no possible solution, it puts that cell in a list to match last, after all the other tiles have been matched. We know that whatever tile it chooses for this cell will not be a good choice, and we do not need that bad choice to propagate to its neighbors.

It chooses non-matching tiles similar to how Godot does, by scoring them and choosing the highest score. However, instead of iterating over all the possible tiles in the terrain set, it iterates only the tiles for that have that tile terrain.

There is one special case here: matching to empty.

I don't believe there are any open issues regarding this, but Godot's non-determinism in matching to empty is a common complaint on social media.

For example, looking at the tileset above, there are no tiles that have empty peering terrains. This is a common scenario, and means that all tiles painted on an empty background will be non-matching.

Godot chooses tiles like this:

It selects the Water terrain since it is first in the terrain set, and reordering the terrains yields different results. However, no matter how you order the terrains, the result will be inconsistent.

You could argue that this is fair since there are no matching tiles. These edge tiles should probably be off-screen anyways. But the problem comes in when the extra terrain (Water) propagates to surrounding tiles. For example, Grass and Sand won't transition to each other, even though the tiles exist to do so, because Water is already there:

In order to match terrains to empty in a deterministic way when a terrain doesn't have empty peering bits defined, Terrain Autotiler pretends that the empty tiles are the same terrain as the tile's terrain. This yields consistent results that are generally in line with what users expect to happen.

The algorithm.

Once you have all the requirements above in place, you have a number of algorithms to choose from. The choice will be based on performance and code complexity.

I've tried a number. To be honest, a Wave Function Collapse-type algorithm was my favorite. It updated 'collapsed' cells (with only one possible tile) first, then found the most constrained cell, updated it, then checked for more collapsed cells. It was satisfying and highly accurate, but was also an order of magnitude slower than the current algorithm.

In general, the more cautious the algorithm, the slower it is. And you actually don't need to be that cautious. For most cells, you can accurately "guess" the correct one on the first try. And you can tell ahead of time when you won't be able to, and be more cautious with sorting, lookaheads and backtracking in those cases. This is what Terrain Autotiler's current algorithm does.

It updates in this order:

static cells that have only one good tile choice that can be determined ahead of time; these are then locked so they can't be changed later in case of backtracking.
- empty cells
- single-tile terrains (like water in the above tileset)
- tiles surrounded only by the same tile terrain
complex cells that require lookaheads and potential for backtracking
- cells with 3 or more unique top peering terrains
- incomplete autotiles
simple cells - complete autotiles, only 2 terrains to consider
non-matching cells

Performance.

Despite being in GDScript -- and having a heavy reliance on objects, which are known to be slow in GDScript -- Terrain Autotiler ranges from slightly slower to up to 6x faster than Godot for executing the same updates (examples here). I believe this is probably because Godot has a brute force algorithm that iterates all tiles in the terrain set for every cell, while Terrain Autotiler uses lookups and narrow search scopes. Godot's performance seems to scale linearly with the update size, while Terrain Autotiler's performance depends on complexity of the update as well.

For example, drawing a large rectangle of the same terrain can cause Godot to freeze for several seconds on a fast computer. However, due to the update's simplicity, it does not require intensive logic in Terrain Autotiler, so it is executed quickly despite the size.

For lookups, Terrain Autotiler uses a nested dictionary, organized with one bit per level, that is created at the time the terrain tiles are loaded into memory. I tried using a flat dictionary with unique keys, but the process of converting the terrain bit values to keys made it slower than this nested approach. This is not the slowest part of the algorithm, but it is a rate-limiting step, and there may be a more efficient lookup strategy available in C++.

If this enhancement will not be used often, can it be worked around with a few lines of script?

Traditionally, many developers have created custom tile-matching algorithms for their games, but they are usually a lot more intensive than a few lines of code. They require both time investment and programming experience. Having a built-in autotiling system in Godot has been a big draw for indie developers.

Is there a reason why this should be core and not an add-on in the asset library?

Terrain Autotiler, on which this proposal is derived, is already available as a plugin. And another plugin, Better Terrain, which originated from a different proposal (https://github.com/godotengine/godot-proposals/issues/5575), has proven to be very popular among Godot 4 users.

However, the terrain tile system is already a core feature that is simply not working as designed. Integrating a fix in the main engine would benefit more users and provide a smoother and faster experience than using a plugin.

Additional Features

First, there are two fortuitous built-in consequences of having deterministic peering terrain selection.

First, it is possible to merge autotiles (related: https://github.com/godotengine/godot-proposals/discussions/6157) out of the box just by using a shared peering terrain, no scripting needed. Terrain Autotiler also allows users to select primary peering terrains but this is mostly for convenience. If you are careful with the terrain order in the terrain set (since secondary peering terrains are chosen by terrain order), merging autotiles is possible without it. So I wouldn't necessarily recommend implementing user selection of primary peering terrains in Godot unless someone finds another use case for them.

Second, the order a user paints terrains doesn't matter. This, in turn, means that you can have a button or function to refresh a whole layer, similar to Godot 3.x. And you can implement a scripting function to place multiple terrains at once, which is a nice convenience as well as being faster in cases like procedural generation.

The following are additional features that I implemented in Terrain Autotiler. They could be integrated in a refactored algorithm in Godot 4 from the beginning (often an easier task) or added later on, so I'd like to encourage discussion about them.

Full 256-tile matching. Related: https://github.com/godotengine/godot/issues/71829, https://github.com/godotengine/godot/pull/72030

In Terrain Autotiler, the logic surrounding cell neighbors is determined by lookups in a hard-coded dictionary, so implementing this was simply a matter of a few extra lines in that dictionary. The open PR that implements this mode with Godot's current algorithm required more edits due to the runtime cell neighbor generation. It wasn't working well when I tested it, but it is not clear to me whether that is due to a problem in the PR or just a reflection of the other issues with Godot's algorithm.

The full 256-tile sets have never been particularly popular, but I know a number of users have had good results with reduced sets using ignore bits in Godot 3. Anecdotally, I know at least a few users of Terrain Autotiler came so they could do the same in Godot 4.

Alternative Terrains or Ignore Terrains. Related: https://github.com/godotengine/godot-proposals/issues/4689, https://github.com/godotengine/godot-proposals/discussions/4896.

In Terrain Autotiler, I originally implemented Ignore Terrains to replace ignore bits from Godot 3.x. They worked well. However, Godot 3.x autotiles only match self vs other, and it seemed that having bits that could match an arbitrary number of terrains (any terrain, or a list of specific terrains), would be a better fit for the terrains system in Godot 4. So that's what Alternative Terrains are. Their functionality is similar to Alternative Tiles (hence the name), but they work in situations that would require creating a prohibitively large number of Alternative Tiles to cover all the possible combinations.

This is a powerful feature. And I think it's a good fit for Godot 4, in particular because they can be used to prevent the combinatorial explosion of tiles needed for multi-terrain transitions or in a full 256-tiles mode (if that is implemented).

However, they were a pain to implement deterministically. They require significantly more logic up front (in the cached peering terrain lists), as well as more logic when you're scoring tiles. Since I've already come up with deterministic algorithms for them in GDScript, they may be easier to port to C++ than they were to initially implement. There may be some other ways to simplify them as well. But the increased code complexity is something to keep in mind.

(Of note, in my experience, ignore terrains, which match any terrain, did not require much less logic than alternative terrains.)

Locked Cells. Because Terrain Autotiler can have such a wide update scope, it also allows users to "lock" cells to prevent specific terrain tiles from being updated. This is most often used to preserve painting in Path mode.

Very interesting read, I am quite happy I am not the only one who got though how difficult it is to design an efficient terrain / auto-tiling system. It's super complex with tons of tradeoffs as you discovered too.

When I have some time, I'll go though the plugin code and try to understand a bit more what are the exact trade-offs we would do with it.

From what I understand, there are two:

updates modify the whole TileMap, which might impact performances on local updates
users complained before that painting a given tiles sometimes modified tiles far away, so actually, I think the "full consistency" all the time might be a problem.

I think that, if we need some sort of "global update" button, then I wonder if we should not go the LDtk route, and allow users to simply paint, like, terrain IDs on the map instead.

@groud, thanks so much for taking a look at this. I really appreciate your time! And, yes, I'm glad I didn't make this algorithm look easy because it definitely isn't simple.

Terrain tiles appear deceptively straightforward. I think the complexity is related, at least in part, to the combinatorial explosion of tiles needed for multi-terrain transitions that users would need for truly complete tilesets. If you have all those extra tiles, choosing tiles is still an easy problem for the algorithm. Godot currently handles tilesets that have all the possible transitions with no problems.

But almost no one has all those tiles. And expecting users to have all the transitions is an unfair burden. So it's on the algorithm to come up with solutions. And that leads to the major sticking point you pointed out -- how far should it look for solutions? At what performance cost? And is there a way to determine when a solution is desired and when a user would just prefer a non-matching tile?

Expanded updates that involve the entire layer appear to be needed only when 3+ terrains meet and no single tile exists that can transition between them. Theoretically, it might also occur with incomplete autotiles, but I haven't yet found any incomplete autotiles that can't find a solution within a 2-tile radius.

Here are a few videos to better clarify the situation for everyone.

Situation A: This is a normal update. The cell logging overlay at the end of the video shows all the cells that were recalculated in the last update performed. For context, when you paint with the pencil tool in Terrain Autotiler, it creates a new update every time the mouse enters a new tile, but the update area encompasses all the tiles from mouse-down to mouse-up.

As you can see, it considers changing a lot of tiles (2 levels of neighbors), but it only changes 2-3 tiles each time a new cell is painted. This is because, thanks to the deterministic peering terrain selection, it makes exactly the same decisions about what tile belongs in the other cells as the earlier updates when they were originally placed. If a user had painted in Path mode or placed a terrain tile individually that wasn't Terrain Autotiler's best choice, it would update those, so the user would need to use the lock tool to prevent them from being updated. Terrain Autotiler doesn't recalculate probabilities for tiles that aren't changed, so this large update area is generally invisible to users.

https://github.com/godotengine/godot-proposals/assets/68911895/edafe673-46b1-4416-b80d-07b9b7cc1fbf

Situation B: Here is an update that gets expanded to the entire layer (ignore the "0 tiles updated" in the debugger -- that is an obvious lie.)

https://github.com/godotengine/godot-proposals/assets/68911895/4be7c6f6-bdde-48ac-96c5-4752bc9575e8

Situation C: And here are two more very similar updates, solved with the same logic as above. They did not require expansion because the solution existed within the original update area. Because of the sorted update order, these updates happen routinely without requiring backtracking, so they don't throw any errors or warnings. This means that the current algorithm has no way to know if either of them are not the desired solution. The only thing unusual about them, as far as the algorithm is concerned, is that the cells that touch 3-terrains have to be updated first, and it has to check if their neighbors also now touch 3 terrains and need to be updated early, too.

https://github.com/godotengine/godot-proposals/assets/68911895/36cb5248-a14d-4c7e-9c2c-77e63f2c95de

https://github.com/godotengine/godot-proposals/assets/68911895/f9b324a0-fde6-4847-910a-f661ef102bf5

Like you mentioned, there's a few ways it could be handled:

(1) Expand the update area. The current solution in Terrain Autotiler, which prioritizes accuracy and determinism at all costs. I haven't received complaints about this, but I also haven't had that many users yet. And I personally do find it annoying in situations like (B) above.

(2) Don't expand the update area. This would mean that tiles will be chosen differently in Situations B and C, sacrificing determinism and accuracy.

(3) Let the user decide. (3a) Don't expand the update but have a button/script function available to recalculate the layer, or (3b) have a setting to toggle expanded updates on/off.

(4) Don't attempt to solve this problem. Instead, when 3 terrains meet and there is no single tile that matches them all, place a non-matching tile and move on. This would be more deterministic than 2, but would break solving situations where the solution is the desired outcome.

(5) Expand the update area, but only when solving the 3-terrain problem is the desired solution. I haven't been able to come up with reliable criteria to determine when it's desired and not, but maybe something will come out of this discussion?

(6) @groud's suggestion re:painting terrain IDs. I'm not actually familiar with LDtk, but if I'm understanding right, the user would paint terrains but the tile choice wouldn't be calculated in real time?

Terrain Autotiler has an update button, so you can do that by painting in the regular editor and then clicking the button. Would it be something like this?

single_update

This discussion gave me an idea. I have a number of tilesets set up to test edge cases (Terrain Autotiler would not have been possible without GUT). I can put them together into an MRP here along along with a dev branch of Terrain Autotiler with 2 new buttons: toggle on/off expanded updates, toggle on/off placing non-matching tiles for 3+-terrain transitions (when no matching 3-terrain tile exists). Then anyone who wants to could test the options, get a feel for how they'd work in actual use, and discuss them.

Yeah, I think you got the grasp of it.

The main issue I often got reported is that, when you don't have the full 256 combinations for some terrains, the algorithm often cannot find the tile it would like to put. And this is an acceptable thing, we should not require users to always have the full combinations of tiles.

This causes a lot of issues, as, when the algorithm gets lost and does not find the right tile to use, this messes things up for the next update, and thus makes the editor hard to use. That's why user complained some weird things were happening far away from what they were editing when I use an approach like yours, updating more things than the ones local to the painted area.

Ultimately, I think that the approach LDtk uses is likely the best one, yes.

I'm not actually familiar with LDtk, but if I'm understanding right, the user would paint terrains but the tile choice wouldn't be calculated in real time?

Basically, you paint on the TileMap the terrains you want to use, like, you register 0 for "water", 1 for "dirt", etc... instead of storing the tiles ID. This means that, even if you picked a wrong tile because none fit, then you can at least know what the user wanted in the given cell. You can then either display the calculated tiles, or the basic color you selected for your terrain. Then users could choose the logic when a tile cannot be found (maybe flipping another tile automatically ? that kind of thing). Eventually, we could introduce custom rules, so that some terrains could connect to different ones and so on.

This would solve most issues with the terrain painting tool IMO.

However it requires a significant amount of work, as it would maybe mean that we would have to store a special kind of data in the TileMap.

@groud That's interesting! I hadn't realized you were thinking of going that direction. I know you could do some manual rules-based matching in Godot 3 by overriding _is_tile_bound(), but I would have assumed rules matching would be too prohibitively slow to add to the terrains system. That would be really cool if it works out.

I'm not sure that you'd need to store the terrain indexes in the tilemap separately, though. Since those PR's for center bits at the end of the beta, I haven't seen Godot change the tile terrain for any cell (until a user specifically paints a new terrain over it). (And Terrain Autotiler won't place a tile that doesn't have the same center bit as the previous tile.) Is that something you're still seeing happen?

I edited the text for Situation A to explain a little more about how the wide update area works. I'm not sure that it would necessarily be a cause for complaints in this situation as long as there was an option to lock tiles. I think the earlier complaints about the wider updates were coming from users who were seeing the terrains/center bits of their tiles changed, right?

but I would have assumed rules matching would be too prohibitively slow to add to the terrains system. That would be really cool if it works out.

I mean, rules would be local to each tile, so it would be pretty fast to compute.

I'm not sure that you'd need to store the terrain indexes in the tilemap separately, though. Since those PR's for center bits at the end of the beta, I haven't seen Godot change the tile terrain for any cell (until a user specifically paints a new terrain over it). (And Terrain Autotiler won't place a tile that doesn't have the same center bit as the previous tile.) Is that something you're still seeing happen?

Yeah, my main concern is whether or not the center bit will be enough for all use cases. Maybe it will, since LDtk does not seem to have more granularity than the center bit, but maybe we need something more granular, with the possibility to define "peering bits" directly on the map.

I edited the text for Situation A to explain a little more about how the wide update area works. I'm not sure that it would necessarily be a cause for complaints in this situation as long as there was an option to lock tiles. I think the earlier complaints about the wider updates were coming from users who were seeing the terrains/center bits of their tiles changed, right?

Yeah that's true, that's a bit the issue with "super consistent" behaviors. It's a bit like your example in your original post. In case you have 3 terrains type (earth, water and ground), and have no direct transition between earth and ground, you might sometimes have to change some center bits to keep things consistent. If we just display the terrains users would like to have, we can at least tell them that no tile fitting their requirement exists. (and then either the algorithm selects a wrong tile or display an error)

Is there any plans on working on this proposal?

The addon that fixed many outlined issues is discontinued now, so we don't have any alternatives: https://github.com/dandeliondino/terrain-autotiler

Is there any plans on working on this proposal?

The addon that fixed many outlined issues is discontinued now, so we don't have any alternatives: https://github.com/dandeliondino/terrain-autotiler

You can still use Better Terrain. But a working solution in Godot itself would be also my favorite way

https://github.com/Portponky/better-terrain

I thought that Better Terrain and Terrain Autotiler worked in tandem, and not a replacement for each other.

Autotiler was supposed to be just drag-n-drop replacement of the autotiling algorithm and noting else, while Better Terrain brings new features.

I thought that Better Terrain and Terrain Autotiler worked in tandem, and not a replacement for each other.

Autotiler was supposed to be just drag-n-drop replacement of the autotiling algorithm and noting else, while Better Terrain brings new features.

I do not know your terrain autotiler plugin. But as far as I know better-terrain is its own solution for auto tiling in Godot. It also might bring new features but is also a replacement for Godots AutoTiling. So maybe give it a try.

I thought that Better Terrain and Terrain Autotiler worked in tandem, and not a replacement for each other.

Autotiler was supposed to be just drag-n-drop replacement of the autotiling algorithm and noting else, while Better Terrain brings new features.

Can confirm, I've been using better-terrain and it fixes tile placement order and no longer randomly gives me tiles that do not match the tiling settings.

I do not know your terrain autotiler plugin

It's not mine, it was made by @dandeliondino , the original poster of this very discussion we are in.

I do not know your terrain autotiler plugin

It's not mine, it was made by @dandeliondino , the original poster of this very discussion we are in.

Sorry for the late reply. I haven't had as much time lately.

Terrain Autotiler was created to prototype a more accurate tile matching algorithm. It does work, but I don't think it makes sense to continue to maintain it as a plugin. It's much slower in GDScript, and will break every time the UI gets a minor update. I think it makes much more sense to fix the core engine algorithm. I'm not a C++ programmer, so I'm not able to port it myself.

Better Terrain is a completely separate plugin with its own matching system, and has many more users and ongoing support.

My understanding from this discussion is that the Godot maintainers are only pursuing an update to the algorithm that can generate missing tiles the user can't provide. Terrain Autotiler can't do this. While it can rearrange tiles to compensate for missing tiles up to a point, it strictly respects the terrain that the user painted, so there will still be situations where there are errors when the user paints terrains next to each other on the TileMap but hasn't provided a TileSet terrain tile that can match those terrains. This is what the follow-up discussion was talking about here.

Given the combinatorial explosion of transition tiles required when you have 3 or more terrains, the user currently has to provide hundreds of tiles if they want to paint terrains next to each other in any possible combination. This is an inherent limitation to supporting multiple terrains.

I respect the decision of the Godot team here, but, from my perspective, the requirement to have an algorithm to fill in these holes feels a bit like sacrificing the good for the perfect. I don't think anyone's opened a proposal for a generative algorithm yet, but it will be a lot more work and require its own UI. The current generative tile algorithms out there are pretty neat but only work with tiles laid out in very specific ways and with specific art styles. Generative AI will probably be able to do it for a broader range of styles but that comes with its own complications.

A generative algorithm will also still require a more accurate matching algorithm on its backend so it knows when it needs to create a new tile. The current algorithm is not accurate enough to support this, and does not actually have a way to recognize when there is an error state due to missing tiles.

Terrain Autotiler is able to identify this error state accurately, so it would be able to support adding a generative system on top of it. If Godot wanted to add a similar matching algorithm to the core engine, it could function as a stepping stone on the way to eventually adding a generative algorithm.

godotengine / godot-proposals