Java：为无限的游戏世界存储坐标图的好的数据结构是什么？
我习惯于使用PHP进行编码，但是我对Java并不熟练，现在这已经成为一个问题了。 我期望它是一个相当简单的解决scheme，但是我找不到任何好的示例代码，所以我在这里search：
我正在编程一个游戏，发生在基于瓦片的地图上的二维随机生成的无限世界中（我知道它不会是真正无限的，我只是期望世界变得相当大）。 map [x] [y]multidimensional array的常用方法是作为一个基本思想开始的，但是由于Java没有为像PHP这样的非整数（即负数）的数组关键字提供一种方法，我不能正确地使用（ – x，+ x，-y，+ y）带有数组键的坐标系统。
我需要能够在一个特定的x，y坐标上查找一个图块上的对象，以及查找某个图块的“相邻图块”。 （微不足道，如果我可以getObjectAt（x，y），我可以得到（x + 1，y）等）
我读过四叉树和R树等。 这个概念是令人兴奋的，但是我还没有看到Java中的任何好的，简单的示例实现。 除此之外，我不确定这是否正是我所需要的。
任何build议是受欢迎的
谢谢
我来到这个线程有同样的问题，但我的解决scheme是使用Map / HashMaps ，但这些是一维的。
为了克服这个问题，我使用了一个普通的Pair类（不是在股票java库中可以find的东西），而不是在地图内使用地图（这将是一个混乱和非常低效的），尽pipe你可以用Position类replace它（几乎相同的代码，但不是通用的，而是整数或浮动）。
所以当定义地图时： Map<Pair, Tile> tiles = new HashMap<Pair, Tile>;
为了将贴图对象放到地图上，我使用tiles.put(new Pair(x, y), new GrassTile()); 并检索对象tiles.get(new Pair(x, y)); 。
[x / y将是你想要放置的任何坐标（ 这允许负面坐标没有任何混乱！），“新GrassTile（）”只是在地图创build过程中放置某种types的图块的一个例子。 很显然 – 如前所述 – Pair类是可replace的。]
为什么不ArrayLists你可能会问？ 由于数组列表比线性更加线性，在我看来，添加和检索切片更加困难，特别是在2维上。
更新：
对于任何人想知道为什么Java中没有Pair（）类，下面是一个解释 。
1）而不是一个数组，你可以使用Map<Integer, Map<Integer, Tile>>或Map<Point, Tile> ，这当然会允许负面的索引
2）如果你从一开始就知道你的世界的维度，你可以修改你的getter来让API接受否定的结果，并且[线性地]把它们转化为正面的结果。 因此，例如，如果你的世界是100×1000的瓷砖，你想要（-5，-100），你将有WorldMap.getTile(-5,-100) ，这将转化为return tileArray[x+mapWidth/2][y+mapHeight/2]; （45,400）
我不是游戏编程方面的专家，但是如果数组没有问题的话，你可以简单地将你的坐标从（-x，+ x）转换为（0,2x）（对于y轴同样）。
或者，如果您习惯于像PHP这样的关联数组，则可以使用Java中相应的结构（即Map（HashMap应该是OK））：使用适当的equals和hashCode方法定义Coordinate类，并使用HashMap<Coordinate> 。 使Coordinate不可变使代码更健壮，并允许cachinghashCode。
树木，四叉树，二叉树，红黑树和其他所有树木对你来说都是无用的（除非你打算有一个巨大的森林地图）。
专门的数据结构有其特定的用途。 除非你能想出一个很好的理由，为什么你的游戏需要一个空间索引，不要build立一个。 如果您的典型场景是“遍历可见区域，找出在每个方块上可见的图块”，那么您需要一个结构，使您能够快速，随机地访问存储在特定密钥下的值。 这样的结构是一个HashMap（PHP使用的是一种LinkedHashMap，但你可能不使用“链接”部分）。
你需要遵循xephox的build议（并给他信贷），那就是：
- 做一个描述位置的类（Pair，Location，Point，等等）;
- 使所有的字段（可能是x和y）最终。 一个位置本身不能改变是非常重要的（这会让你的生活变得更容易）;
- 生成equals和hashcode方法（每个IDE都会帮助你，请记住，实现必须同时使用x和y–在你的IDE中的向导将会帮助你）。
- 你的地图将会是：Map map = new HashMap（）;
最好的事情是：如果你继续使用Map界面，你不会被locking，你将能够做出很多改进。 就像将HashMap封装到一个使用某些algorithm技术创build地图部分的对象一样。
你可以尝试一个QuadTree（很好的例子： http : //www.mikechambers.com/blog/2011/03/21/javascript-quadtree-implementation/ ）
把你的地图分成几块（是的，Minecraft的粉丝，我知道这里也用到了：P）？ 所以你有两个坐标系统，都有相同的来源：
-
x/y坐标 -
c1/c2块坐标
块总是一个固定大小的现实世界坐标（比如128×128）。 然后你有一个类Chunk你有一个固定的数组（128×128）与每个像素的所有信息。 并且你将你的块存储到一个Map<ChunkCoordinates, Chunk>正如其他人已经解释过的那样。 我会推荐一个HashMap 。
只要你的播放器在某个特定的区域，必要的块从地图加载，然后你可以在那里访问固定大小的数组。 如果块知道，它被放置在x/y坐标中，你甚至可以有一些支持像Pixel Chunk#getPixel(long x, long y)左右的function。
顺便说一句：这也给了你一个简单的方法来推迟整个世界的生成，直到它真的需要：在开始时，什么也没有生成，只要一个Chunk在地图中访问，尚未生成，您可以生成那呢。 或者你可以在启动时填写它，如果这对你更容易。 （填补无限世界需要很长时间，即使是伪无限的）
我写了一些你可能感兴趣的Java实验备用数据结构。
最有意思的是Octreap ，我相信它是一个Treap和Octree之间的完全新颖的交叉，它具有以下特征：
- 60位世界坐标（约100万* 1,000,000 * 1,000,000格）
- 消极的协调支持
- 空的空间不需要存储（支持高度稀疏的世界）
- 压缩相同单元的体积（例如，相同材料的大块将被有效存储）
- O（log n）用于读取和写入
你可能想要使用Map的实现。 HashMap，SortedMap等，这取决于你打算存储多less数据和你的访问模式（Sorted Map对顺序访问非常好，HashMap对于随机访问更好）。
您可以使用二维地图，也可以将二维数据embedded到一维地图的关键字中。
这是两个不同的问题：如何模拟负数组标记，以便可以有一个“无限”的地图，以及如何有效地存储瓷砖。
关于第一个问题，一个黑客应该是维护四个不同的matrix（matrix？），每个象限一个matrix。 那么所有的指标都可以是正面的。
关于第二个问题，你需要一个稀疏的地图。 一个不是非常有效的方法是拥有hashmaps的hashmap。 事实上，这也可以解决第一个问题：
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");
你可以做你自己的地图实现，把整数作为关键，更有效得多。
如果你想成为一个真正的快速和真正的可扩展性，一定要去一个稀疏的八叉树。
我不知道在Java中的任何实现，但它是微不足道的。 只需要在一个字节中存储一个当前链接节点的位域，并使用一个链表来保存这些引用（每个八叉树节点最多8个条目的单独列表）。
hashmap风格的解决scheme对于邻接计算来说很糟糕，它们需要迭代整个数据集。
像四叉树或八叉树是完美的除了它不是无限的，它是一个任意大小（世界的差异）。
但是，如果你想一想，ArrayList不是无限的，它只是一个随机的大小，对吧？
所以四叉树是sparce和相当不错的广告毗邻计算，除了“无限”的规定，这是完美的。 为什么不使用其中一个大小为100倍你认为你可能需要（这是稀疏的，不是什么大不了的）。 如果你已经到了靠近边缘的地步，分配一个更大的新四叉树。
我相信，如果你很小心（你可能需要实现自己的四叉树），你可以用很less的努力来“升级”四叉树，而不需要复制 – 它应该只是一个简单的问题，是二进制的，四叉树每一位表示将现有的宇宙一分为二或一分为二）。
