Работа с большим расстоянием между ячейками в Hashlife

Question

Я пишу реализацию Game of Life от Conway и решил использовать вариацию Hashlife algorithm, используя квадранты и хеш-таблицу для хранения ячеек и обработки столкновений, несколько похожих на то, что описано here и here. Детали в основном состоят в том, что все пространство состоит из квадрантов, которые спускаются до листьев с живым или мертвым состоянием. Квадцы сами по себе неизменны и хэшируют, чтобы делиться ссылками по всему дереву, чтобы иметь дело с очень скудными областями или обычными повторяющимися шаблонами.

Одна проблема, с которой я сталкиваюсь, даже создает поле для хранения ячеек, которые очень далеки друг от друга. Кажется, что даже рекурсивное определение пустого квадратного дерева высоты 24 занимает очень значительное количество времени.

Каков наилучший способ решения этой проблемы?

Два решения, которые я вижу, могут состоять в том, чтобы оставить пустые квадранты неинициализированными до тех пор, пока они не понадобятся, но неизменность квадроциклов может сделать это немного сложнее - если я сохраню каждый неизменный цикл, я не могу просто создать экземпляр дочернего узла, мне придется обновить всю структуру с нуля.

Другое решение, я думал, будет иметь несколько quadTrees - так что, если у меня есть точка в нескольких триллионах клеток от других ячеек, они будут управляться отдельными деревьями. Очевидно, проблема здесь связана с слиянием деревьев, которые становятся смежными или перекрывающимися - похоже, что спуститься по этому пути потребуются четыре дерева деревьев, и я подозреваю, что это не закончится хорошо для меня.

Каковы другие решения, которые мне не хватает? Есть ли что-то, что я игнорирую в отношении вышеупомянутых двух решений, которые сделают их менее волосатыми?

Спасибо!

Answer 1

Я занимался этим и семантической реализацией. Golly общается с этим, используя NULL (или какое-то подходящее значение ожидания) как представляющее «пустое» на любом уровне дерева. Это работает, потому что мы знаем, что пустые авансы опустели.

Так что, если вы представить себе размах 8x8 проведения планера в квадранте Северо-Западе вы бы иметь структуру, которая была

СЕВЕРО-ЗАПАД = планер (удерживаемая в 4x4 поддерева) NorthEast = = юго-западе Юго-Восточные = 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... 

}; 

Я смотрел на идеи о том, чтобы иметь отдельные деревья, но обработка деревьев с массивными пустотами в них настолько эффективна, что это было совершенно бессмысленно.