Recovery memory from unneeded sections of the graph

[Ralith]

The core Graph data structure that models world space presently grows without bound as players explore. This leads to unbounded memory use over time, giving instances of the world an effectively finite lifetime before they become unplayable.

To some extent this is inherent in the genre: a Minecraft world, continuously explored, will eventually fill your disk. However, hyperbolic space amplifies the problem: for a given view distance, a far larger volume is visible from a single viewpoint, to say nothing of the volume visible in the course of traveling a certain distance. Graph size is linearly proportional to these figures.

Exact graph memory use as a function of distance traveled by players should be analyzed to quantify the magnitude of the problem. If the memory growth is indeed significant enough to threaten reasonable playtimes, we should take measures to free unused sections of the graph.

Graph nodes must not be freed if they encode data that cannot be regenerated on demand. Nodes that must be preserved include those that contain persistent entities, those that contain chunks that have been persistently modified, and those that the graph considers parents of persistent nodes.

• In each node, maintain a reference count describing the number of persistent references that require it.
• When a persistent reference is introduced, increment the associated node's counter. If the counter was previously zero, this constitutes introducing another persistent reference to the node's parent, and the algorithm recurses.
• When a persistent reference is removed, decrement the associated node's counter. If the counter becomes zero, this constitutes removing a persistent reference from the node's parent, and the algorithm recurses. Nodes that have zero persistent references are eligible to be freed.
• When a persistent reference is moved between nodes, special care should be taken if the original node's counter would become zero and the target node's counter is initially zero. Execute both the removal and the introduction simultaneously, always recursing on the node furthest from the origin. If the recursions reach a common ancestor, terminate them both without updating the ancestor's counter. This ensures that e.g. an entity moving between neighboring nodes requires only constant work.