不可变持久3D网格的最佳数据结构 [英] Best data structure for an immutable persistent 3D grid

问题描述

我正在尝试用功能编程风格编写游戏，这意味着用纯功能的，不可变的数据结构代表游戏状态。

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.

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

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:

• 不可变


• 快速持续更新 - 即创建具有小变化的整个网格的新版本是便宜的并且通过结构共享来实现。网格可能很大，所以写时复制不是一个可行的选择。


• 有效处理稀疏区域/相同的值 - 空/未填充区域应消耗没有资源（允许大的开放空间）。奖金积分，如果它也有效地存储相同值的大块块$ / $
  
• 无限 - 可以根据需要增加任何方向


• 快速阅读/查找 - 即可以快速检索[x，y，z]中的对象


• 快速查询，即快速搜索区域[x1，y1，z1] - > [x2，y2，z2]，理想地利用稀疏性，以便空格快速跳过

• 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?

PS我知道这可能不是写作游戏的最实际的方式，我只是做一个学习的经历，并用FP来伸展自己的能力......

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......

推荐答案

我会尝试八进制。每个节点的边界坐标在结构放置中是隐含的，每个非终结节点保留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.

我认为 Immutable 和无限是（一般）冲突的要求。

无论如何...要成长八卦，必须更换根。

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.

这篇关于不可变持久3D网格的最佳数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！