Infinite loop in OverlappingModel constructor

[ejmahler]

WaveFunctionCollapse version tested: 1cf308c (HEAD of master as of this writing)

When I run the program with a specific setting and image, I get an infinite loop on line 85 of OverlappingModel.cs in the constructor:

while (residue >= power)
{
    residue -= power;
    count++;
}

This loop appears to be doing a combination division and modulo of "residue / power". When I replace it with a division and modulo, I get a division by zero error -- IE, 'power' becomes zero.

To reproduce this bug, replace the contents of samples.xml with:

<samples>
    <overlapping name="Office4" N="5" periodic="True"/>
</samples>

And add the following png image to your 'samples' folder:

It's possible that this image is simply an invalid input for the parameters given. Maybe there can never be a valid output for this image when N = 5 and periodic = true. If this is the case, I would expect an exception, or maybe an early return with some "invalid state" flag set, or some sort of detectable/recoverable error. If it is a valid input, then obviously I expect a valid constructed object.

[tomprogrammer]

The problem is, that an overflow occurs in the calculation of the index, which is of type int. In your case of 3 distinct colors and a pattern size of 5 the maximum index is 3^(5*5) which can't be represented by the int type.

Reference: OverlapplingModel.cs:51

[mxgmn]

Yes, the issue is in the integer overflow. A fast fix is to make index long integer, a better one is to abolish indices altogether, I'll update the code.

[mxgmn]

A "better" way turned out to be not that good, so I just made indices long.

@ejmahler Here are the results generated from your sample: N=5, N=4 and two N=3 with a dot trick from rid5x to make rooms bigger:

[mxgmn]

@ejmahler Btw, what other interesting samples have you discovered?

[Asmageddon]

Personally I'm really curious what this would look on things that aren't patterns. For example, the pepe: https://www.quickhoney.com/image/pepe_ani_1

It'd probably do well with some color reduction, and the additional-color trick to prevent it from "looping"

[mxgmn]

@Asmageddon Pepe:

[tomprogrammer]

@mxgmn What is the dot tick?

[mxgmn]

@tomprogrammer Placing dots in spacious areas of the input to make corresponding areas of the output bigger. See the attached results, I placed little gray dots in white rooms in your Office sample.

[tomprogrammer]

Ah, interesting. Thanks for the explanation!

[Asmageddon]

@mxgmn Haha that's funky. Have you thought about fixing edges, or doing histogram matching to ensure one distribution or another?

[mxgmn]

@Asmageddon Sure. This repo contains the very basic version of WFC, one could also tune it, add other heuristics for specific needs.

[ejmahler]

@mxgmn I'm especially interested in the office building layouts. Similar to the dot trick, I've been lining the border of rooms with a distinct color if I want to enforce a maximum size which is larger than N.

And similar to using a color to mark doorways (Probably unnecessary tbh) I've been using a color to mark hallway entrances. If you look at the dot trick outputs, there are lots of giant rooms that snake back and forth, specifically marking corners fixes that.

BTW do you have any guidance for where to start if I want to introduce some constraints into the OverlappingModel algorithm? There are gif examples of constraints, but it's not obvious where to start to actually use them.

[mxgmn]

@ejmahler Or placing dots in walls or in corners, yes.

About constraints, let me copy part of the conversation from another place:

"To start with constraints look how foundation (now ground) param is handled.

Foundation is a special case of constraint. I use it in examples like Flowers, City, Platformer to make the ground level be at the bottom of the output. If you delete the foundation param from samples.xml, you'll see that ground appears anywhere in the middle of an output, not necessary at the bottom. So in Clear() setting foundation consists of 2 steps: setting the bottom line to be of foundation patterns, and then forbidding foundation patterns anywhere else. If you comment the second part, you'll see that it produces cities or platformer levels with several ground levels.

General constraints work the same way. Even simpler way, actually. First, you need to make some true values in the wave false. And then call propagation cycle while(Propagate());. Just be careful not to make contradictive constraints. The easiest constraint looks like this:

for (int t = 0; t < T; t++) wave[5][6][t] = (t == 9); while(Propagate());

T is the total number of elementary options (tiles or patterns, depending on the model)."

Let me know if you have any trouble with constraints. I think I will record a video with interactive constraining in the overlapping model in a week or two.