游戏引擎学习第299天:改进排序键 第二部分

回顾并为当天内容做准备

我们会现场编写完整的游戏代码。回顾上周发现自己对游戏中正确的排序规则并没有清晰的理解。主要原因是我们更擅长三维游戏开发，缺乏二维游戏和二维游戏技术的经验，对于二维精灵排序、模拟三维效果的最佳方案等没有太多技巧和经验。

因此，今天的目标是专注于研究和理清二维游戏中的Z轴排序问题。我们希望通过深入思考，理解各种排序方案的权衡，找到在大多数情况下能够产生最佳效果且最少依赖临时解决办法的规则。

黑板讲解：瓦片的Z轴排序

目前我们关注的是在同一层内的排序问题，假设不同层可以单独排序。游戏中的房间被划分成若干离散的部分，这些部分会分别淡入显示。在一个具体的房间内，我们重点考虑瓷砖的排序方式。

开始思考时，我们想到了如何合理地对这些瓷砖进行排序，使得视觉上符合预期效果。重点是处理好瓷砖之间在同一层中的先后关系，而不是跨层排序。这样可以保证房间内部的图层渲染顺序正确，同时也方便整体房间在不同层之间进行排序和切换。

黑板讲解：从正上方俯视时如何进行排序

我们分析了从完全正上方（100%俯视角度）观察瓷砖时的排序规则。在这种视角下，我们可以非常清楚地知道，排序只需要根据物体的最高Z值来进行。因为瓷砖之间不会相互重叠，只会有高低关系，所以只要按照角色或精灵的最高点的Z值排序，就能得到正确的视觉效果。最高的Z点决定了哪个物体会被看到。

然而，情况变得复杂的是当摄像机稍微倾斜时。虽然在完全俯视时排序相对简单，但倾斜后物体会跨越多个瓷砖，导致排序不再那么直接。此时，我们可能会遇到精灵覆盖多个瓷砖的情况，不能单纯地按一个Z值排序。

尽管如此，大多数情况下还是可以通过对每个瓷砖和相关物体分别排序来解决问题。比如一个跨越多个瓷砖的地毯，在Z值排序中，地毯会相对这些瓷砖进行排序，任何Z值比地毯高的瓷砖会绘制在前，反之则绘制在后。虽然这可能导致一些看似不合逻辑的画面（比如地毯部分“穿透”瓷砖），但这是合理的渲染结果，因为如果地毯和瓷砖发生交叉，那就是模型本身的问题，而非渲染算法的问题。

总结来说，从正上方看，排序规则非常简单，只需按最高Z点排序；而倾斜视角带来了物体跨瓷砖的问题，但通过分别对每个瓷砖和物体排序，也能基本解决，虽然存在极少数不完美的边缘情况。

黑板讲解：相机倾斜带来的排序复杂性

问题的复杂性出现在我们不再是纯粹正上方观察物体，而是摄像机稍微倾斜的情况下。这样一来，单纯按最高Z值排序就不能保证得到正确的绘制顺序。

具体来说，虽然某个物体的最高Z值最大，按理应该最后绘制，但由于摄像机角度的变化，视线射线（viewing ray）会先遇到画面中靠前的物体，而后遇到靠后的物体。这样，单纯依据Z值排序会导致绘制顺序错误。

这个错误的原因在于，影响排序的关键维度不再只是Z轴，而是发生在Y轴方向上。假设摄像机是围绕X轴旋转的，实际上物体的距离远近更多取决于它们在Y轴上的位置。

之前尝试的解决思路是，既然摄像机倾斜，物体在Y轴上的位置其实反映了它们离摄像机的远近。最靠近的物体Y值较低，最远的Y值较高。因此，先按照Y轴从近到远排序，再按照Z轴排序，可能就能解决这个问题。

还可以进一步扩展这个排序规则，从物体离摄像机最近到最远，先根据Y值排序，再用Z值细化排序，这样有望得到合理的绘制顺序。之前对此考虑不足，这是现在需要补充和深入分析的地方。

黑板讲解：将实体量化到瓦片上

困扰我们的是，当游戏中有连续移动的实体时，排序变得复杂和混乱。因为这些实体的位置不断变化，很难判断某个实体相对于另一个实体应该如何排序。

为了解决这个问题，一个可能的办法是将实体的位置量化到它所处的瓦片（tile）中心。也就是说，在进行排序时，无论实体实际在瓦片内的哪个位置，都将其视为位于瓦片的中心点。这样，实体始终被归类到某个特定的瓦片列中进行排序。

在同一个瓦片列内，再按Z值升序排序，从而保证实体之间的正确绘制顺序。这个想法的灵感是在观察艺术资源时突然产生的，觉得或许可以解决连续移动实体排序难题。

关键点是，虽然视线会先遇到某些瓦片中的物体再遇到另一些瓦片的物体，但只要我们先将实体量化到瓦片中，然后在每个瓦片中根据Z值排序，就能较好地理清绘制顺序，避免排序混乱。

这意味着，为了让排序合理且易于管理，必须先把实体定位限制在瓦片级别，再在瓦片内进一步细化排序，这样才有可能得到一致且正确的视觉结果。

黑板讲解：地毯（Rug）问题

我们假设所有物体都被量化到瓦片大小，并且物体尺寸大致和瓦片一致，这种情况下排序应该是比较合理的。但问题在于，并不是所有物体都符合这个假设。

比如，有些物体会跨越多个瓦片，比如桌子或者地毯这样的地面覆盖物。特别是地毯这种东西，角色是可以站在它上面的，这样的物体就不能简单地被量化到单个瓦片中心去排序。

一种可能的量化方法是将这类跨瓦片的物体归到它最前面的瓦片去排序，不管具体是哪一个瓦片，关键是要和它前面的瓦片在同一行进行排序，因为X轴位置在这里是相关的。但是问题是，如果这样做，这个物体就会被绘制在后面那排瓦片的物体前面，这并不是我们想要的结果。

理想情况是，这种跨瓦片的物体应该覆盖后面那排瓦片的物体，但同时允许站在这些瓦片上的角色显示在它的上面，也就是仍然在视觉上覆盖住后面的瓦片但不遮挡站在其上的角色。

这个情况就很复杂，因为一旦涉及到跨越多个瓦片的物体，排序关系就变得难以用简单的规则表示。不能简单地说“这一堆物体都在前面，这一堆都在后面”，因为这些跨瓦片的物体实际上是在两个层次之间交叉，这种“交叉”的排序关系非常棘手。

我们可以尝试设计一种特殊的排序系统来处理这类情况，但理想的做法是找到一条智能的规则，能够合理且自动地处理这些跨越多个瓦片的物体，能够根据它们的空间关系正确地进行排序，而不是靠特殊处理。

总之，这个跨瓦片的排序问题非常复杂，现有的简单量化方案在这种情况下开始失效，需要更高级的思考和设计来解决。

黑板讲解：画家算法（Painter’s Algorithm）

我们想开始用更系统化的方法来考虑排序问题。想到的一种可能的思路是借鉴“画家算法”（Painter’s Algorithm），即排序时不仅仅简单比较Z值，而是考虑物体实际的空间形状和它们的平面如何延展，从而决定正确的绘制顺序。

具体来说，比如有一个平铺的物体，上面站着一个竖直的物体，我们可以通过知道这两个物体的Z坐标，以及它们所在的平面类型，来判断哪个应该先绘制，哪个应该后绘制。比如，竖直物体的高度随着向上延伸可能并不会变化太大，通过对平面方程的了解，我们可以更精确地进行排序。

这就回到了之前讨论的“竖直物体”和“非竖直物体”的分类问题。我们甚至可以进一步推广，给每个物体一个平面方程，根据这个方程来辅助排序。

不过，我们对这种方法是否划算持怀疑态度，感觉这条路可能比较复杂，且代价较大。我们希望能找到一种更巧妙、更聪明的排序方式，而不是简单粗暴地用物理平面计算来处理。

总之，这个思路在脑海中存在，但还不确定是否是最佳方案，仍需要进一步探索和尝试。

黑板讲解：地毯情况的多种场景

我们来详细列举一下关于地毯（rug）排序的具体情况。假设我们有四块地板瓷砖，分别标记为A、B、C、D，然后把一块地毯E放在它们上面，另外一个英雄角色F站在地毯上。理想的绘制顺序是从后到前依次绘制这些元素。具体来说：

• A和B的绘制顺序相互之间不太重要，可以互换。
• C和D的绘制顺序同样可以互换。
• 但是整体排序需要保证A、B先绘制，接着是C、D，然后是地毯E，最后绘制站在上面的英雄F。

如果我们仅考虑按瓷砖分列进行排序，比如只看B这块瓷砖，那么排序规则依然成立，可以得到正确的局部顺序 B → E → F。

问题出现在C和D之间的排序。每个瓷砖内部的排序可能正确，但当试图将所有瓷砖的排序结果合并成一个整体绘制顺序时，可能出现冲突和矛盾。

举个更复杂的例子：假设一个3D视角中，块A竖直穿过地毯E，导致地毯和A相互穿插。地毯是平铺的，穿插的块A是竖直的实体，这会导致排序变得非常困难。因为：

• 地毯E需要覆盖在C前面，
• 但是在某些排序中，A可能被绘制在E之前，
• 这就产生了不可能满足的排序冲突：E既要在C前面，又不能在A前面，这两者之间的顺序难以调和。

即使我们对每个瓷砖分别排序，整体合并时依然会遇到排序矛盾，导致无法确定一个唯一的正确绘制顺序。

可能的解决方案之一是把地毯“切割”成多块，分别排序。这虽然不一定是糟糕的主意，反而可能是合理的做法，但仍然增加了复杂性。

这也说明为什么很多2D游戏很少做复杂的3D排序。通常做法是：

• 避免在地板上放置会导致穿插的覆盖物（比如禁止地毯跨越高低不同的地砖），
• 或者根本不允许地板高度发生变化，
• 这样只用简单的Z排序就可以解决问题。

总的来说，单纯靠Z值排序在完全顶视角下非常简单且有效，但一旦涉及复杂的覆盖和穿插，排序问题就变得棘手且难以优雅解决。

或许可以尝试将Y坐标与Z坐标结合，找到一个简化排序的办法，但目前还没有明确的好思路。

我们对这个问题依然持开放态度，还没有找到一个满意的、优雅的解决方案。

黑板讲解：顶视二维与三维的比较

我们从俯视角度来看这个问题。假设有一个英雄角色站在一个略微凹陷的区域里，地形高度不一，有的地方高，有的地方低。英雄站在相对低洼的位置。单纯用Z值排序，从纯顶视角看，这种排序对于大多数情况是可行的，虽然可能存在一些小瑕疵，但总体上是可以接受的。

但是一旦视角稍微倾斜，视线从侧面看时，原本后面的某个物体可能会遮挡前面的位置，这时候单纯用Z值排序就不够了。比如有个物体在更高的Z值处，它会正确地排在前面，遮挡后面的物体，这是符合预期的。但另一个问题是，低Z值但Y值更大的物体有可能错误地被排在高Z值物体前面，造成视觉上的错乱。

这时，Y坐标的排序就变得重要。如果先按Y排序，再按Z排序，可以保证：

• 位于不同Y位置的物体有合理的层叠关系，
• 而站在某个位置上方的英雄，其Z值较高，始终排在覆盖物的前面，避免被错误遮挡。

这种结合Y和Z排序的方式，对于局部瓷砖内的元素排序来说，是较为合理且有效的。

接下来考虑跨瓷砖的情况，比如有一张地毯或类似的覆盖物跨越多个瓷砖。此时，为了让跨瓷砖的覆盖物正确显示，地面必须相对平坦，各个瓷砖的Z值变化不大，否则无法合理叠放桌子或其他物品。

在这种较为平坦的情况下，覆盖物（如地毯）可以叠加在地面上。但问题出现在Y排序上。因为英雄站在地毯的某个后方瓷砖上时，按Y排序，地毯可能会被错误地分配到其他位置，导致排序出现矛盾：英雄应该排在地毯前面，但由于Y值排序，地毯反而被排在英雄前面或错位，造成视觉错误。

总结来说：

• 纯Z排序在顶视图下大多数情况下可行，
• 视角倾斜时，结合Y和Z排序能更合理处理遮挡关系，
• 但跨瓷砖覆盖物导致的排序问题比较复杂，Y排序可能带来冲突，
• 要求地面高度平坦才能较好处理跨瓷砖覆盖物的排序，
• 依然存在英雄和覆盖物排序矛盾的问题，排序逻辑难以完全简单化。

整体来看，Y和Z的结合排序是当前较合理的解决方案，但仍有细节和特殊情况需要特别处理。

黑板讲解：使用平面数学方法

我们思考用平面排序的方法来处理复杂的排序问题。假设我们为每个物体定义一个平面方程，通过平面数学来判断两个物体在它们重叠的点上哪个应该排在前面。

这种思路在某种程度上是合理的：在它们相交的位置，我们可以判断哪个物体应该覆盖另一个，从而确定正确的绘制顺序。但困难在于，如果有多个物体分布在不同的位置，涉及的平面交叉会非常复杂。我们不仅要判断排序顺序，还可能需要裁剪物体的一部分来避免绘制错误。

例如，有时候我们希望某个瓷砖先绘制，但基于平面排序却显示另一个瓷砖应该先绘制，这会导致视觉上的干扰，物体“穿插”在不该穿插的位置。这种情况让平面排序的方案显得不够可靠。

因此，虽然理论上可以用平面排序并写出相应的规则，但在实际应用中，问题非常棘手。为了完全解决这类复杂的排序关系，可能必须真正地用3D模型表示所有物体，从3D视角来处理遮挡和排序。

如果不走3D的路，我们可能就必须放弃那些跨瓷砖铺设的覆盖物（比如地毯），要求所有东西严格按照瓷砖边界摆放，不允许跨越多个瓷砖。这无疑会限制设计的灵活性，令制作更大或跨多瓷砖的家具（例如沙发）变得困难。

总体来看，虽然平面排序方案有其逻辑基础，但它带来的复杂裁剪和不确定排序问题，让我们难以找到理想的解决方法。可能唯一的办法就是承认无法完全解决跨瓷砖复杂排序问题，要么限制设计，要么采用3D系统处理。

黑板讲解：将问题视为三维问题

我们把问题看作一个真正的三维排序问题。假设有两个瓷砖，每个瓷砖有中心点，从上方俯视它们。地毯叠加在瓷砖上面，英雄人物站在一边，每个对象都有它们的最高点。我们关注这些对象在视线方向上的投影位置和对应的Z值。

关键难点在于：不同选取物体上的点会导致排序结果不同。比如选取地毯的一个点，可能排在英雄前面；选另一个点，则可能在英雄后面。也就是说，排序依赖于选取的参考点，导致排序结果不稳定。而通常在渲染时，我们是基于每个像素的深度进行排序，因此不会遇到选择单点的问题。

为了解决这个问题，可以考虑物体的最低点和最高点（即物体在视线方向上的范围，称为投影范围），用物体的投影范围来判断排序。具体来说，观察两个物体在视线方向上的投影区间，可以归纳出几种情况：

1. 不相交（投影区间不重叠）
   如果物体A的所有点都在物体B之前，那么A总是应该先绘制，B后绘制。这种情况排序非常明确。

2. 部分重叠
   两个物体的投影区间有部分交叉，这种情况比较模糊，不容易判定谁先绘制。比如地毯和站在上面的英雄之间的关系，这时候存在一定的排序歧义。

3. 完全包含
   一个物体的投影范围完全包含另一个物体。此时也比较难判断，排序会更加复杂。

举例来说，假设英雄站在地毯上，投影范围部分重叠，理论上英雄应该覆盖地毯被绘制在后面。但如果英雄向后移动，投影关系可能反转，导致排序出现问题。换句话说，单靠投影区间无法准确、稳定地判断正确绘制顺序。

总结来看，这种基于投影范围的排序方法虽然能在部分情况有效区分物体遮挡关系，但面对物体交叠或动态移动，依然存在明显的歧义和排序冲突，没有简单、通用的解决方案。除非采用更精细的每像素深度排序或者直接用三维渲染技术，否则难以解决复杂场景下的排序难题。

黑板讲解：平面实体与竖直实体的区别

我们考虑将场景中的物体分为两类：平面的和竖立的。针对这两种类型，排序问题可能会有所不同。对于竖立的物体和铺在地面上的平面物体，可以通过观察它们投影交汇处的高度（Z值范围）来判断哪个应该在前面绘制。也就是说，判断两者重叠时哪个在上方，依据它们在交汇点处的高度来确定绘制顺序。

这其实归结为：竖立的物体主要根据它们的Z值进行排序，而平面物体主要根据Y值进行排序。这样的划分和排序逻辑可以帮助解决两类物体混合时的遮挡问题。

但实际上，除了这种竖立和平面的区别之外，我们还是会遇到更复杂的情况，尤其是那些跨越多个格子的物体。对于单个格子里的物体，只要先按照Y排序格子，再在格子内部根据Z排序物体，排序问题大部分都能得到合理解决。

真正的难点还是跨格子的物体，它们会跨越多个格子，导致简单的Y+Z排序无法完美解决。针对这种情况，可以考虑限制跨格子的物体只能跨越固定大小的格子，但这种做法在实际应用中可能会显得比较笨拙、不够灵活，也不一定好实现。

综上，除了跨格子物体的情况之外，采用先按Y排序格子，再按Z排序格子内部物体的方式，配合竖立物体以Z为主，平面物体以Y为主的排序策略，整体排序问题基本可以得到有效处理。其他情况的排序难题较少，当前看来并没有更理想的排序算法。

黑板讲解：单个格子内Y轴排序的问题

在单个格子（cell）内部，我们仍然面临Y轴排序的问题。即使物体都在同一个格子里，我们也需要根据它们在Y方向上的位置来决定绘制顺序，比如从上方俯视图来看，Y值较小的物体应当先绘制，Y值较大的物体后绘制，这样视觉上才不会出现遮挡错误。

对于完全平面的物体，可以采用一种偏置的方法，比如将它们的排序点设在物体末端，从而在单格子内部实现合理的排序。这种偏置能帮助平面物体在Y排序中表现正确，避免被误判遮挡顺序。

不过，问题更复杂的是那些能在格子内自由移动的物体，比如飞行中的投射物（子弹、飞箭等）。由于通常一个格子内不会同时存在两个站立的角色，格子内的竖立物体不会堆叠，但这些小的浮动物体却会带来排序难题。它们的位置在Y轴上随时变化，排序不易准确处理。

最初提出的“竖立卡片（upright cards）”和“非竖立卡片”的分类，正是为了应对这种复杂的排序需求。竖立物体和非竖立物体需要采用不同的排序策略，但这仍然没有完全解决所有问题。

目前来看，纯粹靠二维排序难以完美解决这个问题。虽然考虑使用深度缓冲区（z-buffer）进行三维渲染可以避免排序问题，但这会带来额外的复杂性和资源浪费，尤其是在带宽和计算上，因为二维场景通常不需要完整的3D光栅化处理。

传统方法里，这类排序通常是手动固定好的，比如预先设定好物体的高度和遮挡关系，类似地毯这种东西直接“烘焙”到贴图里，不需要实时排序，简化了流程。

总结来说，单格子内的排序问题依然存在，尤其是动态移动的物体和完全平面的物体混合时的排序仍然棘手。传统2D排序方式有限，三维渲染能解决问题但代价大。手动预设物体层级和高度依然是业界常用的折中方案。

黑板讲解：倾斜相机俯视站在地毯上的角色的排序问题

我们从上方视角看一个场景，有一张地毯和一个英雄角色。如果使用z-buffer进行排序，英雄会显示在地毯前面，因为他们在三维空间中其实是无限薄的平面。在用3D卡片模拟时，这些平面会被正交投影到一个平面上。

在这种情况下，会把这些对象投影到某个轴线上，比如x轴或者y轴，然后观察它们投影的范围。英雄和地毯的投影区域会有重叠部分，正是这个重叠区域决定了它们的排序关系。

关键点是，我们只关心它们在屏幕上的重叠部分，也就是它们投影在同一条轴线上重合的区域。只要知道它们在屏幕上出现的具体位置，就能判断哪个应该绘制在前面。

所以，可以尝试用类似画家算法（painter’s algorithm）的思路，找到它们在某个轴上的投影范围重叠处，来确定排序关系。具体操作是将物体的范围投影到x轴或y轴，然后找出它们的交集区间，在这个区间内比较深度信息，从而决定绘制顺序。

这个方法的核心是，将三维排序问题简化成投影轴上的区间重叠比较，利用物体在屏幕上的投影位置来解决遮挡和排序问题。

黑板讲解：使用实体共有的最近点来确定排序

我们从视角出发，定义视图的Z轴和Y轴，区别于世界坐标的Z轴和Y轴，关注的是相对于观察者的坐标。考虑一个场景，有地毯和人物，我们用二维卡片表示它们，分别在Y轴上有各自的最小值和最大值，也就是它们在Y轴上的范围。

首先，我们知道这些精灵在Y轴上的位置范围。如果两个对象在Y轴上的范围有重叠，那么它们之间就存在排序的必要。如果不重叠，从理论上讲，它们的绘制顺序可以不影响最终效果，因为没有交集，不存在遮挡问题。但是，这里也存在潜在的问题：

如果两个对象在Y轴上不重叠，我们随意决定绘制顺序，可能会影响另一个同时与这两个对象有交集的第三个对象的绘制顺序。因为这个第三个对象需要依赖正确的排序顺序来决定自己该绘制在谁前面或后面，如果我们排序顺序错误，第三个对象的遮挡关系就会出错。

为了解决这个问题，我们提出了一个思路：找出两个对象在Y轴上“最近的共同点”，也就是说，要么是它们重叠的区域，要么是它们范围最接近的两个端点之间的点。在这个共同点处比较它们在Z轴上的深度值，深度小的先绘制，深度大的后绘制，从而确定绘制顺序。

进一步思考，这个过程实际上可以看作一种空间划分。每个精灵对应一个平面，我们可以通过判断实体相对于这些平面的位置，来确定谁离观察者更近。具体来说，如果一个实体位于某个平面的观察者一侧，那么它应该比位于另一侧的实体更靠近观察者，因而优先绘制。

唯一复杂的情况是实体“穿插”了平面，即部分实体位于平面一侧，部分位于另一侧，这种情况下很难确定绘制顺序，甚至无法保证绘制正确。这属于特殊情况，需要额外处理或拆分对象。

总的来说，这种排序规则基于每个精灵都有对应的平面方程，且平面的法线方向是固定的（例如世界坐标中的Z轴或Y轴），所以计算相对位置比较简单且高效。对于较厚的对象，虽然理论上可能需要多个平面来描述，但实际中可以用单一平面近似，效果应该也足够好。

这种方法的优点是：

• 每个精灵只需知道自己的边界和对应的平面；
• 利用简单的几何关系判断相对深度和绘制顺序；
• 对大部分情况有效，只需特别处理穿插情况。

总之，通过视图坐标下的平面位置关系判断排序，是一种较为稳妥且易于实现的绘制顺序解决方案。

问答环节

如果只关注跨越多个格子的精灵，为什么不在格子边界处分割多边形？应该不多，也不太耗性能吧？

针对存在于多个格子（cell）中的精灵，有一种想法是将这些精灵的多边形沿着格子边界进行切分。理论上，这样做不会产生太多的多边形，计算开销也不一定很大。但是问题不完全在于计算成本，更重要的是这些精灵实际上并不是普通的多边形，而是“直立的假卡片”（upright fake cards）。这种情况下，切分操作不仅是几何上的拆分，还涉及到基于二维原始图形的切割和重组。

虽然从技术上讲，切割并分别排序是可行的，但即使这样做了，在单个格子内部仍然需要对切割后的部分进行排序。这意味着切分只是解决了跨格子排序的问题，但格子内的排序问题依然存在。

因此，虽然切割精灵以适应格子边界看似一种可行方案，但并没有彻底解决所有排序上的难题。内部排序依然需要处理，整体流程并没有因此变得简单。

总结来看，切割方法可能会增加处理流程的复杂度，而不是显著降低问题的复杂度。