[Suggestion] Multi-Layered TileMap Support about godot-constraint-solving

[AlexeyBond]

Hi.

I did think about adding such feature. I can see two possible approaches to implement it:

1. Implement 3D WFC support and treat layer index as Z coordinate. That's why multi-layer tilemaps are mentioned along with 3D support in readme.
2. Implement a 2D mapper that works with multiple layers and treats each combination of tiles on different layers as a single tile. This approach is easier and may work even better in many cases.

I will implement both approaches sooner or rather later. But right now I'm busy with different feature plus some more fundamental issues of this addon.

The approach with multi-layer 2D mapper seems easy enough, so you (or anybody else) are welcome to implement it and submit a PR.

[Supamiu]

Hi @AlexeyBond, do you have more guidance on that second approach? I need something similar for my project and better not reinvent the wheel, I just need to check if this WFC implementation can handle pre-placed tiles (like place main goals in the map first, then make WFC populate the map) and then I'd be happy to give multi-layers a try if you don't have time for it.

[AlexeyBond]

@Supamiu

Hi.

That approach requires implementation of a new mapper class.

A mapper maps tiles (in format depending on specific map node type) to and from integers, which are used by the algorithm. So the algorithm works with a map node as with something like a 2D array of integers. A single-layer mapper uses only one layer e.g. tile A <=> 0, tile B <=> 1, .... In case of multi-layer mapper, it should map between combinations of tiles on different layers and numbers e.g. (tile X on layer 0, tile Y on layer 1, no tile on layer 2 and tile Z on layer 3) <=> 0, (tile X on layer 0, tile Y on layer 1, tile W on layer 2, tile U on layer 3) <=> 1, .... The numbers must start with 0, and go on sequentially, without unused numbers between used numbers.

One tile on a layer can be represented as vector of 4 integers (see _read_cell_attrs in WFCTileMapMapper2D and write_cell in same class). A single-layer mapper uses a dictionary to efficiently map a tile vector to number and a lazily-populated array for reverse mapping.
Perhaps, the most significant challenge with multi-layer mapper will be to choose the right data structure to store the mappings. Arrays of vectors as a key in dictionary may be an acceptable solution here, but that wouldn't be perfect - since an array will be allocated on each cell read. And I'm not sure if array can be a key in dictionary.

If the multi-layer mapper will not be significantly less efficient than a single-layer one, then a single layer mapper can be replaced with multi-layer one.

Not sure, how helpful was that. Feel free to ask any more specific questions.

like place main goals in the map first, then make WFC populate the map

That should work fine. However, tiles of main goals should be present in positive sample map to allow the algoritm to generate their neighbours correctly. And that means that the generator will be able to place more such tiles in different places. If it's not desired, then some additional customization of constraints will be necessary. That isn't yet fully supported in master version of the addon, but there is some work-in-progress (but mostly completed) functionality for that in another branch.

[Supamiu]

I was thinking of two different approaches for storing, dunno which one is best yet, still trying to get a proper understanding of how mapper_2d works 😄.

These approaches are:

• Make _read_cell_attrs return an Array[Vector4i] and take one more arg that's layers: int, to indicate the # of layers it should scan, then store these as usual in the disctionary (and yes, anything can be a key in GDScript's Disctionnaries)
• Create a model that's called LayeredCellInfo that contains x: int, y: int, tiles: Array[int], alts: Array[int] but I'm not sure how alts are used at all so I'm not very comfortable with this level of changes (even thi this would be a different mapper anyways).

So atm I'm trying to implement the first one and I'll try to benchmark it to see how it goes 😄

[AlexeyBond]

Multi layered tilemap support (using a multi-layer mapper) is added in #4.
3D WFC is not yet implemented but I think it's still ok to close this issue.