不可变持久 3D 网格的最佳数据结构
我正在尝试以函数式编程风格编写游戏，这意味着用纯函数式、不可变的数据结构来表示游戏状态。
最重要的数据结构之一是代表世界的 3D 网格，其中对象可以存储在任何 [x,y,z] 网格位置。我想要的这个数据结构的属性是：
- 不可变
- 快速持久更新 - 即通过小的更改创建整个网格的新版本成本低廉，并且通过结构共享实现。网格可能很大，因此写入时复制不是一个可行的选择。
- 有效处理稀疏区域/相同值 - 空的/无人居住的区域不应消耗任何资源（以允许较大的开放空间）。如果它还能有效地存储相同值的大“块”，则奖励积分
- 无界 - 可以根据需要向任何方向增长
- 快速读取/查找 - 即可以快速检索对象(s) at [x,y,z]
- 快速批量查询，即快速搜索区域 [x1,y1,z1] -> [x2,y2,z2]，理想情况下利用稀疏性，以便快速跳过空白空间
关于用于此目的的最佳数据结构有什么建议吗？
PS我知道这可能不是编写游戏的最实用方式，我只是将其作为一种学习经验并扩展我的 FP 能力......
I'm experimenting with writing a game in a functional programming style, which implies representing the game state with a purely functional, immutable data structures.
One of the most important data structures would be a 3D grid representing the world, where objects can be stored at any [x,y,z] grid location. The properties I want for this data structure are:
- Immutable
- Fast persistent updates - i.e. creation of a new version of the entire grid with small changes is cheap and achieved through structural sharing. The grid may be large so copy-on-write is not a feasible option.
- Efficient handling of sparse areas / identical values - empty / unpopulated areas should consume no resources (to allow for large open spaces). Bonus points if it is also efficient at storing large "blocks" of identical values
- Unbounded - can grow in any direction as required
- Fast reads / lookups - i.e. can quickly retrieve the object(s) at [x,y,z]
- Fast volume queries, i.e. quick searches through a region [x1,y1,z1] -> [x2,y2,z2], ideally exploiting sparsity so that empty spaces are quickly skipped over
Any suggestions on the best data structure to use for this?
P.S. I know this may not be the most practical way to write a game, I'm just doing it as a learning experience and to stretch my abilities with FP......
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我会尝试八叉树。每个节点的边界坐标在结构放置中是隐式的，每个非终端节点保留8个子树但没有数据。因此，您可以通过“联合”来获得空间。
我认为不可变和无界（通常）是相互冲突的要求。
无论如何......要生长八叉树，您必须更换根。
您提出的其他要求应得到满足。
I'd try an octtree. The boundary coordinates of each node are implicit in structure placement, and each nonterminal node keep 8 subtree but no data. You can thus 'unioning' to gain space.
I think that Immutable and Unbounded are (generally) conflicting requirements.
Anyway... to grow a octtree you must must replace the root.
Other requirement you pose should be met.