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

Question

我正在尝试用函数编程风格编写游戏,这意味着用纯粹功能的,不可变的数据结构来表示游戏状态.

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

• 不可变
• 快速持久更新 - 即通过小的变化创建整个网格的新版本是便宜的并且通过结构共享来实现.网格可能很大,因此写时复制不是一个可行的选择.
• 对稀疏区域/相同值的有效处理 - 空/未填充区域应该不消耗资源(以允许大的开放空间).如果它在存储相同值的大"块"方面也很有效,则可以获得奖励积分
• 无界 - 可以根据需要向任何方向生长
• 快速读取/查找 - 即可以快速检索[x,y,z]处的对象
• 快速卷查询,即快速搜索区域[x1,y1,z1] - > [x2,y2,z2],理想情况下利用稀疏性,以便快速跳过空白区域

有关最佳数据结构的建议吗？

PS我知道这可能不是最实用的写游戏方式,我只是把它作为一种学习经验并用FP来扩展我的能力......

Answer 1

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

我认为不可变和无界（通常）是相互冲突的要求。
无论如何......要生长八叉树，您必须更换根。

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