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

Entropy Calculation #51

Closed LearnedLately closed 5 years ago

LearnedLately commented 5 years ago

I'm trying to make sense of the entropy calculation. Line 61 in Model.cs has: startingEntropy = Math.Log(sumOfWeights) - sumOfWeightLogWeights / sumOfWeights;

and the readme says this is the Shanon Entropy, which should be -sumOfWeightLogWeights with log base 2, though the choice of log base doesn't change the result of the algorithm. I understand that the weights won't sum to 1 once tiles begin to be excluded.

To account for the weights not summing to 1, you'd just need to normalize the distribution by dividing each weight by sumOfWeights, right? So that would be: entropy = -sum(Math.Log(weight[i] / sumOfWeights) * weight[i] / sumOfWeights)

but I don't see how this is equivalent to line 61. What are the steps I'm missing to go from this to line 61?

mxgmn commented 5 years ago

If you apply the logarithm property log(ab)=log(a)+log(b), you'll see that they are equivalent.

Why not just normalize the weights and do all calculations with probabilities via standard Shannon formula? Because the normalizing factor is different for different wave configurations.

LearnedLately commented 5 years ago

Sorry, you're right. I see now. Starting with: 1. entropy = -sum(log(weight[i] / sumOfWeights) * weight[i] / sumOfWeights) You can expand it to: 2. entropy = -sum( (log(weight[i]) - log(sumOfWeights)) * weight[i] / sumOfWeights ) and split it into two sums: 3. entropy = sum( log(sumOfWeights) * weight[i] ) / sumOfWeights - sumOfWeightLogWeights / sumOfWeights The first sum is just log(sumOfWeights), which gives line 61: startingEntropy = Math.Log(sumOfWeights) - sumOfWeightLogWeights / sumOfWeights;