language-agnostic - 不可变持久 3D 网格的最佳数据结构

Question

我正在尝试以函数式编程风格编写游戏，这意味着用纯函数式、不可变数据结构表示游戏状态。

最重要的数据结构之一是表示世界的 3D 网格，其中对象可以存储在任何 [x,y,z] 网格位置。我想要这个数据结构的属性是:

不可变

快速持续更新 - 即，通过结构共享，以较小的更改创建整个网格的新版本很便宜。网格可能很大，所以写时复制不是一个可行的选择。

有效处理稀疏区域/相同值 - 空的/无人居住的区域不应消耗资源(以允许大型开放空间)。如果它在存储相同值的大“块”方面也很有效，则加分

无界 - 可以根据需要向任何方向生长

快速读取/查找 - 即可以快速检索 [x,y,z] 处的对象

快速批量查询 ，即快速搜索区域 [x1,y1,z1] -> [x2,y2,z2]，理想情况下利用稀疏性以便快速跳过空白空间

关于用于此的最佳数据结构的任何建议？

附言我知道这可能不是编写游戏最实用的方法，我只是将它作为一种学习经验并用 FP 扩展我的能力......

Answer 1

我会尝试八叉树。每个节点的边界坐标隐含在结构放置中，每个非终结节点保留8个子树但没有数据。因此，您可以“联合”以获得空间。

我认为不可变 和 无界是(通常)相互冲突的要求。
无论如何......要种植八叉树，您必须替换根。

应满足您提出的其他要求。