Nokia 5110: Game of Life

Zápisník experimentátora

Hierarchy: Nokia 5110

Pomocou displeja Nokia 5110 si naprogramujeme simulátor života, ktorý napodobňuje množenie baktérií. Baktérie sú umiestnené v matici a na základe množstva baktérií v okolí buď prežijú alebo umrú. Na náš experiment použijeme Arduino Pro Mini, lineárny regulátor 3,3 V, level shifter a displej Nokia 5110.

Hra života

Pôvod hry spadá do rokov 1940 a 1970 a súvisí s menami John von Neumann a John Horton Conway. Rozsiahly popis je možné nájsť na stránkach anglickej a českej Wikipédie.

Podstata simulácie je veľmi jednoduchá. Každá bunka v matici má 8 susedov. Podľa množstva susedov bunka alebo prežije, alebo umrie. Každá nová generácia obsadí miesto pôvodnej generácie a výsledkom je krásna animácia, pripomínajúca život.

Pôvodne pravidlá prežitia obsahovali iba jednu sadu pravidiel. Dnes býva označovaná ako S23/B3.

  • S23 (survive) zmenená, že existujúca bunka prežije, ak má dvoch alebo troch susedov.
  • B3 (born) znemená, že mŕtva bunka ožije, ak má troch susedov.

Dnes je dostupných viac pravidiel a vznikajúce animácie sa od seba radikálne líšia. Niektoré umrú po pár iteráciách, iné potrebujú desiatky iterácii, pokiaľ vznikne niečo zaujímavé a iné sa zastabilizujú na zvláštnych formáciach, ktoré sa alebo nehýbu, alebo sa zase dramaticky menia.

Čo budeme potrebovať

V nasledovnom zozname nájdete všetky použité súčiastky (odkazy sú na Banggood):

Vo videu je použité Arduino Pro Mini. V tomto Arduine nemáme k dispozícii napätie 3,3 V, ktoré sa používa na napájanie displeja. Preto musíme použiť ešte lineárny regulátor 78L33, ktorým si upravíme napätie z 5 V na 3,3 V. Je zapojený v katalógovom zapojení spolu s kondenzátorom 0,33 uF na vstupe a 0,1 uf na výstupe.

Pretože potrebujeme okrem napájania pripojiť aj 5 dátových vodičov, ktoré majú na strane Arduina 5 V a na strane displeja 3,3 V, potrebujeme level shifter. Existuje ich viacero typov, niektoré sú vhodné do skúšobného poľa, iné sú len v SMD prevedení.

Level shifter tohoto typu je jednostranná cesta, ale to pre naše účely plne vyhovuje, nakoľko všetkých 5 vodičov odosiela údaje do displeja a nič nie je potrebné prenášať naspäť. Budeme takto ovládať piny s označením RST, CE, DC, DIN a CLK.

Zvyšné vodiče len pripojíte tak, že VCC sa pripojí na 3,3 V a vodiče LIGHT a GND sa pripoja na GND. To zabezpečí napájenie pre displej a zapnutie podsvietenia.

Algoritmus

Pretože existuje viac pravidiel a chceme ich vidieť v jednom programe, pokúsime sa ich jednotným spôsobom popísať a jednotlivé pravidlá postupne zobraziť pomocou cyklu.

Pretože existuje aj viac spôsobov, ako počítať okolité bunky, budeme postupne meniť aj tieto výpočty v každom pravidle. Výpočet ovplyvňuje najmä to, ako sa správajú bunky v rohoch matice. Nedá sa s istotou povedať, čo je pre bunky najlepšie. Pri každom pravidle je úspešnosť množenia úplne iná, ak sa použije ktorýkoľvek z nasledovných algoritmov.

  • Na okraji je všade mŕtva zóna a bunky na pozícii x=0 a x=šírka-1 nikdy neprežijú. To isté sa týka aj osi y.
  • Na okraji bunky vidia len to, čo je vo vnútri matice.
  • Na okraji sa bunky môžu pozerať aj cez hranicu a použiť na výpočet bunky na opačnej strane matice.

Pretože bunky vo veľkosti jedného pixela by boli na pozeranie príliš malé, použijeme dvojnásobné zväčšenie na bunky a budeme mať maticu 42x24 buniek. To je aj tak dosť veľa a pri vyhradení jedného bajtu na bunku by sme potrebovali 1152 bajtov. Na výpočet ale treba dve matice a niečo spotrebuje aj vykresľovanie. Toľko RAM v Arduine nemáme a preto bude nutné na matice použiť jednotlivé bity, ktoré mám spotrebu RAM zredukujú osemnásobne.

Programovanie

V programe je niekoľko miest, ktoré treba vysvetliť.

Pravidlá

Pretože som potreboval v programe používať rôzne pravidlá, navrhol som jednoduchú štruktúru na ich ukladanie. Pretože jedna bunka môže mať v okolí 0-8 susedov, potreboval som 9 bitov na uloženie informácie. Preto je používaný typ uint16_t. Definície jednotlivých pravidiel sú zapísané v dvojkovej sústave, aby sa to pohodlne zapisovalo.

// rules of Game of Life
struct rule
{
uint16_t s; // survive
uint16_t b; // born
char name[15];
};

// different rules
const rule rules[]={
  {0b000001100,0b000001000,"S23/B3"},        // S23/B3 classic Game of Life
  {0b000111110,0b000001000,"S12345/B3"},     // S12345/B3 maze
  {0b000001100,0b001001000,"S23/B36"},       // S23/B36 HighLife
  {0b000000000,0b000000100,"/B2"},           // /B2 
  {0b000000000,0b000011100,"/B234"},         // /B234 
  {0b000000010,0b000000010,"S1/B1"},         // S1/B1 
  {0b100101010,0b010101000,"S1358/B357"},    // S1358/B357 
  {0b000111100,0b111110000,"S2345/B45678"},  // S2345/B45678 
  {0b111101100,0b111001000,"S235678/B3678"}, // S235678/B3678 
  {0b111101100,0b110001000,"S235678/B378"},  // S235678/B378 
};

const uint8_t nrules=sizeof(rules)/sizeof(rule);

Použitie pravidla v kóde je potom triviálne. Parameter r je index do poľa pravidiel. Postupne sa počíta Game of Life s rôznymi pravidlami. Parameter orig nám hovorí, či počítame pre živú alebo mŕtvu bunku. Parameter near nám hovorí, koľko buniek je v susedstve. Výraz 1<<near je bitový posun doľava. Pomocou neho posunieme jednotku na pozíciu hľadaného bitu v pravidlách, pričom pozícia 0 je vpravo. Potom už len stačí pomocou logického súčinu zistiť, či je výsledok operácie true alebo false.

///
/// Apply the rules of life and death
///
uint8_t canSurvive(uint8_t r, uint8_t orig, uint16_t near)
{
if(orig) // live cell
  {
  return rules[r].s&(1<<near);
  }
else // dead cell
  {
  return rules[r].b&(1<<near);
  }
}

Makrá

Pretože dve polia o rozmeroch 42x24 by sa nám do pamäte Arduina nezmestili, používam bitové pole, ktoré nám umožní ukladať informácie v menšom priestore. Definované makrá uľahčujú operácie nad bitovým poľom.

// cell matrix
// each bit is one cell
uint8_t grid[42][3];  // main array
uint8_t ngrid[42][3]; // temporary array

// bit manipulation
#define gridRead(x,y) bitRead(grid[(x)][(y)/8],(y)%8)
#define gridSet(x,y) bitSet(grid[(x)][(y)/8],(y)%8)
#define gridClear(x,y) bitClear(grid[(x)][(y)/8],(y)%8)

#define ngridSet(x,y) bitSet(ngrid[(x)][(y)/8],(y)%8)
#define ngridClear(x,y) bitClear(ngrid[(x)][(y)/8],(y)%8)

Pointer na funkciu

Toto nie je často používaná vec na programovanie, ale v tomto prípade sa nám hodí. V jazyku C môžeme využívať aj samotné funkcie, ale aj pointre na funkcie, ktoré umožňujú do pointra podľa potreby priradiť adresu konkrétnej funkcie. Ja mám tri funkcie, ktoré majú rovnaké parametre a líšia sa iba svojim vnútrom. Postupne používam každú funkciu na výpočty. Takto sa to definuje v jazyku C.

// pointer to function - get number of neighbors
uint8_t (*getNON)(uint8_t x, uint8_t y);

uint8_t getNumberOfNeighbors(uint8_t x, uint8_t y)
{
...
}

uint8_t getNumberOfNeighborsWithBorder(uint8_t x, uint8_t y)
{
...
}

uint8_t getNumberOfNeighborsInfinite(uint8_t x, uint8_t y)
{
...
}

void loop() {
getNON=getNumberOfNeighbors;
loopAlgo();
getNON=getNumberOfNeighborsWithBorder;
loopAlgo();
getNON=getNumberOfNeighborsInfinite;
loopAlgo();
}

Výpočet nasledovnej generácie

Kód výpočtu je prekvapivo krátky a jednoduchý. Iba sa do dočasného poľa vypočítajú výsledky pre každú bunku a výsledok sa uloží do pôvodného poľa, odkiaľ sa vykresľuje na displej.

/// Calculate next step
///
void nextStep(uint8_t rule)
{
for(uint8_t i=0;i<42;i++)
  for(uint8_t j=0;j<24;j++)
    {
    int near=getNON(i,j);
    if(canSurvive(rule,gridRead(i,j),near))
      {
      ngridSet(i,j);
      }
    else
      {
      ngridClear(i,j);
      }
    }
for(uint8_t i=0;i<42;i++)
  for(uint8_t j=0;j<3;j++)
    grid[i][j]=ngrid[i][j];
}

A zvyšok je už len omáčka v podobe nejakých výpisov textov a inicializácie displeja.

Github

Aktuálnu verziu zdrojových textov nájdete aj na webe Github.

Video

Vo videu je vidno jednotlivé pravidlá a algoritmy v akcii.



Download

22.03.2016


Menu