java - 基于 x/y 坐标高效地查找数组元素

Question

我编写了一个 java 自上而下的 2d 游戏，它使用生成的 map 图 block 。每个图 block 都由包含其 x/y 坐标的 Tile 类描述。

当玩家在 map 上移动时，我需要能够获取玩家“在”上的方 block 。玩家类知道它当前的 x/y，而 Tile 类知道它被分配到的 x/y。

目前，所有需要渲染的图 block 都存储在 Tile[][] 中。我是 java 的新手，但简单地使用我想要的数组索引的 x/y 坐标似乎不是一个好主意(如果可能的话)——主要是因为我当前正在渲染的图 block 可能并不总是从 0,0 开始。假设玩家在 1000,1000 时加载已保存的游戏 - 当我不需要它们时，我当然不会从 0,0 加载它们。

那么，存储这些坐标的最佳方式是什么？

在 PHP 中它可以完成，因为我知道数组不关心从 0 开始的索引:

$tiles[1000][1000] = new Tile()

但我不确定 Java 中推荐的方法是什么。必须遍历每个图 block 并检查 x/y 是否匹配，这感觉非常低效。

Answer 1

老实说，你问的是一个相当高级的话题。这种涉及到如此大 map 的项目，真的不是一个简单的数组就能完成的。有些人会建议使用简单的偏移量和动态数组，但这是非常低效的。

不过我可以给你一个建议。您可以分块加载图 block 。例如，每个 block 都是一个 32 x 32 的二维数组。您可以加载当前 block 和周围的 block ，而不是一般地加载玩家位置周围的图 block 。例如，假设位置 1000, 1000 落在 block C 中。然后加载 block C 和所有周围的 block 。当您从 block C 移动到 block D 时，您卸载了围绕 C 的 block ，而是加载了围绕 block D 的 block

block 类可能看起来像这样:

class Chunk {
    private Tile tiles[32][32];
    private Coordinate origin; // (0, 0) on this chunk's array is actually equal to origin on the map
    // Example: if the chunk started at (128, 128), then origin would be (128,128)
    ...
    public static Chunk loadChunk(...) { ... }
    ...
}

并且您需要 Map 类来协助定位和加载 block :

class Map {
    public Chunk currentChunk;
    public ArrayList<Chunk> loadedChunks;
    ...
    public ArrayList<Chunk> getSurroundingChunks( Chunk ch ) {...}
    ...
}

几乎所有具有大 map 的游戏都采用分块加载的方式(我的世界是一个著名的例子，尽管该游戏的编程通常很糟糕)。

当然，它的算法很复杂，您需要进一步研究它，而不仅仅是阅读这篇文章。但它应该为您提供一个适用于任何大小的 map 的强大系统，并且已被证明在现实世界中有效。

该系统的一个弱点是，由于垃圾收集，卸载在 Java 中很难预测。但是，我不知道有一个健壮的加载系统至少不会受到 Java 垃圾收集器的轻微伤害。

注意

这种技术也称为延迟加载。这意味着您只将真正需要的内容加载到内存中。这是用于加载大量可预测数据的最佳技术，因为它可以让您最大限度地减少加载时间和内存消耗。基于 block 的加载不是唯一一种延迟加载，但我什至可以说它可能是最好的一种。