search

mxgmn / WaveFunctionCollapse

Bitmap & tilemap generation from a single example with the help of ideas from quantum mechanics
Other
23.05k stars 1.23k forks source link

Return value of Propagate #70

Closed pvigier closed 2 years ago

pvigier commented 2 years ago

Hi!

Thank you for the algorithm and the code! I was translating the code to C++ and everything makes sense to me except this line:

https://github.com/mxgmn/WaveFunctionCollapse/blob/8bbf089a5882c3ae4093d4f591a1731c4c7761c9/Model.cs#L185

Why are we only interested in the number of remaining tiles for the node 0 for the return value of Propagate?

As far as I understand, as soon as the number of remaining tiles for a node (not only the node 0) reaches zero, the algorithm should fail.

I think we can do this check after each call to Ban in Propagate. Or in NextUnobservedNode and we return a special value (e.g. -2) in this case.

Best regards, Pierre

mxgmn commented 2 years ago

Hi! Because as soon as the number of remaining tiles reaches 0 in some node, it becomes 0 in all the other nodes.

Adding a check after each Ban is equivalent to this. I think my version would be slightly faster, though I haven't benchmarked this particular change.

pvigier commented 2 years ago

Thank you for the explanation!

Moonfair commented 1 year ago

Hi! Because as soon as the number of remaining tiles reaches 0 in some node, it becomes 0 in all the other nodes.

But why would that happen?

mxgmn commented 1 year ago

@Moonfair Suppose there 0 tiles available in some node. This means that all tiles are forbidden in adjacent nodes too, and so on.

Moonfair commented 1 year ago

@Moonfair Suppose there 0 tiles available in some node. This means that all tiles are forbidden in adjacent nodes too, and so on.

@mxgmn That sounds reasonable! Thank you!