Un excès de vitesse Cellular Automata

Question

Est-il possible, avec une sorte d'algorithme ou quelque chose du genre, pour accélérer un automate cellulaire? J'utilise un jeu de Conway de la mise en œuvre dans la vie faite XNA et cela fonctionne parfaitement, mais le problème est que lorsque j'utilise une grille plus grande que 128x128 cellules, il devient terriblement lent.

Je ne pense pas est doit faire avec le code ou la façon dont les textures poignées XNA et le dessin, mais le fait que la mise à jour tant de cellules (c.-à-évaluer chacun des voisins et sur la base de la cellule que l'obtention de son nouvel état), il est un beaucoup de calcul.

Bien sûr, un automate cellulaire idéal doit être infiniment grand, mais en réalité, c'est impossible de le faire. Mais 128x128 est trop petit pour voir réellement comment le système se comporte de, à mon avis.

Toute aide serait grandement appréciée!

Answer 1

If you try this a few times, you'll see where the time goes.

One shouldn't guess, but my guess is essentially all the time goes into rendering. The evaluation of neighbors may look like a lot of code, but chances are it's extremely simple. If you have a way to avoid re-rendering cells that haven't changed, that might save a lot.

Answer 2

I would recomend to use OpenGL and GLSL. This way you can eliminate the data transfer from cpu to gpu and gain a nice speedup of 10x or more.

Answer 3

The Hashlife algorithm uses quad-trees, hashing, and memorization to compress the time and space of the CA for a massive increase in performance. Check out Golly for an example implementation.

I'm still trying to figure it out myself, and look for good libraries.

There's good explanation here (with example code): http://www.drdobbs.com/jvm/an-algorithm-for-compressing-space-and-t/184406478.