Best data structure for an immutable persistent 3D grid

Question

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

Answer 1

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.