[Discussion] Tile probability

[Supamiu]

After working on layered map support, I realized that it'd be better for me to use this for my game rather than trying to make my own solution, because your solver works like a charm and you seem to be very comfortable with it and keeping it up to date.

What I'm missing for my game is mostly multi-layers (which is being done in #4) and tiles probability.

This issue is mostly to open the discussion on how it could be implemented and what the solver should accomplish to be considered as working with probabilities.

The features

In order to be considered done, the solver would have to be able to read a weight from each tile in a tileset, tile by tile. Setting this info could be done using different methods, one of which being using custom property painting in the tileset editor (or even using the built-in probability property), the other being using some kind of configuration resource for more advanced cases.

A feature that's not required per se but that could be interesting would be to have conditional weights, for instance tile A having a weight of 5 next to tile B but weight of 2 next to tile C, that's a more advanced case that would probably only be solved using a custom resource or a custom ruleset (maybe tile aliases or something to help with that?)

The implementation

If we're using the built-in approach to have a basic probability system, we could simply read the tile's properties to grab probability from that, then using it to computed a weighted random when picking the tile in the solver (I'm failing to see where tho)

Using a more custom approach would require giving cells a probability using a config resource, which could be useful to handle Scene Tiles (which is something I'm doing in my game to have collectable elements placed directly as tiles so they match the grid perfectly).

Maybe we should just make it either support both approaches or just the custom one so worst case, everything can be done with it even tho it'd be worse in terms of DX

[AlexeyBond]

Some random thoughts on this matter:

I like idea of using a built-in probability property for simple tiles. For scene tiles a custom metadata seems to be the only option. But it isn't obvious, how it should work with multi-layer maps.

Also, we shouldn't forget GridMaps. It looks like custom mesh metadata is the best option there.

A feature that's not required per se but that could be interesting would be to have conditional weights, for instance tile A having a weight of 5 next to tile B but weight of 2 next to tile C

I thought about something like that. In order to implement it properly, we'd have to use floats instead of booleans almost everywhere i.e. vector of probabilities of every tile should be stored for every cell, rules s hould be stored as two NxN matrices, etc. Since now the boolean vectors are stored as bits in 64-bit integers, it will turn every bitwise integer operation with those vectors into 64 floating point operations, so performance is highly likely to be significantly decreased. And, yeah, that also requires rewriting the solver almost from scratch.

But that's for proper implementation. Perhaps, there are some shortcuts.

when picking the tile in the solver (I'm failing to see where tho)

Tile picking happens in WFCSolverState class:

• first method prepare_divergence choses what cell to "observe" (I use different terminology - "diverge", like diverging timelines in multiverse) by calling pick_divergence_cell. And then choses what tiles and in what order the solver will try to place in that cell - by filling divergence_options array.

• then either metod diverge is called to create new state with a cell being "observed" or diverge_in_place to set tile without creating new state is called by solver. In case of diverge call, the solver may "travel back in time" (backtrack) and create a new "timeline" with different tile chosen for the cell if it meets a contradiction (a cell no tiles can be assigned to) in later states.

Now prepare_divergence just randomly shuffles divergence_options array. The easiest way to introduce probabilities would be to shuffle it the way that tiles with higher probability values are more likely to appear in the beginning of array.

One of caveats is - the probability won't really always work as real probability. For example, if there is a tile X with probability of 1.0 and cell Y with probability of 0.00001, but X tile must always be surrounded with Y tiles, then in a generated map there will be at least as much Y cells as X cells, despite huge difference in probabilities. Of course, in real rule sets the relations may be way more complicated and way less obvious.

[Supamiu]

Hm I didn't think of GridMaps indeed, nor multilayer.

I feel like the best solution then would be to have a matrix of weights alongside the tileset, maybe using a dedicated layer in the sample and something like user-defined tiles that they paint on top of each tile stack they want to edit the probability?

So you'd have a tileset dedicated to weights, on which you'd have the probability attached, and then just paint weights on top of your sample, we could even provide a basic tileset for that in 3 resolutions (16x16, 32x32, 48x48) that would just be a gradient from red to purple that people can use to associate probabilities (or even provide a .tres that contains, let's say 16 tiles with each value associated with it being 1/16 higher than the previous one).

That way, all we'd have to do is have a specific layer name for the sample that would make it filtered for the output (like, probably skip this layer when scanning data for the mapper), something like WFC_Weights that would be entirely optional and just make all weights equal 1 by default.

I'm not familiar enough with gridmaps and how it'd be used in them, but I think this "named layer" approach would be the best of both "custom vs built-in prop" situation and it'd also just make it work fine no matter the amount of layers and their composition (like PackedScenes).

[AlexeyBond]

I do get the idea with special weights layer in sample map. But I dont like the idea that users will have to add special set of tiles to their tilesets just to markup probabilities in samples - it's not possible to use a totally separate tileset for one of tilemap layers, so users will have to either create their tilesets starting with special tilesets provided by the addon or create the special tiles in their own tilesets manually. Plus, it creates possible ambiguous situations: what if there are two otherwise equivallent tiles in sample tilemap that have different tiles on special layer?

I think it may be a better solution to use built-in probability values (or custom data-layer in tile set) and just multiply probability values when there are tiles on multiple tilemap layers.

Another possible appreach is to use number of tiles of given type in sample tilemap as probability of tiles of that type. But with this approach it mey become difficult to set very low probabilities for some tiles or avoid too high probabilities of some generic (e.g. ground) tiles.

[Supamiu]

Oh indeed multiplying each layer's probability, as they are 1 by default, totally makes sense !

I'd love to give this a try if you're ok with it 🙂

[AlexeyBond]

I'd love to give this a try if you're ok with it 🙂

I'm ok with that. Here are some hints on how it can be implemented:

In WFCProblem add a method like

func get_cell_divergence_options(domain: WFCBitSet) -> Array[int]:
    ...

that by default returns a shuffled array of all bits set in domain - part of what prepare_divergence does now. WFC2DProblem should override this method to account for probabilities of different cell types.

prepare_divergence will call this new method instead of just populating and shuffling array.

In WFCMapper2D a method like

func read_cell_type_probability(cell_type: int) -> float:
    return 1.0

should be added and implemented for all it's subclasses. WFCRules2D should read probabilities in learn_from method, using that new mapper method and store them in a property.

Perhaps, the most difficult part here is get_cell_divergence_options implementation with probabilities. It may also have a significant performance impact - the best algorithm I can come up with quickly is O(number_of_tile_types**2). If it will do so, it makes sense to make tile probabilities optional - perhaps, by adding an exported flag in WFCRules2D, that will let user choose between probabilistic and simple shuffling.

[AlexeyBond]

Tile probabilities implemented in version 1.3.