Hashlife中处理细胞之间的大距离

Question

我正在编写Conway's Game of Life的实现，并决定使用Hashlife算法的一种变体，使用四叉树和哈希表来存储单元和处理碰撞，有点类似于这里和这里描述的内容。细节基本上是整个空间由四叉树组成，这些四叉树下降到具有活或死状态的叶子。四元组本身是不可变的，并且在整个树中被散列以共享引用，以处理非常稀疏的区域或常见的重复模式。

我遇到的一个问题是甚至产生一个字段来容纳彼此相距很远的细胞。看起来，即使递归地定义一个高度为24的空四叉树也需要花费大量的时间。

解决这个问题的最好方法是什么?

我看到的两种解决方案可能是在需要时才初始化空的四边形，但是四边形的不可变性可能会使这有点棘手-如果我保持每个四边形不可变，我不能只是实例化一个子节点，我将不得不从头开始更新整个结构。

我想到的另一个解决方案是有多个四叉树——所以如果我有一个点，它与其他细胞有几万亿个细胞的距离，它们将由单独的树来管理。显然，这里的问题是处理相邻或重叠的树的合并-似乎沿着这条路走下去将需要四叉树的四叉树，我怀疑这对我来说不会有好结果。

我还缺少其他的解决方案吗?在上述两种解决方案中，我是否忽略了一些可以让它们不那么麻烦的东西?

谢谢!

Answer 1

我已经处理了这个问题，而Golly的开创性实现通过使用NULL(或一些合适的替代值)来表示树的任何级别的'空'来处理这个问题。这是有效的，因为我们知道empty会提前变为empty。

如果你想象一个8x8的跨度在西北象限支撑着一个滑翔机你就会有一个结构是

西北=滑翔机(保持在4x4子树)东南东北西南= = = nullptr

使用这种方法，你可以创建大量的模式，只要它们是稀疏的。

在程序的某个地方，您将访问哈希表，您可能需要添加如下形式的代码:

Node* getNode(Node* NW,Node* NE,Node* SW,Node* SE) {
   if(NW==nullptr&&NW==nullptr&&NW==nullptr&&NW==nullptr){
       return nullptr;
   }   
  //Actually go into the hash-table....

}

和一个advance函数:

Node* AdvanceQuarterSpan(Node* node, unsigned span_index){
    if(node==nullptr){
        return nullptr;
    }
    //Actually divide the node up advance the sub-quadrants and advance the resulting centre quadrant.
}

我粗略地假设你有一些结构，如:

class Node {
    Node* NW; //North West Quadrant. nullptr if empty.
    Node* NE; //North East Quadrant. nullptr if empty.
    Node* SW; //South West Quadrant. nullptr if empty.
    Node* SE; //South East Quadrant. nullptr if empty.
    //Other fields...
};

我考虑过有单独的树的想法，但是处理有大量空隙的树是如此有效，这种方式是完全没有意义的。