Java：用于存储无限游戏世界的坐标图的良好数据结构是什么？

Question

我习惯用 PHP 编码，但我不太精通 Java，这已经成为一个问题有一段时间了。我希望这是一个相当简单的解决方案，但是我无法以任何方式找到任何好的示例代码，所以这里是：

我正在编写一个游戏，该游戏发生在基于图块的地图上的 2d 随机生成的无限世界中（挑剔） ：我知道它不会是真正无限的。我只是希望世界很大）。 map[x][y] 多维数组的常用方法一开始是一个基本思想，但由于 Java 没有像 PHP 那样提供非整数（即负数）数组键恶作剧的方法，所以我不能正确地拥有 (- x,+x,-y,+y) 带有数组键的坐标系。

我需要能够在特定 x,y 坐标处找到图块上的对象，以及找到某个图块的“相邻图块”。 （如果我可以 getObjectAt(x,y)，我可以 get(x+1,y) 等等，这很简单）

我已经阅读了有关四叉树和 R 树等的内容。这个概念很令人兴奋，但是我还没有看到任何好的、简单的 Java 示例实现。此外，我不确定这是否正是我所需要的。

欢迎任何建议

谢谢

Answer 1

1) 除了数组之外，您还可以使用 Map> 或 Map，这当然允许负数索引

2) 如果您从一开始就知道世界的维度，您只需修改 getter 即可允许 API 接受负值并[线性]将它们转换为正值。例如，如果您的世界是 100x1000 个图块，并且您想要 (-5,-100)，则您将拥有 WorldMap.getTile(-5,-100) ，这将转换为 returntileArray[ x+mapWidth/2][y+mapHeight/2]; 即 (45,400)

Answer 2

我遇到了同样的问题，但我的解决方案是使用 Map/HashMaps< /a>，但这些是一维的。

为了克服这个问题，我没有使用地图中的地图（这会很混乱且效率很低），而是使用通用的 Pair 类（不是你在库存 java 库中找到的东西），尽管你可以用 Position 类替换它（实际上相同的代码，但不是通用的，而是整数或浮点数）。

所以定义地图时：Map tiles = new HashMap;

为了将图块对象放置到地图上，我使用了 tiles.put(new Pair(x, y), new GrassTile()); 并用于检索对象tiles.get(new Pair(x, y));。

[x/y 可以是您想要放置的任何坐标（这允许负坐标，不会造成任何混乱！），“new GrassTile()”只是在地图期间放置某种类型的图块的示例创建。显然 - 如前所述 - Pair 类是可替换的。]

您可能会问为什么不是 ArrayLists？因为数组列表比映射更加线性，并且在我看来，添加和检索图块更加困难，尤其是在二维上。

更新：

对于任何想知道为什么 Java 中没有 Pair() 类的人，这里有一个 解释。

Answer 3

树、四叉树、二叉树、红树和黑树 - 以及所有其他种类的树对你来说都是无用的（除非你计划拥有一张包含巨大森林的地图）。

专门的数据结构有其特定的用途。除非您能找出游戏需要空间索引的充分理由，否则不要构建空间索引。如果您的典型场景是“迭代可见区域，找出每个方块上可见的图块”，那么您需要一个结构来快速、随机地访问存储在特定键下的值。这样的结构就是 HashMap（PHP 使用的是一种 LinkedHashMap，但您可能没有使用“链接”部分）。

您需要遵循 xephox 的建议（并给予他信任），即：

• 创建一个描述位置的类（对、位置、点等）；
• 将所有字段（可能是 x 和 y）定为最终字段。重要的是位置本身不能改变（这会让你的生活更轻松）；
• 生成 equals 和 hashcode 方法（每个 IDE 都会帮助您。记住，实现必须同时使用 x 和 y - IDE 中的向导会帮助您）；
• 你的地图将是： Map map = new HashMap();

最好的事情是：如果您继续使用地图界面，您将不会被锁定，并且您将能够做出很多改进。就像将 HashMap 包装到一个对象中，该对象使用一些算法技术创建映射的一部分。

Answer 4

我不是游戏编程专家，但如果数组没问题，您可以简单地将坐标从 (-x, +x) 转换为 (0, 2x)（同上，对于 y 轴）。

或者，如果您习惯像 PHP 那样的关联数组，则可以使用 Java 中的相应结构，即 Map（HashMap 就可以了）：使用适当的 equals 和 hashCode 方法定义一个 Cooperative 类，并使用HashMap<坐标>。使坐标不可变可以使代码更加健壮，并允许缓存 hashCode。

Answer 5

你可以尝试使用QuadTree（这里是一个很好的例子：http:// www.mikechambers.com/blog/2011/03/21/javascript-quadtree-implementation/）

Answer 6

将你的地图分成块怎么样（是的，Minecraft 粉丝，我也知道它用在哪里：P）？因此，您有两个坐标系，它们具有相同的原点：

• x/y 坐标
• c1/c2 块坐标

块始终是现实世界坐标的固定大小（例如 128x128） ）。然后你有一个类Chunk，其中有一个固定数组（128x128），其中包含每个像素的所有信息。并且您将块存储到 Map 中，正如其他人已经解释的那样。我会推荐一个HashMap。

每当你的玩家位于某个区域时，就会从地图中加载必要的块，然后你就可以访问那里的固定大小的数组。如果块知道它在 x/y 坐标中的位置，您甚至可以拥有一些支持函数，例如 Pixel Chunk#getPixel(long x, long y) 等...

顺便说一句：这也为您提供了一种简单的方法来推迟整个世界的生成，直到真正需要为止：开始时，不会生成任何内容，并且一旦在地图中访问了Chunk，尚未生成，您可以直接生成它。或者，如果对您来说更容易的话，您可以在启动时填写它。 （填充一个无限的世界需要很长时间，即使它是伪无限的）

Answer 7

我用 Java 编写了一些您可能感兴趣的实验性备用数据结构。

最有趣的是 Octreap 我认为这是 Treap 和 八叉树 ，它具有以下功能：

• 60 位世界坐标（大约 1,000,000 * 1,000,000 * 1,000,000 网格）
• 支持负坐标
• 空空间不需要存储（支持高度稀疏的世界）
• 压缩相同单元的体积（例如相同单元的大块）材料将得到有效存储）
• O(log n) 读取和写入

Answer 8

您可能想使用 Map 的实现。 HashMap、SortedMap 等取决于您打算存储多少数据和您的访问模式（Sorted Map 非常适合顺序访问，HashMap 更适合随机访问）。

您可以使用二维映射，也可以将二维索引转换为一维映射的键。

Answer 9

这是两个独立的问题：如何模拟负数组索引，以便拥有“无限”地图，以及如何有效地存储图块。

关于第一个问题，一个技巧是维护四个独立的矩阵（矩阵？），每个象限一个。那么所有的指标都可以为正。

关于第二个问题，你需要一张稀疏地图。一种不是很有效的方法是使用哈希图的哈希图。事实上，这也可以解决第一个问题：

HashMap<String, HashMap> x = new HashMap()
HashMap<String, Tile> y = new HashMap()

// get the tile at coordinates 1,2
Tile myTile = x.get("1").get("2");

// this would work as well
myTile = x.get("-1").get("-2");

您可以执行自己的 Map 实现，将整数作为键，并且效率要高得多。

Answer 10

如果您想要真正快速且真正可扩展，那么一定要使用稀疏八叉树。

http://en.wikipedia.org/wiki/Octree

我不知道有任何实现Java，不过是微不足道的。只需在单个字节中存储当前链接节点的位字段，并使用链接列表来保存这些引用（对于每个八叉树节点，有一个最多包含 8 个条目的单独列表）。

Answer 11

哈希图样式的解决方案对于邻接计算来说非常糟糕，它们需要整个数据集的迭代。

像四叉树或八叉树这样的东西是完美的，除了它不是无限的，它是任意大小的（那里存在差异）。

然而，如果你仔细想想，ArrayList 并不是无限的，它只是任意增长的大小，对吧？

因此，四叉树是稀疏的，并且可以很好地进行广告邻接计算，除了“无限”规定之外，它是完美的。为什么不直接使用您认为可能需要的 100 倍大小的一个（它很稀疏，并不是什么大问题）。如果您到达接近边缘的位置，请分配一个更大的新四叉树。

我相信，如果你小心的话（你可能必须实现你自己的四叉树），你可以用很少的努力来“升级”四叉树，并且不需要复制——这应该只是在所有现有地址前加上一些位的前缀（地址是二进制的，四叉树的每一位都表示将现有宇宙在一个维度或另一个维度上一分为二）。

Answer 12

使用 apache commons 中的 Pair 类。它有一个左值和一个右值，将 x 和 y 坐标实现为左/右。每对也分别根据其左值和右值进行哈希处理。

然后，您可以使用称为坐标的对的哈希集（Set<>）。这样，每个坐标都应该是唯一的。如果要将任何对象链接到坐标，则可以使用坐标及其相关对象的 HashMap。