Accelerare un Cellular Automata

Question

E 'possibile, con una sorta di algoritmo o qualcosa di simile, per accelerare un automa cellulare? Sto utilizzando Gioco di implementazione vita fatta in XNA di un Conway e funziona perfettamente, ma il problema è che quando uso una griglia più grande di 128x128 celle diventa terribilmente lento.

Non credo che si ha a che fare con il codice o come XNA maniglie texture e il disegno, ma il fatto che l'aggiornamento in modo da molte cellule (cioè valutando ciascuno dei vicini di casa della cellula e sulla base di che ottenere il suo nuovo stato) è di un molto della computazione.

Naturalmente, un automi cellulari ideale dovrebbe essere infinitamente grande, ma in realtà questo è impossibile da fare. Ma 128x128 è semplicemente troppo piccolo per vedere in realtà come il sistema si comporta, a mio parere.

Qualsiasi aiuto sarebbe molto apprezzato!

Answer 1

Se provare questo un paio di volte, si vedrà dove il tempo passa.

Non si deve indovinare, ma la mia ipotesi è essenzialmente tutto il tempo va in rendering. La valutazione dei vicini può sembrare un sacco di codice, ma le probabilità sono è estremamente semplice. Se si dispone di un modo di cellule ri-rendering di evitare che non sono cambiati, che potrebbe risparmiare un sacco.

Answer 2

mi sento di raccomandare di utilizzare OpenGL e GLSL. In questo modo è possibile eliminare il trasferimento dei dati dalla CPU alla GPU e ottenere un bel aumento di velocità di 10x o più.

Answer 3

L'algoritmo utilizza Hashlife quad-alberi, hash e memorizzazione di comprimere il tempo e lo spazio della CA per un massiccio aumento delle prestazioni. Scopri Golly per un esempio di implementazione.

sto ancora cercando di capirlo io stesso, e il look per buone biblioteche.

Non c'è buona spiegazione qui (con codice di esempio): http://www.drdobbs.com/jvm/an-algorithm-for-compressing-space-and-t/184406478 .