如何修正Unity中Wave Function Collapse算法的邻居瓦片选项传播问题？

核心问题分析 #

• 约束传播仅单次执行：WFC的约束传播需要迭代更新，直到所有单元格的选项不再变化。原代码仅在Generate方法中遍历一次单元格，未处理“单元格选项更新后连锁影响邻居”的逻辑。
• 邻居规则方向错误：UpdateNeighborOptions中过滤逻辑搞反匹配方向，比如检查上方邻居时，当前单元格的选项需满足“是上方邻居允许的下方邻居”，原代码的规则调用方向完全颠倒。
• 选项初始化逻辑错误：每次更新选项时都从原始瓦片列表重新初始化，而非基于单元格当前已有的选项过滤，导致之前的约束被重置。

修复后的完整代码 #

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using UnityEngine;

public class WaveFunction : MonoBehaviour
{
    [SerializeField] private GameObject generationManager;
    public int dimensions;
    public Tile[] tileObjects;
    public Tile fallbackTile;
    public Cell cellObj;
    
    private List<Cell> gridComponents;
    private int iterations = 0;

    void Awake()
    {
        gridComponents = new List<Cell>();
        InitializeGrid();
    }

    void InitializeGrid()
    {
        for (int y = 0; y < dimensions; y++)
        {
            for (int x = 0; x < dimensions; x++)
            {
                Cell newCell = Instantiate(cellObj, new Vector2(x, y), Quaternion.identity, transform);
                newCell.CreateCell(false, tileObjects);
                gridComponents.Add(newCell);
            }
        }

        StartCoroutine(CalculateEntropy());
    }

    IEnumerator CalculateEntropy()
    {
        List<Cell> tempGrid = GetUncollapsedCells();

        if (tempGrid.Count == 0)
            yield break;

        int minEntropy = tempGrid.Min(c => c.tileOptions.Length);
        var candidates = tempGrid.Where(c => c.tileOptions.Length == minEntropy).ToList();

        yield return new WaitForSeconds(0.01f);

        CollapseCell(candidates);
    }

    void CollapseCell(List<Cell> candidates)
    {
        if (candidates == null || candidates.Count == 0)
        {
            Debug.LogError("No cells available for collapse.");
            return;
        }

        float totalWeight = candidates.Sum(c => c.tileOptions.Sum(t => t.weight));
        float randomWeight = UnityEngine.Random.Range(0, totalWeight);

        Cell cellToCollapse = null;
        Tile selectedTile = null;

        foreach (var cell in candidates)
        {
            foreach (var tile in cell.tileOptions)
            {
                randomWeight -= tile.weight;
                if (randomWeight <= 0)
                {
                    cellToCollapse = cell;
                    selectedTile = tile;
                    break;
                }
            }
            if (cellToCollapse != null)
                break;
        }

        if (cellToCollapse == null)
        {
            Debug.LogError("Failed to select a cell to collapse.");
            Instantiate(generationManager);
            Destroy(transform.gameObject);
            return;
        }

        cellToCollapse.collapsed = true;
        cellToCollapse.tileOptions = new Tile[] { selectedTile };

        Instantiate(selectedTile, cellToCollapse.transform.position, Quaternion.identity, cellToCollapse.transform);

        StartCoroutine(PropagateConstraints());
    }

    IEnumerator PropagateConstraints()
    {
        bool changed;
        do
        {
            changed = false;
            List<Cell> uncollapsed = GetUncollapsedCells();

            foreach (var cell in uncollapsed)
            {
                int x = (int)cell.transform.position.x;
                int y = (int)cell.transform.position.y;
                List<Tile> currentOptions = new List<Tile>(cell.tileOptions);

                FilterOptionsByNeighbor(x, y, currentOptions, Direction.Up);
                FilterOptionsByNeighbor(x, y, currentOptions, Direction.Down);
                FilterOptionsByNeighbor(x, y, currentOptions, Direction.Left);
                FilterOptionsByNeighbor(x, y, currentOptions, Direction.Right);

                if (currentOptions.Count != cell.tileOptions.Length)
                {
                    // 若无有效选项，使用fallbackTile兜底
                    if (currentOptions.Count == 0 && fallbackTile != null)
                    {
                        currentOptions.Add(fallbackTile);
                    }
                    cell.RecreateCell(currentOptions.ToArray());
                    changed = true;
                }
            }

            yield return null;
        } while (changed);

        iterations++;
        if (iterations < dimensions * dimensions)
        {
            StartCoroutine(CalculateEntropy());
        }
    }

    void FilterOptionsByNeighbor(int x, int y, List<Tile> options, Direction dir)
    {
        int neighborX = x;
        int neighborY = y;
        Func<Tile, Tile[]> neighborAllowedTiles = null;

        switch (dir)
        {
            case Direction.Up:
                neighborY = y - 1;
                neighborAllowedTiles = tile => tile.downNeighbours;
                break;
            case Direction.Down:
                neighborY = y + 1;
                neighborAllowedTiles = tile => tile.upNeighbours;
                break;
            case Direction.Left:
                neighborX = x - 1;
                neighborAllowedTiles = tile => tile.rightNeighbours;
                break;
            case Direction.Right:
                neighborX = x + 1;
                neighborAllowedTiles = tile => tile.leftNeighbours;
                break;
        }

        if (neighborX < 0 || neighborX >= dimensions || neighborY < 0 || neighborY >= dimensions)
            return;

        Cell neighbor = gridComponents[neighborX + neighborY * dimensions];
        var validTiles = new HashSet<Tile>();

        if (neighbor.collapsed)
        {
            validTiles.UnionWith(neighborAllowedTiles(neighbor.tileOptions[0]));
        }
        else
        {
            foreach (var tile in neighbor.tileOptions)
            {
                validTiles.UnionWith(neighborAllowedTiles(tile));
            }
        }

        options.RemoveAll(t => !validTiles.Contains(t));
    }

    List<Cell> GetUncollapsedCells()
    {
        return gridComponents.FindAll(c => !c.collapsed);
    }

    enum Direction
    {
        Up, Down, Left, Right
    }
}

关键修复点说明 #

1. 迭代约束传播：新增PropagateConstraints协程，循环更新所有单元格选项直到无变化，确保约束完全传递；用yield return null避免主线程卡死。
2. 修正规则匹配方向：通过Direction枚举明确逻辑，确保当前单元格选项与邻居的规则双向兼容。
3. 基于现有选项更新：过滤时复用单元格当前的选项列表，保留之前的约束结果。
4. 添加兜底逻辑：当单元格无有效选项时，自动使用fallbackTile填充，避免生成中断。

额外注意事项 #

• 确保Tile类的邻居规则双向一致：比如瓦片A的upNeighbours包含瓦片B，那么瓦片B的downNeighbours必须包含瓦片A。

内容的提问来源于stack exchange，提问作者Azerty