un'altra domanda Game of Life (griglia infinita)?

Question

Ho giocato con Conway's Game of life e recentemente ho scoperto alcune incredibili implementazioni come Hashlife e Golly. (scarica Golly qui - http://golly.sourceforge.net/)

Una cosa che non riesco a capire è come i programmatori implementano la griglia infinita? Non possiamo tenere una serie infinita di nulla, se corri gol e fai volare alcuni alianti oltre i bordi, attendi alcuni minuti e fai lo zoom indietro, vedrai gli alianti ancora lì nello spazio che scappano, quindi come diavolo si tratta di questo concetto di infinito trattato a livello di codice? C'è un modello ben documentato o cosa?

Molte grazie

Answer 1

Wikipedia explains it. L'idea di base è che Conway's Game of Life esibisce località, poiché le informazioni viaggiano a una velocità ridotta rispetto alle dimensioni del pattern e la densità massima delle celle piene è circa 1/2 delle celle in qualsiasi regione. (Più cancellerà le celle a causa del sovraffollamento.)

Poiché esiste una località, è possibile separare il campo in sezioni diverse e simulare ciascuna sezione in modo indipendente. Se scegli bene la tua località, vedrai spesso gli stessi modelli. È possibile simulare come si evolvono e archiviare i risultati in una tabella di ricerca, in modo che non sia necessario simulare altre istanze dello stesso modello più di una volta. La combinazione di pattern adiacenti in "metapatterns" più grandi consente di precalcolare anche quelli, e così via.

Answer 2

In questa situazione è possibile rappresentare nodi viventi con un tipo di matrice sparsa. Ad esempio, se archiviamo un elenco di coppie (LivingNode, Coordinate) invece di un array di Nodes in cui ognuno è vivo o morto, stiamo semplicemente modificando lo Coordinates invece di aumentare le dimensioni di un array. Pertanto, lo spazio richiesto per questo è proporzionale al numero di LivingNodes.

Questa soluzione non funziona per gli stati in cui il numero di nodi viventi è in costante aumento, ma funziona molto bene per gli alianti.

MODIFICA: Quindi era fuori di testa. Risulta Wikipedia has an article che mostra una soluzione molto più ben pensata. Oh bene! :) Godere.