Java更高效的数组搜索

Question

我正在使用 LibGdx 编写游戏代码，我有一个数组，其中包含玩家可以与之碰撞的所有墙壁对象。对于那些不使用 LibGdx 的人，我说的是 LibGdx 的 Array 类，它提供与 ArrayList 相同的功能，但它在构建时考虑了内存效率。当我检查碰撞时，我必须穿过阵列中的每一面墙并像这样检查碰撞:

for(Wall  w : walls) {
    if(w.bounds().contains(player.bounds()) {
    // handle collision
    }
}

我意识到这是低效的，因为我要穿过每一堵墙，即使那堵墙不在 map 的当前 View 之外。显然，如果我正在检查与当前在摄像机视口(viewport)中的墙壁的碰撞(这意味着玩家当前可以看到它们)，那么遍历整个数组是没有意义的，因为玩家在进入之前无法与它们发生碰撞看法。我正在考虑通过仅检查与靠近玩家的墙壁的碰撞来提高我的游戏效率。在我的游戏中，我将所有的墙壁都捕捉到一个单元格为 32x32 像素的网格上。我真的不知道如何创建更有效的碰撞搜索。我可以使用某种 map ，它使用 vector2 位置作为其键，然后查找玩家的位置并在玩家在 map 中的位置一定范围内看穿墙壁吗？我只是真的迷失了如何让代码不会穿过我游戏中的所有 100 多堵墙，因为玩家目前只能触摸 10 面可能的墙，因为它目前所在的位置。这有意义吗？有人可以解释做这样的事情的好方法吗？非常感谢。

Answer 1

有很多碰撞算法，您需要找到适合您需要的一种。

我能想到的一个解决方案是:
让您的挂单按坐标排序。如果您创建一堵新墙，请使用插入排序来求助于您的数组。当你想检查碰撞时，获取对象坐标(在本例中可能是正在运行的玩家)并进行二进制搜索以找到离玩家最近的墙。然后计算玩家和这面墙是否发生碰撞。如果最近的墙没有引起碰撞，您可以非常确信没有其他墙也发生碰撞。