WFC-从入门到放弃

,

1. 过程化生成（综述）

1.1 概念

过程化生成是计算机科学中的一种使计算机自动制造一类数据的算法。在电子游戏领域中常用于自动地制造大量游戏内容。

优点：

  • 减小文件体积
  • 扩大内容数量
  • 增加游戏的随机性

1.2 过程化生成的方法

简单介绍一下关于过程化生成的几种比较直观的方法：

1.3 应用场景

在电子游戏中应用非常广泛：

  • Rogue(1980)

    Rouge-1980

  • 暗黑破坏神II（2000）

    DiabloII-2000

  • 我的世界（2011）

  • 无人深空（2016）

    NoMansSky

  • Dwarf Fortress(2006)

    Dwarf Fortress

1.4 挑战

Mathematical uniqueness vs. Perceptual uniqueness

2. Wave Function Collapse Algorithm

2.1 概念

波函数坍缩算法是受到了量子力学中的相关概念的启发，用来过程化地生成与输入图案局部相似的输出图案的算法。算法将还未生成的结果看作完全未观测状态（即所有可能结果的叠加态），通过观测，得到确定态的过程。

局部相似(N=3)

局部相似的含义是：

  • (C1) 输出位图中的每一个 NxN 的像素图案都至少在输入位图中出现过一次
  • (Weak C2) 输入位图中 NxN 的像素图案的概率分布，应该与足够数量的输出位图中 NxN 像素图案的概率分布相同。换句话说，相同的图案在输出中出现的可能性接近输入位图中这个图案的比例。

2.2 应用

  • 位图生成

    bitmap

  • Townscaper(545个组件)

    Townscaper

2.3 算法原理

  1. 读取输入位图，计算 NxN 的图案

    1. （可选）通过旋转、翻转扩充图案数据的数量

  2. 创建输出尺寸相符的数组（wave），数组中每一个元素代表一个 NxN 区域在输出结果中的状态。一个 NxN 区域的一个状态是输入的所有 NxN 图案及其 bool 系数的叠加。

  3. 将代表 wave 的数组初始化为完全未观测状态（全部 bool 系数值为 True）

  4. 循环：

    1. 观测：
      1. 选择一个非零最小熵的数组（波）元素。若找不到符合条件的数组元素（熵为 0 或未定义的熵），跳到第5步。
      2. 根据当前的 bool 系数，以及输入的 NxN 图案的分布律，将这个元素 Collapse 到确定态。
    2. 传播：将上一个观测阶段得到信息传递到其他元素

  5. 至此，所有数组元素都处在已观测状态（系数为 one-hot 位元组合，仅容许单一位元为 1，其他位元均为 0），或处在矛盾状态（系数全为 0）

可交互版本的 WFC 示例

2.4 实现

2.4.1 算法流程

  • WFC 算法的主体入口：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    public bool Run(int seed, int limit)
    {
        if (wave == null) Init();

        Clear();
        random = new Random(seed); // 缓冲随机种子

        for (int l = 0; l < limit || limit == 0; l++) // 步数限制
        {
            bool? result = Observe(); // 观测
            if (result != null) return (bool)result; // 终止条件
            Propagate(); // 传播
        }

        return true;
    }

  • 观测:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    bool? Observe()
    {
        double min = 1E+3; // 最小熵
        int argmin = -1; // 最小熵索引

        for (int i = 0; i < wave.Length; i++)
        {
            if (OnBoundary(i % FMX, i / FMX)) continue;

            int amount = sumsOfOnes[i]; // 当前叠加态叠加数量
            if (amount == 0) return false;

            double entropy = entropies[i]; // 提取缓存的熵
            if (amount > 1 && entropy <= min)
            {
                double noise = 1E-6 * random.NextDouble(); // 使用扰动来随机在相同熵值的区域进行选择
                if (entropy + noise < min)
                {
                    min = entropy + noise;
                    argmin = i;
                }
            }
        }

        if (argmin == -1)
        {
            observed = new int[FMX * FMY];
            for (int i = 0; i < wave.Length; i++) for (int t = 0; t < T; t++) if (wave[i][t]) { observed[i] = t; break; } // 构建 observed 输出结果
            return true;
        }

        double[] distribution = new double[T];
        for (int t = 0; t < T; t++) distribution[t] = wave[argmin][t] ? weights[t] : 0; // 被禁用的权重为 0，未禁用的默认值
        int r = distribution.Random(random.NextDouble()); // 扩展方法，选择未禁用的一个图案索引

        bool[] w = wave[argmin]; // 当前熵最小的区域的叠加态
        for (int t = 0; t < T; t++) if (w[t] != (t == r)) Ban(argmin, t); // 禁用未选中状态

        return null;
    }

    • 熵的计算：

      $wi$表示当前位置，第$i$个状态的权重值，$w{sum}$表示所有状态的权重和。

      可选的状态越少，计算得到的熵越高；仅有一种状态可行时，熵为$0$。

  • 传播:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    protected void Propagate()
    {
        while (stacksize > 0) // 对全部更新过的区域进行传播
        {
            var e1 = stack[stacksize - 1]; // 被禁用的索引和图案
            stacksize--;

            int i1 = e1.Item1;
            int x1 = i1 % FMX, y1 = i1 / FMX; // 计算坐标

            for (int d = 0; d < 4; d++) // 处理四个方向相邻
            {
                int dx = DX[d], dy = DY[d];
                int x2 = x1 + dx, y2 = y1 + dy;
                if (OnBoundary(x2, y2)) continue;

                if (x2 < 0) x2 += FMX;
                else if (x2 >= FMX) x2 -= FMX;
                if (y2 < 0) y2 += FMY;
                else if (y2 >= FMY) y2 -= FMY;

                int i2 = x2 + y2 * FMX;
                int[] p = propagator[d][e1.Item2]; // 被禁用的图案可连接当前方向的所有类型的图案
                int[][] compat = compatible[i2]; // 传播到的索引位置，对每种图案在每个方向的可能数量

                for (int l = 0; l < p.Length; l++) // 对于当前方向每种曾经可连接的图案
                {
                    int t2 = p[l]; // 取得图案的索引（派生类中用来索引patterns）
                    int[] comp = compat[t2]; // 要连接 t2 类型的图案的所有方向的可能数量

                    comp[d]--; // 取得t2类型在当前方向上可能的连接数量，并排除已经禁用的 e1.Item2 图案
                    if (comp[d] == 0) Ban(i2, t2); // 如果被禁用的 e1.Item2 是最后一个可行的连接图案，那么将图案t2在i2位置禁用
                }
            }
        }
    }

2.4.2 数据准备

对输入数据进行处理，这里将输入数据分成位图和图集两种类型分别处理。

  • 位图图案 (bitmap)

    • 对图案进行采样，得到原始数据

      1
      2
      3
      4
      5
      6
      7
      8
      byte[] pattern(Func<int, int, byte> f)
      {
          byte[] result = new byte[N * N];
          for (int y = 0; y < N; y++) for (int x = 0; x < N; x++) result[x + y * N] = f(x, y);
          return result;
      };

      byte[] patternFromSample(int x, int y) => pattern((dx, dy) => sample[(x + dx) % SMX, (y + dy) % SMY]); //从(x, y)来取样

    • 通过旋转、镜像扩充原始数据集

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      for (int y = 0; y < (periodicInput ? SMY : SMY - N + 1); y++) for (int x = 0; x < (periodicInput ? SMX : SMX - N + 1); x++)
      {
          byte[][] ps = new byte[8][];

          ps[0] = patternFromSample(x, y); // 每个位置取得8种变换的结果
          ps[1] = reflect(ps[0]);
          ps[2] = rotate(ps[0]);
          ps[3] = reflect(ps[2]);
          ps[4] = rotate(ps[2]);
          ps[5] = reflect(ps[4]);
          ps[6] = rotate(ps[4]);
          ps[7] = reflect(ps[6]);

          for (int k = 0; k < symmetry; k++)
          {
              long ind = index(ps[k]);
              if (weights.ContainsKey(ind)) weights[ind]++; // 累加重复的图案的权重
              else
              {
                  weights.Add(ind, 1);
                  ordering.Add(ind);
              }
          }
      }

    • 得到邻接元素之间的连接信息

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      bool agrees(byte[] p1, byte[] p2, int dx, int dy) // 图案之间各方向的可能性判断，边界像素完全相同为 true
      {
          int xmin = dx < 0 ? 0 : dx, xmax = dx < 0 ? dx + N : N, ymin = dy < 0 ? 0 : dy, ymax = dy < 0 ? dy + N : N;
          for (int y = ymin; y < ymax; y++) for (int x = xmin; x < xmax; x++) if (p1[x + N * y] != p2[x - dx + N * (y - dy)]) return false;
          return true;
      };

      propagator = new int[4][][]; // 每个方向 每个图案 可连接的图案索引
      for (int d = 0; d < 4; d++)
      {
          propagator[d] = new int[T][];
          for (int t = 0; t < T; t++)
          {
              List<int> list = new List<int>();
              for (int t2 = 0; t2 < T; t2++) if (agrees(patterns[t], patterns[t2], DX[d], DY[d])) list.Add(t2);
              propagator[d][t] = new int[list.Count];
              for (int c = 0; c < list.Count; c++) propagator[d][t][c] = list[c];
          }
      }

  • Tiles

    • 图集中全部元素的连接数据文件

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      <set size="10">
          <tiles>
          <tile name="corner" symmetry="L" weight="0.5"/>
          <tile name="cross" symmetry="I"/>
          <tile name="empty" symmetry="X"/>
          <tile name="line" symmetry="I"/>
          <tile name="t" symmetry="T"/>
          </tiles>
          <neighbors>
          <neighbor left="corner 1" right="empty"/>
          <neighbor left="corner" right="cross"/>
          <neighbor left="corner" right="cross 1"/>
          <neighbor left="corner" right="line"/>
          <neighbor left="corner 1" right="line 1"/>
          ...
          <neighbor left="t 1" right="t"/>
          <neighbor left="t 3" right="t 1"/>
          </neighbors>
      </set>

    • 对称类型

      通过不同的对称类型（X、L、T、I、/），来描述不同方向的连接信息是否可以统一

    • 通过旋转、镜像扩充原始数据集，通过索引代替对原始数据的操作

      不同对称类型经过旋转、镜像操作的全部图案

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      64
      65
      66
      67
      68
      69
      70
      71
      72
      73
      74
      75
      76
      77
      78
      79
      80
      81
      82
      83
      84
      85
      86
      87
      88
      89
      90
      91
      92
      93
      foreach (XElement xtile in xroot.Element("tiles").Elements("tile"))
      {
          string tilename = xtile.Get<string>("name");
          if (subset != null && !subset.Contains(tilename)) continue;

          Func<int, int> a, b; // a "逆时针旋转90°" b "水平镜像" 对8张图的索引进行变换
          int cardinality; // 集合的势，简单来说表示对称类型下全部图案（旋转、镜像）后

          char sym = xtile.Get("symmetry", 'X');
          if (sym == 'L') // 每两个相邻互为镜像
          {
              cardinality = 4; 
              a = i => (i + 1) % 4; // 循环取下一个索引的图案
              b = i => i % 2 == 0 ? i + 1 : i - 1; // 奇数索引取下一个，偶数索引取上一个
          }
          else if (sym == 'T')
          {
              cardinality = 4;
              a = i => (i + 1) % 4;
              b = i => i % 2 == 0 ? i : 4 - i;
          }
          else if (sym == 'I')
          {
              cardinality = 2;
              a = i => 1 - i;
              b = i => i;
          }
          else if (sym == '\\')
          {
              cardinality = 2;
              a = i => 1 - i;
              b = i => 1 - i;
          }
          else if (sym == 'F')
          {
              cardinality = 8;
              a = i => i < 4 ? (i + 1) % 4 : 4 + (i - 1) % 4;
              b = i => i < 4 ? i + 4 : i - 4;
          }
          else
          {
              cardinality = 1;
              a = i => i;
              b = i => i;
          }

          T = action.Count;
          firstOccurrence.Add(tilename, T); // 累加

          int[][] map = new int[cardinality][];
          for (int t = 0; t < cardinality; t++)
          {
              map[t] = new int[8]; // t、t逆时针90、t逆时针180、t逆时针270、t镜像、t逆时针90镜像、t逆时针180镜像、t逆时针270镜像

              map[t][0] = t; // 对 tiles 表的索引
              map[t][1] = a(t);
              map[t][2] = a(a(t));
              map[t][3] = a(a(a(t)));
              map[t][4] = b(t);
              map[t][5] = b(a(t));
              map[t][6] = b(a(a(t)));
              map[t][7] = b(a(a(a(t))));

              for (int s = 0; s < 8; s++) map[t][s] += T; // 偏移，

              action.Add(map[t]);
          }

          if (unique) // 表示图集中对称元素旋转后用到的图案不同
          {
              for (int t = 0; t < cardinality; t++)
              {
                  Bitmap bitmap = new Bitmap($"samples/{name}/{tilename} {t}.png");
                  tiles.Add(tile((x, y) => bitmap.GetPixel(x, y)));
                  tilenames.Add($"{tilename} {t}");
              }
          }
          else
          {
              Bitmap bitmap = new Bitmap($"samples/{name}/{tilename}.png");
              tiles.Add(tile((x, y) => bitmap.GetPixel(x, y)));
              tilenames.Add($"{tilename} 0");

              for (int t = 1; t < cardinality; t++)
              {
                  if (t <= 3) tiles.Add(rotate(tiles[T + t - 1]));
                  if (t >= 4) tiles.Add(reflect(tiles[T + t - 4]));
                  tilenames.Add($"{tilename} {t}");
              }
          }

          for (int t = 0; t < cardinality; t++) tempStationary.Add(xtile.Get("weight", 1.0f));
      }

    • 通过xml数据得到邻接元素之间的连接信息

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      propagator = new int[4][][];
      var tempPropagator = new bool[4][][]; //存储了所有状态之间的兼容情况是true还是false，[d][t1][t2] -> t1在d方向上能否与t2兼容 -> t2在d的反方向(opposite[d])上与t1兼容
      for (int d = 0; d < 4; d++)
      {
          tempPropagator[d] = new bool[T][];
          propagator[d] = new int[T][];
          for (int t = 0; t < T; t++) tempPropagator[d][t] = new bool[T];
      }

      foreach (XElement xneighbor in xroot.Element("neighbors").Elements("neighbor")) // 通过读表来初始化 propagator 数组
      {
          string[] left = xneighbor.Get<string>("left").Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries); // 只关注每种图案（原图案的衍生）的左右邻接
          string[] right = xneighbor.Get<string>("right").Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);

          if (subset != null && (!subset.Contains(left[0]) || !subset.Contains(right[0]))) continue;

          // firstOccurrence 取出原图案在 action 中的位置
          // xml 中的 left 和 right 是相互约束的

          int L = action[firstOccurrence[left[0]]][left.Length == 1 ? 0 : int.Parse(left[1])], D = action[L][1]; // L对应的图案逆时针90度
          int R = action[firstOccurrence[right[0]]][right.Length == 1 ? 0 : int.Parse(right[1])], U = action[R][1]; // R对应的图案逆时针90度

          tempPropagator[0][R][L] = true; // R 放在右边 与 L 放在左边 可以相连
          tempPropagator[0][action[R][6]][action[L][6]] = true; // R "逆时针180度并镜像" 放在右边 与 L "逆时针180度并镜像" 放在左边 可以相连
          tempPropagator[0][action[L][4]][action[R][4]] = true; // L "镜像" 放在右边 与 R "镜像" 放在左边 可以相连
          tempPropagator[0][action[L][2]][action[R][2]] = true; // L "逆时针180" 放在右边 与 R "逆时针180" 放在左边 可以相连

          tempPropagator[1][U][D] = true;
          tempPropagator[1][action[D][6]][action[U][6]] = true;
          tempPropagator[1][action[U][4]][action[D][4]] = true;
          tempPropagator[1][action[D][2]][action[U][2]] = true;
      }

      for (int t2 = 0; t2 < T; t2++) for (int t1 = 0; t1 < T; t1++)
      {
          tempPropagator[2][t2][t1] = tempPropagator[0][t1][t2]; // 更新方向反向的情况
          tempPropagator[3][t2][t1] = tempPropagator[1][t1][t2];
      }

      List<int>[][] sparsePropagator = new List<int>[4][]; // Propagator的稀疏表示
      for (int d = 0; d < 4; d++)
      {
          sparsePropagator[d] = new List<int>[T];
          for (int t = 0; t < T; t++) sparsePropagator[d][t] = new List<int>();
      }

      for (int d = 0; d < 4; d++) for (int t1 = 0; t1 < T; t1++)
      {
          List<int> sp = sparsePropagator[d][t1];
          bool[] tp = tempPropagator[d][t1];

          for (int t2 = 0; t2 < T; t2++) if (tp[t2]) sp.Add(t2); // 统计全部兼容图案索引

          int ST = sp.Count;
          if (ST == 0) Console.WriteLine($"ERROR: tile {tilenames[t1]} has no neighbors in direction {d}");
          propagator[d][t1] = new int[ST];
          for (int st = 0; st < ST; st++) propagator[d][t1][st] = sp[st];
      }

2.5 Unity Demo

通过 prefab 之间的连接约束，得到邻接约束信息，在线或离线地进行过程化生成。