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

Java: What is a good data structure for storing a coordinate map for an infinite game world?

提问by Ayk?n

I am used to coding in PHP but I am not really proficient with Java and this has been a problem for some time now. I expect it to be a fairly easy solution, however I cannot find any good example code any way I search it, so here goes:

我习惯用 PHP 编码，但我并不真正精通 Java，这已经有一段时间了。我希望它是一个相当简单的解决方案，但是我无法以任何方式搜索它的任何好的示例代码，所以这里是：

I am programming a game that takes place in a 2d random generated infinite world on a tile based map (nitpicking: I know it will not be truly infinite. I just expect the world to be quite large). The usual approach of map[x][y] multidimensional array started out as a basic idea, but since Java does not provide a way for non-integer (i.e. negative) array key shenanigans like PHP does, I cannot properly have a (-x,+x,-y,+y) coordinate system with array keys.

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

I need to be able to find the objects on a tile at a specific x,y coordinate as well as finding "adjacent tiles" of a certain tile. (Trivial if I can getObjectAt(x,y), I can get(x+1,y) and so on)

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

I have read about quad trees and R-trees and the like. The concept is exciting, however I haven't seen any good, simple example implementation in Java. And besides I am not really sure if that is what I need exactly.

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

Any advice is welcome

欢迎任何建议

Thank you

谢谢

采纳答案by Liam Gray

I came to this thread with the same problem, but my solution was to use Map/HashMaps, but these are one dimensional.

我带着同样的问题来到这个线程，但我的解决方案是使用Map/HashMaps，但这些是一维的。

To overcome this, instead of using a map within a map (which would be messy and very inefficient) I used a generic Pairclass (not something that you'll find in the stock java library) although you could replace this with a Position class (virtually the same code, but not generic, instead integers or floats).

为了克服这个问题，我使用了一个通用的Pair类（不是你会在股票 java 库中找到的东西），而不是在地图中使用地图（这会很麻烦而且效率很低），尽管你可以用一个 Position 类替换它（几乎相同的代码，但不是通用的，而是整数或浮点数）。

So when defining the map: Map<Pair, Tile> tiles = new HashMap<Pair, Tile>;

所以在定义地图时： Map<Pair, Tile> tiles = new HashMap<Pair, Tile>;

For placing tile objects onto the map I used tiles.put(new Pair(x, y), new GrassTile());and for retrieving the object tiles.get(new Pair(x, y));.

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

[x/y would be any coordinate you wish to place (this allows negative coordinateswithout any mess!), "new GrassTile()" is just an example of placing a tile of a certain type during map creation. Obviously - as previously stated - the Pair class is replacable.]

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

Why not ArrayLists you may ask? Because array lists are much more linear than mapping, and in my opinion are more difficult to add and retrieve tiles, especially on 2 Dimensions.

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

Update:

更新：

For anyone wondering why there isn't a Pair() class in Java, here's an explanation.

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

回答by davin

1) Instead of an array you could use a Map<Integer, Map<Integer, Tile>>or Map<Point, Tile>, which would of course allow negative indexes

1) 您可以使用Map<Integer, Map<Integer, Tile>>or代替数组Map<Point, Tile>，这当然允许负索引

2) If you know the dimensions of your world from the start you could just modify your getter to allow the API to accept negatives and [linearly] transform them into positives. So for example if your world is 100x1000 tiles and you want (-5,-100), you would have WorldMap.getTile(-5,-100)which would translate to return tileArray[x+mapWidth/2][y+mapHeight/2];which is (45,400)

2）如果你从一开始就知道你的世界的维度，你可以修改你的 getter 以允许 API 接受否定并[线性地]将它们转换为肯定。因此，例如，如果您的世界是 100x1000 的图块并且您想要 (-5,-100)，那么您会将WorldMap.getTile(-5,-100)哪个转换return tileArray[x+mapWidth/2][y+mapHeight/2];为 (45,400)

回答by fdreger

Trees, Quad Trees, Binary trees, red and black trees - and all other kinds of trees are USELESS for you (unless you are planning to have a map with a huge forest).

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

Specialized data structures have their specific uses. Unless you can come up with a good reason why your game needs a spatial index, don't build one. If your typical scenario is "iterate over the visible area, find out what tile is visible at each of the squares", then you need a structure that gives you a quick, random, access to a value stored under a specific key. Such structure is a HashMap (what PHP uses is a kind of a LinkedHashMap, but you were probably not using the "linked" part).

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

You need to follow xephox's advice (and give him the credit), and that is:

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

• make a class that describes a location (Pair, Location, Point, whatever);
• make all the fields (probably x and y) final. It is important that a location itself cannot change (it will make your life MUCH easier);
• generate equals and hashcode methods (every IDE will help you with that. Remember that the implementations MUST use both x and y - a wizard in your IDE will help you);
• your map will be: Map map = new HashMap();

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

The best thing: if you keep using the Map interface, you will not be locked out, and you will be able to make a lot of improvements. Like wrapping the HashMap into an object that creates parts of the map using some algorithmic techniques.

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

回答by JB Nizet

I'm not an expert in game programming, but if arrays are OK, you could simply translate your coordinates from (-x, +x) to (0, 2x) (idem for the y axis).

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

Or if you're used to associative arrays like PHP has, the use the corresponding structure in Java, which is a Map (HashMap would be OK) : define a Coordinateclass with appropriate equals and hashCode methods, and use a HashMap<Coordinate>. Making Coordinate immutable makes the code more robust, and allows caching the hashCode.

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

回答by Simon

you could try a QuadTree (nice example here: http://www.mikechambers.com/blog/2011/03/21/javascript-quadtree-implementation/)

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

回答by mikera

I wrote a couple of experimental spare data structures in Java that you might be interested in.

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

The most interesting one was the Octreapwhich is what I believe is a completely novel cross between a Treapand an Octree, which had the following features:

最有趣的是Octreap，我认为它是Treap和Octree之间的一种全新的交叉，它具有以下特点：

• 60 bit world co-ordinates (aprox 1,000,000 * 1,000,000 * 1,000,000 grid)
• Negative co-ordinates supported
• Empty space requires no storage (supports highly sparse worlds)
• Compresses volumes of identical cells (e.g. large blocks of the same material would get stored efficiently)
• O(log n) for reads and writes

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

回答by brimborium

How about dividing your map into chunks (yes, Minecraft fans, I know where this is used as well :P)? So you have two coordinate systems, both with the same origin:

把你的地图分成几块怎么样（是的，Minecraft 的粉丝，我也知道这在哪里用：P）？所以你有两个坐标系，都具有相同的原点：

• x/ycoordinates
• c1/c2chunk coordinates

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

A chunk is always a fixed size of real world coordinate (say 128x128). Then you have a class Chunkwhere you have a fixed array (128x128) with all the information for every pixel. And you store your chunks into a Map<ChunkCoordinates, Chunk>as was already explained by others. I would recommend a HashMap.

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

Whenever your player is in a certain region, the neccessary chunks are loaded from the map and then you can access the fixed size array in there. If the chunk knows, where it is placed in x/ycoordinates, you can even have some support function like Pixel Chunk#getPixel(long x, long y)or so...

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

Btw: This also gives you an easy way to postpone generation of the whole world until it is really needed: At start, nothing is generated and as soon as a Chunkis accessed in the map, that is not yet generated, you can just generate it then. Or you could fill it up at startup if that's easier for you. (filling an infinite world will take a long time though, even if it is pseudo infinite)

顺便说一句：这也为您提供了一种简单的方法，可以将整个世界的生成推迟到真正需要它时：一开始，什么都不会生成，一旦Chunk在地图中访问了尚未生成的 a，您就可以生成它然后。或者你可以在启动时填满它，如果这对你来说更容易。（尽管填充无限世界需要很长时间，即使它是伪无限的）

回答by Bill K

The hashmap style solutions are terrible for adjacency calculations, they require an iteration of the entire dataset.

hashmap 风格的解决方案对于邻接计算来说很糟糕，它们需要对整个数据集进行迭代。

Something like a quadtree or octree is perfect EXCEPT that it's not infinite, it's an arbitrary size (world of difference there).

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

However if you think about it, an ArrayList isn't infinite, it's just an arbitrary size that grows, right?

但是，如果您考虑一下，ArrayList 不是无限的，它只是一个任意大小的增长，对吗？

So a quadtree is sparce and pretty good ad adjacency calculations, except for the "infinite" provision it's perfect. Why not just use one of those sized to 100x what you think you might need (it's sparse, not really a big deal). If you ever get to the point where you are near the edge, allocate a new quadtree that is much bigger.

所以四叉树是稀疏的并且非常好的广告邻接计算，除了“无限”规定它是完美的。为什么不使用其中一个大小为您认为可能需要的大小的 100 倍（它很稀疏，并不是什么大问题）。如果您到达边缘附近的点，请分配一个更大的新四叉树。

I believe if you are careful (you may have to implement your own quadtree) you can "upgrade" the quadtree with very little effort and no copying--it should be simply a matter of prefixing all your existing addresses with some bits (the addresses are in binary, quadtrees each bit represents dividing the existing universe in half in one dimension or the other).

我相信如果您小心（您可能必须实现自己的四叉树），您可以毫不费力地“升级”四叉树，无需复制——这应该只是在所有现有地址前面加上一些位（地址是二进制的，四叉树的每一位代表将现有的宇宙在一个维度或另一个维度上分成两半）。

回答by patros

You probably want to use an implementation of Map. HashMap, SortedMap, etc depending on how much data you intend to store and your access patterns (Sorted Map is very good for sequential access, HashMap is better for random access).

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

You can either use two-dimensional Maps or munge your 2-d indeces into a key for a 1-d Map.

您可以使用二维地图或将您的 2-d indeces 转换为 1-d Map 的键。

回答by ccleve

This is two separate questions: how to simulate negative array indicies so you can have an "infinite" map, and how to store tiles efficiently.

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

On the first question, one hack would be to maintain four separate matricies (matrixes?), one for each quadrant. Then all the indexes can be positive.

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

On the second question, you need a sparse map. One not-very-efficient way is to have a hashmap of hashmaps. In fact, that could solve the first problem as well:

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

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");

You could do your own Map implementation that took integers as keys and was much, much more efficient.

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