Technické záležitosti

Obsah

• API pro organismy
• Popis formátu ENV
• Zpětná kompatibilita s verzí M1
  • ENV soubory
  • Organismy
• Zdrojový kód a kompilace The Life!
• Rychlost × paměť
• Seznam organismů

API pro organismy

Zajímavou kapitolou je návrh API pro tvorbu organismů. Organismus je tvořen knihovnou DLL, která musí povinně obsahovat funkce OrgGetRequieredVersion a OrgRun. The Life! po svém spuštění načte všechny DLL knihovny v adresáři Org, zjistí, zda exportují zmíněné funkce, a zavolá GetRequiredVersion. Ta musí v současné verzi vrátit hodnotu $00050000, což značí, že organismus je určen pro verzi API 5.0. Z toho je vidět, že API jsem v průběhu vývoje upravoval a to tak, že nebylo zpětně kompatibilní. Při každé takovéto úpravě jsem číslo verze zvedl a bude to tak pravděpodobně i v budoucích verzích. Organismy, které vrátí správné číslo verze API, jsou pak zobrazeny v The Life! v seznamu organismů.

Při každém kroku simulace se pro každý organismus volá procedura OrgRun příslušného DLL. Jako parametr se jí předává ukazatel na rozhraní (interface) IVLFOrganism. Voláním jeho metod pak realizuje organismus svůj "život".

Proč jsem zvolil zrovna rozhraní? Je to ve Windows asi nejstandardnější metoda, jak předat odkaz na soubor metod manipulující s objektem (v C++ by se tomu říkalo abstraktní třída). Podstatnou výhodou je také to, že rozhraní podporují prakticky všechna vývojová prostředí ve Windows (od Borlandu, Microsoftu i od jiných výrobců), takže to usnadňuje tvorbu organismů v jiných jazycích.

Nevýhoda rozhraní je, že se u něj automaticky počítají reference a když jejich počet dosáhne nuly, zavolá se destruktor objektu, který rozhraní implementuje. Nevím, koho v Microsoftu napadlo míchat dohromady abstraktní třídu a počítání referencí, ale docela by mě zajímaly důvody. Object Pascal počítání referencí zajišťuje automaticky při přiřazování, předávání jako parametr apod. To je sice hezké, ale za určitých podmínek (např.při přetypování a uložení objektu jako pointer) se mechanismus chová nekonzistentně a není lehké ohlídat, aby byl počet referencí správný. V jiných jazycích si vše musí programátor dělat ručně sám.

Každá DLL organismu je načtena jen jednou, není tedy tvořena separátní instance pro každý organismus (to by drasticky snížilo výkon aplikace). To má ten důsledek, že pokud v souborech tvořících knihovnu deklarujeme globální proměnné, jsou tyto přístupné z každého organismu. Protože by to příliš zjednodušovalo komunikaci mezi organismy, považuji globální proměnné v organismech za zakázané. Samozřejmě je na autorovi organismu, zda to bude dodržovat, ale zdá se mi to férové.

Zajímavou možností, jak obejít API, je přepsat paměť s daty o organismu. Když OrgRun dostane ukazatel na rozhraní organismu, dá se při znalostech zdrojového kódu The Life! a způsobu, jak Delphi zachází s pamětí, zjistit adresa, kde jsou zapsány důležité proměnné organismu, jako je hmotnost nebo energie. Vzhledem k tomu, že DLL a hlavní EXE soubor sdílí stejný paměťový prostor, není problém tyto hodnoty přepsat. Opět platí, že slušné organismy toto nedělají, ale je to zajímavý námět na hraní si s assemblerem.

Při troše snahy lze zneužít i uživatelské registry — stačí je přetypovat na pointery a rázem je můžete používat k uchovávání dynamicky alokovaných struktur, čímž si můžete libovolně zvětšit paměť organismu. Problémem je, že organismus nikdy předem neví, kdy zahyne, a nemá tak kdy tyto struktury odalokovat. Proto i toto chování organismů považuji za nesportovní.

Popis formátu ENV

ENV je formát binární (tzn. nikoliv textový). Dokáže přesně zaznamenat stav celé simulace. Je optimalizován především na rychlé načítání a ukládání, ale má v sobě i vestavěnou volitelnou možnost komprimace, díky niž se může objem dat v souboru značně zmenšit (běžně i pod 10%). Nevýhodou je značné zpomalení při ukládání a načítání. Komprimace se hodí třeba při posílání souborů přes internet apod.

Popsána je pouze varianta formátu používaná verzí M2. Variantu používanou verzí M1 si mohou zájemci odvodit za domácí úkol ze zdrojáků (M2 umí načítat soubory M1, ale neumí je ukládat).

Soubor se skládá z hlavičky a vlastních datových struktur. Obsah celého souboru se dá popsat pomocí následující tabulky:

Poznámka

Všechny typy dat a konstanty jsou v Object Pascalu (Delphi). Pro céčkaře a jim podobné: Integer je 32bitové celé číslo se znaménkem, Byte je 8bitové celé číslo bez znaménka, Char je 8bitové celé číslo bez znaménka představující jeden znak v ASCII. Konstanty začínající dolarem ("$") jsou v šestnáctkové soustavě.

Zpětná kompatibilita s verzí M1

ENV soubory

Formát ENV souborů byl v průběhu vývoje verze M2 podstatně upraven a není kompatibilní s verzí M1. Verze M2 nicméně umí načítat soubory z verze M1, ale neumí je ukládat.

Organismy

DLL organismů nejsou mezi verzemi M1 a M2 vůbec binárně kompatibilní — pokud zkusíte zkopírovat DLL soubor z jedné verze do adresáře Org verze druhé, ta ho nebude vůbec detekovat jako organismus.

Na úrovni zdrojových kódů by neměl být problém s převodem organismů z verze M1 — změny v API by neměly příliš narušit zpětnou kompatibilitu. Je potřeba zajistit, aby soubor s implementací organismu používal novou verzi unity OrgInterface a na začátek jeho kontrolní procedury je nutné připsat příkaz alokující uživatelské registry — např. AllocUR(5) pokud organismus používá registry 0-4. Pak by mělo vše fungovat.

Při převodu je také nutné si uvědomit, že se oproti verzi M1 změnil algoritmus distribuce potravy a také pohyb stojí víc energie (v závislosti na hmotnosti organismu).

Zdrojový kód a kompilace The Life!

Ve zdrojovém balíčku najdete vše, co potřebujete k vytvoření úplné distribuce The Life! — tj. všechny zdrojové a datové soubory. Nejsou zde žádné závislosti na čemkoliv mimo tento balíček. Všechny soubory mimo adresář zlib jsou moje práce (v adresáři zlib se nachází Pascalský port kompresní knihovny, který není mým dílem). Ve zdrojovém kódu jsem komentoval jen důležitá místa — triviality a kód generovaný Delphi jsem vesměs nechal nekomentované.

The Life! je napsán v Borland Delphi 6. Ke kompilaci by mělo stačit otevřít v tomto nástroji projekt Life.dpr a zvolit Project|Compile Life. V nižších ani vyšších verzích jsem kompilaci nezkoušel, a tak nevím, zda se vám povede. Ve vyšších verzích by ale vše nejspíš mělo fungovat.

Organismy by měly jít zkompilovat obdobným způsobem. Zkoušel jsem je kompilovat i s Delphi 3 a vše fungovalo.

Problémem je kompilace DLLInstall.exe. Tento soubor je určen k nahrání potřebných DLL do systému Windows 95, pokud je tam uživatel nemá (viz Známé problémy). Pokud ho zkompilujete v Delphi 6, bude ale sám tyto knihovny ke svému spuštění vyžadovat! Ze začarovaného kruhu se dá vymotat tím, že DLLInstall zkompilujete v nějaké nižší verzi Delphi (já používám Delphi 3 a funguje to).

Rychlost × paměť

Při implementaci jsem několikrát musel řešit klasické programátorské dilema, zda-li optimalizovat program na rychlost nebo paměťovou náročnost. Ve většině případů jsem jednoznačně volil rychlost.

Místo, kde je to asi nejvíc vidět, jsou metody ForeignAllocedURCount, ForeignUR, SetForeignUR, OrgAt a Attack třídy TOrg. V nich je potřeba najít organismus, který leží na daných souřadnicích. Při několika desítkách tisíc organismů je velmi neefektivní procházet celý seznam organismů a vybírat toho, který má správné souřadnice. Proto jsem přidal pomocné seznamy organismů na každém řádku prostředí. Tyto seznamy se stále udržují aktuální, podle toho, jak se organismy pohybují, rodí a hynou. Při hledání organismu na nějakém políčku pak stačí prohledat jen jeden z těchto pomocných seznamů. Výsledkem optimalizace sice není kvalitativní snížení složitosti vyhledávání (stále je lineární), ale prohledávaný seznam je podstatně kratší (v průměru tolikrát, kolik je řádků v prostředí — a těch jsou typicky stovky). Nevýhodou je několik desítek až stovek kB paměti zabraných navíc.

Ve verzi M2 je tato optimalizace dotažena ještě dál — seznamy organismů se udržují dokonce pro každé políčko.

Seznam organismů

Zajímavým problémem bylo, jak navrhnout samotný hlavní seznam organismů. Z analýzy vyplynulo, že potřebuju především tyto tři operace:

• přístup k položkám (hlavně sekvenční)
• přidávání na konec seznamu
• odebírání z prostřed seznamu

Delphi má na tyto účely vyhrazený vlastní třídu TList, což je generický seznam pointerů. TList je interně implementovaný jako dynamicky alokované pole s tím, že se přealokovává vždy "po větších kusech", tedy ne při přidání/odebrání každé jednotlivé položky. Přístup k položkám je O(konst), přidávání na konec seznamu je sice obecně O(n), ale vzhledem k tomu, že se přealokovává jen čas od času, většinou je konstantní. Největší nevýhodou je odebírání zevnitř seznamu, protože všechny položky za tou odebíranou se musí posunout — operace má tedy lineární složitost, ale praxe ukazuje, že je velmi pomalá.

Jako řešení jsem zkusil navrhnout vlastní třídu TDoubleLinkedList, která navenek odpovídá TListu (tj. implementované metody jsou shodné), ale je to dvojitě zřetězený lineární spojový seznam. Přidávání i je O(konst), ale je pomalejší než u TListu. Odebírání má stejně jako u TListu lineární složitost, ale je mnohonásobně rychlejší. Problémem je přístup k položkám, který je O(n). Zkusil jsem implementovat speciální kešovací mechanismus optimalizující vícenásobný přístup k jedné položce a sekvenční přístup, ale i tak je simulace s tímto seznamem v průměru dvakrát pomalejší, než s TListem. Zatím je tedy TDoubleLinkedList defaultně vypnut (jde zapnout kompilační volbou), ale možná se někdy ještě k tomu dostanu a třeba TList trumfnu :-)

Zajímavým problémem je také procházení seznamem, když se pro každý organismus spouštějí kontrolní procedury. To znamená, že libovolné organismy mohou přibýt nebo naopak zemřít a změnit tak právě procházený seznam. Abych se vyhnul problémům s pohyblivými mezemi a podobnými jevy, zavedl jsem několik pravidel:

• Cyklus běží jen přes objekty, které jsou v seznamu na začátku cyklu. Kontrolní procedury těch, co se nově narodí, jsou spuštěny až v dalším kroku simulace.
• Položka příslušející zemřelému organismu se ve skutečnosti neodebírá, ale jen se nastaví na nil. Tím se zabrání zkracování seznamu. Při přístupu k položkám se v tomto cyklu na nil testuje, aby nedošlo v chybě při přístupu do paměti.
• Po skončení cyklu se všechny položky s hodnotou nil ze seznamu vyhází.

Vliv těchto pravidel na rychlost simulace není skoro žádný (pouze testování na nil navíc), protože je úplně jedno, zda se položky odebírají hned, nebo až později. Vliv na zjednodušení programu je značný.