« 我们的手游 陌陌争霸 终于上线了 | 返回首页 | COC Like 游戏中的寻路算法 »

斜视角游戏的地图渲染

这篇文章是在大半年前, 我们的手游 刚刚做预研的时候写给公司内部分享的。由于这个项目公司不希望在开发阶段对外暴露信息,所以文章也没有在 blog 贴出来。

现在游戏已经上线 就没有消息保密的需求了,我就可以把当初开发时写的一些东西逐步贴出来。


所谓类似 COC 这样的斜视角引擎,在英文社区中叫作 Isometric Tileset Engine。它在早期计算资源匮乏的年代用的很多,后来内存不是问题了后,就很少有人用了。由于没有 Z-Buffer ,这种引擎的绘制次序其实很讲究。比如下图:

            /\
           /  \
          /    \
         /     / /\
  /\    /  B  / /C \
 /A \  /     /  \  /
 \  / /     /    \/
  \/ /     /
     \    /
      \  /
       \/

如果 A B C 三个菱形标识了三个物件的基座块的话,它们的正确绘制次序是怎样的呢?

在没有 Z-Buffer 的支持时,我们需要利用画家算法从后向前绘制。那么就是先画 A 再画 B ,最后画 C 。(我们设想一下 A B C 都有一定高度,那么 B 会挡住 A ,C 会挡住 B 。

那么,A 和 C 之间,是不是一定是先 A 再 C 呢?答案是不一定,这取决于 B 的摆放。比如 A C 位置不变,而 B 是这个样子:

        /\  
       /  \    
      /    \    
     /      \    /\
  /\ \    B  \  /C \
 /A \ \       \ \  /
 \  /  \       \ \/
  \/    \      /
         \    /
          \  /
           \/

就需要先画 C 再画 B ,最后画 A 了。

也就是说,两个物件的绘制次序,单靠每个物件自己的空间坐标来排序是不够的。

(Ps. 如果所有物件都是正方形则不会出现这种情况,按对称中心排序即可。)

那应该怎样做呢?事实上,在 Isometric Tileset Engine 中,任意两个物件的绘制次序有三种状态:A 在 B 的前面,A 在 B 的后面;A 和 B 无关。

每个基座为菱形的物件 A,它向上都可以延伸出一个扇面,在这个扇面之类的物件都必须在它之前绘制。

\............../
 \....扇面..../
  \........../
   \......../
    \../\../
     \/A \/
      \  /
       \/

如果两个物件 A 和 B ,A 不在 B 的扇面内,B 也不在 A 的扇面内,就认为 A 和 B 无关。

一个简单的方法是,利用所有物件之间的关系做一次冒泡排序。一遍扫描出一个物件,它在所有物件之前,或是跟其它物件无关,把它放在第一位绘制;然后依次处理剩下的物件即可。

这个方法很好理解,但是时间复杂度偏高。

另一种方法不需要排序,但是实现略微复杂一些。为了好描述,我把地图旋转 45 度,变成正方形的方便解说。假如有如下场景。

             +-+
      +---+  |C|
      | B |  +-+
 +-+  |   |   
 |A|  +---+  
 +-+

如果我们顺时针旋转 45 度就和第一张图类似了。我们需要按 A B C 的次序绘制。

现在从第一行开始从左到右扫描,直到碰到第一个东西 C :

 ----------> +-+
      +---+  |C|
      | B |  +-+
 +-+  |   |   
 |A|  +---+  
 +-+

检查 C 的左边是否全部被触碰过,如果没有,就把 C 压入一个临时堆栈,然后另起一行重复前面的过程。但不要扫描已扫描过的区域。

如果 C 的左边全部被触碰过,则可以绘制 C ,然后从 C 的右边继续这个过程。

 ............+-+
 .... +---+  |C|
 ---> | B |  +-+
 +-+  |   |   
 |A|  +---+  
 +-+

按照这个规则,我们会发现 A 最先被处理掉,然后是 B 最后是 C 。因为 B 的下半部分被 A 挡住,所以 A 不处理完之前, B 一定在堆栈中。

这个堆栈的最大深度不会超过总行数。而扫描永远是从左向右的,只需要一个和行数相同的数组就可以保存下已经扫描过的位置。这个算法的时间复杂度以及空间复杂度都是 O(n) 的。我大约用了 60 行 C 代码实现了这个过程。

看完这个绘制过程,就知道,如果需要把场景正确的出来,需要知道地图上有哪些东西,它们是什么,它们在哪里,它们有多大。其它的信息是不必要的。

所以,我为这个需求设计了一个简单的数据结构,服务于绘制流程以及后面会提到的生成寻路图。

管理绘制次序只有一个 API ,就是从一个坐标取下一个需要绘制的对象所在的坐标。这个 API 所需要用到的数据,只要是一个 2D 数组,数组上的每个元素可以表明所在位置的建筑的尺寸就可以了。

Comments

找到云风一篇好旧的文章:https://www.codingnow.com/isomtric/isotile.htm 。敬佩。

照着实现了,很好用.

第一种情况,如果是另一个物件横跨在扇面左边或者扇面右边呢

有向无环图的拓扑排序

拓扑排序正解

@lee

如果你搞不明白,就让所有单位都是正方形的,然后按中心点高低排序即可。

只有长方形才需要用到上文中的算法。

这个两年前的帖子不知道你还记不记得了。我用了冒泡排序但是出来的层级是不对的。第二种复杂一点的办法不是很能理解。这个问题已经困扰我很久了,不知道能不能指点一下啊?

为什么不用拓扑排序呢?

难道不是按底座面积中点坐标相加后排序么?
(中点所在行+中点所在列)

很久以前就在玩斜视角游戏,我个人觉得玩多了斜视角游戏对视力有一定影响.其次斜视角游戏的3D引擎应该有转角功能,可以在小范围内转动.

特意看了一下楼主的游戏,如果所有建筑都是1*1,2*2,3*3,4*4,5*5这种形式的,情况就非常简单了.

很巧妙.但还是感觉排序更好,关键就是处理那些"不确定"谁先谁后的对象即可.即楼主例子里的a和c

你好,我的游戏也在解决同样的问题,这个问题困扰了我很久,我也在上面花了大量的时间。看了这个我知道我该怎么做饿了。

为啥不把B这种大块的物件按标准菱形大小,沿纵轴裁分,然后排序问题变得超级简单,按格子顺序,从头到尾画一遍就行了,COC类的东西,物件都是按格子摆放的,裁分也可以由程序自动完成。

@一楼的。先看懂文章再提问,总感觉玷污了这里。

既然有Z-Buffer,为什么还需要斜视角排序咧?

Post a comment

非这个主题相关的留言请到:留言本