斜拼地格(Herringbone Tiles)

2023-11-22 16:59
文章标签 tiles 地格 herringbone

本文主要是介绍斜拼地格(Herringbone Tiles),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

斜拼地格(Herringbone Tiles)

作者 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种图块。它对为什么这样就能有足够好的结果做出解释,也没有给出如何通过特定数目的的约束来构造一个好的图块集合的机制。很明显,每一步有两种图块选择给予了我们一些随机选择的空间,也让生成结果不会有周期性;但它不是一定要最小化的,也不是很明显如何选择一组好的“输出”边缘给每个情况,来保证生成的内容分布良好。

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

大的网格

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

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

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

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

目前尚不清楚如何编写一个高效的求解器来满足现有约束并生成有效的平铺,因为这是个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个图块

每条边有两种情况(一个宽的通道或者一个短的通道),就算用了错误的匹配形式,但结果看起来尚可,所以约束基本上是被忽略的。(如果我把通道放在边缘的不同位置,这就不起作用了)

这是一个使用人字形网格进行地牢生成的例子。

因为要放置一些额外的程序化生成的元素(如家具、地板),所以还有一些额外的变化。

正由于生成的随机性,所以看起来非常不连贯。(由于视野的限制,所以玩家看不出来,嘻嘻。这对游戏的设计也没有什么影响)

但是,仍然有一部分需要注意:

  • 尽管你还是能够找到长长的像墙一样的边界,但它们不相互连接。这是因为人字形样式打破了边界。

  • 总体的区域间连通性是非常复杂的。
    在有复杂连通性时,写一个地牢生成算法并不困难。但是,地牢生成时每个格子的选择都是独立的,与其他每一个格子无关。

使用人字形网格给连通性带来了一个小的技巧:每一个格子能够被看作两个方格,方格中间连不连通是可以设计的,就像128个图块左上角的那个图块一样。

如果内部没有连通,那连通性看起来如下图所示:

值得一提的是,这保证了完全的连通性,没有无法到达的图块生成,尽管有的时候需要绕路。

这篇关于斜拼地格(Herringbone Tiles)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:https://blog.csdn.net/qq_21958271/article/details/120114570
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/411585

相关文章

Apache Tiles 布局管理器

陈科肇 =========== 1.简介 一个免费的开源模板框架现代Java应用程序。  基于该复合图案它是建立以简化的用户界面的开发。 对于复杂的网站,它仍然最简单,最优雅的方式来一起工作的任何MVC技术。 Tiles允许作者定义页面片段可被组装成在运行一个完整的网页。  这些片段,或Tiles,可以用于为了降低公共页面元素的重复,简单地包括或嵌入在其它瓦片,制定了一系列可重复使用

three.js使用3DTilesRendererJS加载3d tiles数据

原生的 three.js 目前不支持 3d tiles 数据的加载,不过开源社区已经给出了一些解决方案,其中最活跃的要属 3DTilesRendererJS。它为 three.js 提供了加载和调度 3d tiles 数据的基本能力,虽说和 Cesium.js 对 3d tiles 的支持相比还有很大的差距,但也比没有的好。毕竟 3d tiles 数据的加载和调度还是比较复杂的,要自己写也没那么容

openlayers官方教程(十一)Vector Tiles——The VectorTile layer

The VectorTile layer 我们已经知道如何载入瓦片图片,并且能够用不同的方法载入渲染矢量地图。但是我们如何能够用传输到浏览器更快的瓦片的同时,能够样式化数据?这就是矢量瓦片的作用,openLayer通过vectorTile层来支持矢量瓦片。 A world map rendered from vector data 同样需要在index.html中定义基础的东西:

Gym - 101485IIdentifying Map Tiles (递推)

题目大意:给一个字符串,求它是在第几个图中的哪个位置,每个图与相邻图之间关系都类似于细胞分裂(大概是这么个意思) 找到0123的在田字格的位置关系,递增的时候也是这样的规律,所以按字符串每个字母来推测它是如何得到的,便能得到位置了 建议先以(1,1)为起点来递推方便理解,最后结果减一就好了 代码 #include<iostream>#include<cstring>#include

地图图源#ESRI ArcGIS XYZ Tiles系列(TMS)

目录 1、前言 2、地图图源网址 2.1、Satellite 卫星图源 2.2、Terrain 地形图源 2.3、Street 路网/标注图源 2.4、Specifity 特色设计图源 3、专业推荐”穿搭“ 4、图源配置下载及使用 图源名称图层类别特别注意谷歌 Google①地形 ②影像 ③矢量及标注 ④特色图源国内大矢量路网偏移 卫星实景三维模型必应 Bing①影像

Struts1.2、Struts1.3和Struts2.0下Tiles的配置

struts和Tiles配置取决于两者的版本,就是所需的配置文件和文件的写法有些不同。   Struts1.2和Tiles1.2: 如果使用MyEclipse自带的Struts1.2,那么就是使用自带的Tiles1.2   1.将struts.jar下META-INF/tlds/struts-tiles.tld文件复制到WebRoot/WEB_INF下,这是tiles语法解析文件;在we

Tiles配置问题

Struts配置Tiles郁闷的问题2007-12-10 11:24ERROR - Can't create Tiles definition factory for module ''.ERROR - Unable to initialize Struts ActionServlet due to an unexpected exception or error thrown, so marki

3D Tiles语义分割流水线

Dylan Chua 和 Anne Lee 开发了一个处理管线,用于对 3D Tiles 中包含的 GL 传输格式 (glTF) 模型进行语义分割。 该管道读取并遍历 3D Tileset,以输出包含元数据的经过转换的划分对象集。 该项目为 3D 语义分割器提供了最小可行产品,作为各种应用程序的概念验证。 他们接受模拟和培训系统中心首席工程师 How Chang Hong 的指导。 1、动机

tiles框架(转载)

Tiles 框架增强了基于组件的 Web UI 开发的设计,它和 Struts 框架的组合工作得很好。您可以很容易的协同 WebShpere Studio 使用 Tiles 和 Struts 框架以显著降低您的 Web 开发工程的开发时间和维护代价。 © Copyright International Business Machines Corporation 2003. All rights

Eclipse jsp Struts tiles 开发实例

Step1  lms-tiles-defs-fa-finalaccount.xml Path: C:/eclipse/workspace/lscn/web/WEB-INF/tiles/lms-tiles-defs-fa-finalaccount.xml <?xml version="1.0" encoding="ISO-8859-1" ?> <!DOCTYPE tiles-definitio