波函数坍缩生成地图

QSTX2025/9/2大约 5 分钟

一、波函数坍缩原理

简单来说，WFC算法就是：从一个充满无限可能性的空白画布开始，通过随机选择第一个点并确定其状态，然后让这个选择的影响像波浪一样传播开来，限制其邻居的可能选择，一步步直到整个画布的所有格子都坍缩为唯一状态。

主要算法步骤：

初始化地图所有单元，每个单元拥有多种可能性（记为熵）
查找所有熵最小的单元，对其进行坍缩（选择任意1种可能）
从坍缩后的单元开始传播，剔除邻居多余的可能性
回到步骤2，直到所有单元坍缩完成

二、伪代码实现

提示

其实WFC就是一个特化的深搜算法，只是在搜索路径上有一些特殊处理。例如：自定义选择不同状态的概率、自定义不同单元间相配的概率等等。

本文实现的算法会从理论上对所有可能性进行遍历，直到遇见第一个可行解。

1.递归版本

重要

注意辨别引用类型与值类型，下面伪代码中不进行标注

//1.假设地图初始化完成，Cell中存储了一个单元所有可能性
bool CollopseMap(Map map){
  //2.1.获取所有熵最低的单元
  List<Cell> alterCells=FindLowestEntropyCells(map);
  //4.所有节点均坍缩完毕，坍缩成功
  if(alterCells.Count==0)
    return true;
  //2.2.随机选取一个单元进行坍缩
  while(alterCells.Count>0){
    curCell=alterCells[randIdx];
    alterCells.RemoveAt(randIdx);

    while(curCell.GetStates().Count>0){
      Map oldMap=map.Clone();
      List<State> restStates = curCell.Collopse();
      //3.1.从坍缩后的单元开始传播
      if(Propagate(map,curCell)){
        //3.2.传播成功，基于当前状态继续递归
        if(CollopseMap(map))
          return true;
      }
      //3.2.传播失败后，更新可能的状态，剔除不可能的状态
      map=oldmap;
      curCell.SetStates(restStates);
    }
  }
  return false;
}

注意

上述实现并不会进行随机化剪枝，会将所有路径都遍历出来，直到找到第一个所有单元均坍缩的状态。但是每次递归的方向是随机的，支持自定义概率。

2.迭代版本

基于上面递归版本，我们自己维护一套堆栈来实现下面的迭代版本

重要

注意辨别引用类型与值类型，下面伪代码中不进行标注

public class HexHistory
{
    public Map map;
    public List<HexCellCoord> alterCoords;
    public bool hasCell;
    public HexCellCoord curCoord;
}

public bool Collapse(Map map)
{
    Stack<HexHistory> stk = new Stack<HexHistory>();
    //压入初始状态堆栈
    HexHistory curHistory = new HexHistory()
    {
        map=map,
        alterCoords = FindLowestEntropyCells(map);
        hasCell = false,
    };
    if(curHistory.alterCoords.Count==0)
    {
        Debug.Log("初始坍缩成功");
        return true;
    }
    stk.Push(curHistory);

    bool success = false;

    while (true)
    {
        //每次尝试栈顶进行处理，栈顶为空说明所有情况都已遍历，不存在有效解
        if (stk.Count == 0)
        {
            success = false;
            Debug.Log("坍缩失败");
            break;
        }
        curHistory = stk.Peek();
        //用hasCell和restStates.Count > 0,表示处于内部while循环
        //当前有正在处理的单元，持续坍缩该单元
        if (curHistory.hasCell)
        {
            HexCell curCell = curHistory.GetCurCell();
            List<HexState> restStates = curCell.GetStates();
            //当前单元可以坍缩
            if (restStates.Count > 0)
            {
                restStates = curHistory.GetCurCell().Collapse();
                HexHistory nextHistory = new HexHistory
                {
                    map = curHistory.map.Clone(),
                    alterCoords = new List<HexCellCoord>(),
                    hasCell = false
                };
                curHistory.GetCurCell().SetStates(restStates);
                curHistory.GetCurCell().IsCollapsed = false;
                //传播成功，记录当前状态，并加入下一次要处理的状态
                if (Propagate(nextHistory.map, curHistory.curCoord))
                {
                    //stk.Push(curHistory);
                    nextHistory.alterCoords = FindLowestEntropyCells(nextHistory.map);
                    stk.Push(nextHistory);
                    if (nextHistory.alterCoords.Count == 0)
                    {
                        success = true;
                        Debug.Log("坍缩成功");
                        break;
                    }
                    continue;
                }
                else
                {
                    continue;
                }
            }
        }
        //hasCell==false或restStates.Count==0，说明进入外部while循环，
        //当前没有正在处理的单元，但有候补处理单元
        //从中选出一个待处理单元
        if (curHistory.alterCoords.Count > 0)
        {
            curHistory.curCoord = curHistory.alterCoords[randIdx];
            curHistory.alterCoords.RemoveAt(randIdx);
            curHistory.hasCell = true;
            continue;
        }

        //hasCell==false或restStates.Count==0，且alterCoords为空，说明栈顶已无效
        stk.Pop();
    }

    return success;
}

3.传播的实现

提示

本质上，传播又是一个搜索。。。
但是这个搜索是确定的，因为要把所有单元都遍历一遍，深搜广搜都一样啦！

但是可以剪枝哟！

3.1.以广搜为例

传播过程：

初始化一个队列，用来记录接下来需要遍历的单元
将起点单元压入队列
从队列取出一个单元，开始传播
用已传播的邻居来约束自身，更新可能性
将未传播的邻居加入队列，等待遍历
回到步骤3直到队列为空

什么情况下，不需要从当前单元继续传播？

答：当前单元经周围传播后的邻居约束后，如果自身所有可能性都没有变时，不必继续传播。因为自己的状态没有变换，未传播的邻居必然不会因为自己发生变化。
需要注意传播的起点不适用这个情况。

public bool Propagate(Map map, Coord coord)
{
    bool[] visited = new bool[map.Size()];
    Queue<Coord> queue = new Queue<Coord>();
    queue.Enqueue(coord);

    bool isFirst = true;
    while (queue.Count > 0)
    {
        var curCoord = queue.Dequeue();
        visited[curCoord]=true;

        List<HexState> possibleStates = new List<HexState>();
        //所有状态都匹配
        bool allStatesOk = true;
        foreach (State state in map[curCoord].GetStates())
        {
            //所有方向上是否匹配
            bool all_dirs_ok = true;
            foreach (var direction in directions)
            {
                Coord neighborCoord = curCoord.GetNeighborCoord(direction);
                //邻居已经被传播，用邻居的状态约束自己
                if (IsVisited(neighborCoord))
                {
                    //特定方向上是否匹配
                    bool this_dir_ok = false;
                    foreach (State neighborState in map[neighborCoord].GetStates())
                    {
                        if(IsPairedFunc(state,neighborState,direction))
                        {
                            this_dir_ok = true;
                            break;
                        }
                    }
                    if(!this_dir_ok)
                    {
                        all_dirs_ok = false;
                        break;
                    }
                }
            }

            if (all_dirs_ok)
                possibleStates.Add(state);
            else
                allStatesOk = false;
        }

        if (possibleStates.Count == 0)
            return false;

        //当前单元所有可能的状态都没发生改变，必然不会由于自己引起邻居的改变，
        //即状态的传播等价于“终止了”，故不必再将邻居加入传播队列
        //但传播的起点是例外
        if (allStatesOk && !isFirst)
            continue;
        isFirst = false;
        map[curCoord].SetStates(possibleStates);

        foreach (var direction in directions)
        {
            Coord neighborCoord = curCoord.GetNeighborCoord(direction);

            //邻居未被传播，无需用邻居的状态约束自己，但要把邻居加入待访问队列
            if (!IsVisited(neighborCoord))
                queue.Enqueue(neighborCoord);
        }
    }

    return true;
}

三、Unity内的实现及持续改进

指定迭代步数上限。对于实时性要求较高的程序，必不会运行迭代无限进行下去，需要在指定步数后停止迭代并返回结果。
结合协程等机制，将迭代进度进行实时呈现，对于调试也是一大利好。
约束初始条件，指定某些区域的限制，提高可控性。