我有一个 2D 自上而下的 45 度游戏，比如口袋妖怪或塞尔达。由于对象的 y 值决定了它的深度，因此需要按照 y 值的顺序绘制对象。因此，例如，当您站在一棵树后面时，树会被绘制在您的播放器顶部，看起来就像您站在树后面一样。
我目前的设计是画一排瓷砖，然后画站在那排的任何玩家，然后画下一行，然后画站在上面的任何玩家。这样，任何 y 值高于玩家的图块都被绘制在它们前面以模拟深度。
但是，我的玩家目前是一个std::vector在绘制所有瓷砖后简单地迭代和绘制的对象。为了使我的方法起作用，我必须为每一行图块迭代向量，并且仅在它们位于当前行时才渲染，或者以某种方式按每帧的 y 值对每个玩家进行排序。这两种方法似乎都占用大量 CPU，也许我想多了，在这种类型的游戏中有一种更简单的模拟深度的方法。
编辑： 这个游戏是MMORPG类型的游戏，所以可能会有很多玩家/NPC四处走动，这就是为什么我需要一个非常有效的方法。
和想法或意见将不胜感激！
谢谢
您可以使用std::setorstd::map代替vector来保持您的对象排序。不幸的是，您无法简单地修改它们的位置，每次需要更改y坐标时都必须删除/插入。
（忽略我最初的建议，如果你读过它；那是愚蠢的。）
据我所知，每次渲染帧时，您基本上都必须遍历已排序的容器；这会带来计算上的损失，并且每次都必须进行复制和排序不会那么糟糕（我猜是 O(N log N) 排序时间）。
一个聪明的数据结构可能会帮助你；例如，一个包含游戏对象向量作为每个元素的数组。数组的每个元素代表您的平铺网格的一行，并且您遍历对象向量并将它们合并到深度缓冲区数组中（这将花费大约 O(N) 时间）。然后只需遍历表示每一行的向量并依次绘制每个对象，再次为 O(N)。
可能有更聪明的 z-buffering 技术，但我将把这些留给读者作为练习。
只要您不尝试根据其他标准对玩家进行排序，那么每次您想要遍历他们时，您只需按 y 坐标对玩家进行排序即可。只要您使用在输入大部分已排序时以线性时间运行的排序，那么您甚至可能不会为此步骤花费 O(n log n) 时间。我在这里假设您的玩家组变化缓慢，并且他们的 y 坐标也将缓慢变化。如果是这种情况，那么每次您需要对向量进行排序时，它已经大部分排序，并且诸如平滑排序或 Tim 排序之类的东西将在线性时间内运行。
对于 c++，您可以在此处找到 Tim sort 的实现。
如果你有空间，另一种选择是创建一个球员列表数组，数组的索引是行号，数组包含该行中的球员集合。
正如我所提到的，这将需要一些额外的内存，并且每次玩家移动到不同的行时都会进行一些记录，但是绘制只是遍历行并绘制存在于该行中的玩家的问题。