« 我们的手游 陌陌争霸 终于上线了 | 返回首页 | 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 数组，数组上的每个元素可以表明所在位置的建筑的尺寸就可以了。

云风 提交于 January 11, 2014 04:47 PM |

Comments

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

Posted by: tna | (16) December 11, 2023 04:06 PM

照着实现了，很好用.

Posted by: kyrn | (15) July 19, 2023 04:37 PM

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

Posted by: 何吓吓 | (14) December 15, 2021 07:23 PM

有向无环图的拓扑排序

Posted by: 海的味道 | (13) December 23, 2019 10:46 AM

拓扑排序正解

Posted by: Jaden | (12) November 18, 2016 04:11 PM

@lee 如果你搞不明白，就让所有单位都是正方形的，然后按中心点高低排序即可。 只有长方形才需要用到上文中的算法。

Posted by: Cloud | (11) August 19, 2016 02:03 PM

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

Posted by: lee | (10) August 18, 2016 05:51 PM

为什么不用拓扑排序呢?

Posted by: noname | (9) November 28, 2014 09:51 PM

难道不是按底座面积中点坐标相加后排序么？ （中点所在行＋中点所在列）

Posted by: pig345 | (8) November 18, 2014 07:57 PM

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

Posted by: icicle | (7) February 12, 2014 10:08 PM

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

Posted by: 大德 | (6) January 27, 2014 05:54 PM

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

Posted by: 大德 | (5) January 27, 2014 03:13 PM

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

Posted by: 史蒂芬森 | (4) January 20, 2014 10:08 AM

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

Posted by: spe | (3) January 13, 2014 05:30 PM

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

Posted by: Rooker | (2) January 12, 2014 12:41 PM

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

Posted by: h00w | (1) January 11, 2014 05:31 PM

Post a comment

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