46

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

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

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

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

欢迎任何建议

谢谢

4

11 回答 11

7

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

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

于 2011-03-07T22:44:15.170 回答
5

我带着同样的问题来到这个线程，但我的解决方案是使用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() 类的人，这里有一个解释。

于 2012-06-07T15:50:10.010 回答
3

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

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

你需要听从 xephox 的建议（并给予他信任），那就是：

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

最好的一点：如果你一直使用地图界面，你就不会被锁在外面，而且你可以做出很多改进。就像将 HashMap 包装到使用某些算法技术创建部分地图的对象中一样。

于 2012-06-07T16:29:28.477 回答
2

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

或者，如果你习惯了 PHP 那样的关联数组，那么在 Java 中使用相应的结构，它是一个 Map（HashMap 就可以了）：Coordinate用适当的 equals 和 hashCode 方法定义一个类，然后使用HashMap<Coordinate>. 使 Coordinate 不可变使代码更加健壮，并允许缓存 hashCode。

于 2011-03-07T22:40:52.940 回答
2

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

于 2011-09-16T11:58:26.433 回答
1

我用 Java 写了几个实验性的备用数据结构，你可能会感兴趣。

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

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

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

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

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

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

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

于 2012-11-13T11:09:55.327 回答
0

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

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

于 2011-03-07T22:42:23.827 回答
0

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

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

关于第二个问题，您需要一张稀疏地图。一种不是很有效的方法是拥有一个 hashmap 的 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");

你可以做你自己的 Map 实现，它以整数作为键并且效率更高。

于 2011-03-07T22:48:01.220 回答
0

如果您想真正快速且真正可扩展，请务必使用稀疏八叉树。

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

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

于 2011-03-07T22:49:27.300 回答
0

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

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

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

因此，四叉树是稀疏且非常好的邻接计算，除了“无限”规定它是完美的。为什么不只使用您认为可能需要的大小为 100 倍的其中一个（它很少，没什么大不了的）。如果您到达靠近边缘的位置，请分配一个更大的新四叉树。

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

于 2013-08-08T20:32:01.047 回答