c++ - 处理Hashlife中单元格之间的大距离

Question

我正在编写康威生命游戏的实现，并决定使用 Hashlife algorithm 的变体。 ，使用四叉树和哈希表来存储单元格和处理冲突，有点类似于所描述的 here和 here .细节基本上是整个空间由四叉树组成，四叉树下降到叶子，有活的或死的状态。四边形本身是不可变的，并且经过哈希处理以在整个树中共享引用，以处理非常稀疏的区域或常见的重复模式。

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

解决这个问题的最佳方法是什么？

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

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

我还缺少哪些其他解决方案？关于上述两种解决方案，我是否忽略了一些可以使它们不那么毛茸茸的东西？

谢谢!

Answer 1

我已经处理了这个问题，Golly 的开创性实现通过使用 NULL(或一些合适的替代值)在树的任何级别表示“空”来处理这个问题。这是可行的，因为我们知道空预付款为空。

因此，如果您想象一个 8x8 的跨度在西北象限中装有一架滑翔机，您将拥有一个结构

NorthWest=Glider(在 4x4 子树中) NorthEast=SouthWest=SouthEast=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....

还有一个高级函数:

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

};

我考虑过拥有单独的树的想法，但处理其中有大量空隙的树非常有效，但这种方式完全没有意义。