作者 Sean Barrett
来自 Silver Spaceship Software
原文

在这篇文章中我将阐述一种对于王氏网格(Wang Tile)技术的扩展，它使用许多小2D区域生成大的2D区域。我将其命名为斜拼王氏网格(Herringbone Wang Tiles)。它也特指由Sucker Punch制作的《Infamous》的地图生成系统。

在我2010做的一个没发布的CRPG游戏里，我用了一种特别简单的地牢地图生成方式。它用小方块地格去拼成大的地图，这些小的方块从预制的128种中选出(这128个地格由传统意义上的tile拼出来，为了避免歧义这里叫他们精灵(sprites))。这个地图生成算法特别简陋：每个地格都是随机生成的，即没有关于相邻地格的约束，也没有关于连通性的约束。

让它变得可用的主要技术是一个与众不同的斜拼方法，在把小2D方格拼成大块时，这个技术能够降低规则方格的可见程度，并且带来比啥都不做好一些的连通性。

另一种我没用的技术是拼图颜色(jigsaw colors)。它可以是的地格边缘的形状改变，以此来打破常规拼贴方式带来的长直边。因为我没有用它所有也就不再谈论了。

王氏网格(Wang Tile)

这个技术的核心思想是基于王氏网格的。它直接生成有许多边界约束的小地格，把地格放在适合他们现有边界约束的地方，然后生成一张地图。边界约束是最主要的特征；比方说去生成一张有联通性约束的mostly-solid(译者：大部分是固体/固定？)的地图，比如说地牢，你也许会想：“规则1，每个边界的中间都有一个1米宽的门”。你也许也会有对于其它属性的约束，比方说渲染属性，高度属性之类的。

在王氏网格(Wang Tile)中，你可以使用一个简单的从左往右，从上到下的生成器。在生成的每一步中，你需要挑选一个地格，它要满足至多两条边界的限制(也就是说，它需要需要满足毗邻的已生成的地格的约束)，这时你需要满足四种约束情况。只要你对于每种情况都有至少一个地格以供选择，就能生成一张大地图了。

当然，你也需要更多的备选项来防止重复。

一条得到“最佳”结果的原则是，你必应该对每种情况都有足够的地格，以便可以拥有“输出”边的所有可能组合；这使得给出位置的地格的选择被限制在了仅影响了它当前的邻居；这对更远的地格的选择没有影响。对于两种边界变化来说，这意味着最少有16个预制地格。对于三种变化来说，这意味着最少81种地格，这似乎太过了。我会称呼这种地格的组合为“完全随机组合”。

这是一篇使用王氏网格的经典文章，Wang Tiles for Image and Texture Generation (作者：Cohen et al)，每种规则仅仅使用了2个图块；例如，有3种边界变化的话，就总有9种情况，那他们就只用了18种图块。它对为什么这样就能有足够好的结果做出解释，也没有给出如何通过特定数目的的约束来构造一个好的图块集合的机制。很明显，每一步有两种图块选择给予了我们一些随机选择的空间，也让生成结果不会有周期性；但它不是一定要最小化的，也不是很明显如何选择一组好的“输出”边缘给每个情况，来保证生成的内容分布良好。

作为对比，完全随机的组合虽然需要更多的内容，但它不需要对生成过程进行干预。

大的网格

有时候放入一些“特别内容”是很有用的，这些内容会比一般的单个网格大不少。对于纹理生成来说，这可能是一些特别出现的组合；对城市生成来说，可能是一个会覆盖不止一个寻常地格的巨大会议中心；对地牢来说，它可能是一个巨大的洞穴。这种特殊的区域会覆盖等同于多个一般地格所占据的区域；也许是2×1大小，1×2大小，3×4大小，乃至于不规则大小的格子。对于王氏网格来说，这处理起来很简单；比如处理一个2×1大小的格子时，将它分成两个1×1的格子并在他们彼此边界中间引入一种全新的规则(颜色)。这样当你放置了其中一个格子之后就只能拜访剩下的那一个来完成生成。

但是，它在上述的完全随机生成中却会不生效。一旦你放下了第一个格子，你就已经使用了一种对于临近方格的独特约束，但这时候已经有了先前生成的行的方块的另一种约束(译者：就是上面一行或者左边一列先生成了的话)，如果第二个方格与已经存在的约束不匹配，整个生成讲无法完成。

其中一种解决方案是，第二个格子可以有一系列的变化；假如有了三种可能的边界约束，那么第二个格子就需要三个变种。鉴于此处的目的是创作特殊的“仅一次”内容，这似乎是一个重大负担，但在某些情况下它可能是可行的。

第二种方法是不使用这种算法来生成大格子。我们可以在一开始先放置特殊的大格子，替代原先从左往右，从上到下的的生成顺序。(既然没有使用一般的王氏网格的处理方案，那我们也不需要引入特别的规则(颜色)来来保证他们生成在一起；简单的放下他们即可)之后再按照规则填充剩下的地图即可。(译者：因为是“完全随机组合”所以不可能会有没法填充的问题，下面也提到了)

目前尚不清楚如何编写一个高效的求解器来满足现有约束并生成有效的平铺，因为这是个NP完全问题(???)。对于王氏网格上面的方法之所以有效是因为它没有额外的约束，从设计之初就订好了。

但是，如果你用了完全随机组合，这个填充算法就很简单啦，因为我们保证对于每一种边的组合我们都有一个方块。所以回到从左往右，从上到下的的生成中去，只要注意一下额外的由已被放置的方块生成的的约束即可。

正因如此，我相信完全随机组合是一种重要且值得的实现王氏网格的方式；尽管这个方式微不足道，也没有什么文献讨论了它的好处，总而言之，好处是：

保证格子的选择不会影响超过它邻居的范围
简单地支持在随机生成之前预先放置常规瓷砖和大瓷砖

坏处则是大量的内容需求(比方说：两种边界约束要16种格子，三种则要81种格子)。尽管如此，如果它需要的内容量与您想要生成的内容量相同，那么完整的随机集因此特别值得使用。（比方说你觉得你要创建64个预制的格子用三种边界约束，那就不如创建81个）

旋转

允许格子旋转或者镜像也是可能的。然而，这使边缘约束的性质变得复杂；当旋转90度的时候，水平的边界约束必须与垂直的相同。如果镜像（或者180度旋转），边界约束也必须对称。它的优势则是，如果旋转或镜像可以使用的话，地格需要的最小数量将会降低。（我没有算这能减少到多少）

王氏网格的问题

当使用王氏网格生成地图或者数据时，一些artifact必须被注意。一个artifact由格子形式的布局引起；边界都是以直线的方式排布的，所以如果有些边界有特别的特征或者特定的偏向，这个直线能够被很轻松的看出来。比方说，在我的应用里，地图中的大多数地区是开放的而不是封闭的，但边界一定是关闭的。这导致了明显的网格状的“更强的封闭性”。

我的应用的第二个问题涉及地图的联通性。如果每个边约束都控制着“走廊”在格子之间的连接方式，并且我们将自己限制在足够小的瓦片上，以至于每条边只能有一个走廊，那么我们将面临两个联通性问题：跟踪边界如何在内部连接，以及判断整个地图是完全联通的。

我们能让每个格子在内部是完全联通的，这样我们就不需要特别的去追踪每一个了。这么做的话，地图就是完全联通的，但这样的话就有太多一样的连接了。我们能通过假如一种叫“不连接”的边界约束来处理这个问题。（这又会使得需要的格子增加了）接着，在生成的时候，我们就能用一些联通性检查算法来确保所有的东西连着；比方说某种迷宫生成算法。

六边形网格

另一种可能是去使用六边形网格，就像SuckerPunch的声名狼藉中一样。(译者：本来有链接但是失效了)使用六边形网格进行随机生成时，三条边被约束住了而剩下的三条就能自由选择了。在无法选装且仅有两种边界变化时，它需要8种情况和16种网格，或者64种网格来形成完全随机组合。(在声名狼藉中，SuckerPunch想必允许了旋转并似乎有四种以上的边界约束，但他们是手动组合的所以可以较好的限制预知地格的数量)

人字形网格

在我2010没完成的那个CRPG游戏里，我尝试去去解决由王室网格引起的问题，通过开发一种我称为人字形网格的变种。人字形网格使用2:1或1:2的网格。

下面的图片展示了一般的人字形网格图案：

就像在图案中看到的，矩形的每条边都以固定的方式接触；垂直矩形的右边上半条边总是紧靠在水平矩形的左边上；而右边下半条边总是紧靠在另一个矩形的左边上半条边上。

也就是说，我们能区分出6种“边界组合”在这样的固定方式下，就像王氏网格中的上线边界区别一样。事实上，人字形网格与王氏网格是同构的；每个矩形都能被视作是一个六边形，这个六边形边长是固定的而转角被挤压到了九十度。

方块有两种不同的边界朝向(水平和垂直)，而六边形有三种不同的朝向(水平，正120度，负120度)。人字形网格则有六种不同的边界“朝向”，因为水平和垂直的各自混合制造了更多的组合上的区别。

无论如何，每个格子只有六条边，所以随机生成所需要的格子数量和六边形仍是一致的，但因为有两种朝向的关系这里会翻倍。

(原文计算了格子的数量，这里使用我觉得更好的方式表达)
假设有两种边界约束条件(每边有且只有一种约束)：
完全或然需要64种格子，且横竖不同需要翻倍
(原文没有使用旋转来优化数量限制)
假如加入旋转的话 (两种边界条件)14种 (3种边界条件)130种，
假如加入镜像的话 (两种边界条件)13种 (3种边界条件)92种，
再往上超出一千了建议换成其它算法
(暴力算的) 代码如下

    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("输入六边形边界种类n:");
            int n = int.Parse(Console.ReadLine());
            Console.WriteLine("是否镜像(y/n):");
            bool isCouldMirror = Console.ReadLine() == "y";

            List<Hex> hexList = new List<Hex>();
            List<Hex> answerHexList = new List<Hex>();

            for (int a1 = 0; a1 < n; a1++)
            {
                for (int a2 = 0; a2 < n; a2++)
                {
                    for (int a3 = 0; a3 < n; a3++)
                    {
                        for (int a4 = 0; a4 < n; a4++)
                        {
                            for (int a5 = 0; a5 < n; a5++)
                            {
                                for (int a6 = 0; a6 < n; a6++)
                                {
                                    hexList.Add(new Hex(a1,a2,a3,a4,a5,a6));
                                }
                            }
                        }
                    }
                }
            }

            answerHexList.Add(hexList[0]);
            foreach (Hex hex in hexList)
            {
                int startSize = answerHexList.Count;
                bool isSame = false;
                for (int i = 0; i < startSize; i++)
                {
                    var answerHex = answerHexList[i];
                    for (int j = 0; j <= 6; j++)
                    {
                        if (hex == answerHex)
                        {
                            isSame = true;
                            break;
                        }
                        hex.Rotate(1);
                    }
                    if (isSame)
                        break;
                }
                if (!isSame && isCouldMirror)
                {
                    hex.Mirror();
                    for (int i = 0; i < startSize; i++)
                    {
                        var answerHex = answerHexList[i];
                        for (int j = 0; j <= 6; j++)
                        {
                            if (hex == answerHex)
                            {
                                isSame = true;
                                break;
                            }
                            hex.Rotate(1);
                        }
                        if (isSame)
                            break;
                    }
                }
                if (!isSame)
                {
                    answerHexList.Add(hex);
                }
            }
            Console.WriteLine(string.Format("完全或然组合有{0}个六边形", answerHexList.Count) );
            foreach (var item in answerHexList)
            {
                Console.WriteLine(string.Format("{0} {1} {2} {3} {4} {5}"
                    , item.typeArray[0]
                    , item.typeArray[1]
                    , item.typeArray[2]
                    , item.typeArray[3]
                    , item.typeArray[4]
                    , item.typeArray[5]));
            }
        }
    }


    class Hex
    {
        public int[] typeArray = new int[6];
        public Hex(int a1, int a2, int a3, int a4, int a5, int a6)
        {
            typeArray[0] = a1;
            typeArray[1] = a2;
            typeArray[2] = a3;
            typeArray[3] = a4;
            typeArray[4] = a5;
            typeArray[5] = a6;
        }

        public override bool Equals(object obj)
        {
            return obj is Hex hex &&
                   EqualityComparer<int[]>.Default.Equals(typeArray, hex.typeArray);
        }

        public override int GetHashCode()
        {
            return HashCode.Combine(typeArray);
        }

        public void Rotate(int r)
        {
            if (r == 0)
            {
                return;
            }
            if (r < 0 || r > 6)
            {
                Console.WriteLine("不支持的旋转");
                return;
            }

            int[] temp = new int[6];
            for (int i = 0; i < 6; i++)
            {
                temp[i] = typeArray[(i+r)%6];
            }
            typeArray = temp;
        }

        public void Mirror()
        {
            Array.Reverse(typeArray);
        }

        public static bool operator ==(Hex a,Hex b)
        {
            for (int i = 0; i < 6; i++)
            {
                if (a.typeArray[i] != b.typeArray[i])
                {
                    return false;
                }
            }
            return true;
        }
        public static bool operator !=(Hex a, Hex b)
        {
            for (int i = 0; i < 6; i++)
            {
                if (a.typeArray[i] != b.typeArray[i])
                {
                    return true;
                }
            }
            return false;
        }
    }

这里是我用来生成地牢的128个图块