有效存储稀疏的2D网格

Question

我有一张巨大的地图，上面有瓷砖。这是一个地牢，所以显然有很多空白空间，我将在其中存储空值。

显然，拥有巨大的2D阵列是一种选择，但我认为这不是最优雅的一种。另外，当我想将其保存到文件中时，存储大量的空标记不是很整齐。

像这样的东西，但是要大得多：

+--------------+
|   X     X    |
| XXX    XX    |
|   XXXXXXX    |
|    X   XX    |
|   XXX   XXX  |
|     X   X    |
+--------------+ 

我还可以使用宽度×高度数组的其他替代方法吗？

只有这样Map<IntCoord, Tile>吗？还是在类似情况下有一些广泛使用的解决方案？

Answer 1

您可以使用三件事：

1. 2D阵列。
2. 清单。
3. 地图。

除非您的地图很大，否则二维数组是最好的，在这种情况下，您可以使用列表。

2D阵列：

优点：它具有最快的查找时间。

缺点：（很可能）占用最多的内存。

查找时间可能大大超过内存成本。除非您的地牢有成千上万的瓷砖，否则这可能是要走的路。

列表（可能是ArrayList）：

优点：仅存储您需要的物品。

缺点：查找时间会很糟糕。

虽然列表将使用较少的内存，但查找磁贴或项目将需要更长的时间，因为您必须遍历列表以查找与位置匹配的内容。

地图（可能是HashMap）：

优点：每个位置将在每个地图上链接到一个对象，因此查找时间可以。

缺点：查找时间不是最佳的，将使用适度的内存。

映射位于列表和数组之间。与阵列相比，会占用更多的内存，但与列表相比，查找时间更好。

由于查找时间的缘故，二维数组是最好的。在大多数现代计算机上，内存不是问题。如果是这样，您可以始终缓存当前未用于文件的区域，并根据需要动态加载它们。