如何在《River City Ransom: Underground》中实现 2.5D 排序
我们正在研究如何对精灵进行排序，特别是在具有一定深度感的2D游戏中，这并不是一个简单的问题。起初我们希望这能是一个相对直接的问题，但很快就意识到它的复杂性远超预期。
这个问题的核心在于，在一个具有“伪3D”或“2.5D”表现形式的游戏中，精灵之间的遮挡关系并不能单纯地通过一个简单的 Z 值排序来解决。尤其是在多个精灵的边界框发生重叠时，仅仅依靠它们的坐标信息，往往不足以确定它们的绘制先后顺序。
有的游戏会在精灵的定义中提供更丰富的信息，比如每个精灵在不同深度（Z 轴）上的覆盖范围。这种方法可以让我们在精灵之间发生重叠时，更准确地判断谁在谁的前面。但我们目前的渲染体系中并没有类似的支持，也不确定是否真的需要增加这样的复杂性。
另一个关键因素在于视角问题。在某些倾斜式（等距投影）场景中，比如一个有双重倾斜的视角（例如既有上下方向的倾斜，也有左右方向的倾斜），精灵前后关系不仅取决于坐标位置，还可能受其朝向或边界形状影响。而在我们当前使用的视角中，主要是单向倾斜，因此情况相对简单一些，不需要考虑“从哪个侧面看过去”的复杂判断。
对于这种排序难题，一个比较务实的思路是：承认这并不是一个纯粹几何的问题，而是一个语义问题。也就是说，我们并不总是能够用数学坐标来精确描述谁应该在前谁应该在后。因此，采用“构建语义图”的方式就显得尤为合理。
具体来说，可以遍历场景中的所有精灵，列出我们已知的前后关系，比如“精灵 A 应该在精灵 B 前面”，“精灵 C 应该在精灵 D 后面”等等。然后基于这些信息构建一个有向图，图中的边表示“在前”的关系。接着，对这个图进行拓扑排序，以确定精灵的绘制顺序。
当然，构建这样的图可能会出现环路（循环依赖），也就是存在精灵 A 在 B 前，B 在 C 前，而 C 又在 A 前的情况。这时就需要使用一些图算法（例如 Tarjan 算法）来检测环，并通过删除某些边的方式打破循环。这种删除边的操作可以一开始是任意的，如果后续发现渲染结果不正确，再通过引入启发式规则来优化边的去除方式。
这种方法的优势在于，它允许我们加入完全与空间位置无关的语义规则。例如，可以规定“主角的头部永远绘制在斗篷前面”、“斗篷永远在身体前面”等等。这些关系是明确的、固定的，但如果依赖位置和 Z 值排序可能很难保证。而语义图允许我们显式声明这些关系，并可靠地控制渲染结果。
相比之下，之前尝试的通过调整 Z 值或 sort key（排序键）来实现这些效果的方法就比较麻烦。那种方式依赖于人为设定数值大小，既不直观，也容易出错。
总的来说，构建基于语义的排序图是一种更通用、更可控的方式。它适用于各种复杂排序关系，无论是几何遮挡还是逻辑优先级。同时，也为未来处理更复杂的场景或添加更丰富的渲染细节提供了扩展空间。
虽然这种方法实现起来可能比简单的 Z 值排序复杂一些，但考虑到问题本身的本质复杂性，这是可以接受的。特别是当我们观察到其他项目在处理类似问题时也不得不采用类似的思路时，就可以更加确信这并不是我们遗漏了什么简单方案，而是问题本身确实需要较高的处理复杂度。因此，采用语义驱动的排序策略，是目前看来最合理的解决路径。
下面是那个博客
https://andrewrussell.net/2016/06/how-2-5d-sorting-works-in-river-city-ransom-underground/
/
在解决这个问题之前，有一个重要的决策需要先做：你是否希望将互相穿插的精灵拆分开来？
如果你的答案是“是”，那么这篇博客文章就不适合你。你可能会采用类似 Z 缓冲（Z-buffering） 的方法（按像素进行处理）。我们在《River City Ransom: Underground》中其实可以这么做——我们拥有深度信息，也有 1-bit 的透明像素风格图像，也具备相关的技术能力。
然而，我们之所以没有这么做，是出于一个重要的美术审美上的考虑：拆分精灵的显示效果很差。请看下面这个例子：
在这个例子中，Alex 的排序结果显示他在汽车前方。但在三维空间中，他的手实际上穿插进了汽车的内部。玩家的碰撞边界比他们在图像上看起来要小——这一点对于实现良好的视觉效果和良好的游戏体验都是必要的。
如果我们使用体素（voxels）来渲染实际的游戏世界（实际上我们就是通过这种方式在调试工具中获得上图所示的视角），那么 Alex 的手就会消失在汽车的前部内部。而这是没有人愿意看到的！
一旦做出了是否拆分精灵的决策，接下来的排序问题可以被分为两个明确的部分：如何判断两个物体之间的前后关系，以及如何对整个场景中的所有物体进行排序。
第一个部分在很大程度上依赖于具体的游戏逻辑。在我们的情况下，我们首先尝试根据 Y 轴和 Z 轴上的包围盒（bounding box） 来进行排序。如果一个物体明显高于或位于另一个物体之前，那么排序就非常明确。
但如果两个物体的包围盒发生了穿插，这时候就需要查看物体本身的 3D 数据（这就是与游戏具体实现有关的部分）。理论上我们可以采用类似 Z-buffer 的方法，在一个二维区域中判断哪一个物体拥有更多的“前景”像素。但这样做的计算代价非常高。
为了避免进行昂贵的二维计算，我们利用了一个事实：我们的实心物体是通过 高度图（heightmap） 来表示的。我们从侧面观察这些高度图，预先计算出“深度切片”，这些切片可以界定出高度图在某个 Y 位置的范围。由于高度图本身不允许出现悬垂结构（即没有凸出部分），我们可以确定任意一个切片一定会完全包含其上方的所有切片。
一旦做出了是否拆分精灵的决策，接下来的排序问题可以被分为两个明确的部分：如何判断两个物体之间的前后关系，以及如何对整个场景中的所有物体进行排序。
第一个部分在很大程度上依赖于具体的游戏逻辑。在我们的情况下，我们首先尝试根据 Y 轴和 Z 轴上的包围盒（bounding box） 来进行排序。如果一个物体明显高于或位于另一个物体之前，那么排序就非常明确。
但如果两个物体的包围盒发生了穿插，这时候就需要查看物体本身的 3D 数据（这就是与游戏具体实现有关的部分）。理论上我们可以采用类似 Z-buffer 的方法，在一个二维区域中判断哪一个物体拥有更多的“前景”像素。但这样做的计算代价非常高。
为了避免进行昂贵的二维计算，我们利用了一个事实：我们的实心物体是通过 高度图（heightmap） 来表示的。我们从侧面观察这些高度图，预先计算出“深度切片”，这些切片可以界定出高度图在某个 Y 位置的范围。由于高度图本身不允许出现悬垂结构（即没有凸出部分），我们可以确定任意一个切片一定会完全包含其上方的所有切片。
为了比较两个物体的深度，我们只需选择它们在共有的最低 Y 坐标处的切片。然后针对该切片进行一维深度比较，同时特别考虑物体上方的部分。
（上图中，围绕物体的绿色和红色线条就是该物体在 Y=0 位置的切片。）
虽然这种方法不会产生与二维测试完全一致的结果，但其精度已经足够接近。事实上，这种方法更优，因为它减少了物体在移动过程中，特别是在 Y 轴方向上闪烁的可能性。
接下来我们想要对整个场景进行排序……
一旦有了判断任意两个物体前后顺序的方法，就可以构建一个有向图。具体来说，就是一组顶点（每个物体对应一个顶点），这些顶点通过边相连，每条边都指向一个方向，表示连接的两个物体的绘制顺序。
（这里会涉及一些图论知识，强烈建议至少学习基础内容，因为在游戏开发中经常会遇到。）
首先需要认识到，这个图不是完全图。我们不需要计算两个不重叠物体之间的排序方向。除了这种计算可能比较耗费资源之外，图中的每条边本质上是一个必须被解决的约束条件（而且——正如后面会说明的——越少越好）。
（顺便说一句，在《River City Ransom: Underground》中，我们用每个动画的边界来检查重叠，而不是逐帧检查，这样能减少深度闪烁的风险，特别是对于循环动画。）
因为这不是完全图，这排除了使用标准排序算法（如插入排序、冒泡排序、归并排序）的可能。相反，我们需要使用拓扑排序（例如：深度优先搜索排序）。
第二点需要认识到的是，这个图不一定是无环图！它可能包含强连通分量（SCC，即循环）。这会阻止任何排序的进行！这就是所谓的“画家困境”。
所以，编写一个好的2.5D排序算法的第一步是承认我们有这个问题。
那么，我们该如何解决呢？在《River City Ransom: Underground》中，我们简单地识别出导致强连通分量的边，然后尝试自动删除尽可能少的边以去除这些循环。基本上就是在当前情况下，尽量得到最优的排序结果。
实际上，在游戏中触发这种情况是非常困难的。上面截图来自算法测试环境，显示了两个已解决的强连通分量（SCC）。我推测这种情况难以在游戏中发生，主要是因为游戏中的物体形状相对方正且合理，并且物体不旋转；同时，游戏使用了良好的碰撞检测，且碰撞检测使用的数据与前面提到的排序函数相同，从而避免了物体相互穿透。
我们用来解决这个问题的算法是经过修改的Tarjan算法。
Tarjan算法是一种高效的方法，用于找出图中所有的强连通分量，且额外的好处是它还能生成拓扑排序。一旦找到强连通分量，我们就可以尝试删除一些边，直到该分量不再是强连通的。此时，该分量可以独立排序，不会影响整个图的排序顺序。
我们会做一些简单的操作，尽量选择删除对视觉影响最小的边。但由于这种情况非常罕见，我们没有花费太多时间去专门优化这部分。
/
关于进行语义排序
我们认为采用语义排序是一个可行且合理的方向，目前来看也没有太多阻碍。主要的挑战在于，我们在构建语义排序系统时，方式可能需要与 River City Ransom: Underground（以下简称 RCRU）所使用的方法有所不同。虽然我们都在解决类似的问题，但每个项目的需求和技术结构不尽相同。
RCRU所面对的问题可能在某些方面更复杂。例如，他们的画面在模拟深度方面使用了更多的轴向倾斜，可能不只是Y轴（垂直方向），还涉及到水平轴的偏移。这意味着他们需要应对的遮挡关系会更加复杂，尤其是在判断某个精灵是否位于另一个精灵前面时，不仅要考虑纵向位置，还要考虑侧向关系。而我们当前的画面风格并不涉及那么多轴向，因此复杂度相对较低，这可能使我们可以采用更简单的解决方案。
此外，RCRU的精灵可能具有更高的纵向差异，也就是说，一个精灵可能会在垂直方向上占据更大的范围。而我们的精灵相对简单，没有那么多高度变化，这意味着我们在判断遮挡关系时可以依赖更简洁的信息结构。
因此，我们希望能在不增加额外数据的前提下完成排序系统。现有精灵只包含图像信息，没有额外的几何描述或结构数据，我们倾向于保持这种简单性。如果不必为每个精灵引入额外的结构信息，比如三维边界框、复杂坐标系等，那将大大减轻整体系统的负担。
基于以上考虑，我们准备尝试构建一个类似的语义排序原型系统，通过实践来验证它的可行性。计划是先动手编码一版语义图排序实现，实际观察在代码层面会遇到什么问题，再评估这种方法在当前项目下的适用性与稳定性。
从长远来看，如果能在语义层面明确哪些精灵应当在前，哪些应当在后，并通过拓扑排序完成绘制顺序的确定，我们将获得一个更灵活、更精确的渲染控制方式。这也为将来处理更多复杂场景留下了空间。
我们目前的思路就是从简单出发，不引入额外精灵数据，通过尽量纯粹的语义关系构建排序图。接下来的计划是尝试着手实现，并观察是否能在保持系统简洁的同时，解决遮挡顺序的问题。如果实现过程中发现问题，也可以及时调整策略，逐步完善。
接下来将继续展开编码测试，从构建初始的语义排序逻辑开始，看看它在我们的渲染架构中如何运行，是否存在明显问题，以及我们是否喜欢这种方式带来的控制感和结果表现。
game_render_group.h: 建议将拓扑排序从渲染组中分离出来
我们现在准备开始研究这部分内容。首先，我们可能先暂缓拓扑排序的讨论，因为在更高层次上还有一种排序概念——图层（layers）。这些图层似乎可以与之前提到的包裹在排序中的边界框（bounding box）排序结合起来。因此，我们也应该关注这部分，随着探索逐步深入。
有一点让我们有些疑惑且还没下定论的是，把所有这些排序信息都“打包”进渲染组（render group）可能并不是最合适的做法。过去，渲染器是负责排序的，排序作为渲染器最后的一个环节，把所有要绘制的内容推入渲染组后统一排序。但现在看来，或许排序应当成为一个独立的系统，与渲染器分开。
原因是如果把复杂的拓扑排序信息直接嵌入到渲染组，反而可能把本该专注于如何输出图形的渲染部分变得复杂起来。现在看来，可能我们把太多排序的逻辑塞进了渲染组这一单一模块中，这样的设计不够清晰合理。目前对此还没有确定的答案，这个问题仍然值得继续斟酌和验证。
game_entity.cpp: 建议让 UpdateAndRenderEntities() 绘制时前面的图块覆盖后面的
正如之前提到的，我们目前还不确定具体要怎么做，所以现在的计划是先动手尝试一些思路，看看实际会出现什么情况。
首先，我们选择一个非常简单的场景来测试，也就是我们已经掌握的基本情况。比如我们现在有一些正在渲染的“部件”（pieces），可能我们希望先考虑这些部件之间的排序关系。
刚开始没找到迭代器的原因，是因为这部分代码结构比较特殊，部件的迭代器其实是在某个特定的位置。我们看到了 piece_indec 相关的部分，在这段逻辑中我们可以构想出每个部件在排序上如何相互关联。这种部件之间的排序在游戏中几乎是必须的，尤其是当我们构造了一个“生物”这样的复杂对象时，其每个组成部分（例如角色的身体各部位）之间的前后顺序是明确且稳定的。我们通常希望这些 2D 精灵在显示时能够按照预定的层次关系正确地叠加起来，就像它们原本在 Photoshop 文件中的分层那样。
因此，在处理 piece_indec 相关逻辑时，可以设想在 PushBitmap 操作的同时，我们不仅仅推送一张位图，还额外提供一些排序信息，比如“这个位图必须永远在另一个位图的前面”，或者“这个位图永远在另一个位图的后面”等。我们可以为每个部件设定一个“排在谁前面”的索引信息。如果该信息等于自身的索引，那表示它不在任何其他部件前面；如果是其他索引，就表示它要排在那个索引对应的部件前。
这个机制可以非常简单地在部件层面上实现，并且解决了“内部排序”的问题。也就是说，这种方式足以确保同一个生物或对象中的各个部件按照既定的顺序渲染出来。
接下来一个更大的问题是：这些部件与其他对象之间又该如何排序呢？这就不是内部排序能解决的了。因为这些部件之间只知道彼此之间的排序关系，却不知道自己在整个场景中的相对位置。通常来说，每个实体（entity）是单独输出渲染指令的，因此我们必须要搞清楚这些实体在场景中该如何排序，特别是当某个部件没有额外信息说明自己如何融入整个场景时。
所以我们现在需要进一步明确的是：到底要根据哪些规则来判断“谁在谁前面”。这个问题仍然悬而未决，需要继续探索和测试。
黑板：排序规则
我们现在要做的事情是尽可能枚举出所有的排序规则。
首先，我们目前已经掌握了一些关于“平面”的信息。根据当前系统的构造，我们可以把精灵（sprite）分成两类：一种是位于 Z 平面上的，另一种是位于 Y 平面上的。基本上，我们目前只处理这两种情况。
为了更清晰地理解这个问题，可以先看我们使用的坐标系统。坐标系统定义了 X、Y、Z 三个轴，我们的精灵贴图要么贴在 Z 平面（即平躺在地面上的那种），要么贴在 Y 平面（即垂直于地面朝向玩家的那种）。
第一类：Z 平面上的精灵
这些是贴在 Z 平面上的精灵，也就是看起来像“躺在地上”的对象，比如地板上的道具、阴影或者血迹之类的。它们的法线方向是 Z 轴方向，因此排序主要依据它们的 Z 值。
由于我们是用正交投影（orthographic projection）来渲染的，所以从视觉角度看，这些精灵是以平面方式展现出来的；如果是透视投影，它们会呈现出更具深度的效果。
第二类：Y 平面上的精灵
这些是垂直于 Z 平面的对象，比如人物、立起的道具、墙壁等。这类精灵的法线方向是 Y 轴，它们面朝玩家方向（但并不完全垂直于屏幕，而是略微有角度的倾斜），以模拟一种 2.5D 的视觉效果。
总结：
目前我们的排序逻辑只需要覆盖这两类精灵。任何一个精灵都必须被归类为这两种类型之一。目前没有考虑引入其他类型的平面或混合类型。换句话说，我们的系统只支持 Z 平面和 Y 平面上的图像，没有考虑更多自由旋转或变换的精灵对象。
这个基础分类是我们建立排序规则的前提，后续的排序逻辑将根据这两种不同类型的精灵展开处理。
黑板：考虑到我们只需要对有重叠的精灵进行排序
在观察这些精灵的时候，我们必须承认一件事情——而且从 Andrew 的内容中也能进一步印证这一点：我们真正关心排序问题的前提，其实只是当两个精灵发生重叠时。
也就是说，如果两个精灵在屏幕空间中根本没有发生重叠，它们的绘制顺序实际上是无关紧要的，无论先画哪个都不会影响最终效果。所以我们真正需要关心的，只是在“两个精灵发生重叠”的情况下，该如何决定它们的前后顺序。
因此，在制定排序规则时，我们只需要处理“重叠时”的情况。换句话说，排序系统并不需要穷举所有可能的对象组合，而只需专注于那些可能会在画面中相互遮挡或接触的对象。这不仅简化了问题，也意味着我们可以更高效地实现排序逻辑。
总结：
- 排序判断只在重叠发生时才有意义；
- 非重叠精灵之间无需排序规则；
- 我们的排序算法需要以“是否发生重叠”为前提来构建排序关系网；
- 这也意味着我们可以忽略绝大多数对象对之间的排序判断，从而优化性能。
接下来要做的就是进一步细化“当发生重叠时”的排序规则。
黑板：涉及 Z 平面和 Y 平面精灵的三种基本情况
我们在明确了只支持两种类型的精灵之后——Z 平面精灵（Z planar）和 Y 平面精灵（Y planar）——可以得出所有可能出现的重叠类型为以下几种：
- Z 平面精灵 和 Z 平面精灵 重叠（Z-Z 重叠）
- Y 平面精灵 和 Y 平面精灵 重叠（Y-Y 重叠）
- Z 平面精灵 和 Y 平面精灵 重叠（Z-Y 或 Y-Z 重叠）
虽然从数学上说还有“Y-Z 重叠”这种情况，但由于我们讨论的是相对排序，不存在“谁主谁次”的概念，因此我们可以把 Y-Z 重叠看作是 Z-Y 重叠，只需交换两个对象的顺序即可。所以，实际上我们只需要处理 三类重叠情况即可。
这三种情况的具体含义如下：
-
Z-Z 重叠：两个处于地面（Z平面）上的精灵互相遮挡，例如角色与箱子、箱子与道具等，这种情况通常按 Z 值排序就足够。
-
Y-Y 重叠：两个站立的物体（Y平面）重叠，比如两个墙壁上的海报，或是背景板之间的遮挡，这通常按 Y 值判断谁在前。
-
Z-Y 重叠：一个在地面上的物体（如角色）与一个立起的物体（如墙）发生遮挡关系，这种混合情况需要额外判断，比如判断角色是否站在墙前，或者是否被墙挡住。
通过将精灵分为这两种基本类型，并归纳为这三种重叠组合，我们可以大大简化排序系统的设计。接下来的任务就是逐个分析这三种情况，定义具体的排序规则。
黑板：Z 与 Z 重叠
我们先来详细分析第一种情况：Z 平面与 Z 平面（Z overlaps Z）的重叠排序问题。
背景设定
Z 平面精灵是“贴在地面上”的，也就是说它们的朝向是平行于地面的。这些通常是角色的脚、地上的物体（道具、阴影、血迹等），也可能是某些贴地的动画效果。
排序的基本原则
我们需要为这些互相重叠的 Z 平面精灵设定合理的排序规则，以确保渲染时显示出正确的前后遮挡关系。
最直接、也最有效的排序方式是 按 Z 值进行排序。具体来说，Z 值越大，物体越靠近屏幕底部，应该后绘制；Z 值越小，物体越远，应该先绘制。
多种情况分析
在排序中，我们可能遇到以下几种空间关系：
- Z 不相交（Disjoint）：两个精灵在 Z 方向上没有交集 → 不需要管排序。
- Z 相交但 Y 不重叠：在 Z 上部分重叠，但在 Y 上不重叠 → 不影响遮挡，不需要管排序。
- Z 和 Y 都重叠（真正的遮挡情况）：这是我们需要处理的重点，确保前者遮住后者。
但由于 Z 平面精灵本身就是一个二维贴图（没有厚度），我们可以认为它们是“无限薄”的。因此，排序不需要考虑“体积感”或者“Z 深度覆盖范围”，只需要取它们在 Z 轴上的某一个关键值——通常是底边的位置或中心点的 Z 值——即可。
所以在这种设计下：
Z 平面与 Z 平面之间，只需要按照 Z 值升序排序即可得到正确的绘制顺序。
深度和分片的额外说明
在进一步分析中也考虑到，如果有一个对象既包含了 Y 平面部分又有 Z 平面部分（例如一个箱子有立起来的侧面和贴地的顶部），则应该把它拆成两个精灵，一个处理 Z，一个处理 Y，分别参与各自的排序逻辑。这样可以避免复杂的“体积排序”逻辑。
结论
- Z 平面与 Z 平面重叠的排序可以完全通过 Z 值进行，无需考虑 Y 坐标。
- 只要按照 Z 值升序排列精灵，渲染顺序就是正确的。
- Z 平面精灵应当保持“无厚度”的建模理念，必要时分拆为多精灵处理。
下一步就需要进入第二类情况，即 Y 平面与 Y 平面重叠（Y overlaps Y） 的处理——这将更复杂，因为它涉及视角方向、遮挡判断甚至潜在的深度交叉。
黑板：Y 与 Z 重叠
我们处理的是一个 Y 平面精灵（竖直放置）与 Z 平面精灵（水平放置）相互重叠 的排序问题。
背景概念
我们场景中的精灵分为两类：
- Z 平面精灵：比如地面贴图，是沿 Z 轴铺展的“地板”式精灵。
- Y 平面精灵：比如树干或角色，是沿 Y 轴竖直展开的精灵。
我们只关心两个精灵 在视觉上重叠的情况，只有在这种情况下排序才有意义。
排序基本逻辑
如果 Y 平面精灵的 Y 范围 不与 Z 精灵的 Y 范围重叠：
此时可以简单地使用 Y 坐标进行排序：
- 谁的 Y 值大（即更靠近屏幕下方），谁后画；
- 这是一个快速判断，不需要额外计算。
如果 Y 平面精灵的 Y 范围 与 Z 平面精灵的 Y 范围有交集：
需要使用一个更精确的判断规则：
- 判断 Y 精灵的最高点在 Z 轴方向上的位置（即 Y 精灵的“头顶”），是否高于 Z 平面精灵的 Z 值；
- 如果高于，就应该把 Y 精灵画在上面；
- 如果低于或等于，就把 Z 精灵画在上面。
这个判断的本质是：
- Z 平面是水平的；
- Y 平面是竖直的；
- 所以当它们重叠时，只有 Y 精灵的“顶点”超过了 Z 精灵的“平面高度”，才合理地挡住它。
排序伪代码（逻辑表达）
if (Y 精灵与 Z 精灵的 Y 范围没有交集) {根据 Y 坐标排序；
} else {if (Y 精灵的顶点 Z 值 > Z 精灵的 Z 值) {Y 精灵后画；} else {Z 精灵后画；}
}
关于穿透和复杂交互的说明
- 如果某些效果（比如角色从地面升起）需要看起来像是穿透地面，那不是排序系统应该处理的；
- 这些情况应由具体的效果系统处理，比如分割精灵、遮罩或手动裁剪；
- 排序系统只负责处理正常情况下的图层关系，不会支持穿透或物体部分遮挡等复杂交互；
- 我们不打算支持精灵之间的自动“切割”或“拆分”以适配这种情况。
总结
在 Y 与 Z 精灵重叠的情况下：
- 不重叠时，直接按 Y 坐标排序；
- 重叠时，比较 Y 精灵最高点和 Z 精灵高度决定谁在上；
- 不处理精灵穿透或自动裁剪，这类特殊情况由其他系统处理。
黑板：Y 与 Y 重叠
我们现在讨论的是 Y 精灵与 Y 精灵之间发生重叠 的情况，这是所有情况中最复杂的一种。
问题背景
两个 Y 精灵分别是竖直放置的，比如角色、树、柱子等。如果它们在屏幕上的 Y 范围发生重叠，我们就必须判断谁该画在前面。
从顶部视角来看，这两个精灵在 Y 轴方向上有交集，因此无法仅靠简单地比较 Y 坐标来确定前后顺序。
初步判断：能不能只根据 Y 值排序？
疑问在于：Z 值是否也会影响排序？
我们知道角色的身体不同部位（如头、身体、披风）在视觉上有不同的前后层次：
- 头部在最上层；
- 披风在中间；
- 身体在最下层。
这些部位的 Y 范围是重叠的，但它们之所以能正确显示，是因为我们人为地设定了它们的 Z 顺序。
这说明：Y 精灵的 Z 值确实可能影响视觉排序。所以，不能一概而论地说只要比较 Y 坐标就足够。
Z 值影响排序的情况分析
我们遇到的 Z 相关排序主要在这两种场景中出现：
-
角色自身内部的精灵装配（assembly）排序：
- 如角色的头、披风、身体等构成一个整体；
- 它们必须按照特定的顺序渲染；
- 此时我们不能依赖通用的 Y 坐标排序，必须单独为这个“整体”规定固定排序顺序；
- 这是一种“特殊处理”的情况。
-
不同实体间是否存在类似问题？
- 我们尝试设想一些非装配类的精灵间发生 Y 重叠且需要考虑 Z 排序的情况；
- 目前没有清晰的例子说明有这种需求；
- 因此我们推测除了装配类精灵外，其他情况可能都可以通过 简单的 Y 坐标排序 来正确地处理。
结论逻辑
-
普通 Y 精灵之间的排序：
- 如果不是同一个装配结构内的元素；
- 那么我们只需根据 Y 值从小到大排序即可；
- 也就是说，Y 越大的（越靠近屏幕下方的）越晚画，越在前面。
-
装配结构内的排序（例如角色身体部件）：
- 它们是被强制定义了特定的前后层级；
- 不参与普通的全局排序；
- 在排序系统中，它们应作为一个整体参与排序，而不是单个碎片。
-
Z 值在普通精灵排序中不直接使用：
- 除非明确要求需要 Z 值参与排序，否则一律按 Y 排序处理；
- 避免在通用排序逻辑中引入过多的复杂维度。
总结
- 对于 Y 精灵与 Y 精灵的重叠，大多数情况下我们只需按照 Y 坐标排序即可；
- 装配类结构（如角色身体各部分）需特殊处理，作为整体排序；
- 除非出现特殊需求，否则不将 Z 维度纳入常规排序逻辑；
- 目前来看，没有发现常规情况下不能用 Y 排序的例外情况，因此我们倾向于将 Y 重叠问题简化为按 Y 坐标排序处理。
黑板：整合这些情况
我们对前面所有情况进行了归纳整理，尝试统一出一套通用的排序逻辑。通过分析，我们发现所有的排序其实都可以归结为两种基本方式：按 Z 值排序 和 按 Y 值排序，整个系统的核心就在于：我们如何决定当前应当使用哪种排序方式。
核心结论
最终的判断逻辑可被简化为：
如果满足某个 Y 与 Z 的条件（这个条件稍后详细定义），那么就按 Z 排序；否则按 Y 排序。
三种情况的分类归纳
我们对不同类型的精灵配对做了具体分类判断，得出以下整理：
-
Z-Z 精灵对（Z 与 Z 重叠）
- 比如两个贴地的物体如箱子与石头；
- 显然应该按 Z 值排序（即深度排序），Z 值高的先画；
- 所以此时我们应返回
true，选择按 Z 排序。
-
Y-Y 精灵对（Y 与 Y 重叠）
- 比如两个竖立的角色或旗杆；
- 它们没有 Z 的深度（只有厚度为 0 的立面），不可能在 Z 上重叠；
- 所以这类永远不能通过 Z 排序解决，只能按 Y 值进行排序；
- 此时应返回
false，选择按 Y 排序。
-
Y-Z 精灵对（一个是 Z 精灵，一个是 Y 精灵）
- 比如一个竖立的人站在地上的箱子前；
- 这种组合必须判断 Y 精灵是否在 Z 精灵的 Y 范围内；
- 如果 Y 精灵顶部落在 Z 精灵上方，则说明应该在其前面，反之则在其后；
- 所以需要根据范围交叉情况，决定是否用 Z 排序。
判断逻辑的实现方式
我们将这整套逻辑抽象成一个统一的判定函数：
if (满足 Y-Z 条件) {按 Z 排序；
} else {按 Y 排序；
}
这个“Y-Z 条件”具体含义如下：
-
是 Z-Z 情况 → 返回 true → 使用 Z 排序；
-
是 Y-Y 情况 → 返回 false → 使用 Y 排序；
-
是 Y-Z 情况 → 检查 Y 精灵是否处于 Z 精灵的 Y 范围内 →
- 如果是 → 使用 Z 排序；
- 否则 → 使用 Y 排序。
系统的灵活性与可拓展性
这套系统不仅结构清晰，而且具有良好的灵活性与拓展性。一旦我们在实际使用中发现存在特殊情况（比如一个动画特效、某个特殊角色或事件逻辑），我们完全可以在这个判定函数中添加特例处理，例如：
- 某个特定的精灵类型需要强制优先；
- 某个特殊效果需要跳过常规排序逻辑；
- 某些“非物理意义”的重叠处理；
这意味着我们可以通过添加特定规则来解决那些“语义上很奇怪”但确实存在的个别场景。
总体评价与方向
这套排序策略既满足了主流场景的需求，也预留了对特殊情况的处理机制。它清晰地将排序决策划分为两个核心维度（Y 或 Z），并通过判断条件选择其一。同时也具有足够的灵活性，应对游戏中突发的、非物理但必须处理的画面重叠需求。这是我们在类似 2D/2.5D 游戏中所需要的那种“结构清晰但足够包容”的排序系统。
黑板：考虑这种方案是否能实现完整排序
我们在考虑排序算法时，关注的核心问题是：
- 现有的排序规则能否生成完整且无循环依赖的排序结果，也就是说，排序过程是否会出现环状依赖导致死锁或无法确定先后顺序。
排序的关键点与潜在问题
-
排序类型的确定
- 按 Z 值排序（Z-Z 精灵间）和按 Y 值排序（Y-Y 精灵间）本质上是清晰且无歧义的排序；
- 但当出现一个 Y 精灵同时与多个 Z 精灵重叠时，会引发排序的复杂性。
-
多个对象交叉重叠情况
- 例如，有两个 Z 精灵彼此排列，另有一个 Y 精灵同时与它们都发生重叠；
- 这种情况下是否会出现排序上的冲突或循环？即一个元素是否可能被判定为既在另一个元素前，又在其后？
- 经过思考，尽管看起来复杂，但目前判断这类情况导致的排序冲突并不十分明显，且大部分情况下可以正确排序。
-
提升一个精灵高度是否影响排序？
- 将 Y 精灵竖直“抬高”可能改变其排序关系，但前提仍是它必须与其他精灵有重叠；
- 如果没有重叠，就不会触发复杂排序逻辑；
- 实际上，这样的“抬高”不太可能导致排序逻辑的根本改变。
对排序方法的思考
-
是否需要完整的拓扑排序？
- 虽然拓扑排序可以解决复杂的依赖关系，防止排序循环，但它的计算复杂度和实现成本较高；
- 目前的情况看，可能并不需要真正的拓扑排序，通过基于部分顺序的比较排序（partial ordering）即可正确处理大部分需求。
-
如何判断排序优先级？
-
可以根据每个对象的三个关键参数：
- Y 轴的最小值（y_min）
- Y 轴的最大值（y_max）
- Z 轴的最大值（z_max）
-
以这些参数来决定元素间的排序关系；
-
具体来说，我们关心的是 Y 的范围是否有交集以及 Z 的值大小，来决定先后绘制顺序。
-
代码实现相关思考
-
排序逻辑是否应当放在渲染代码内部，还是独立成一层处理？
- 有观点认为，这样的排序处理最好独立于渲染流程之外，作为单独的排序层来管理，这样渲染代码更简洁，职责更单一；
- 这种设计有助于代码维护和功能扩展。
-
当前系统中存在多个代码库和接口，代码结构较复杂，容易导致找某些数据和排序入口时混淆；
- 需要理清渲染条目（render entries）和排序键（sort keys）的对应关系，确保排序逻辑正确集成。
总结
- 现有排序逻辑基本能覆盖大部分常见情况，并且不太可能产生循环依赖；
- 复杂情况下仍需详细验证是否存在排序矛盾，但初步判断无大问题；
- 关键参数为 y_min、y_max 和 z_max，通过它们可以有效判断排序先后；
- 拓扑排序虽强大，但可能不是必要，简单的部分顺序比较排序就能满足需求；
- 推荐将排序逻辑独立成模块，避免直接写入渲染代码，提升代码清晰度和可维护性；
- 当前代码库复杂，需要系统梳理渲染条目和排序键，确保排序调用流程明确。
game_sort.cpp: 引入 sort_sprite_bound 并让 MergeSort() 使用它
我们面对的问题是，现有的排序方法不再适用，因为需要的排序逻辑比单纯比较数值更加复杂，无法通过简单的单一键值来完成排序。
具体情况与解决思路：
-
不能使用基数排序
- 由于无法将排序依据简化成单一数值，基数排序（radix sort）不再适合；
- 必须采用更通用的排序算法，比如归并排序（merge sort），它能通过自定义比较函数实现复杂排序逻辑。
-
采用归并排序的理由
- 归并排序可以处理复杂比较，允许自定义比较规则；
- 能保证排序稳定性，且适合处理不容易量化成单值的排序条件。
-
归并排序实现中的改动
- 核心代码结构保持不变，只需修改比较两个元素的逻辑；
- 比较操作不再是简单的数值比较，而是需要根据之前讨论的排序规则，综合考虑 Y 轴范围、Z 值以及元素间重叠关系等因素；
- 需要设计更复杂的判断函数，决定两个元素哪个应该排在前面。
-
比较方向的调整
- 将比较的方向统一，避免方向不一致导致排序混乱；
- 这有助于确保归并排序在合并阶段的判断一致性。
总结：
- 现有简单排序方法不适用，必须使用支持复杂比较的排序算法；
- 归并排序是一个合适的选择，因为它灵活且稳定；
- 实现归并排序时，要重点修改比较两个元素的逻辑，令其支持复杂的空间关系判断；
- 比较函数需统一方向，保证排序结果一致；
- 这样做可以满足复杂场景下的绘制顺序需求。
拷贝一份MergeSort修改
game_sort.cpp: 引入 IsInFrontOf() 用来处理三种情况
我们准备引入一个比较器函数，这个函数返回一个布尔值，判断两个元素中哪一个应该排在前面。
排序逻辑设计：
-
比较器设计
- 比较器命名为“is_in_front_of”，意思是判断一个元素是否应该排在另一个元素前面；
- 在排序时，如果比较器返回 true，说明需要交换这两个元素的位置；
- 排序操作中，只需根据这个比较器的结果来决定是否交换元素。
-
排序数据结构
- 每个元素包含 y 轴的最小值（y_min）、最大值（y_max）、最大 z 值（z_max）和索引；
- 这些数据字段的大小适中（约16字节），适合频繁移动和复制；
- 只存储最大 z 值，而非最小 z 值，因为最小 z 值在排序中无实际用处。
-
排序规则的核心
-
我们实际上只有两种排序方式：
- 按 z 值排序
- 按 y 值排序
-
对于按 z 值排序，比较的是两个元素的 z_max，z_max 较大的排前面；
-
对于按 y 值排序，比较的是 y_min，y_min 较小的排前面（因为 y 越小越靠近视点）。
-
-
确定排序依据的条件
- 当两个元素都是 Z 类型的精灵，或者它们在 y 轴上存在包含关系时，执行按 z 排序；
- 在所有其他情况下，执行按 y 排序；
- 这里的“包含”意思是一个元素的 y 范围完全覆盖另一个元素的 y 范围。
-
进一步简化
- 因为 Y 类型的精灵的 y_min 和 y_max 是相等的，意味着它们没有高度范围，无法包含其他元素；
- 所以两个 Y 类型的元素不可能互相包含，也不会触发按 z 排序的条件；
- 因此，只要判断是否都是 Z 类型，或者存在包含关系，就可以决定使用按 z 排序；其余情况按 y 排序。
-
代码实现细节
- 用一个三元表达式来简化排序条件：如果需要按 z 排序，则比较 z_max，否则比较 y_min；
- 通过判断两个元素的类型和 y 范围包含关系决定排序方式；
- 这个过程可以进一步优化，减少不必要的判断。
总结：
- 引入比较器函数负责判断两个元素的排序顺序；
- 元素数据包含 y_min、y_max、z_max 以及索引，便于快速比较和移动；
- 只有两种排序方式，按 z 排序和按 y 排序，通过元素类型和范围包含关系决定；
- Y 类型精灵无法包含其他元素，简化了排序条件；
- 排序逻辑简洁，易于扩展和优化。
game_sort.cpp: 引入一个接受 sort_sprite_bound 的 Swap() 函数
如果接受使用模板的话，可以将排序逻辑模板化处理，因为不同情况下的排序操作其实是相同的，比如交换元素的操作在不同的排序情境下是一样的。
这样做的好处是代码复用度高，结构更简洁明了，后续维护和扩展也更方便。
明天可以进一步深入检查和完善这个方案。
问答时间
是不是 Y（垂直）方向的精灵才会出现 YMin == YMax？
当 Y 最小值等于 Y 最大值时，说明这是两个 Y 轴方向的精灵（Y sprites），而不是两个 Z 轴方向的精灵（Z sprites）。这是之前的判断错误。
换句话说，Y 轴精灵的最小和最大 Y 值相等，表明它们没有在 Y 方向上有范围扩展，而是固定在同一条线上，所以这种情况下不可能是 Z 轴精灵。
这个细节的确认对于后续的排序逻辑判断和分类非常重要。
game_sort.cpp: 修正 IsInFrontOf() 中 BothZSprites 的判断逻辑
我们在判断排序条件时，应该使用等于号来判断是否满足某些条件，特别是在判断 Y 轴精灵的最小值和最大值是否相等时，这对于流程控制非常关键。通过这样明确的判断，可以保证排序逻辑的正确性和流程的顺畅，避免逻辑错误或遗漏。这种严谨的比较方式是保证排序算法稳定执行的基础。
你总是直接比较 == float。考虑到浮点精度问题，你怎么确保这个判断成立？
关于比较操作中浮点数相等的问题，我们要注意浮点数计算带来的精度误差。通常，浮点数计算结果可能存在微小误差，因此直接用等号判断是否相等是不可靠的，需要考虑一个容差范围（epsilon）。但是在这里之所以可以直接用等号判断，是因为这些值不是通过计算得来的，而是直接设置的确定值。比如在记录Y轴精灵时，会明确将y_min和y_max设置为完全相同的值，这样它们之间就是完全相等的，不存在计算误差的问题，因此可以安全地用等号比较。
所以，只有当值是通过计算得出的才需要考虑浮点数误差，进而使用容差比较；而在这里，由于直接赋值确保了精确相等，判断时就不必担心浮点误差的问题。这样做能简化判断逻辑，避免额外的容差处理，也保证排序规则在处理Y轴和Z轴重叠的情况下准确无误。
在 Y 与 Z 重叠的情况下，比如悬崖支撑地面的场景（这样地面不会悬空），会不会造成什么问题？
在处理支撑地面精灵的侧面时，比如那些支撑悬空地面的结构，这种设计是为了避免地面看起来悬浮在空中而没有支撑。考虑这种情况时，需要评估它是否会对排序或渲染造成影响。
具体来说，这类支撑的侧面通常会与地面精灵形成空间上的重叠或包含关系，因此在排序时需要正确处理它们的层级关系，确保支撑结构能够正确显示在地面之下或合适的位置，避免视觉错乱。
整体来看，只要排序规则能够准确判断这些支撑精灵与地面精灵之间的关系，比如通过Y轴和Z轴的边界判断，并合理应用排序规则，那么这种支撑结构不会引发排序上的问题。也就是说，正确管理这些支撑部分的边界信息，可以让它们自然融入渲染流程，确保地面不会“漂浮”，视觉上更真实且不影响整体排序逻辑。
黑板：将问题精灵拆分成两个部分
对于那些可能会带来排序问题的精灵，比如悬崖的侧面和顶部，我们可以考虑将它们拆分成两个独立的精灵。比如悬崖顶端是一个精灵，悬崖侧面是另一个精灵，这样做能够更精确地控制它们各自的排序关系。
不过，也不一定非要拆分。因为悬崖侧面通常不会有角色站立其上，所以它的位置通常会在Y轴上排在其他可站立物体的后面，也就是说，侧面的Y值不会和那些可站立物体的Y值重叠，因此排序上不会冲突。换句话说，悬崖的侧面自然会排在更靠后的层次，不会影响整体排序。
即使如此，如果需要，也可以在资源制作时就可靠地将这些部分拆分，确保排序时更简单、更明确。总的来说，这种特殊情况并不常见，也不会造成排序上的大问题，所以不必过于担心。
我上周也用了“float ==”判断，我觉得是可以接受的，因为我是检测这个值是否就是我上一帧刚刚设定的那个
浮点数本质上还是整数，只不过是通过指定小数点的位置来表达数值的方式，浮点数的每个值其实都是具体且精确的位模式。如果知道数值是自己直接赋值的，而不是通过复杂计算得出的，那么这些浮点数值是完全相等的，可以直接用等号比较。
在实际编程中，通常我们不会去深入分析浮点运算的误差范围（epsilon）以及数值的精确度，尤其是计算产生的结果，因为计算过程会引入误差。但如果明确是直接赋了某个数值，比如上一帧刚刚设定的值，那么判断是否相等是可以接受的，完全不会有误差问题。
总之，浮点数确实有精度问题，但在直接赋值的情况下，这个问题不存在，可以安全地用等号判断两个浮点数是否相等。
)
