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

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

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

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

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


person federico-t    schedule 11.01.2012    source источник


Ответы (3)


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

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

person Mike Dunlavey    schedule 11.01.2012

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

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

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

person delax    schedule 21.01.2013

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

person labotsirc    schedule 07.06.2012