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².