Better data structure for immutable 3D mesh

Question

I am experimenting with writing a game in the style of functional programming, which involves representing the state of the game with purely functional, immutable data structures.

One of the most important data structures will be a three-dimensional grid representing the world where objects can be stored anywhere on the grid [x, y, z]. The properties I want for this data structure are:

• Unchanging
• Fast continuous update - i.e. creating a new version of the entire grid with minor modifications is cheap and is achieved through structural exchange. The grid can be large, so copy-by-copy is not an option.
• Effective management of sparse areas / identical values - empty / uninhabited areas should not consume resources (to provide large open spaces). Bonus points if they are also effective when storing large "blocks" of the same value
• Unlimited - can grow in any direction as needed
• Fast read / search - i.e. can quickly get an object in [x, y, z]
• The fast volume of queries , that is, a quick search in the region [x1, y1, z1] → [x2, y2, z2], ideally using sparsity, so that empty spaces are quickly passed through

Any suggestions on the best data structure you can use for this?

PS I know that this may not be the most practical way to write a game, I just do it as a learning experience and stretch my abilities using FP ......

Answer 1

I would try octtree. The boundary coordinates of each node are implicit in the placement of the structure, and each nonterminal node contains 8 subtrees, but does not contain data. That way you can “team up” to get space.

I think that Immutable and Unlimited (usually) conflicting requirements.
In any case ... you must replace the root to grow an octet.

Other requirements that you set must be met.