Přednášející: RNDr. Dagmar Brechlerová Ph.D.
Zápočtová úloha - Conway’s Game of LIFE
Kompletní řešení ke stažení: jtomsa13-life.zip (95 KB)
Popis řešení: JTOMSA13.doc (262 KB)
Příklady vstupních dat: life-example-input (2 KB)
Zadání
Naprogramujte Conwayovu hru Life.
Vyřešte vstup úvodní pozice (počáteční konfigurace), zadání požadovaného počtu generací, výpis každé generace a překročení mezi zvolené hrací plochy.
Hra Life je model života bakterií. Hraje se v rovině ve čtverečkové síti. Každé políčko sítě představuje buňku, která může být živá nebo mrtví (tj. bakterie v ní žije nebo nežije). Počáteční konfigurací je výchozí rozmístění živých buněk v této síti. Stav buňky v následujícím kroku závisí na počtu živých buněk v jejím okolí (okolím buňky rozumíme 8 sousedních políček) a je dán tzv. zákony života:
- Živá buňka přežije do následujícího kroku, jestliže v jejím okolí jsou dvě nebo tři živé buňky,
- jinak zahyne na osamocení (jestliže v jejím okolí nejsou živé buňky nebo je tam jen jedna živá buňka)
- nebo na přemnožení (jestliže v jejím okolí jsou aspoň čtyři živé buňky).
- V mrtvé buňce vznikne nová bakterie, jestliže jsou v jejím okolí přesně tři živé buňky.
V jednom kroku mění svůj stav všechny buňky najednou - tak vznikne nová generace.
Zdrojová forma programu
//------------------------------------------------------------------------- /* * 13. Naprogramujte Conwayovu hru Life. * * Vyřešte vstup úvodní pozice (počáteční konfigurace), * zadání požadovaného počtu generací výpis každé generace a překročení * mezi zvolené hrací plochy. * * Hra Life je model života bakterií. * Hraje se v rovině ve čtverečkové síti. * Každé políčko sítě představuje buňku, která může být živá nebo mrtví * (tj. bakterie v ní žije nebo nežije). * Počáteční konfigurací je výchozí rozmístění živých buněk v této síti. * Stav buňky v následujícím kroku závisí na počtu živých buněk v jejím * okolí (okolím buňky rozumíme 8 sousedních políček) * a je dán tzv. zákony života. * Živá buňka přežije do následujícího kroku, jestliže v jejím okolí jsou * dvě nebo tři živé buňky, jinak zahyne na osamocení (jestliže v jejím * okolí nejsou živé buňky nebo je tam jen jedna živá buňka) * nebo na přemnožení (jestliže v jejím okolí jsou aspoň čtyři živé buňky). * V mrtvé buňce vznikne nová bakterie, jestliže jsou v jejím okolí přesně * tři živé buňky. * V jednom kroku mění svůj stav všechny buňky najednou * - tak vznikne nová generace. * * Autor: Jan TOMSA */ //------------------------------------------------------------------------- #include <conio.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <dos.h> #include <time.h> #include <ctype.h> #include <values.h> // Velikost hrací plochy (vstupní soubor musí být velikosti přizpůsoben!) #define WORLD_SIZE 100 #define WORLD_SHIFT_X 110 #define WORLD_SHIFT_Y 45 typedef unsigned char byte_t; byte_t far* video_buffer = (byte_t far*)0xA0000000; // pozastavení programu na wait ms void mySleep( clock_t wait ) { clock_t goal; goal = wait + clock(); while( goal > clock() ); } // -- Zpracování vstupu --------------------------------------------------- // Načtení vstupní konfigurace char * initLife( char *pole[WORLD_SIZE], char *filename ) { char LineBuf[WORLD_SIZE+1]; char c; FILE *fr; int i; int j; fr = fopen(filename,"r"); if (fr==NULL) { return NULL; } else { i = 0; while ( !feof(fr) && i<WORLD_SIZE ) { pole[i] = (char *)malloc(WORLD_SIZE+1); if (pole[i] == NULL) { return NULL; } else { j = 0; while ((c = fgetc(fr)) != '\n' && j < WORLD_SIZE ) { pole[i][j] = c; j++; if feof(fr) return NULL; // ošetření předčasného konce souboru } pole[i][j+1] = 0; i++; } } fclose(fr); return (char *) pole[0][0]; } } // Načtení maximálního počtu generací long decode_max_gen( char *s ) { char TmpStr[12]; int i=0; if (strlen(s) < 7) { while ((s[i] != 0) && (isdigit(s[i])) && i<7) { TmpStr[i] = s[i]; i++; } return atol( TmpStr ); } else { return -1; } } // -- Grafický výstup ----------------------------------------------------- // nakreslení pixelu přímým zápisem do videopaměti void set_pixel(int x,int y,byte_t color) { video_buffer[y * 320 + x] = color; } // inicializace grafického režimu void initgraph() { _AX = 0x13; geninterrupt(0x10); } // vypnutí grafického režimu void closegraph() { _AX = 3; geninterrupt(0x10); } // -- Grafický výstup hry LIFE -------------------------------------------- // zobrazení čísla aktuální generace void displayGeneration( long g ) { char *string; int i=0; ltoa(g, string, 10); while(string[i] != 0) { set_pixel(i*4+1,20, 15*((string[i] == '3') || (string[i]=='4') || string[i]=='5' || string[i]=='7') ); set_pixel(i*4+2,20, 15*(string[i]!='4') ); set_pixel(i*4+3,20, 15*((string[i] == '5') || (string[i] == '6') || (string[i] =='7')) ); set_pixel(i*4+1,21, 15*((string[i] != '3') && (string[i] != '7'))); set_pixel(i*4+2,21, 15*(string[i] == '1') ); set_pixel(i*4+3,21, 15*((string[i] != '1') && (string[i] != '4') && (string[i] != '5') && (string[i] != '6')) ); set_pixel(i*4+1,22, 15*((string[i] == '0') || (string[i] == '4') || (string[i] == '5') || (string[i] == '6')) ); set_pixel(i*4+2,22, 15*((string[i] != '0') && (string[i] != '2') && (string[i] != '4')) ); set_pixel(i*4+3,22, 15*((string[i] == '0') || (string[i] == '2') || (string[i]=='4') || (string[i]=='7') || (string[i] == '9')) ); set_pixel(i*4+1,23, 15*((string[i] == '0') || (string[i] == '4') || (string[i] == '6') || (string[i] == '8')) ); set_pixel(i*4+2,23, 15*((string[i] == '1') || (string[i] == '2') || (string[i] == '4')) ); set_pixel(i*4+3,23, 15*((string[i] != '1') && (string[i] != '2'))); set_pixel(i*4+1,24, 15*((string[i] == '1') || (string[i] == '2') || (string[i] == '3') || (string[i] == '5')) ); set_pixel(i*4+2,24, 15*((string[i] != '4') && (string[i] != '7'))); set_pixel(i*4+3,24, 15*((string[i] == '1') || (string[i] == '2') || (string[i] == '4') || (string[i] == '7')) ); i++; } } // grafické zobrazení buněk void displayWorld ( char * w[] ) { for (int xx=0; xx<WORLD_SIZE-1; xx++) { for (int yy=0; yy<WORLD_SIZE-1; yy++) { set_pixel(WORLD_SHIFT_X+xx,WORLD_SHIFT_Y+yy,w[yy][xx]); } } } // -- Hra LIFE - hlavní algoritmus ---------------------------------------- void live ( char * w[], long maxg ) { char *newWorld[WORLD_SIZE+1]; long generation = 0; int neighbours; // inicializace pomocného pole newWorld pro generování nové generace for (int i=0; i<=WORLD_SIZE; i++) newWorld[i] = (char *)malloc(WORLD_SIZE+1); // Cyklus života buněk while(!kbhit() && (generation<=maxg || maxg==0) && (generation<MAXLONG)) { for (int xx=0; xx<=WORLD_SIZE-1; xx++) { for (int yy=0; yy<=WORLD_SIZE-1; yy++) { // výpočet počtu sousedních buněk neighbours = ((w[yy-1][xx-1] != 32) && (yy>0 && xx>0) ? 1 : 0 ) + ((w[yy-1][xx ] != 32) && (yy>0) ? 1 : 0 ) + ((w[yy-1][xx+1] != 32) && (yy>0 && xx<WORLD_SIZE-1) ? 1 : 0 ) + ((w[yy ][xx-1] != 32) && (xx>0) ? 1 : 0 ) + ((w[yy ][xx+1] != 32) && (xx<WORLD_SIZE-1) ? 1 : 0 ) + ((w[yy+1][xx-1] != 32) && (xx>0 && yy<WORLD_SIZE-1) ? 1 : 0 ) + ((w[yy+1][xx ] != 32) && (yy<WORLD_SIZE-1) ? 1 : 0 ) + ((w[yy+1][xx+1] != 32) && (yy<WORLD_SIZE-1 && xx<WORLD_SIZE-1) ? 1 : 0 ); // Vyhodnocení pravidel života: // Živá buňka přežije do následujícího kroku, // jestliže v jejím okolí jsou dvě nebo tři živé buňky, // jinak zahyne na osamocení // (jestliže v jejím okolí nejsou živé buňky nebo je // tam jen jedna živá buňka) // nebo na přemnožení (jestliže v jejím okolí jsou // aspoň čtyři živé buňky). // V mrtvé buňce vznikne nová bakterie, jestliže jsou // v jejím okolí přesně tři živé buňky. if (w[yy][xx] != 32) { // buňka je živá -> if (neighbours == 2 || neighbours == 3) { newWorld[yy][xx] = w[yy][xx]; // --> buňka přežívá } else { newWorld[yy][xx] = 32; // --> buňka umírá } } else { // buňka je mrtvá -> newWorld[yy][xx] = ((neighbours == 3) ? 31 // --> rodí se nová buňka : w[yy][xx]);// --> zůstává předchozí } } } for (int y=0; y<=WORLD_SIZE-1; y++) { strcpy(w[y],newWorld[y]); } displayWorld( w ); displayGeneration( generation ); // // Nakresli ukazatel běhu aplikace for (int xxx=0; xxx<320;xxx++) for (int yyy=190;yyy<=199;yyy++) set_pixel(xxx,yyy,32+(32+xxx+yyy-190-(generation%32))%16); generation++; mySleep(4); } } // --- MAIN --------------------------------------------------------------- int main(int argc, char **argv) { char *FileName = argv[1]; char *world[WORLD_SIZE+1]; long MaxGen = 0; if (argc > 1) { if (initLife(world,FileName)==NULL) { printf("Chyba pri cteni souboru %s.\n",FileName); return 1; } else { if (argc > 2) { MaxGen = decode_max_gen(argv[2]); } if (MaxGen<0) { printf("Chybny format maximalniho poctu generaci. "); printf("Zadejte maximalne 6 ciferne kladne cele cislo.\n"); return 1; } else { initgraph(); displayWorld( world ); live( world, MaxGen ); while(!kbhit()); closegraph(); return 0; } } } else { printf("Conway's game of LIFE\n"); printf("Pouziti: JTOMSA13 <soubor.ext> [generace]\n"); printf("parametry:\n"); printf(" soubor.ext textovy soubor se vstupni konfiguraci\n"); printf(" generace max. pocet generaci (default=neomezene)\n"); return 1; } } // ------------------------------------------------------------------------
Předcházející předmět: Algoritmizace