I’m using WFC to generate random dungeons in my game. However, the algorithm seems to fail and reach a contradiction almost immediately every time it is run. Here is the code:
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class OverlappingModel
{
class Pattern
{
public Color[,] tile;
public int frequency;
public List<OverlappingPattern> overlappingPatterns;
public Pattern(Color[,] tile)
{
this.tile = tile;
frequency = 1;
overlappingPatterns = new List<OverlappingPattern>();
}
}
class OverlappingPattern
{
public Color[,] tile;
public int offsetX;
public int offsetY;
public OverlappingPattern(Color[,] tile, int offsetX, int offsetY)
{
this.tile = tile;
this.offsetX = offsetX;
this.offsetY = offsetY;
}
}
class Cell
{
public List<Pattern> superpositions;
public Cell()
{
superpositions = new List<Pattern>();
}
public void Collapse()
{
int patternFrequencyIndex = Random.Range(0, GetEntropy());
int currentFrequencyIndex = 0;
for (int i = 0; i < superpositions.Count; i++)
{
currentFrequencyIndex += superpositions[i].frequency;
if (currentFrequencyIndex >= patternFrequencyIndex)
{
superpositions = new List<Pattern>{superpositions[i]};
}
}
}
public int GetEntropy()
{
int entropy = 0;
for (int i = 0; i < superpositions.Count; i++)
{
entropy += superpositions[i].frequency;
}
return entropy;
}
}
public Color[,] output;
Texture2D texture;
int N;
int symmetry;
bool periodicInput;
bool periodicOutput;
int outputWidth;
int outputHeight;
List<Pattern> patterns = new List<Pattern>();
public OverlappingModel(Texture2D texture, int N, int symmetry, bool periodicInput, bool periodicOutput, int outputWidth, int outputHeight)
{
this.texture = texture;
this.N = N;
this.symmetry = symmetry;
this.periodicInput = periodicInput;
this.periodicOutput = periodicOutput;
this.outputWidth = outputWidth;
this.outputHeight = outputHeight;
}
public void Compile()
{
int inputWidth = texture.width;
int inputHeight = texture.height;
Color[,] input = new Color[inputWidth, inputHeight];
for (int x = 0; x < inputWidth; x++)
{
for (int y = 0; y < inputHeight; y++)
{
input[x, y] = texture.GetPixel(x, y);
}
}
int maxInputX = periodicInput ? inputWidth : inputWidth - N + 1;
int maxInputY = periodicInput ? inputHeight : inputHeight - N + 1;
for (int cornerX = 0; cornerX < maxInputX; cornerX++)
{
for (int cornerY = 0; cornerY < maxInputY; cornerY++)
{
Color[,] tile = new Color[N, N];
for (int x = cornerX; x < cornerX + N; x++)
{
for (int y = cornerY; y < cornerY + N; y++)
{
tile[x - cornerX, y - cornerY] = input[Wrap(x, inputWidth), Wrap(y, inputHeight)];
}
}
patterns.Add(new Pattern(tile));
if (symmetry > 1) patterns.Add(Reflect(patterns[patterns.Count - 1]));
if (symmetry > 2) patterns.Add(Rotate(patterns[patterns.Count - 2]));
if (symmetry > 3) patterns.Add(Reflect(patterns[patterns.Count - 1]));
if (symmetry > 4) patterns.Add(Rotate(patterns[patterns.Count - 2]));
if (symmetry > 5) patterns.Add(Reflect(patterns[patterns.Count - 1]));
if (symmetry > 6) patterns.Add(Rotate(patterns[patterns.Count - 2]));
if (symmetry > 7) patterns.Add(Reflect(patterns[patterns.Count - 1]));
}
}
for (int i = 0; i < patterns.Count; i++)
{
for (int j = i + 1; j < patterns.Count; j++)
{
if (CompareTiles(patterns[i].tile, patterns[j].tile))
{
patterns[i].frequency++;
patterns.Remove(patterns[j]);
j--;
}
}
}
for (int i = 0; i < patterns.Count; i++)
{
for (int j = i + 1; j < patterns.Count; j++)
{
for (int offsetX = 1 - N; offsetX < N - 1; offsetX++)
{
for (int offsetY = 1 - N; offsetY < N - 1; offsetY++)
{
int minX = GetOverlapMin(offsetX);
int maxX = GetOverlapMax(offsetX);
int minY = GetOverlapMin(offsetY);
int maxY = GetOverlapMax(offsetY);
for (int x = minX; x < maxX; x++)
{
for (int y = minY; y < maxY; y++)
{
if (patterns[j].tile[x - offsetX, y - offsetY] != patterns[i].tile[x, y])
{
goto noOverlap;
}
}
}
patterns[i].overlappingPatterns.Add(new OverlappingPattern(patterns[j].tile, offsetX, offsetY));
patterns[j].overlappingPatterns.Add(new OverlappingPattern(patterns[i].tile, -offsetX, -offsetY));
noOverlap:;
}
}
}
}
int GetOverlapMin(int offset)
{
return offset <= 0 ? 0 : offset;
}
int GetOverlapMax(int offset)
{
return offset <= 0 ? offset + N : N;
}
Pattern Rotate(Pattern pattern)
{
Pattern p = new Pattern(new Color[N, N]);
for (int x = 0; x < N; x++)
{
for (int y = 0; y < N; y++)
{
p.tile[x, y] = pattern.tile[N - y - 1, x];
}
}
return p;
}
Pattern Reflect(Pattern pattern)
{
Pattern p = new Pattern(new Color[N, N]);
for (int x = 0; x < N; x++)
{
for (int y = 0; y < N; y++)
{
p.tile[x, y] = pattern.tile[N - x - 1, y];
}
}
return p;
}
}
public bool Run()
{
int maxOutputX = periodicOutput ? outputWidth : outputWidth - N + 1;
int maxOutputY = periodicOutput ? outputHeight : outputHeight - N + 1;
output = new Color[outputWidth, outputHeight];
for (int x = 0; x < outputWidth; x++)
{
for (int y = 0; y < outputHeight; y++)
{
output[x, y] = new Color(0f, 0f, 0f, 0f);
}
}
Cell[,] cells = new Cell[maxOutputX, maxOutputY];
for (int x = 0; x < maxOutputX; x++)
{
for (int y = 0; y < maxOutputY; y++)
{
cells[x, y] = new Cell();
cells[x, y].superpositions = patterns;
}
}
List<Vector2Int> uncollapsedCells = new List<Vector2Int>();
for (int x = 0; x < maxOutputX; x++)
{
for (int y = 0; y < maxOutputY; y++)
{
uncollapsedCells.Add(new Vector2Int(x, y));
}
}
while (uncollapsedCells.Count > 0)
{
List<Vector2Int> lowestEntropyCells = new List<Vector2Int>();
int lowestEntropy = -1;
for (int i = 0; i < uncollapsedCells.Count; i++)
{
Vector2Int position = uncollapsedCells[i];
int entropy = cells[position.x, position.y].GetEntropy();
if (lowestEntropy == -1 || entropy < lowestEntropy)
{
lowestEntropy = entropy;
lowestEntropyCells.Clear();
}
if (entropy == lowestEntropy)
{
lowestEntropyCells.Add(new Vector2Int(position.x, position.y));
}
}
Debug.Log("Uncollapsed Cells: " + uncollapsedCells.Count);
Debug.Log("Lowest Entropy: " + lowestEntropy);
if (lowestEntropyCells.Count == 0)
{
Debug.Log("DONE");
break;
}
else if (lowestEntropy == 0)
{
Debug.Log("CONTRADICTION");
return false;
}
Vector2Int lowestEntropyCell = lowestEntropyCells[Random.Range(0, lowestEntropyCells.Count)];
cells[lowestEntropyCell.x, lowestEntropyCell.y].Collapse();
uncollapsedCells.Remove(new Vector2Int(lowestEntropyCell.x, lowestEntropyCell.y));
Stack<Vector2Int> flagged = new Stack<Vector2Int>(GetNeighbors(lowestEntropyCell.x, lowestEntropyCell.y));
while (flagged.Count > 0)
{
Vector2Int cell = flagged.Pop();
bool changed = false;
List<Vector2Int> neighbors = GetNeighbors(cell.x, cell.y);
// for each superposition in the current cell
for (int i = 0; i < cells[cell.x, cell.y].superpositions.Count; i++)
{
// loop through each of its neighbors
for (int j = 0; j < neighbors.Count; j++)
{
Vector2Int neighborCell = neighbors[j];
Vector2Int offset = cell - neighborCell;
// loop through each of the nieghbor's superpositions
for (int k = 0; k < cells[neighborCell.x, neighborCell.y].superpositions.Count; k++)
{
// loop through each of the superposition's overlappingPatterns
for (int l = 0; l < cells[neighborCell.x, neighborCell.y].superpositions[k].overlappingPatterns.Count; l++)
{
// if the overlappingPattern is equal to the current cell overlapping legally at the offset that it is at
if (CompareOverlappingPatterns(cells[neighborCell.x, neighborCell.y].superpositions[k].overlappingPatterns[l], new OverlappingPattern(cells[cell.x, cell.y].superpositions[i].tile, offset.x, offset.y)))
{
goto legal;
}
}
}
// remove the superposition if it isn't legal
cells[cell.x, cell.y].superpositions.RemoveAt(i);
changed = true;
i--;
break;
legal:;
}
}
// if any superpositions were removed, check all the neighbor cells to see if all THEIR superpositions are still possible
if (changed)
{
for (int i = 0; i < neighbors.Count; i++)
{
flagged.Push(neighbors[i]);
}
}
}
}
for (int x = 0; x < maxOutputX; x++)
{
for (int y = 0; y < maxOutputY; y++)
{
output[x, y] = cells[x, y].superpositions[0].tile[0, 0];
if (periodicOutput && (x == maxOutputX - 1 || y == maxOutputY - 1))
{
for (int subX = 0; subX < N; subX++)
{
for (int subY = 0; subY < N; subY++)
{
output[x + subX, y + subY] = cells[x, y].superpositions[0].tile[subX, subY];
}
}
}
}
}
return true;
}
bool CompareTiles(Color[,] tile1, Color[,] tile2)
{
for (int x = 0; x < N; x++)
{
for (int y = 0; y < N; y++)
{
if (tile1[x, y] != tile2[x, y])
{
return false;
}
}
}
return true;
}
bool CompareOverlappingPatterns(OverlappingPattern op1, OverlappingPattern op2)
{
if (!CompareTiles(op1.tile, op2.tile) || op1.offsetX != op2.offsetX || op1.offsetY != op2.offsetY)
{
return false;
}
return true;
}
int Wrap(int num, int max)
{
int wrapped = num;
while (wrapped < 0)
{
wrapped += max;
}
while (wrapped >= max)
{
wrapped -= max;
}
return wrapped;
}
List<Vector2Int> GetNeighbors(int cellX, int cellY)
{
List<Vector2Int> neighbors = new List<Vector2Int>();
for (int x = cellX - N + 1; x < cellX + N; x++)
{
for (int y = cellY - N + 1; y < cellY + N; y++)
{
if (x == cellX && y == cellY)
{
continue;
}
if (!periodicOutput && x >= 0 && x < outputWidth - N + 1 && y >= 0 && y < outputHeight - N + 1)
{
neighbors.Add(new Vector2Int(x, y));
}
else if (periodicOutput)
{
neighbors.Add(new Vector2Int(Wrap(x, outputWidth), Wrap(y, outputHeight)));
}
}
}
return neighbors;
}
}
The debug console outputs exactly the same thing (shown in the attached file) every time the algorithm is run.
