存储和加载二维无限程式生成的基于瓦片的世界

背景:

我正在开发一个二维无限世界生成器。它是基于瓦片的,意味着我的地形完全由方块组成。你可以把它想象成从上方观察到的二维Minecraft地形。

我实现了标准块系统,将地形分割成小的8x8瓦片区域,这些区域会随着玩家在世界中的行动而被加载和删除。到目前为止,这个系统非常顺畅,没有任何卡顿或延迟。我使用的是Lua和Corona SDK。

问题:

由于玩家将能够修改地形,我需要一个快速高效的系统,在玩家加载新块时将块存储在内存中,并且能够从内存中加载这些块,如果它们之前已经被加载过。

这就是问题所在。它需要经常从文件(内存)中读取和保存,这会导致明显的延迟。将块变得更大不是一个选择。

我尝试过但都会导致延迟的解决方案:

a)我实现的第一个和显而易见的解决方案,就是为每个块创建一个文本文件,用字符串作为瓦片名称。它看起来像这样:x12y10.txt,文件内我按它们在屏幕上需要放置的顺序倾倒了所有瓦片名称:"Grass Grass Water Sand Sand Sand Grass Grass ..."。这很管用,但加载字符串很慢,所以我尝试了另一个解决方案:将瓦片保存为索引。

b)将瓦片保存为它们的索引。我将每个瓦片与一个数字配对。由于数字更短,它们占用更少的内存并且更快速度。我为每个瓦片分配了它自己的索引:Grass -> id 1Water -> id 2Sand -> id 3等等。这样,我只需要为每个瓦片保存1或2个字符而不是完整的字符串。现在,我的文本文件看起来像这样:"1 1 2 3 3 3 1 1 ..."。这个解决方案效果更好,但仍然会导致延迟。

c)我所做的下一个改进是如何在内存中组织块。与其将所有块倾倒到单个文件夹中,我为每个x坐标创建了一个文件夹,并把具有该x值的所有块放在其中。

所以,与其这样:

-包含所有块的文件夹:x0y0.txtx0y1.txtx0y2.txtx1y0.txtx1y1.txtx1y2.txt

所有块的文件夹内都是这样的:

-文件夹x0:x0y0.txtx0y1.txtx0y2.txt

-文件夹x1:x1y0.txtx1y1.txt x1y2.txt

我不确定这有多大帮助,对于少数块而言,但我很确定对于数千个块,有所改善。

可能的解决方案?

我有一些改进的想法,但我想听听你对这些解决方案的意见。

a)将地形保存在二进制文件中?

b)我已经阅读了有关Minecraft区域格式的文档,真的很想了解它的工作原理,但由于几乎没有关于它的信息,所以我没有得到它。因此,如果有人了解它并能够向我解释他们的系统,我将不胜感激。

c)其他更快的文件格式?

d)创建/访问许多文件夹会很慢吗?是否有更好的替代方案?

点赞
用户4687565
用户4687565

我真的觉得这是一个cs-101问题,但是无法立即通过Google找到任何答案,所以快速总结。

所有文件都只是一系列字节。如果我们谈论读写原始字节,没有任何格式可以使64个字节在内存中比另一个更快地出现。

文本文件是一系列具有轻微值限制的字节(好吧,限制是如果您希望标准文本程序将其显示)。文本文件中的字符串“11”(位序列:110001110001)不会比从“二进制”文件中加载的不可打印位序列100000100000更快。

至少在目录结构中的规划可以减少系统在尝试打开您请求的文件时检查的节点数量。但是,底层文件系统的机制非常复杂,并受到许多因素的影响。总体猜测是即使是小文件的频繁读取也会很慢。由于所有文件都带有一些储备开销(系统信息以使其跟踪和排序),因此小文件将具有较低的实用/辅助信息比率。我至少知道有一个二维项目,其可变地图在多年前移动到更大的文件之前会使硬盘发出咆哮声和哀嚎声。

您不必使块变得更大,那是不同的事情,但是您可以将它们写入同一个文件中。使用每个块一个字节的假设,您可以有一个单独的兆字节文件,而不是64个字节的100万个文件。 一百万个块对于玩家来说修改或遍历是很多的。如果将数据解压缩到表中,它将占用更多的空间,但您不必解密所有字符串,只需要当前需要的字节。是的,使用lua修改兆字节字符串会导致创建另一个兆字节字符串,这很慢,但是您不必每次都这样做,或者您可以将字符串拆分为较小的字符串并对它们进行修改。只在需要时进行写入。 I/O缓冲可以在没有您干预的情况下发生,但是它通常对于大文件非常有用。 是的,每个图块会有超过一个字节的信息(每个图块有2^8个可能的状态非常多),但系统保持不变。

纹理也是这样做的,因为在单个大块中加载数据比在这里那里搜索微小位更快。索引单个长存储区域也比追踪指针更快。

除此之外,您可以尝试读写比内存中需要的字节少。例如通过压缩数据。

2018-07-25 16:09:54
用户5129715
用户5129715

在 Minecraft 中,除非它们被访问/修改过,否则不会存储区块,否则它们会生成。

这将使您拥有一个系统,只有玩家修改过的方块需要存储,未修改的区域通过使用相同的随机种子每次重新生成。

创建一种修改的层次结构……一个区块是一个8x8块,创建一个超级区块,它是8x8个区块,仅查找文件,如果8x8个超级区块中的任何一个被修改过。

可能将所有超级区块都存储在一个文件中,这将限制文件的数量(增加文件会降低系统速度,也会浪费系统的空间)。

如果您有一些闲置的时间和空间,可以在玩家附近创建一个区块缓存,并预加载即将接近的修改区域。这将限制所需的可见滞后。

2018-07-25 16:20:52