javascript - 用于在网格级别移动图 block 的组织系统

Question

这里是概念问题。

我有一个数组，它将被渲染以在网格中显示图 block 。现在，我希望这些图 block 能够移动 - 但不仅仅是在网格中移动。每个像素。它确实需要是一个网格，因为我需要移动整行图 block ，并且能够按其位置访问图 block ，但它也需要进行逐像素调整，同时仍然保持“网格”最新。想象一个带有移动方 block 的平台游戏。

我可以使用一些组织系统来做到这一点，我将概述一些我想到的以及它们的优点和缺点(XY 风格)，以防它帮助您理解我在说什么。我问你是否认为其中一个最好，或者想出更好的方法。

1. 一种方法是将对象放入具有属性 xOffset 和 yOffset 的数组中。然后我将把它们渲染在它们的平铺位置加上它们的偏移量。 (x *tileWidth +tile.xOffset)。优点:维护原版网格系统。缺点:那么一旦移动，我就必须将每个图 block 调整到其实际的网格位置。此外，当瓷砖移动时，“网格”位置会变得有点困惑。 (旁注:如果您认为这是一个好方法，我将如何处理碰撞？它不再像 player.x/tileWidth 那么简单。)

2. 另一种方法是放置大量带有 x 和 y 的对象并渲染它们。优点:简单。缺点:然后我必须检查每一个，看看它是否在我想要移动的行中，然后再这样做。此外，碰撞不能简单地检查玩家所在的一个图 block ，他们必须检查所有实体。

3. 我想到的另一种方法是两者的结合。图 block 将位于原始数组中，并以 x *tileWidth 普通图 block 进行渲染。然后，当它们移动时，它们会从网格中删除，并放置在用于移动图 block 的单独数组中，其中存储它们的 x 和 y。然后碰撞将以快速方式检查网格，以慢速方式检查移动瓷砖。

谢谢!

PS:我正在使用 JavaScript，但它不应该相关。

PPS:如果这不是 Stack Overflow 上的 Material ，请原谅我。我想，这是最合适的。这不完全是代码审查，但也不是专门针对 GameDev 的。我还需要一个标签，所以我选择了一个有点相关的标签。如果你们推荐其他东西，我很乐意将其切换并删除这个。

PPPS:抱歉，如果重新发布，我不知道如何用谷歌搜索这个问题。我尝试过，但没有成功。

Answer 1

(关于处理碰撞的旁注:你的障碍物正在移动。因此，将玩家的位置与网格进行比较已经不够了。此外，你始终必须根据对象的当前位置进行绘制。这两者都是不可避免的，但也不是很贵。)

您希望对象易于查找，同时仍然能够有效地绘制它们，更重要的是，快速检查碰撞。这很容易做到:将对象存储在数组中，并为 X 和 Y 位置保留索引，从而允许 1) 有效查询范围和 2) 有效地左右移动元素(当它们的 x 和 y 位置发生变化时)。

如果您的对象移动得相当慢(也就是说，在任何一个时间步长上，一个对象不太可能传递很多其他对象)，那么您的索引可以是数组!当一个对象移动经过另一个对象(例如，在 X 中)时，您只需检查 X 索引数组中的邻居，看看它们是否应该交换位置。继续这样做，直到不需要交换为止。如果它们移动缓慢，则其摊余成本将非常接近 O(1)。在数组中查询范围非常容易；二分查找第一个较大的元素，也查找最后一个较小的元素。

总结/实现:( fiddle https://jsfiddle.net/LsfuLo9p/3/ )

初始化(O(n)时间):

1. 创建一个名为 Objs 的对象数组。
2. 创建一个(x 位置，对 Objs 的引用)对的数组，按 X 排序，称为 Xs。
3. 创建一个(y 位置，引用 Objs)对数组，按 Y 排序，称为 Ys。
4. 对于 Xs 和 Ys 中的每个元素，告诉 Objs 中的对象在这些数组中的索引(以便 Xs 具有 Objs, 的索引，Objs 具有 Xs 的索引。)

当一个对象在 Y 方向上移动时(每个移动对象的预期时间为 O(1)，假设它们移动缓慢):

1. 使用Objs，在Ys中找到它的索引。
2. 将其与 Ys 中的下一个最高值进行比较。如果它更大，则在 Ys 中交换它们(并更新 Objs 中的 Y 索引) )。
3. 重复第 2 步，直到不再交换为止。

(很容易将其应用到其他三个方向。)

当玩家移动(O(log n + k²) 时间，其中 k 是行或列中可以容纳的最大项目数)时:

1. 在 Xs 中查找 small， Player.X 之上最小的 X，以及 large， 最大的 X X+Player.X 下方的宽度。 如果 large ≤ small，则返回范围 [large,small]。
2. 在 Ys 中查找 small， Player.Y 上方最小的 Y， 和 large， 最大的 Y Y+高度低于 Player.Y. 如果 large ≤ small，则返回范围 [large,small]。
3. 如果这两个范围之间有任何交集，则玩家正在与该对象发生碰撞。

(您可以通过使用 HashMap 检查集合交集来将时间缩短至 O(log n + k)。)