automatZ
06.12.08

automatZ je prográmek sloužící jako nástroj pro simulaci celulárních automatů. (Nejznámější konkrétní celulární automat je asi Game of Life) Celulární automat je (když to trochu zjednodušíme) soubor různě barevných políček (buněk) na hrací ploše přesně daného tvaru. To jak jsou políčka obarvena se mění v čase (po každém kroku). To, jak budou obarvena políčka v určitém kroku, je dáno pravidly, která jsou založena na obarvení sousedních políček v předchozím kroku.

Pro lepší představu popíšu pravidla jednoho konkrétního automatu; jmenuje se Game of Life:

Hrací plocha tohoto automatu je představována (nekonečnou) čtvercovou sítí. Každý čtvereček (říkejme těmto čtverečkům buňky) této sítě je v jednom ze dvou stavů: živá(bílá) nebo mrtvá(černá).

Každá buňka interaguje se svými osmi sousedy, jimiž jsou buňky těsně kolem ní ve čtvercové síti.

V každém kroku se provedou následující změny:

  • Jakákoliv živá buňka s méně než dvěma živejma sousedama umře.
  • Jakákoliv živá buňka s více než třema živejma sousedama umře.
  • Jakákoliv živá buňka se dvěma nebo třema živejma sousedama přežije.
  • Jakákoliv mrtvá buňka s právě třema živejma sousedama obživne.

Představme si že na začátku máme nějaký počáteční stav automatu, to znamená mít hrací pole nějakým způsobem zaplněné živými a mrtvými buňkami. Tomuto stavu můžeme říkat první generace. Druhou generaci dostaneme aplikací předchozích čtyř pravidel. Třetí generaci dostaneme aplikací pravidel na druhou generaci a tak dál.

Konkrétní příklad přechodu z jedné generace na další (světle šedé čtverce jsou živé buňky, tmavě šedé jsou mrtvé):

Celulární automat si jde představit jako takový jednoduchý vesmír, který má hodně jednoduché fyzikální zákony. Tyhle zákony jsou právě pravidla automatu. V téhle představě můžeme pokračovat a představit si políčko hrací plochy automatu jako místo v tomto vesmíru. Jednotlivá obarvení políček pak můžeme interpretovat jako obsah daného políčka. Třeba tak, že když je políčko černé, tak na tomhle místě není nic, a když je zas třeba bílé je na něm částice.

Program tedy umožňuje (na základě uživatelem definovaných pravidel, počátečního stavu automatu a tvaru hrací plochy) simulace chodu celulárního automatu a navíc ještě pár věciček (například rozpozná raketu, co se tim myslí se můžete dočíst níže).

automatZ jsem dělal v zimním semestru v prváku na Matfyze jako zápočtový program v předmětu Programování I. Podrobné informace jsou v Dokumentaci, kterou naleznete níže.

Kdyby vás cokoliv zajímalo ohledně tohodle prográmku, stačí se zeptat v komentářích úplně dole na téhle stránce.







Dokumentace

Obsah

SPECIFIKACE
    Zadání úlohy
    Pravidla automatu
    Výzkumné funkce
    Jazyk
    Přídavek oproti původní specifikaci
STRUČNÁ HISTORIE PROJEKTU A KOMENTÁŘ K DOKUMENTACI
SOUČASNÝ STAV PROGRAMU
    Hlavní nedostatky
OVLÁDÁNÍ
    Ovládání Automatu
    Několik dalších příkazů
TŘÍDA AUTOMAT
    Zadání pravidel
    Evoluční funkce
    Reprezentace hrací plochy
    Sousedství buňky
    Jak probíhá evoluce
    „Výzkumná funkce“ : Metoda CoJeTo()
    Formát vstupních souborů
    Veřejné rozhraní třídy
    Členské proměnné třídy
SOUBORY PROJEKTU

Specifikace

Zadání úlohy

Program bude nástrojem pro simulaci celulárních automatů. (Celulární automat je soubor různě barevných políček (buněk) na hrací ploše přesně daného tvaru. To jak jsou políčka obarvena se mění v čase, respektive po každém kroku (čas je zde diskrétní). To, jak budou obarvena políčka v určitém kroku, je dáno pravidly, která jsou založena na obarvení sousedních políček v předchozím kroku.) To znamená, že program umožní (na základě uživatelem definovaných pravidel a tvaru hrací plochy) simulace chodu celulárního automatu.

Tvar hrací plochy bude možno zvolit jedno, dvou a tří-rozměrný. Dále bude možno zvolit počet barev, kterými je možno políčka obarvovat.

Pravidla automatu

Důležitou součástí úkolu je správné navržení tvaru, v jakém budou zapsána pravidla chování automatu. Ten by měl být co nejobecnější, tedy být takový, že je v něm možno popsat co možná nejširší spektrum pravidel.

Výzkumné funkce

Program by měl dále obsahovat funkce zpříjemňující práci uživateli, který zkoumá vlastnosti nějakého útvaru v celulárním automatu. Takovými vlastnostmi jsou například to, zda je zkoumaný útvar periodický (po určité době se vrátí do některé ze svých předchozích pozic), raketa (je periodický až na pozici na které se nachází, tedy je periodický pokud by se jeho pozice nebrala absolutně ale vzhledem k nějaké pohybující se soustavě souřadnic.), dělo („vystřeluje“ ze sebe rakety) a jiné vlastnosti.

Jazyk

Program bude napsán v jazyce C++. Grafika bude zrealizována pomocí knihovny OpenGL.

Přídavek oproti původní specifikaci

2D varianty celulárních automatů mají navíc možnost jiného než čtvercového tvaru políčka: je možné zvolit hexagon nebo trojúhelník.

Stručná historie projektu a komentář k dokumentaci

Jelikož jsem se rozhodl dělat program s grafickým rozhraním, nejprve jsem začal pracovat na tomto rozhraní. Udělal jsem obecnou „šablonu“ pro pohodlnější práci s grafikou, vstupy a pro to abych nemusel přemýšlet nad prácí s WinApi. Vznikl tak program-šablona se spoustou funkcí pro manipulaci s tímto rozhraním. Ve zdrojových textech jsem tuto šablonu pojmenoval SBS. Zvláště praktická je podle mě hlavně interní (podomácku vyrobená) konzole, díky níž se program relativně dobře ovládá. Do této doby program nijak nesouvisel s celulárními automaty. Poté jsem začal pracovat na třídě Automat, která zastřešuje všechny věci ohledně celulárních automatů (kromě samotného vykreslování). Automat jsem následně začal začleňovat do SBS pomocí funkcí pro vykreslování „hrací plochy" a také pomocí příkazů pro interní konzoly. V této dokumentaci bych se chtěl věnovat hlavně třídě Automat, protože je pro problém nejpodstatnější a protože SBS je velice velké a tedy by byla podrobná dokumentace hodně náročná.

Program je vyvíjen ve volně šiřitelném IDE jménem Dev-Cpp.

Současný stav programu

Popravdě řečeno, s programem ještě nejsem zcela spokojen. Podcenil jsem jeho náročnost a tak jsem zatím nestihl včas všechno co jsem stihnout chtěl. Na druhou stranu je v současnem stavu relativně celistvý a myslím, že je na něm vidět relativně dost práce (celková velikost zdrojových textů se pohybuje okolo 100kB).

Hlavní nedostatky

  • Zatím je implementována pouze jeden typ evoluční funkce (tzn. obecnější pravidlo, jak zjistit následující stav automatu.) To však není velký problém, implementace dalších funkcí se dá do programu jednoduše zařadit.
  • Chybí pohodlný editor: zatím je všechno editování pravidel ale hlavně samotných stavů automatů realizováno přes načtení textového souboru, kde je daná věc popsána.
  • Nehezky udělaná 1D (zatím bez viditelného zobrazování průběhu vývoje automatu (historie), jak bývá zvykem. Tzn. 2D zobrazení kde rozměr navíc představuje čas.) a 3D verze (evidentně hnusně udělaná, zatím bez možnosti rotovat nebo jinak manipulovat (pouze možnost oddalovat či přibližovat a posouvat) ). Dále také odfláknuté barvičky buněk, zatím jsou všechny z šedého spektra.
  • Zatím není „výzkumná funkce“ na rozpoznání děla.

Ovládání

Program se ovládá primárně přes interní konzoly. Při zadání příkazu help se zobrazí seznam všech příkazů plus další rady.

Kamerou lze hýbat pomocí myši (levé tlačítko a kolečko). Pomocí šipek nahoru a dolů se může listovat v historii zadaných vstupů do konzole. Pomocí TABulátoru lze postupně projet všechny funkční příkazy.

Pokud zavoláme jakýkoliv příkaz s parametrem -? (tzn. například exit -?) , pak se zobrazí podrobnější popis příkazu, nežli je uveden příkazem help.

Zde je seznam hlavních příkazů, kterými lze program ovládat:

Ovládání Automatu

lp jméno : načte pravidla Automatu ze složky pravidla. (Nepište koncovku .txt, tzn. pokusí se načíst soubor ./pravidla/jméno.txt ) Dále se pokusí nahrát implicitní stav automatu ze souboru ./stavy/_jméno.txt kde jméno je zadané jméno.

ls jméno : načte stav Automatu ze složky stavy, nepište koncovku .txt . (Tzn. program se pokusí načíst soubor ./stavy/jméno.txt )

play : nastartuje chod simulace. Ta bude probíhat dokud se nezastaví příkazem stop.

stop : zastaví chod simulace.

next n : posune automat o n taktů dopředu. Pokud n není vyplněno, posune o jeden takt dopředu.

pravidla : vypíše pravidla automatu.

rand : stav automatu se nastaví náhodně.

takt t : nastaví dobu jednoho taktu na t milisekund. Pokud není t zadáno, vypíše aktuální nastavení délky taktu.

cojeto hloubka : program se pokusí blíže identifikovat, zda není útvar v automatu něco speciálního. Hloubka (bez udání je 100) udává počet generací dopředu, které má program při analýze prozkoumat, než se vzdá.

Několik dalších příkazů

help : Vypíše help.

exit : Vypne program.

clrscr : Smaže výstup konzole.

fulscr : ON/OFF fullscreen.

fps : Vypíše FPS.

zoom hodnota : hodnota udává jak moc se přiblíží kamera. Pro kladnou hodnotu přibližuje, pro zápornou vzdaluje.

Program dále obsahuje ještě několik spíše pokusných/žertovných příkazů, ty lze najít TABulátorem.

Pozn.: celá konzole je dělaná na koleně. V tom je zahrnuto i rozložení klávesnice, takže nastavení klávesnice ve Windows nemá vliv na nastavení v programu. Tam je vždy česká klávesnice. Protože jsem dělal program na notebooku, zapomněl jsem implementovat numerickou klávesnici, proto čísla se píšou jako shift + čísílka nad písmenkovou klávesnicí.

Třída Automat

Třída Automat reprezentuje celulární automat: jeho pravidla i stav. Její popis je hlavní částí této dokumentace.

Zadání pravidel

Pravidla jsou zadána následujícími vlastnostmi:

  • Dimenze – možné hodnoty 1,2 nebo 3
  • Tvar políčka – pro 1D a 3D je to čtverec, pro 2D čtverec, hexagon nebo trojúhelník
  • Toroidnost – pokud je hrací plocha toroidní, potom okrajová políčka sousedí s políčky na druhé straně, jako by byla hrací plocha toroid.
  • Počet možných barev buněk – [1 až 255] přičemž barva „mrtvá buňka“ se do tohoto počtu nepočítá.
  • Velikost – určuje velikost hrací plochy, respektive počet políček. Pro 1D automat je počet políček přímo velikost. Pro 2D automat je počet políček roven velikost*velikost. Pro 3D automat je počet políček roven velikost*velikost*velikost.
  • Typ evoluční funkce – Evoluční funkce je obecnější pravidlo, které definuje, jak se má z určitého stavu automatu dostat následující stav.
  • Zadání evoluční funkce - to je řada čísel, která přesně charakterizuje evoluční funkci.

Stav automatu

Automat se vždy nachází v nějakém stavu. Stavem se rozumí barevné ohodnocení políček hrací plochy.

Evoluční funkce

Evoluční funkce je obecnější pravidlo, které definuje, jak se má z určitého stavu automatu dostat následující stav.

Zatím je implementován pouze typ PREZIJE_VS_NARODI.

PREZIJE_VS_NARODI

Tato strategie je definovaná jako dva výčty. První je výčet počtu sousedů stejné barvy jako má živá buňka, který je potřeba k přežití do dalšího taktu. Druhý výčet je výčet počtu sousedů jedné barvy okolo mrtvé buňky který je zapotřebí k tomu, aby tato mrtvá buňka ožila do živé buňky s barvou těchto sousedů. Může nastat situace, kdy není jednoznačné, „do které barvy“ se mrtvá buňka v příštím taktu narodí. Potom je to ta z možných barev s nejnižším číslem (tím se myslí číslem barvy).

Příklad:

Klasická Game of Life je tohoto typu (je charakterizována výčtem 23/3). Výčet 23/3 konkrétně znamená : Buňka přežije právě tehdy když ji obklopují 2 nebo 3 sousedi stejné barvy, mrtvá buňka ožije právě tehdy když ji obklopují 3 živé buňky stejné barvy.

Ve vstupním souboru pravidel je přesná definice této evoluční funkce dána jako dvojice posloupností čísel, kde každá je zakončena číslem -1. Druhou -1čku následuje -2, která ukončuje celé zadání (viz dále ve „Formát vstupních souborů“).

Game of Life je podle tohoto pravidla zapsatelná jako : 2 3 -1 2 -1 -2

Program obsahuje zatím pouze jednu implementovanou evoluční funkci, dodělat další typy však není velký problém.

Reprezentace hrací plochy

Každá hrací plocha se reprezentuje jako jednorozměrné pole čísel (respektive přesněji: jako vector). Pokud je hrací plocha 1D, je vše jasné. Pokud je hrací plocha 2D, potom se hrací plocha vnímá jako „čtvercová síť“. Pole pak představuje hrací plochu, jako by byla čtena po řádcích. Tzn. že pokud máme zadán index v tomto poli, x-ovou a y-ovou pozici políčka na čtvercové síti dostaneme jako (Kde velikost je vstupní parametr pravidel velikost) :

xpos = index mod velikost
ypos = index / velikost

Naopak index z x-ové a y-ové pozice dostaneme jako:

index = ypos * velikost + xpos

(Pozn.: souřadnice jsou vždy z rozsahu 0 až velikost-1 )

Pokud je hrací plocha 3D, potom se hrací plocha chápe jako „krychlová síť“. Pole pak představuje hrací plochu, jako by byla čtena po řádcích v rámci jedné čtvercové vrstvy se stejnou z-ovou pozicí, pokud je přečtena jedna vrstva, jde se na další v pořadí. Tzn. že pokud máme zadán index v tomto poli, x-ovou, y-ovou a z-tovou pozici políčka na „krychlové síti“ dostaneme jako:

xpos = index mod velikost
ypos = ( index / velikost ) mod velikost
zpos = index / ( velikost * velikost )

Naopak index z x-ové, y-ové a z-ové pozice dostaneme jako:

index = zpos*(velikost*velikost) + ypos*velikost + xpos

Dále zbývá dořešit, jak reprezentovat hexagonovou a trojúhelníkovou síť pro 2D variantu. Obě tyto sítě lze jednoduše číst po řádcích, proto je obě můžeme chápat jako čtvercovou síť. To co z nich dělá něco jiného, než je čtvercová síť je pouze vykreslení a pravidlo, které určuje se kterými políčky nějaké políčko sousedí. Pro úplné vysvětlení postačí snad tento obrázek:

Sousedství buňky

U 1D varianty jsou sousedy buňky ta buňka od ní nalevo a ta od ní napravo.

U 3D varianty jsou za sousedy považovány všechny krychle v krychlové síti, které mají s danou krychlí společný alespoň jeden bod. To znamená že buňky na 3D hrací ploše mají 26 sousedů.

U 2D-čtvercové varianty je za sousedy považováno klasicky všech 8 sousedů (tzn. sousedi jsou ty čtverce, které mají s naším čtvercem společný alespoň jeden bod).

U 2D-hexagonové varianty bereme za sousedy všech 6 okolních políček. Je potřeba však problém převést na situaci ve čtvercové síti. Vyjde nám jednoduchý výpočet relativní pozice souseda ve čtvercové síti. Konstanty relativního posunutí jsou závislé pouze na tom, zda se námi zkoumané políčko nachází na sudém nebo lichém řádku. Vše je snad jednoduše vidět na následujícím obrázku:

U 2D-trojúhelníkové varianty bereme za sousedy jen ty 3 sousedy, kteří sdílí s danou buňkou stranu. Situace je velice podobná jako u hexagonu, s tím rozdílem, že tentokrát nemá na relativní pozice vliv sudost/lichost řádku, na kterém je buňka, ale to, zda je trojúhelníkové políčko, které nás zajímá, „špičkou“ nahoru nebo dolu.

To jestli je trojúhelník šipkou nahoru či dolu lehce spočteme z jeho pozice následovně:

isNahoru = (( xpos mod 2 + ypos mod 2 ) mod 2 == 0 )

Vše je zase jednoduše vidět z obrázku:

Ještě zbývá vyřešit jednu komplikaci: co jsou sousedé políček na kraji hrací desky. Řešení jsou dvě na základě toho, zda je v pravidlech nastavena toroidnost či ne.

Pokud není deska toroidní, potom se soused mimo hrací desku považuje za mrtvého (přesněji: funkce int GetSousedIndex(int index , int s) vrací v takovém případě hodnotu AutomatConst::VYPADNUTI . Tuto funkci využívá funkce pro zjištění barvy buňky podle jejího indexu ( to je funkce Barva Automat::GetBarvaBunky_akt( int index ) ) a tato funkce při tom když dostane jako index VYPADNUTI vrací jako barvu nulu, tzn. mrtvou buňku.)

Pokud je deska toroidní, potom pozici souseda přepočteme následovně: (předpokládejme, že pozice přetekla v x-ové souřadnici, u ostatních souřadnic se postupuje zcela analogicky)

	jestliže xpos < 0 		pak xpos = velikost – 1
	jestliže xpos >= velikost 	pak xpos = 0

Dále platí omezující podmínka na tvar trojúhelníkové sítě: je požadována jako velikost sude číslo. Je to z toho důvodu, aby se toroidnost chovala přirozeně, tedy že se na hrací plochu můžeme dívat jako na plášť toroidu. Podobně to platí i pro hexagonovou síť. Na první pohled tato podmínka není nutná pro netoroidní desky, avšak algoritmy pro zjišťování vlastností zkoumaného stavu využívají toroidnosti, tzn. při jejich volání dochází k neviditelnému zapnutí a po proběhnuvším výpočtu zase vypnutí.

Jak probíhá evoluce

Evolucí se zde rozumí postupný přechod od jednoho stavu ke druhému. Zjednodušeně řečeno to probíhá tak, že ve skutečnosti, neobsahuje třída jednu hrací desku, ale dvě: aktuální a neaktuální. Při výpočtu dalšího stavu se z aktuální desky spočítá nový stav neaktuální desky a přehodí se jim aktuálnost.

„Výzkumná funkce“ : Metoda CoJeTo()

Tato metoda odpoví na otázku, zda je obsah (tedy stav) daného automatu raketa (spaceship) nebo oscilátor. Vrací periodu rakety respektive oscilátoru a do stringu předávaného odkazem uloží podrobnější popis: To zda se jedná o raketu či oscilátor, jeho periodu a v případě, že jde o raketu, řekne jakým směrem se pohybuje a jakou rychlostí. První argument je hloubka (počet generací) do které se testuje, než se testování vzdá. Druhý argumentu je už zmiňovaný string.

Je to prakticky jediná algoritmicky náročnější část projektu.

Současná implementace metody:

Nejdříve vysvětlím, co myslím pojmem Podpis okolí buňky : je to řada čísel, která jednoznačně určuje relativní okolí jedné konkrétní buňky na toroidní hrací desce (zde se okolím nemyslí jen sousedi, ale všechny buňky na hrací ploše, tak jak obklopují tuto konkrétní buňku). Pokud známe podpis a pozici buňky na hrací desce, můžeme rekonstruovat jak vypadá stav. NAOPAK pokud známe pouze podpis, nejde z něho rekonstruovat stav, lze z něj rekonstruovat stav, u kterého ale nevíme, jak je posunut vůči původnímu stavu automatu.

Takovýto podpis můžeme vytvořit tak, že budeme hrací plochu procházet do šířky (tím mám na mysli „algoritmus vlny“).

Na počátku uložíme do fronty pozici buňky, ke které okolí vztahujeme. Zapamatujeme si, že jsme jí navštívili. Pak opakujeme následující sadu kroků, dokud není fronta prázdná: Vyndáme ze předku fronty pozici, podpis rozšíříme (rozšířením se myslí přidání dalšího čísla na konec řady) o barvu buňky na této pozici a přidáme na konec fronty všechny zatím nenavštívené sousedy této buňky (dále si zapamatujeme, že jsme tyto políčka už navštívili).

Díky tomu, že prohledáváme po zatím nenavštívených sousedech, víme že toroidnost nijak nevadí.

Samotný algoritmus metody CoJeTo() pak probíhá zhruba následovně: zapamatujeme si současný stav automatu. Najdeme první nenulovou buňku a zjistíme podpis jejího okolí. (Zde se předpokládá že je součástí potenciální rakety, tzn. pokud raketa není jediná věc obsažená v aktuálním stavu, nebude algoritmus fungovat. Ovšem to by (pokud bychom byli puntičkáři) ani nemělo vadit, neboť raketa plus nějaké smetí okolo už (aspoň podle mě) de jure není raketa.) Dále budeme postupně testovat budoucí stavy hrací plochy, zda nemá nějaká nenulová buňka na tomto budoucím stavu stejný podpis jako je podpis aktuální desky. Stejný podpis by totiž znamenal, že jsou tyto dva stavy shodné až na posunutí na toroidní hrací ploše. Samozřejmě budeme testovat „chytře“, takže při prvním neodpovídání si podpisů přestaneme tento podpis dál počítat. Prohledávání do šířky jsem zvolil kvůli tomu, že zachovává víc lokálnost, než prohledávání do hloubky, díky čemuž je velká šance, že budou hned na začátku nalezeny rozdíly, neboť je pravděpodobné, že blízko první živé buňky (která patří do rakety podle předpokladu) bude i relativně dost jiných živých buněk, které se při nesouhlasu podpisů budou s vysokou pravděpodobností lišit.

Dále je dobré zmínit, že před použitím tohoto algoritmu se tajně zapne toroidnost, pokud je vypnutá, a před ukončením se zase vrátí do původního stavu.

Poznámka o uložení definic funkcí

Protože jsou funkce CoJeTo() a k ní pomocné funkce asi nejdůležitější funkce projektu, jsou uloženy stranou od ostatních funkcí třídy Automat, jsou v souboru automat_cojeto.cpp.

Poznámka o staré implementaci

Dříve byla tato metoda implementována jinak, této implementaci však dělala problém toroidnost:

Zapamatujeme si aktuální stav a postupně stav evolvujeme. Tím dostaneme nějaký budoucí stav. Tyto budoucí stavy budeme porovnávat s aktuálním stavem.

Při porovnávání začneme tím, že najdeme první nenulovou buňku postupným procházením hrací desky.

Předpokladem je, že raketa je periodická k relativní pozici a že hrací deska "nemá zuby" (tím myslím že obdélníková nebo čtvercová, respektive krychlová). Potom, pokud je zkoumaný stav raketa, existují dva stavy „historie“ (započaté aktuálním stavem a postupující do budoucnosti), kde od tohoto nenulového stavu až nakonec jsou všechny barvy buněk stejné. Pokud tyto dva podobné stavy najdeme, víme že se jedná o raketu. Oscilátor je potom speciální druh rakety (mající rychlost 0).

Problémy způsobuje toroidnost respektive okraje obecně: Pokud totiž raketa zajede mimo hrací plochu (tím se myslí i využití toroidnosti), už neplatí pravidlo, že takovýto stav (po přechodu kraje) je u rakety nutně podobný popsaným způsobem nějakému minulému stavu.

Formát vstupních souborů

Soubory s pravidly automatu má čitelnou strukturu a je jednoduše vyplnitelný.

Je formátován takto: Každá zadávaná vlastnost je předznamenána samostatným řádkem, který tam je pouze pro to, aby se to dobře četlo. Na dalším řádku je jedno číslo po kterém následuje libovolný počet bílých znaků. Toto platí pro všechny vlastnosti až na poslední, kterou je Zadání evoluční funkce. To je řada čísel (oddělených libovolným počtem bílých znaků) ukončená číslem -2. Uvnitř této řady se jako oddělovač v rámci této řady používá -1.

Příklad (komentáře jsou červeně):

DIMENZE[1/2/3] pouze hlavička vlastnosti, může být přepsána na něco jiného
2 hodnota vlastnosti dimenze, může nabývat hodnot 1, 2 nebo 3

TVAR_POLICKA[0:ctverec/1:trojuh/2:hexagon]
2 tvar políčka : 0 odpovídá čtverci, 1 trojúhelníku a 2 hexagonu

TOROIDNI?[0/1]
1 určuje, zda je hrací plocha toroidní. Může nabívat hodnot 0 není toroidní, 1 je toroidní

POCET_BAREV[1..255]
5 určuje počet možných barev buněk, nepočítáme-li barvu 0 vždy znamenající mrtvou buňku. Tedy Počet barev 5 znamená, že jsou barvy 0,1,2,3,4,5

VELIKOST[1..hodne]
10 určuje velikost hrací plochy, respektive počet políček. Pro 1D automat je počet políček přímo velikost. Pro 2D automat je počet políček roven velikost*velikost. Pro 3D automat je počet políček roven velikost*velikost*velikost.

TYP_EVOLUCNI_FUNKCE[1]
1 určuje typ evoluční funkce, zatím je implementována pouze jedna evoluční funkce, která má v tomto kontextu číslo 1.

ZADANI_EVOLUCNI_FUNKCE
2 3 -1
3 -1
-2
Touto řadou čísel je přesně dodefinována evoluční funkce.

Soubory s uloženým stavem automatu má zatím o poznání ošklivější vzezření. Je to řada čísel oddělená bílými znaky, která přesně koresponduje s vnitřní reprezentací hrací desky, která je pole čísel (viz Reprezentace hrací plochy). Je povoleno, aby tato řada byla kratší respektive delší (potom se usekne) než počet buněk hrací plochy. Není však dovoleno, aby tato řada obsahovala barvy mimo rozsah aktuálních pravidel.

Příklad:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Formát je to dost nešťastný (z pohledu uživatelova pohodlí), protože ale počítám s přiděláním vestavěného editoru, tak jsem zatím tuto implementaci nechal, což byla asi chyba: zdržuje to při testování.

Načítaní pravidel/stavu přes konzoly programu : pro tyto akce má program dva příkazy: lp jmenoSouboru se pokusí načíst pravidla ze souboru ./pravidla/jmenoSouboru.txt . Podobně funguje ls jmenoSouboru , to se pokusí načíst aktuální stav ze souboru ./stavy/jmenoSouboru.txt .

Podrobněji viz Ovládání.

Program si v konfiguračních souborech ./config/implicitniPravidla.txt respektive ./config/implicitniStav.txt ukládá cesty k pravidlům respektive stavům, které se načtou po zapnutí programu.

Veřejné rozhraní třídy

Stručně shrnu celé veřejné rozhraní třídy Automat :

Automat( )
To je implicitní konstruktor. Vytvoří nekorektní pravidla. (korektnost se uchovává v proměnné třídy.)

bool LoadPravidla (const char* souborPravidel )
Načte pravidla ze souboru, vrací zda se povedlo korektně načíst.

int LoadStav (const char* souborStavu )
Nahraje stav automatu, vrací číslo podle úspěchu.
0 : OK
1 : pravidla nejsou OK
2 : vstup obsahuje nekorektni barvu
3 : soubor neexistuje

int CoJeTo( int kolikTestovatGeneraci , string & info )
Odpoví na otázku, zda je obsah (tedy stav) daného automatu raketa (spaceship) nebo oscilátor. Vrací periodu rakety respektive oscilátoru. První argument je hloubka (počet generací) do které se testuje, než se testování vzdá. Do druhého stringového argumentu se uloží informace o tom, jak to dopadlo.

void ResetHistorie( int newSize )
Smaže historii a nastaví ji novou velikost. (Pozn.: Historie zatím není používána, je to připraveno na budoucí použití.)

void Next( bool ulozitDoHistorie = true )
Vypočítá další stav automatu a zaktualizuje ho. Je volitelné, zda se bude ukládat do historie, pokud tedy nějaká je nastavená.

bool IsOk()
Vrátí, zda jsou pravidla automatu v pořádku, tzn. korektní.

int GetVelikost()
Vrátí velikost automatu.

Tvar GetTvarPolicka()
Vrátí tvar políček.

int GetNumBarev()
Vrátí počet možných barev.

void Rand()
Nastaví stav automatu na náhodný.

int GetDimenze()
Vrátí dimenzi automatu.

Barva GetBarvaBunky_akt( int index )
Vrátí barvu požadovane bunky na aktualní desce.

string GetPravidla( )
Vrátí string s lidsky čitelným popisem pravidel.

int GetNumSousedu()
Vrací počet sousedů pro jedno políčko.

int GetNumBunek()
Vrací počet všech buněk.

string GetDeskaInString2D()
Vrátí string obsahující aktualní situaci na desce (předpokládá se 2D deska). (Metoda pro testovací účely.)

Členské proměnné třídy

Všechny členské proměnné třídy jsou privátní, zde je jejich stručný popis:

Reprezentace hrací desky:

Deska m_deska[2]
jsou použity 2 hrací desky kde je uložen stav automatu: aktuální a neaktuální. (viz Jak probíhá evoluce) (Deska je typedef pro vector , Barva je typedef pro unsigned char)

int m_indexAktDesky
ví, která deska je aktuální

int m_indexNeaktDesky
ví, která deska je neaktuální

Reprezentace historie :

vector m_historie
slouží k ukládání minulých stavu desky

int m_1stFreeHist
pamatuje si první volnou pozici ve vectoru historie

Reprezentace pravidel :

bool m_pravidlaOK
Signalizuje, zda byla pravidla zadána korektně

string m_errMsg
popis chyby, ke které došlo při nahrávání pravidel

int m_dimenze
určuje dimenzi (1 až 3)

Tvar m_tvarPolicka
určuje tvar políčka (CTVEREC, TROJUHELNIK nebo HEXAGON )

bool m_isToroidni
zda je plocha toroidní či nikoliv

int m_numBarev
počet možných obarvení buněk ( „mrtvá“ barva se nepočítá do tohoto čísla)

int m_velikost
určuje „velikost“ hrací desky

TypEvolucniFunkce m_typEF
Určuje typ zvolené evoluční funkce

vector m_dataEF
řada čísel, která přesně určuje evoluční funkci pro pravidla automatu. Interpretace už je na konkrétní implementaci evoluční funkcí. Předpoklad je, že vždy bude pro evoluční funkci pohodlné, aby svá pravidla reprezentovala jako řadu čísel. Tato proměnná je používána dvoufázově: Nejdřív je do ní nahrána přímo řada čísel ze vstupního souboru. Následně je při průběhu funkce LoadPravidla() volána funkce ZpracujDataEF() která m_dataEF s jejich dočasným obsahem zpracuje a předělá na data pohodlná pro vnitřní použití přímo evoluční funkcí.

string m_txtEF
pravidla evoluční funkce zapsaná v klasickém kódu, čitelném člověkem.

Soubory projektu

Projekt se skládá z relativně velkého počtu souborů, zde je jejich seznam a stručný popis toho, co obsahují.

Soubory pro třídu Automat

automat.h – deklarace třídy Automat a pomocných typů a konstant

automat.cpp – definice všech funkcí třídy Automat (až na „výzkumné funkce“)

automat_cojeto.cpp – definice „výzkumných“ funkcí

Soubory pro funkce vykreslující automat

mainDraw.cpp – Obsahuje hlavně funkci MainDraw(), která zprostředkovává vykreslení celé hrací plochy. Dále obsahuje inicializační funkce a funkce pro ovládání rychlosti přehrávání simulace.

drawAutomat.cpp – Obsahuje pomocné funkce pro vykreslování. Vykreslování jednotlivých tvarů atd.

drawAutomat.h – Hlavičky pro drawAutomat.cpp

Soubory pro příkazy interní konzole

prikazy.cpp – obsahuje definici všech funkcí pro příkazy interní konzole plus funkce pro správu příkazů. Nový příkaz se vloží velice snadno: stačí napsat funkci ve tvaru int PrikazJmenoprikazu ( const string & args ) a do funkce void RegistrovatPrikazy() na konci souboru přidat řádek RegistrovatPrikaz("jmenoprikazu", PrikazJmenoprikazu); Pokud je pak příkaz volán z konzole (např. echo zivot je super), je zavolána funkce PrikazEcho() a jako argument args je jí předán string „zivot je super“.

Soubory pro SBS

SBS.h – Hlavní hlavičkový soubor projektu.

config.cpp – funkce pro práci s konfiguračními soubory

config.h – hlavička pro config.cpp

draw.cpp – hlavní funkce pro obecné vykreslování DrawGLScene() která mimo jiné volá funkci pro vykreslování hrací plochy mainDraw(). Dále inicializace SBS a openGL. Funkce pro práci s „kamerou“. Vykreslování konzole. Další pomocné vykreslovací funkce.

eventy.cpp – funkce pro obsluhu událostí (ve smyslu WinApi).

klavesy.cpp – funkce pro reakci na zmačknutí klávesy.

main.cpp –obsahuje funkci WinMain()

SBSconsole.cpp – funkce pro práci s konzolou. Většina je však jen rozhraní mezi objektem g_console a zbytkem programu, tak aby se vyhnulo globální proměnné.

SBSfont.cpp – funkce pro práci s fonty

SBSglobals.cpp – funkce zajišťující rozhraní mezi ostatními funkcemi a globálními proměnnými.

SBSmakra.h – makra preprocesoru

SBSprovozni.cpp – různé provozní funkce, hlavně pro práci se stringy a asertace.

SBStemneFce.cpp – funkce pro chod WinApi, hlavně propojení s openGL.

Soubory pro třídy využívané SBS

fps.cpp – třída zajišťující výpočet hodnoty Frames Per Second (snímky za sekundu). Využívá se k tomu, aby simulace probíhala správnou rychlostí.

fps.h – hlavička pro fps.cpp

SBSClasses.h – mini třídy pro práci s trojicemi a dvojicemi čísel.

textConsole.cpp – třída definující textovou konzoly

textConsole.h – hlavička pro textConsole.cpp




A to je konec dokumentace..



Tady k tomu můžete napsat komentář
Jméno:
Opište text v rámečku: