Proposal: Conflict Resolution Optimization Inspired by Physical Locality Principles

[amazcuter]

Hi mxgmn,

First, I want to express my deep admiration for the Wave Function Collapse algorithm. Its elegance in merging constraint solving with procedural generation is truly inspiring.


Background & Motivation

My optimization idea stems from a philosophical analogy between WFC and quantum systems:

• If we view the entire generation space as a "macroscopic wavefunction", the iterative collapse process reflects the system's intrinsic properties.
• However, real physical systems obey strong locality – long-range dependencies (analogous to "non-local hidden variables") are rare without prior entanglement.
  
  This leads to a key insight: Most conflicts in WFC can be resolved locally without global backtracking.
  

Schematic (Mermaid)

flowchart TD
A[Start Conflict Resolution] --> B[Identify Conflict Cell]
B --> C{Attempt Resolution in Current Layer}
C -->|No Solution| D[Expand to Neighbor Layer]
D --> E[Restore Possibilities for All Layer Cells]
E --> F[Execute Backtracking Algorithm]
F -->|Failure| D
F -->|Success| G[Conflict Resolved]
    
subgraph "Layer Processing"
E1[Restore possibilities from outer to inner layers] --> E2[Build optimized neighbor constraints]
E2 --> E3[Compute new possibility sets for each cell]
end
    
subgraph "Backtracking Solver"
F1[Select possibility for each cell in order] --> F2{Check constraints satisfied?}
F2 -->|Yes| F3[Process next cell]
F2 -->|No| F4[Backtrack to previous cell]
F3 -->|Reach last cell| F5[Valid solution found]
F3 -->|Not last cell| F1
F4 -->|All possibilities tried| F6[No solution in current layer]
F4 -->|Remaining possibilities| F1
end
    
E -.-> E1
F -.-> F1

Loading

It should be noted that this approach offers significant advantages.

First, let’s discuss time complexity. Consider an isolated conflicting cell: in a traditional backtracking approach, we might revert many unnecessary cells. By adopting a layer-by-layer strategy — treating the conflict cell as an uncertainty and iteratively expanding outward — we observe that as we mark cells in outer layers as uncertain, the possibilities for the central conflict cell grow exponentially. Crucially, our layer-wise expansion of the "uncertainty zone" focuses computational effort precisely where it matters most for conflict resolution (though further optimizations remain possible).

Second, I hypothesize that the maximum layer depth (is my fix(wfc:T) parameter) is constrained by the inherent properties of the tile set and grid system. By abstracting my library into three components — tile set definitions, grid system configurations, and the WFC process — I argue that for any well-defined WFC system, this layer depth has an intrinsic upper bound. This property allows us to:

1. Precompute bounds for conflict resolution.
2. Maintain deterministic validity of inner-layer cells during generation.
   
   
   You can reach me at:

• Email: [email protected]
  
  Thank you for your time and pioneering work!

[amazcuter]

Your guidance would be immensely valuable for my undergraduate thesis. I sincerely hope to receive your feedback and would be deeply grateful for your insights!

[mxgmn]

Hi! What do you mean by "layers" exactly?

Have you implemented this algorithm?

[amazcuter]

Just like this.

[amazcuter]

I have an implementation using C++, and its class diagram is as follows

Details are as follows：

WFC Algorithm System Implementation

Modular Design & Core Components

The WFC system architecture adopts a modular design, primarily consisting of the following core components:

1. Foundational Definitions (WFCutil.h)

• Defines core concepts: Cell, GraphEdge, and Tile
• Provides basic data types: CellID, TileID, EdgeID, and their collection types
• Implements utility functions including 2D vector search operations

// Core types and data structures
using CellID = Cell *;
template <typename EdgeData>
using TileID = Tile<EdgeData> *;
using EdgeID = GraphEdge *;
using Cells = std::vector<CellID>;

2. Grid System (GridSystem.h)

• Abstract representation of various grid types, managing cell connectivity
• Provides interfaces for edge creation and neighbor retrieval
• Defines pure virtual function buildGridSystem() requiring concrete grid construction in derived classes
• Implements grid systems like Orthogonal2d and Orthogonal3d

class GridSystem {
protected:
    CellMap cells_;
    CellData edgelist_;
public:
    void CreateEdge(CellID cellA, CellID cellB);
    int getCellsNum();
    Cells getNeighbor(CellID id);
    virtual void buildGridSystem() = 0;
};

3. Tile Set (TileSet.h)

• Manages available tiles and their compatibility rules
• Contains pure virtual function buildTileSet() for specific tile set implementations
• Provides virtual function judgePossibility() for contextual constraint validation

class TileSet {
private:
    Tiles tiles_;
public:
    virtual void buildTileSet() = 0;
    virtual bool judgePossibility(std::vector<Tiles> neighborPossibility,
                                TileID<EdgeData> possibility) = 0;
};

4. WFC Manager (WFCManager.h)

• Executes core WFC algorithm logic
• Manages cell states, calculates entropy, performs collapse and propagation
• Implements conflict resolution with layer-based recovery mechanisms

class WFCManager {
private:
    GridSystem* grid_;
    TileSet<EdgeData>* tileSet_;
    int completedCellCount;
    CellID minEntropyCell;
public:
    virtual void initialize() = 0;
    bool isComplete();
    void run();
    // Conflict resolution methods
    void resolveConflicts();
    bool retrospectiveGetSolution(const Cells& layer, int index);
};

Conflict Resolution Implementation

The system implements layer-based conflict resolution:

// Backtracking function for conflict resolution
bool retrospectiveGetSolution(const Cells& layer, int index) {
    if (index >= layer.size()) {
        // Validate all cells in the layer
        for (CellID cell : layer) {
            if (wfcCellData[cell].possibility.empty()) {
                return false;
            }
        }
        return true;
    }

    CellID currentCell = layer[index];
    Tiles originalPossibilities = wfcCellData[currentCell].possibility;

    for (TileID tile : originalPossibilities) {
        // Try different tile selections and propagate constraints
        cellData.possibility = { tile };
        propagateEffects(currentCell);
        
        if (retrospectiveGetSolution(layer, index + 1)) {
            return true; // Solution found
        }
        
        // Backtrack: Restore state
        cellData.possibility = savedPossibilities;
    }
    return false;
}

// Layered conflict resolution
void resolveConflictsCell(Cells& currentLayer, Cells& visited, int depth) {
    // Attempt resolution in current layer
    bool solved = retrospectiveGetSolution(currentLayer, 0);
    
    // Recursive expansion if unresolved
    if (!solved) {
        Cells nextLayer = collectNextLayer(currentLayer, visited);
        if (!nextLayer.empty()) {
            resolveConflictsCell(nextLayer, visited, depth + 1);
        } else {
            throw std::runtime_error("Conflict unresolvable: Maximum backtrack depth reached");
        }
    }
}

[amazcuter]

I will organize this code repository after completing my graduation thesis and upload it to GitHub.
I am also planning to rewrite it into a Rust version.