Работа с большим расстоянием между клетками в Hashlife
Я пишу реализацию «Игры жизни» Конвея и решил использовать вариант Алгоритм Hashlife, использование четырех деревьев и хеш-таблицы для хранения ячеек и обработки коллизий, что-то вроде описанного Вот а также Вот. Детали в основном состоят в том, что все пространство состоит из четырех деревьев, которые опускаются в листья с живым или мертвым состоянием. Сами четырехугольники являются неизменяемыми и хэшируются, чтобы делиться ссылками по всему дереву, чтобы иметь дело с очень редкими областями или общими повторяющимися образцами.
Одна проблема, с которой я сталкиваюсь, — это даже создание поля для хранения ячеек, которые находятся очень далеко друг от друга. Кажется, что даже рекурсивное определение пустого четырехугольного дерева высотой 24 занимает очень значительное время.
Каков наилучший способ решения этой проблемы?
Два решения, которые я вижу, могут состоять в том, чтобы оставить пустые четырехугольники неинициализированными до тех пор, пока они не понадобятся, но неизменность четырехугольников может сделать это немного сложным — если я оставлю каждый четырехугольник неизменным, я не смогу просто создать экземпляр дочернего узла, мне придется обновить всю структуру с нуля.
Другое решение, о котором я подумал, было бы иметь несколько четырехъядерных деревьев — поэтому, если у меня есть точка, находящаяся на расстоянии нескольких триллионов ячеек от других ячеек, они будут управляться отдельными деревьями. Очевидно, что проблема здесь заключается в слиянии деревьев, которые становятся смежными или перекрывающимися — кажется, что для перехода по этому маршруту потребуются квад-деревья квад-деревьев, и я подозреваю, что для меня это не закончится хорошо.
Какие еще решения мне не хватает? Есть ли что-то, что я игнорирую в вышеупомянутых двух решениях, которые сделали бы их менее волосатыми?
Спасибо!
Решение
Я имел дело с этим, и оригинальная реализация Golly имеет дело с этим с помощью NULL (или какое-нибудь подходящее значение в качестве замены) как представление «пусто» на любом уровне дерева. Это работает, потому что мы знаем пустые авансы для пустых.
Так что, если вы представляете размах 8х8 с планером в северо-западном квадранте, у вас будет структура, которая была
NorthWest = Glider (содержится в поддереве 4×4)
СевероВосточный = SouthWest = = 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...
};
Я рассматривал идеи создания отдельных деревьев, но обработка деревьев с массивными пустотами в них настолько эффективна, что это было совершенно бессмысленно.
Другие решения
Других решений пока нет …
detector