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

我习惯用PHP编码，但我并不熟悉Java，这已经有一段时间了。我希望它是一个相当简单的解决方案，但是我无法通过任何方式找到任何好的示例代码，所以这里是：我正在编写一个游戏，它发生在基于图块的地图上的2d随机生成的无限世界中（挑剔：我知道它不会真正无限。我只是期望世界变得非常大）。 map [x] [y]多维数组的常用方法最初是作为一个基本思想开始的，但由于Java没有提供像PHP这样的非整数（即负数）数组密钥的方法，我无法正确地拥有（ - x，+ x，-y，+ y）带数组键的坐标系。我需要能够在特定的x，y坐标上找到瓷砖上的对象，以及找到某个瓷砖的“相邻瓷砖”。（如果我可以getObjectAt（x，y），我可以获得（x + 1，y）等等）我读过四棵树和R树等。这个概念很令人兴奋，但我还没有在Java中看到任何好的，简单的示例实现。此外，我不确定这是否是我所需要的。欢迎任何建议谢谢

已邀请:

11 个回复

嘘崇蔡对

我遇到同样的问题来到这个线程，但我的解决方案是使用Map / HashMaps，但这些都是一维的。为了克服这个问题，我没有在地图中使用地图（这将是凌乱和非常低效的），我使用了通用的Pair类（不是你在库存java库中找到的东西），尽管你可以用Position类替换它（几乎相同的代码，但不是通用的，而是整数或浮点数）。所以在定义地图时：Map<Pair, Tile> tiles = new HashMap<Pair, Tile>; 为了将瓷砖对象放置在地图上，我使用tiles.put(new Pair(x, y), new GrassTile());并检索对象tiles.get(new Pair(x, y));。 [x / y将是您想要放置的任何坐标（这允许负坐标，没有任何混乱！），“new GrassTile（）”只是在地图创建期间放置某种类型的图块的示例。显然 - 如前所述 - Pair类是可替换的。你为什么不问ArrayLists？因为数组列表比映射更加线性，并且在我看来更难以添加和检索切片，尤其是在2维上。更新：对于任何想知道为什么Java中没有Pair（）类的人，这里有一个解释。

稼悸

1）你可以使用Map<Integer, Map<Integer, Tile>>或Map<Point, Tile>代替数组，这当然会允许负指数 2）如果你从一开始就知道你的世界的维度，你可以修改你的getter以允许API接受负数并[线性]将它们转换为正数。因此，例如，如果你的世界是100x1000个瓷砖而你想要（-5，-100），你将有WorldMap.getTile(-5,-100)，这将转换为return tileArray[x+mapWidth/2][y+mapHeight/2];，即（45,400）

枫湃揩乾纲

树木，四棵树，二叉树，红色和黑色的树木以及所有其他类型的树木对你来说都是无用的（除非你打算有一张巨大的森林地图）。专门的数据结构有其特定的用途。除非你能想出你的游戏需要空间索引的充分理由，否则不要构建一个空间索引。如果您的典型场景是“遍历可见区域，找出每个方块上可见的图块”，那么您需要一种结构，使您可以快速，随机地访问存储在特定键下的值。这样的结构是一个HashMap（PHP使用的是一种LinkedHashMap，但你可能没有使用“链接”部分）。你需要遵循xephox的建议（给他信用），那就是：创建一个描述位置的类（Pair，Location，Point，等等）; 使所有字段（可能是x和y）最终。一个位置本身不能改变是很重要的（它会让你的生活变得更容易）; 生成equals和hashcode方法（每个IDE都会帮助你。请记住，实现必须同时使用x和y - IDE中的向导将帮助你）; 你的地图将是：Map map = new HashMap（）; 最好的事情是：如果你继续使用Map界面，你将不会被锁定，并且你将能够做出很多改进。就像将HashMap包装成一个使用一些算法技术创建地图部分的对象一样。

稍惮

我不是游戏编程方面的专家，但如果数组没问题，你可以简单地将坐标从（-x，+ x）转换为（0,2x）（y轴的同一性）。或者，如果您习惯像PHP那样的关联数组，则使用Java中的相应结构，即Map（HashMap可以）：使用适当的equals和hashCode方法定义一个Coordinate类，并使用HashMap<Coordinate>。使Coordinate不可变使代码更健壮，并允许缓存hashCode。

夏瓤跋棘

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

擅香

如何将你的地图分成块（是的，Minecraft的粉丝，我知道在哪里使用它：P）？所以你有两个坐标系，都有相同的原点： x/y坐标 c1/c2块坐标块总是固定大小的真实世界坐标（比如128x128）。然后你有一个类Chunk，你有一个固定数组（128x128），包含每个像素的所有信息。然后你把你的块存放到Map<ChunkCoordinates, Chunk>，正如其他人已经解释过的那样。我会推荐一个HashMap。只要您的播放器位于某个区域，就会从地图加载必要的块，然后您可以访问其中的固定大小的阵列。如果块知道它放在x/y坐标中的位置，你甚至可以有一些支持函数，如Pixel Chunk#getPixel(long x, long y)左右...... 顺便说一句：这也为你提供了一个简单的方法来推迟整个世界的生成，直到它真正需要：开始时，什么也没有生成，一旦在地图中访问Chunk，尚未生成，你只需生成然后呢。或者你可以在启动时填写它，如果这对你来说更容易。（填充无限的世界将需要很长时间，即使它是伪无限的）

吠强祷豪硅

我用Java编写了一些您可能感兴趣的实验备用数据结构。最有趣的是Octreap，我认为它是Treap和Octree之间完全新颖的交叉，具有以下特征： 60位世界坐标（aprox 1,000,000 * 1,000,000 * 1,000,000网格）支持负坐标空白空间不需要存储（支持高度稀疏的世界）压缩相同单元的体积（例如，相同材料的大块将被有效存储） O（log n）用于读写

膛嵌墒缅欠

您可能想要使用Map的实现。 HashMap，SortedMap等取决于您要存储的数据量和访问模式（Sorted Map非常适合顺序访问，HashMap更适合随机访问）。您可以使用二维地图，也可以将2-d indeces放入1-d Map的键中。

粱委教

这是两个单独的问题：如何模拟负数组指示，以便您可以拥有“无限”地图，以及如何有效地存储切片。在第一个问题上，一个hack将维护四个独立的矩阵（矩阵？），每个象限一个。然后所有索引都可以是正数。在第二个问题上，您需要一个稀疏的地图。一种不太有效的方法是使用哈希映射的哈希映射。事实上，这也可以解决第一个问题：

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实现，并且效率更高。

屡倒雷图

如果你想要真正快速和真正可扩展肯定与稀疏八叉树。 http://en.wikipedia.org/wiki/Octree 我不知道Java中的任何实现，但它是微不足道的。只需在单个字节中存储当前链接节点的位域，并使用链接列表来保留这些引用（对于每个八叉树节点，单独列出最多8个条目）。

杰黔轿缺

hashmap样式解决方案对于邻接计算很糟糕，它们需要迭代整个数据集。像四叉树或八叉树这样的东西是完美的，除了它不是无限的，它是一个任意的大小（那里的差异世界）。但是如果你考虑一下，ArrayList不是无限的，它只是一个增长的任意大小，对吧？所以四叉树是sparce和非常好的广告邻接计算，除了“无限”条款它是完美的。为什么不使用其中一个大小到100倍你认为你可能需要的东西（它很稀疏，并不是什么大不了的事）。如果你到达了靠近边缘的位置，请分配一个更大的新四叉树。我相信如果你小心（你可能必须实现自己的四叉树），你可以轻松地“升级”四叉树而不需要复制 - 它应该只是在所有现有地址前加一些位（地址）在二进制，四叉树中，每个位表示将现有宇宙在一个维度或另一个维度中分成两半）。

要回复问题请先登录或注册

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

11 个回复

发起人

coordinate

tile

问题状态

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

与内容相关的链接

11 个回复

发起人

coordinate

tile

问题状态