Ускорение клеточных автоматов

Question

Возможно ли с помощью какого-то алгоритма или чего-то подобного ускорить клеточный автомат? Я использую реализацию Conway's Game of Life, сделанную в XNA , и она отлично работает, но проблема в том, что когда я использую сетку размером более 128x128 ячеек, она становится ужасно медленной.

Я не думаю, что это связано с кодом или с тем, как XNA обрабатывает текстуры и рисунки, но тот факт, что обновление такого количества ячеек (т.е. оценка каждого из соседей ячейки и на основе этого получение ее нового состояния) это лот вычислений.

Конечно, идеальные клеточные автоматы должны быть бесконечно большими, но на самом деле это невозможно сделать. Но, на мой взгляд, 128х128 слишком мало, чтобы на самом деле увидеть, как ведет себя система.

Любая помощь будет принята с благодарностью!

Answer 1

Я бы рекомендовал использовать OpenGL и GLSL. Таким образом, вы можете исключить передачу данных из процессора в графический процессор и получить приличное ускорение в 10 раз или более.

Answer 2

Алгоритм Hashlife использует квад-деревья, хеширование и запоминание, чтобы сжать время и пространство CA для значительного увеличения производительности.Посмотрите Golly для примера реализации.

Я все еще пытаюсь сам разобраться с этим и ищу хорошие библиотеки.

Здесь есть хорошее объяснение (с примеромкод): http://www.drdobbs.com/jvm/an-algorithm-for-compressing-space-and-t/184406478.

Answer 3

Если вы попробуете это несколько раз, вы увидите, куда уходит время.

Не надо догадываться, но мое предположение по сути все время идет в рендеринг. Оценка соседей может выглядеть как много кода, но, скорее всего, это очень просто. Если у вас есть способ избежать повторного рендеринга ячеек, которые не изменились, это может значительно сэкономить.