Per-Slot random seed

[janper]

To prevent completely different solutions when only few things change I suggest:

• passing a per-Slot random seed from C# (the value will be calculated from the absolute position of the Slot in the world as that is the value that the user can understand)
• the random seed will randomly jitter numbers from 0 to maxSupportedModules (currently 248) representing the preference of a module to be picked by an observation
• if a non-allowed or non-existent module index is chosen, then the next one in stack should be checked

[yanchith]

Any concrete reason why the user should know what the seed is? Do we want them to be able to see and change it? I have a feeling this will complicate the C interface and would avoid it unless there's clear benefit.

Also, why would you jitter the numbers from 0 to max? You can already be deciding between just the valid module choices. I'd look into composing two RNGs - one for the whole world and one for the slot.

[janper]

1. The user won't see the seed. The solver C# wrapper will. This is to fixate seeds in space because that is the expected behavior - if the Slot is at the same place and doesn't change, why would the module in it change when a minor change occured somewhere else?
2. We want to prevent a huge change in the solution triggered by a minor change of the input. Such change may be a different count of Modules entering the solution. The maximum number of Modules is fixed, therefore we may as well expect all the Modules may enter the solution at some point. This also requires fixing a position of a Module in the bitvector.

[yanchith]

Okay, let's address the question of whether C# should see the seeds, I think that one is simpler and I have a clearer idea there.

I too think that fixating things in space is the end goal, but I think we can achieve it more simply than C# knowing about the slot seeds (especially if the user doesn't ever want to set these manually). Let's zoom out and look for better solutions.

To brainstorm, I've been initially thinking that this could be achieved simply by C# providing to Rust the location of origin and Rust adhering to that and generating the seeds (possibly directly from the resolved positions of slots). If the user in C# moves or resizes the envelope, C# provides the new origin translation vector to Rust. What do you think?

Now that I think about it, I don't think it is obvious what should happen if the envelope moves in world-space, but is not resized, but for consistency, I'd say that the origin translation vector changes. This way you could get interesting results by moving the envelope around - almost like scanning the space for solutions.

---

I agree with the sentiment with 2), but I don't think we understand what's supposed to happen here yet.

The maximum number of Modules is fixed

Okay, I agree that this will be more stable, because the number of choices stays fixed.

if a non-allowed or non-existent module index is chosen, then the next one in stack should be checked

What stack? I am assuming you meant "choose an available module with the smallest index that is larger than the one currently picked". As far as non-existent modules go, I think you can just choose in the range [0,module_count_in_ruleset). This is still stable (doesn't change unless the rules change), and you won't need to care about non-existent modules.

This also requires fixing a position of a Module in the bitvector.

This is dependent on the rule data provided to Rust. The module_low and module_high fields there are precisely the positions of the bits in the bit vector. If the positions there are stable, they are also stable in the bit vector.

So, to summarize - this means that the global RNG state now only gets to pick the slot, but there is also an RNG for each slot that picks modules. The question now is, what is the lifecycle of that slot-local RNGs state? Concretely, when does it get reset/reseeded? An obvious answer would be to reset each time we call wfc_observe, but that means this breaks down immediately if you use the observation count limit, because now the slot RNGs are getting reset when you don't want them to. I guess you could pass a flag whether you want to reset the RNGs to wfc_observe, but meh.

---

Thinking about the previous point got me thinking that in Monoceros, you would want to save the state of all RNGs (or at least the slot-local RNGs) if you are using the step solver. Otherwise, how can you guarantee stable output?

[janper]

by C# providing to Rust the location of origin and Rust adhering to that and generating the seeds (possibly directly from the resolved positions of slots)

Yes, that is also an option. I just wanted to take the weight of doing this from Rust (you) to C# (me). Question: What if the Slot diagonal changes? I think Rust needs to be aware of that too. (This will become relevant once we start automatically scaling Modules to fit Slots - which can be supported right away).

[janper]

This is dependent on the rule data provided to Rust. The module_low and module_high fields there are precisely the positions of the bits in the bit vector. If the positions there are stable, they are also stable in the bit vector.

This is only true if the list of Modules in the solution doesn't change. Once you add a new Module (say Empty), it shuffles the positions of the existing Modules in the bitvector.

byte low;
if (nameToPart.ContainsKey(lowStr)) {
    nameToPart.TryGetValue(lowStr, out low);
} else {
    low = nextPart;
    nameToPart.Add(lowStr, low);
    partToName.Add(low, lowStr);
    nextPart++;
    Debug.Assert(nextPart < maxModuleCount);
}

I'm proposing somehow deterministically turning the Module Name (because it is its UID) into its position in the bitvector.

I'll stop here. What I'm proposing means the count of bits in the bitvector should equal the count of possible Module names...

[janper]

A more general question then: How can we ensure a small change in the solution when a small change occurs to the set of Modules?

[yanchith]

by C# providing to Rust the location of origin and Rust adhering to that and generating the seeds (possibly directly from the resolved positions of slots)

Yes, that is also an option. I just wanted to take the weight of doing this from Rust (you) to C# (me). Question: What if the Slot diagonal changes? I think Rust needs to be aware of that too. (This will become relevant once we start automatically scaling Modules to fit Slots - which can be supported right away).

Programming is just a small minority of the work. Let's not drive design decisions by who is going to be implementing what and instead implement the feature where it makes sense.

It's been a while and I think I'll need to re-examine the proposed solutions before proceeding. Intuitively, it still makes some sense to me that this should be done in Rust, if only to reduce the number of round-trips and not expose inconsistent level of low-level control, but I am not so sure anymore.

Diagonals: yeah, if we go this way, they need to be passed too.

[yanchith]

I'll stop here. What I'm proposing means the count of bits in the bitvector should equal the count of possible Module names...

(:

How can we ensure a small change in the solution when a small change occurs to the set of Modules?

An excellent question! I don't think there is a general answer, but there might be a few good enough answers. This is one, but is quite complicated anyway, and requires changes both in C# and in Rust.

The problem we are battling is that inserting an element at the beginning of a list shifts every element already in the list to the right.

I'd think along the lines of doing a lexicographical sort of the module names and spacing the module ids evenly between 0 and MAX_MODULE_COUNT. Once modules change, you remove modules that are no longer in use, and insert new modules in the gaps between the existing modules. You know where to insert, because the names are sorted. If there is not enough space in the gap, you relocate the whole section to make space, but this is still better than shifting everything by one.

For this to have a chance we need to be able to:

• Generate stable UUIDs in C#,
• Have access to previous component state in C# so the minimal diff in module ids can be constructed,
• Be able to have gaps in module ids. (currently we don't, but I think we can change that).

[janper]

Have access to previous component state in C# so the minimal diff in module ids can be constructed

I don't think this is possible or at least it's not usual.

Instead I think we need to define the expectations - from the solver, from the user, from the solution... And define which input change really is small and which is already big. That will be determined by our technological options.

[yanchith]

🤦 I lost tack of the context. I take back my idea. We should not even attempt to keep the solution same-ish if modules change (https://github.com/subdgtl/WFC/issues/20#issuecomment-826088887).

But you can guarantee stable module IDs for when modules don't change, right?

[janper]

As long as the Modules don't change in any way, I can guarantee the persistence of their IDs.