Acelerando un autómata celular

Question

¿Es posible, con algún tipo de algoritmo o algo así, para acelerar un autómata celular? Estoy usando La implementación del juego de la vida de Conway hecha en XNA Y funciona perfectamente, pero el problema es que cuando uso una cuadrícula de más de 128x128 células se vuelve terriblemente lenta.

No creo que tenga que ver con el código o cómo XNA maneja las texturas y el dibujo, pero el hecho de que actualizar tantas células (es decir, evaluar a cada uno de los vecinos de la célula y, en base a que obtenga su nuevo estado), es un lote de cálculo.

Por supuesto, un autómata celular ideal debería ser infinitamente grande, pero en realidad eso es imposible de hacer. Pero 128x128 es demasiado pequeño para ver cómo se comporta el sistema, en mi opinión.

¡Cualquier ayuda sería muy apreciada!

Answer 1

Si usted prueba esto Algunas veces, verás a dónde va el tiempo.

Uno no debe adivinar, pero supongo que esencialmente todo el tiempo se destina a la representación. La evaluación de los vecinos puede parecer mucho código, pero es probable que sea extremadamente simple. Si tiene una manera de evitar volver a reproducir células que no han cambiado, eso podría ahorrar mucho.

Answer 2

Recomendaría usar OpenGL y GLSL. De esta manera, puede eliminar la transferencia de datos de CPU a GPU y obtener una buena aceleración de 10x o más.

Answer 3

El algoritmo Hashlife utiliza cuádruples, hashing y memorización para comprimir el tiempo y el espacio de la CA para un aumento masivo en el rendimiento. Verificar Aficionado Para una implementación de ejemplo.

Todavía estoy tratando de resolverlo y buscar buenas bibliotecas.

Hay una buena explicación aquí (con código de ejemplo): http://www.drdobbs.com/jvm/an-algorithm-for-compresing-space-and-t/184406478.