Na tomto míst¥ bude o ciální zadání va²í práce • Toto zadání je podepsané d¥kanem a vedoucím katedry, • musíte si ho vyzvednout na studiijním odd¥lení Katedry po£íta£· na Karlov¥ nám¥stí, • v jedné odevzdané práci bude originál tohoto zadání (originál z·stává po obhajob¥ na kated°e), • ve druhé bude na stejném míst¥ neov¥°ená kopie tohoto dokumentu (tato se vám vrátí po obhajob¥).
i
ii
eské vysoké u£ení technické v Praze Fakulta elektrotechnická Katedra po£íta£ové gra ky a interakce
Diplomová práce
Simulace davu Bc. Mat¥j Varcl
Vedoucí práce: Ing. Roman Berka, Ph.D.
Studijní program: Otev°ená informatika, strukturovaný, Navazující magisterský Obor: Po£íta£ová gra ka a interakce 1. ledna 2013
iv
v
Pod¥kování Cht¥l bych pod¥kovat v²em, kte°í m¥ p°i tvorb¥ této práce jako i po dobu celého studia podporovali a motivovali k dal²í £innosti.
vi
vii
Prohlá²ení Prohla²uji, ºe jsem práci vypracoval samostatn¥ a pouºil jsem pouze podklady uvedené v p°iloºeném seznamu. Nemám závaºný d·vod proti uºití tohoto ²kolního díla ve smyslu 60 Zákona £. 121/2000 Sb., o právu autorském, o právech souvisejících s právem autorským a o zm¥n¥ n¥kterých zákon· (autorský zákon).
V Praze dne 2. 1. 2013
.............................................................
viii
Abstract This work present two levels design of crowd simulation. The rst level is simulation and second level is visualization. The language for agent motion description is designed too. The simulation application is derived from social forces model. The eor it to reduce wrong abilities of this model and adapt output for motion description language. The visualization application interpret this language and display agents movement in 3D.
Abstrakt Tato práce se zabývá vytvo°ením dvouúrov¬ového konceptu simulace chování dav· na úrovni jednotlivc·. První úrovní je simulace tohoto chování a druhou úrovní je vizualizace. Také je navrºen jazyk, který slouºí k propojení t¥chto úrovní. Simula£ní aplikace vychází z modelu vzájemného p·sobení agent· (social forces model) a dále ho roz²i°uje. Snaha je odstranit nepat°i£né vlastnosti tohoto modelu a uzp·sobit výstup pro pot°eby jazyka pro záznam pohybu. Vizualiza£ní aplikace interpretuje tento jazyk a zobrazuje pr·b¥h simulace ve 3D.
ix
x
Obsah 1 Úvod
1
2 Popis problému, speci kace cíle
3
2.1
2.2
Existující práce . . . . . . . . . . 2.1.1 Simulace davu . . . . . . . 2.1.2 Jazyk pro záznam pohybu 2.1.3 Zobrazení animace . . . . Vymezení cíl· práce . . . . . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
3 Analýza a návrh °e²ení 3.1 3.2 3.3
3.4
Jazyk pro záznam pohybu . . . . . . . . . . Kon gura£ní soubor . . . . . . . . . . . . . Simula£ní aplikace . . . . . . . . . . . . . . 3.3.1 Pouºité technologie . . . . . . . . . . 3.3.2 Návrh aplikace . . . . . . . . . . . . 3.3.3 Simula£ní model . . . . . . . . . . . 3.3.3.1 Síla p°edcházení kolizí . . . 3.3.3.2 Síla pro °e²ení kolizí . . . . 3.3.3.3 e²ení vibrací . . . . . . . . 3.3.3.4 azení do p°irozených front 3.3.3.5 Roz²í°ení o události . . . . Vizualiza£ní aplikace . . . . . . . . . . . . . 3.4.1 Pouºité technologie . . . . . . . . . . 3.4.2 Návrh aplikace . . . . . . . . . . . .
4 Realizace 4.1 4.2 4.3 4.4
Kon gura£ní soubor . . . . . . . Simula£ní aplikace . . . . . . . . Jazyk pro záznam pohybu agent· Vizualiza£ní aplikace . . . . . . .
5 Testování a výsledky 5.1 5.2 5.3
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
4 4 5 5 5
7
7 9 10 10 11 12 15 17 17 18 18 20 20 22
23
23 27 30 32
35
Metody testování . . . . . . . . . . . . . . . . . . . . . . . . . 35 Výsledky testování . . . . . . . . . . . . . . . . . . . . . . . . 36 Interpretace výsledk· . . . . . . . . . . . . . . . . . . . . . . . 37 xi
xii
OBSAH
6 Záv¥r
39
A Slovní£ek pojm· z zkratek
43
B Podrobná de nice jazyk·
45
C Popis kon gura£ního souboru vizualiza£ní aplikace
51
B.1 Kon gura£ní soubor . . . . . . . . . . . . . . . . . . . . . . . 45 B.2 Jazyk pro popis pohybu . . . . . . . . . . . . . . . . . . . . . 48
D Instala£ní a uºivatelská p°íru£ka D.1 Pouºívání alikací . . . . . . . D.1.1 Simula£ní aplikace . . D.1.2 Vizualiza£ní aplikace . D.2 Kompilace ze zdrojových kód·
E Obsah p°iloºeného CD
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
53
53 53 54 54
55
Seznam obrázk· 3.1 3.2 3.3 3.4 3.5
Blokové schéma £ástí práce . . . . . Class diagram simula£ní aplikace . Oblast zájmu ºlutého agenta . . . . Výpo£et sil pro vyhnutí agent· . . Detek£ní oblast pro pravidlo £ekání
4.1
P°evod pozic na p°ímo£arý pohyb a orientaci . . . . . . . . . . 28
xiii
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
8 13 15 16 19
xiv
SEZNAM OBRÁZK
Kapitola 1 Úvod Simulace chování dav· na úrovni jednotlivých lidí je oblast, ve které probíhá výzkum jiº od konce 80. let 20. století. Cílem je vytvo°it model, kde se budou jednotliví ú£astníci v davu (dále agenti) chovat dle svých cíl·. Zam¥°ení výzkumu je moºné rozd¥lit do t°í základních skupin. První z nich je lm, druhým jsou po£íta£ové hry a t°etím bezpe£nostní simulace. Pro kaºdou z t¥chto kategorií jsou d·leºit¥j²í jiné aspekty simulace. Pro pot°eby lmu je nejd·leºit¥j²í vzhled a výsledný dojem. Chování agent· nemusí být úpln¥ reálné, protoºe sta£í, kdyº divák uv¥°í tomu, ºe to tak m·ºe být. Variabilita cíl· jednotlivých agent· je zpravidla malá. Také poºadavky na rychlost simulace a zobrazení nejsou moc d·leºité (zpomalení simulace oproti reálnému £asu m·ºe být n¥kolikanásobné). Na rozdíl od toho u po£íta£ových her je d·leºité, aby simulace probíhala v reálném £ase, aby byla hra plynulá. Výsledné chování agent· sta£í uv¥°itelné jako v p°ípad¥ lmu, ale variabilita cíl· je zde zpravidla v¥t²í. Zárove¬ je kladen d·raz na vzhled a výsledný dojem. Navíc je zde je²t¥ pot°eba reagovat na chování hrá£e. Oproti p°edchozím je v poslední kategorii kladen d·raz p°edev²ím na reálnost chování agent·, protoºe se na základ¥ simulace d¥lají rozhodnutí, která v krizových situacích ovliv¬ují ²anci na p°eºití lidí. Zobrazení sta£í, aby bylo srozumitelné a jasn¥ pochopitelné. Simulace m·ºe probíhat zpomalen¥, ale pokud není obraz n¥kam zaznamenáván podobn¥ jako u lmu, tak toto zpomalení nesmí být moc veliké. Navíc se od simulace o£ekávají je²t¥ n¥jaká dal²í souhrnná data (nap°íklad kdy poslední z lidí opustil budovu, nebo kolik lidí bylo zran¥no).
1
2
KAPITOLA 1.
ÚVOD
Kapitola 2 Popis problému, speci kace cíle Simulace dav· je docela obecné téma, ve kterém je pot°eba °e²it n¥kolik problém·. V²echny tyto problémy vychází z r·zných aspekt· lidského chování. Hlavním cílem v této oblasti výzkumu je vytvo°it model, který na základ¥ malého mnoºství vstupních parametr· provede realistickou simulaci chování v²ech lidí v davu. Nejzákladn¥j²í problém je °e²ení reakce agent· (jednotlivých lidí v davu) na své nejbliº²í okolí a interakce s ním (lokální plánování pohybu). Dal²ím problémem je samotné plánování pr·chodu scénou na základ¥ celkových informací o scén¥. Od toho je jen o kr·£ek dál rozhodovací mechanizmus pro jednotlivé agenty na základe jejich vlastností, znalostí a podn¥t· z jejich blízkého i vzdáleného okolí. Také je pot°eba zajistit dostate£nou r·znorodost agent·. Mimo simulace chování samotných agent· je nutné brát v potaz i dal²í objekty ve scén¥ a to jak statické tak pohyblivé (výtah, dve°e...). Dal²ím samostatným odv¥tvím je simulace dopravy (auta, tramvaje...). Mimo samotných problém· simulace jsou zde je²t¥ problémy s jejím zobrazením. Je nutné jednotlivé díl£í stavy simulace vhodn¥ p°evád¥t na výslednou vizualizaci. Zde záleºí na ú£elu provád¥ní simulace. Pro r·zné bezpe£nostní simulace není okolo zobrazení moc problém·, protoºe sta£í jen n¥jaké schématické, které ale musí být dob°e srozumitelné. V ostatních oblastech, kde je kladen d·raz na gra ckou podobu výstupu, je je²t¥ u agent· pot°eba °e²it mimo r·znorodosti na základ¥ jejich vlastností, znalostí a reakcí, ale i jejich vizuální jedine£nost. Navíc v¥rohodná animace lidské postavy je také velice komplexní problém (tím se ale tato práce zabývat nebude). V²echny vý²e zmín¥né problémy s sebou nesou je²t¥ jeden a tím je moºnost provád¥t celou simulaci (a zobrazení) v n¥jakém rozumném £ase (hodn¥ závisí na pouºití, t°eba pro po£íta£ové hry je nutnost simulace v reálném £ase), coº s sebou nese zna£né poºadavky na rychlost výpo£t·. Tato práce problém náro£nosti výpo£t· a zobrazení d¥lí na dva snaz²í rozd¥lením simulace a zobrazení na úpln¥ odd¥lené £ásti. To ale p°iná²í nutnost záznamu simulace a p°edání jejích výsledk· a pr·b¥hu pro následnou vizualizaci. Zde je 3
4
KAPITOLA 2.
POPIS PROBLÉMU, SPECIFIKACE CÍLE
nutné vy°e²it zp·sob, jak efektivn¥ zaznamenávat pohyb jednotlivých agent· po scén¥.
2.1 Existující práce Na základ¥ vý²e zmín¥ných problém· je z°ejmé, ºe bude pot°eba hledat °e²ení a tedy i vhodné materiály ve t°ech r·zných oblastech, které odpovídají jednotlivým £ástem práce. První z nich je samotná simulace davu, kde byly vyhledávány informace o jiº existujících simula£ních modelech a postupech. Druhou skupinou hledaných informací je popisný záznam pohybu lidí. T°etí skupinou vyhledávaných informací byly informace o moºnostech a nástrojích pro 3D zobrazení a výhodách jejich pouºití v kontextu zobrazení scény. Jelikoº jsou tyto £ásti rozli£né, tak jsou popsány jednotliv¥ v samostatných podkapitolách.
2.1.1
Simulace davu
Výzkum v oblasti simulace dav· stále probíhá v n¥kolika výzkumných skupinách. První z nich je CSG [2], která se zabývá p°edev²ím simulací dopravy, coº není pro tuto práci relevantní. Dal²í výzkumnou skupinou je GAMMA [3], jejíº £lenové vytvo°ili ORCA model [10]. Tento model je zaloºený na výpo£tu nekolizních sm¥r· pohybu v lokálním okolí agenta v závislosti na pohybu ostatních agent· a dal²ích vlastností agenta. Tyto skupiny nejsou jediné, kde probíhá výzkum. Mimo prací t¥chto výzkumných skupin bylo publikováno n¥kolik dal²ích metod simulace. První z nich je metoda zaloºená na analýze reálného záznamu chování lidí [13]. Tato metoda spo£ívá ve vytvo°ení databáze situací v jakých se m·ºe agent v pr·b¥hu simulace vyskytnout na základ¥ videa reálného davu. P°i simulaci je pak tato databáze procházena a na základ¥ podobnosti se ur£í výsledná trajektorie agenta. Velice významnou metodou pro simulaci dav· je metoda sociálních sil (Social Forces Model) [11], která pro simulaci vyuºívá vzájemného p·sobení sil mezi jednotlivými agenty, p°ekáºkami £i zdmi. Z tohoto základního principu vychází model HiDAC [14], který p·vodní model roz²i°uje o adaptivnost chování agenta v závislosti na chování okolních agent·. Cílem tohoto je odstran¥ní neºádoucích vlastností p·vodního modelu (nap°íklad do£asné vibrování agenta mezi dv¥ma body) a roz²í°ení moºností simulace. Dal²í metoda spo£ívá v pouºití vzor· chování [17], která d¥lí simulaci na dv¥ úrovn¥. Na spodní úrovni je °e²en samotný lokální pohyb agent· (ch·ze, gesta...) p°edev²ím pomocí p°edp°ipravených animací. Horní vrstva slouºí k interakci s okolím a je °e²ena pomocí stavového automatu. Také je zde popsána my²lenka rozd¥lení aplikace na dv¥ nezávislé vrstvy tak, ºe první se stará o simulaci a druhá o zobrazení.
2.2.
VYMEZENÍ CÍL PRÁCE
2.1.2
5
Jazyk pro záznam pohybu
V¥t²ina prací ohledn¥ jazyk· pro °ízení pohybu je zam¥°ena na programování robot· a ne na záznam pohybu. Dále existuje mnoºství prací, které se zabývají rozpoznáváním, klasi kací a zaznamenáním pohybu na základ¥ reálných vstupních dat (video, obrázky). P°íkladem takové práce je [15]. Tato práce je zam¥°ena na rozpoznávání pohyb· z sekvence obrázk· ve stupních ²edi. V této oblasti prací se pouºívají r·zné struktury pro záznam pohybu, ale ty slouºí p°edev²ím pro popis v obráceném sm¥ru a tak nejsou vhodné. Jedním z existujících projekt· vyuºívajících jazyka pro popis pohybu je projekt EMBR [12], který na základ¥ popisu ve vlastním jazyce vizualizuje gesta postav. V tomto projektu vytvo°ili vlastní skriptovací jazyk a aplikaci pro jeho interpretaci. Samotná aplikace je °e²ena jako vícevrstvá. První vrstva zpracuje skript na jednotlivé pohyby. Druhá slouºí jako plánova£, který spou²tí a ukon£uje provád¥ní pohyb·. T°etí poskládá v²echny pohyby ur£ené pro jednu osobu a vytvo°í výslednou polohu modelu. Poslední je 3D engine, který zobrazuje výsledek.
2.1.3
Zobrazení animace
Moºností pro zobrazení 3D animací je mnoho. Dají se rozd¥lit do zhruba t°í skupin. První z nich je vytvo°it si vlastní aplikaci postavenou nad DirectX nebo OpenGL. K obojímu existuje mnoho tutoriál·. Druhou moºností je vyuºít n¥jaký existující engine. P°íkladem takových je OGRE [6] nebo Havok[4]. Poslední moºností je vyuºití zobrazovacích prvk· aplikace p·vodn¥ ur£ené pro modelování, jako je t°eba Blender [1].
2.2 Vymezení cíl· práce Z vý²e zmín¥ného je patrné, ºe problém· okolo simulace dav· je dost. V¥t²ina z nich byla jiº n¥jakým zp·sobem °e²ena, ale zatím není ve°ejn¥ známé n¥jaké komplexní, obecn¥ funk£ní °e²ení. Stejn¥ tak není moºné se v¥novat v rámci této práce v²em aspekt·m simulace a tak se zam¥°íme jen na n¥které. Základní cíl této práce vyplývá p°ímo ze zadání. Tím je odd¥lení výpo£tu simulace a její zobrazení na dv¥ samostatné £ásti, jenº budou propojeny pomocí jazyka pro záznam pohybu. Proto je moºné i práci rozd¥lit na t°i £ásti. Nejobsáhlej²í £ástí bude samotná simulace chování davu. Druhou £ástí bude návrh jazyka pro záznam pohybu a t°etí £ástí bude vizualizace takto zaznamenaného pohybu. Hlavní £ástí této práce je samotná simulace. Cílem je vytvo°it obecný simula£ní model chování dav· s podporou jednoduchých lokálních událostí ovliv¬ujících chování agent·. Zam¥°ení tohoto modelu bude na mén¥ rozsáhlé simulace, pro které jsou jiº p°ed jejich za£átkem známé v²echny faktory, které
6
KAPITOLA 2.
POPIS PROBLÉMU, SPECIFIKACE CÍLE
tuto simulaci ovliv¬ují. Simulace se bude zam¥°ovat na chování agent· na základ¥ podn¥t· z jejich blízkého okolí. Proto tato práce nebude obsahovat ºádné mechanismy pro plánování pr·chodu scénou na globální úrovni. Také se tato práce zam¥°uje jen na simulaci lidí (ºádné dopravní prost°edky). Dal²í £ástí této práce je jazyk pro záznam pohybu jehoº cílem je uloºení výsledk· simulace pro pozd¥j²í zobrazení jejího pr·b¥hu. Cílem je vytvo°it kompaktní záznam, který bude snadno interpretovatelný pro pot°eby vizualizace. Poslední £ástí práce je zobrazení pr·b¥hu simulace na základ¥ jiº zmín¥ného jazyka. Zde je cílem vytvo°it jednoduchý postup pro zpracování tohoto jazyka a zobrazení 3D scény. Tato práce se ale nezabývá realisti£ností samotných zobrazených model· ani animací.
Kapitola 3 Analýza a návrh °e²ení Ze speci kace cíl· vyplývá pot°eba vytvo°it dv¥ aplikace (simula£ní a vizualiza£ní), jazyk pro záznam pohybu a jazyk pro kon gura£ní soubor simula£ní aplikace. Celkový pr·b¥h od de nice scény po výsledné zobrazení je °et¥zec n¥kolika krok·. Na za£átku °et¥zce je kon gura£ní soubor slouºící pro de nici scény. Tento soubor je vstupním bodem pro simula£ní aplikaci a slouºí k de nici simulace. Simula£ní aplikace provede simulaci a její pr·b¥h uloºí v jazyce pro popis pohybu agent·. Tento jazyk slouºí jako vstup pro vizualiza£ní aplikaci a je tak spojujícím prvkem obou aplikací. Na konci °et¥zce je vizualiza£ní aplikace, která na základ¥ informací v jazyce pro popis pohybu zobrazí výslednou animaci. Celý tento proces zachycuje blokové schéma na obrázku 3.1. Jelikoº je kaºdý z t¥chto blok· samostatný, je jejich návrh popsán v samostatných podkapitolách. Nejprve jsou popsány oba jazyky. Jelikoº jsou na jazyk pro popis pohybu v¥t²í nároky, bude popsán jako první. Následovat bude popis kon gura£ního souboru a poté p°ijde na °adu simula£ní aplikace. Nakonec bude popsán návrh vizualiza£ní aplikace.
3.1 Jazyk pro záznam pohybu Ú£elem jazyka pro záznam pohybu je zaznamenat pohyb agent· ve scén¥, jehoº základem je zm¥na pozice v závislosti na £ase. S tímto v¥domím byly zvaºovány £ty°i moºnosti, jak tento jazyk vytvo°it. První z nich bylo vytvo°ení n¥jakého vlastního skriptovacího jazyka jako u projektu EMBR [12]. Výhodou by bylo vytvo°ení popisu p°ímo na míru pot°ebám. Díky tomu by bylo moºné dosáhnout intuitivní srozumitelnosti a pom¥rn¥ minimalistického zápisu. Jazyk by um¥l jen to, co by bylo pot°eba, a nic navíc. To by vedlo k moºnosti vytvo°it opravdu efektivní parser. Toto by bylo vyváºeno nutností vytvo°ení vlastního parseru pro daný jazyk. Dále pokud by n¥kdo cht¥l vytvo°it animaci p°ímo v tomto jazyce, musel by se nau£it jeho speci ka (zde by bylo moºné syntakticky vycházet z existujících jazyk·, a tak by to aº 7
8
KAPITOLA 3.
ANALÝZA A NÁVRH EENÍ
Obrázek 3.1: Blokové schéma £ástí práce
takový problém nebyl). Zárove¬ v p°ípad¥ jakékoliv budoucí úpravy by bylo nutné zasahovat do parseru a to by mohlo vést ke vzájemné nekompatibilit¥ jednotlivých verzí nebo by se tím ztrácela výhoda parseru ²itého p°ímo na míru konkrétnímu pom¥rn¥ minimalistickému jazyku. Druhou moºností by bylo vyuºít n¥jakého existujícího skriptovacího jazyka. Díky tomu by odpadla nutnost psát vlastní parser a sta£ilo by jen poskytnout vhodné api pro tento jazyk. P°íkladem takového jazyka je Lua [5]. Tento jazyk dokáºe p°istupovat k C++ objekt·m, a tak by nastavení jednotlivých parametr· pro pohyb agent· mohlo probíhat p°ímo ze skriptu. To by zna£n¥ usnadnilo jeho pouºití. P°i tomto pouºití by v²ak bylo pot°eba zajistit, ºe nejsou ze skriptu nastavovány nesmyslné hodnoty. Kv·li tomu by bylo nutné stejn¥ jednotlivé parametry nastavovat p°es p°ipravené funkce, a tak by zde oproti vlastnímu skriptovacímu jazyku nebyla aº tak veliká výhoda. Vzhledem k tomu, ºe je tvo°en £ist¥ popisný jazyk, by bylo vyuºití b¥ºných schopností skriptovacího jazyka jako jsou podmínky nebo cykly minimální, pokud v·bec. Kv·li tomu by tato moºnost nem¥la oproti vlastnímu skriptovacímu jazyku podstatné výhody a tak od ní bylo upu²t¥no hned z po£átku. T°etí moºností bylo vyuºití XML. Hlavní výhodou je, ºe se jedná o standardizovaný zp·sob záznamu dat. Z toho d·vodu pro n¥j existuje mnoºství parser·. Nevýhodou je, ºe pom¥r mezi mnoºstvím uloºené informace a velikostí, kterou zabírá, není moc dobrý. Obzvlá²t¥ tehdy, kdy je zaznamenáváno velké mnoºství samostatných informací jako v tomto p°ípad¥. Pouºití exis-
3.2.
KONFIGURANÍ SOUBOR
9
tujícího XML parseru navíc p°iná²í oproti skriptovacím jazyk·m moºnost jeho vyuºití i v simula£ní aplikaci pro zápis v tomto jazyce. Z moºných XML parser· byl zkoumán TinyXML-2 [8] a Xerces-C++ [9]. Druhý jmenovaný je komplexn¥j²í. Umoº¬uje pracovat s dokumentem v reºimu SAX i DOM. S tím p°ichází i komplikovan¥j²í api. Naproti tomu se TinyXML-2 zam¥°uje na co nejjednodu²²í a nejefektivn¥j²í práci s dokumentem. A to jak na úrovni výkonu samotného parseru tak i jeho pouºití. Pro práci s dokumentem vyuºívá pouze DOM reºim. To s sebou nese snaz²í pouºití. Poslední moºností by bylo vytvo°ení binární formy jazyka. To by umoºnilo generování malých soubor· i pro komplikovan¥j²í scény. Tyto soubory by v²ak bez pouºití dal²ích nástroj· byly pro £lov¥ka ne£itelné a jejich editace by byla zna£n¥ komplikovaná. Navíc zde platí v¥t²ina nevýhod jako u moºnosti vytvo°ení vlastního skriptovacího jazyka. Na základ¥ vý²e zmín¥ných moºností, jejich výhod a nevýhod byl zvolen zápis v XML za pouºití TinyXML-2 parseru. Hlavním d·vodem bylo, ºe toto °e²í jak na£tení souboru na stran¥ vizualiza£ní aplikace, tak i jeho uloºení na stran¥ simula£ní aplikace. Zápis v XML je pro £lov¥ka £itelný, a tak lze snadno kontrolovat a editovat (coº se projeví p°edev²ím p°i hledání chyb). Obsah tohoto jazyka p°ímo vyplývá z jeho ur£ení. Musí zaznamenávat ve²keré informace pot°ebné pro zobrazení pr·b¥hu simulace. Proto mimo samotného pohybu agent· musí uchovávat i informace o scén¥, ve které simulace probíhá. Hlavní £ástí je v²ak záznam pohybu agent·. Tento pohyb se dá zjednodu²it na dv¥ základní informace. První z jich je trajektorie pohybu (místa po kterých se agent pohybuje) a druhým je orientace agenta (jak je v daný moment agent nato£ený). Pro pot°eby záznamu je výsledná trajektorie kaºdého agenta rozd¥lena na díl£í p°ímo£aré pohyby a tyto jsou teprve zaznamenány. Navíc je u kaºdého tohoto díl£ího pohybu zaznamenáno i nato£ení agenta pokud není ve sm¥ru pohybu. Jednotlivé p°ímo£aré pohyby jdou de novat pomocí £ty° parametr·, kterými jsou poloha a £as za£átku pohybu a poloha a £as konce pohybu. Jelikoº jednotlivé pohybu na sebe co se polohy tý£e navazují, tak není nutné zaznamenávat po£átek, protoºe je schodný s koncem minulého. Toto ale u £asu neplatí, protoºe agent m·ºe n¥jakou dobu jen stát na jednom míst¥. Z toho d·vodu bude pohyb de nován pomocí £asu za£átku a konce pohybu, kone£nou polohou a je²t¥ orientací agenta (orientace ur£uje zda agent couvá, d¥lá úkroky a podobn¥).
3.2 Kon gura£ní soubor Podobn¥ jako jazyk pro záznam pohybu agent· je i de nice po£áte£ní kon gurace scény jazykem £ist¥ popisným. Z tohoto d·vodu jsou i pro zp·sob záznamu kon gurace scény zvaºovány obdobné zp·soby zápisu. Jediným v¥t²ím rozdílem je p°edpoklad, ºe tento popis bude tvo°it pln¥ nebo alespo¬ £áste£n¥ p°ímo £lov¥k. Z toho d·vodu nebyla ani uvaºována n¥jaké forma binárního zápisu a tak byly uvaºovány jen skriptovací jazyky (a´ uº vytvo°ený
10
KAPITOLA 3.
ANALÝZA A NÁVRH EENÍ
speci cky pro tento ú£el, tak i existující obecné) a XML. Výhody a nevýhody jednotlivých °e²ení byli jiº podrobn¥ popsány v p°edchozí kapitole 3.1 a i pro toto ur£ení z·stávají platné beze zm¥n. Na základ¥ vý²e zmín¥ného i s p°ihlédnutím k faktu, ºe simulace je zam¥°ena p°edev²ím na mén¥ rozsáhlé scény byl stejn¥ jako u jazyka pro záznam pohybu agent· zvolen zápis v podob¥ XML. Vyuºití schodné technologie pro zápis obou jazyk· p°iná²í je²t¥ jednu drobnou výhodu, kterou je nutnost integrace jen jedné technologie pro záznam a na£tení dat, coº s sebou nese i v¥t²í p°ehlednost. Obsah kon gura£ního souboru vychází p°ímo z pot°eb parametrizace simulace. Musí obsahovat de nici scény, agent·, událostí a také obecné nastavení simulace (bude-li t°eba). Scéna bude de nována pomocí pozic a rozm¥r· zdí a jiných p°ekáºek. Agenti budou de nováni pomocí jejich po£áte£ní pozice, vlastností ovliv¬ujících simulaci a také seznamem cíl· jejich cesty. Jednotlivé události ovliv¬ující simulaci budou de novány pomocí £asu za£átku a konce, druhu události a dal²ích díl£ích parametr· de nujících její vliv na scénu.
3.3 Simula£ní aplikace Návrh simula£ní aplikace m·ºeme rozd¥lit na 3 £ásti. První je výb¥r technologií pro její realizaci (pouºité knihovny). Druhou £ástí je navrºení vnit°ní logiky této aplikace. Poslední a pro tuto práci nejd·leºit¥j²í £ástí je návrh samotného simula£ního modelu, který bude tato aplikace realizovat.
3.3.1
Pouºité technologie
Simula£ní aplikace nemá na pouºití r·zných stávajících prost°edk· p°íli² velké poºadavky. P°ímo v zadání je poºadavek na implementaci v C++ a tak není nutné zvaºovat ºádné jiné moºnosti a sta£í jen vybrat dopl¬ující pro funkcionalitu, kterou neposkytují p°ímo standardní knihovny. Pro pot°eby simulace jako takové nebude pot°eba ni£eho speciálního a tak vyuºití standardních knihoven, ale i p°i simulaci je nutné vykreslovat její pr·b¥h. Zobrazení sta£í pouze schématická, protoºe to není hlavní vizuální výstup této práce a slouºí p°edev²ím pro kontrolu pr·b¥hu simulace. Proto zde nemá cenu uvaºovat o n¥jakých komplexn¥j²ím °e²ením a sta£í sáhnout po n¥jakém základním. Dosta£uje, kdyº bude umoº¬ovat vytvo°it okno, ve kterém aplikace pob¥ºí, a umoºní základní ovládání a jednoduché zobrazení. Jednou z moºností je t°eba GLUT [16], který je ur£ený pro tvorbu OpenGL aplikací. Jedná se o jednoduchý multiplatformní okenní systém umoº¬ující obsluhu událostí jako stisknutí klávesy a podobn¥. Dal²í existující knihovnou, umoº¬ující vytvo°ení okna, obsluhu událostí a jednoduchou práci s gra kou, je SDL [7]. Tato knihovna obsahuje základní moºnosti pro práci s 2D gra kou, nebo je moºné vyuºití OpenGL pro 3D gra ku. Navíc je²t¥ obsahuje dal²í £ásti pro
3.3.
SIMULANÍ APLIKACE
11
práci t°eba se zvukem nebo se sítí. Stejn¥ jako GLUT je multiplatformní. Ani jedna z t¥chto moºností nep°iná²í ºádné zásadní výhody oproti té druhé v kontextu pot°eb této práce. Nakonec dostal p°ednost GLUT, protoºe jeho základní pouºití je o n¥co jednodu²²í.
3.3.2
Návrh aplikace
Tato aplikace má za úkol na£íst z kon gura£ního souboru iniciální stav scény, provést simulaci chování agent· a uloºit její pr·b¥h. P°itom má v²e schématicky zobrazovat. Zde se p°ímo nabízí vyuºití návrhového vzoru Modelview-controller. Tento vzor d¥lí aplikaci do t°í modul· (vrstev). Prvním je model, který reprezentuje data. Druhým je modul view, který obstarává zobrazení dat. T°etím je controller, který se stará o aktualizaci dat. V nejb¥ºn¥j²ím uºití je aktualizace dat vyvolávána uºivatelem, ale zde bude probíhat automaticky v závislosti na £ase. Nejjednodu²²ím z t¥chto modul· je view. Ten pouze vykresluje 3D scénu na základ¥ aktuálních dat. Také je jeho úkolem interakce s uºivatelem (pohyb po scén¥). Model, nebo také datová vrstva, poskytuje ostatním modul·m jistou abstrakci nad daty. T¥mito daty jsou údaje o scén¥ (pozice a vlastnosti zdí, p°ekáºek a agent·) a dosavadní pr·b¥h animace. Tento modul se také bude starat o na£tení dat z kon gura£ního souboru a uloºení pr·b¥hu animace. Jelikoº je p°edpoklad, ºe simulace se bude ú£astnit v¥t²í mnoºství agent·, je zde pot°eba implementovat n¥jakou datovou strukturu, která bude urychlovat výpo£ty jejich vzájemné interakce. Nejjednodu²²í takovou datovou strukturou je uniformní m°íºka. Ta rovnom¥rn¥ rozd¥lí prostor na jednotlivé bu¬ky (ve 2D £tverce nebo obdelníky, ve 3D krychle £i kvádry). Hlavní výhodou této datové struktury je snadné p°i°azení mezi bodem v prostoru a bu¬kou, ke které pat°í. Jelikoº se nám data v pr·b¥hu simulace m¥ní, je tato výhoda opravdu markantní, protoºe umoº¬uje snadnou adaptaci na zm¥nu dat. Nevýhodou je nutnost pamatovat si i prázdné bu¬ky. Dal²í moºností je vyuºití BVH (bounding volume hierarchy). Jedná se o strom obalových t¥les v jehoº listech jsou jednotlivé prvky scény. Vnit°ní uzel je sjednocením obálek v²ech svých potomk·. Ko°enem tohoto stromu je obálka pro celou scénu. Výhodou této struktury je, ºe kaºdý prvek scény pat°í vºdy jednozna£n¥ do jednoho uzlu na dané úrovni hierarchie. To usnad¬uje manipulaci s nimi. Nevýhodou je, ºe se obálky jednotlivých uzl· na stejné úrovni hierarchie mohou p°ekrývat, coº komplikuje vyhledávání. Díky snadné manipulaci s jednotlivými prvky není p°estavba této struktury moc komplikovaná, ale m·ºe zp·sobovat postupné sniºování efektivity, a to aº do stavu, kdy je vhodn¥j²í celou strukturu zahodit a vystav¥t znovu. Poslední z moºností je vyuºití hierarchického d¥lení prostoru, jehoº p°íkladem jsou KD-stromy. Tato struktura na kaºdé úrovni rozd¥lí prostor na dva podprostory pomocí °ezu zarovnaného s n¥kterou z os. Výhodou tohoto p°ístupu je, ºe se vnit°ní uzly nijak nep°ekrývají, coº zjednodu²uje vyhledávání. Nevýhodou je, ºe jeden prvek scény m·ºe pat°it do více uzl·, coº komplikuje manipulaci s ním. P°i práci s dynamickými
12
KAPITOLA 3.
ANALÝZA A NÁVRH EENÍ
daty zde mohou být dva p°ístupy. První je, ºe se aktualizují jen umíst¥ní jednotlivých prvk· v rámci pevné struktury. Toto m·ºe být výhodné v p°ípad¥, ºe p°edem známe chování dat. P°i obecném chování tento p°ístup nep°iná²í ºádné zásadní výhody oproti uniformní m°íºce. Druhou moºností je tuto strukturu adaptivn¥ p°estavovat podle zm¥n. Tento p°ístup zaji²´uje vºdy co moºná nejv¥t²í efektivitu pro vyhledávání, ale pokud je pom¥r mezi vyhledáváním a zm¥nami p°íli² malý (málo vyhledávání mezi jednotlivými zm¥nami stromu), tak p°estavování datové struktury zabere více £asu neº kolik u²et°í p°i vyhledávání. Jelikoº v jednom simula£ním kroku dojde k aktualizaci polohy prakticky v²ech agent·, je schopnost efektivn¥ pracovat s dynamickými daty klí£ová. Po p°ihlédnutí k tomuto faktu vychází nejlépe pouºití uniformní m°íºky. Modul controller slouºící k aktualizaci dat obstarává samotnou simulaci. Simulace je rozd¥lena do jednotlivých krok·. V kaºdém kroku dojde k aktualizaci sou£asného stavu scény, který je následován jejím zobrazením. Toto probíhá ve smy£ce, dokud uºivatel simulaci neukon£í. P°i simulaci p°edpokládáme konstantní £asovou prodlevu mezi jednotlivými jejími kroky. Výhodou toho je konstantní kvalita nezávislá na dostupném výpo£etním výkonu, který se m·ºe v pr·b¥hu simulace m¥nit. Toto také zaji²´uje opakovatelnost simulace. Nevýhodou tohoto p°ístupu je, ºe tento £asový úsek neodpovídá realit¥, a tak pob¥ºí zrychlen¥ nebo zpomalen¥ v závislosti na výkonu po£íta£e, kde je spu²t¥na. Jelikoº zobrazení pr·b¥hu slouºí p°edev²ím pro kontrolu, ºe probíhá správná simulace, a pro její ukon£ení poté, co prob¥hne v²e podstatné, není toto n¥jakou zásadní nevýhodou. Výhodou vyuºití návrhového vzoru Model-view-controller je jistá míra abstrakce. Díky tomu m·ºe být kaºdý modul nahrazen jiným, který bude poskytovat stejnou funkcionalitu. Z toho vyplývá, ºe jednotlivé moduly se nemusejí starat, jak vnit°n¥ fungují ty ostatní. Co do návrhu vnit°ní funkcionality jsou moduly view a controller velice jednoduché. Oproti tomu model, který se stará o data, je mnohem zajímav¥j²í. Tento modul m·ºeme rozd¥lit do n¥kolika základních t°íd. Hlavní z nich je samotná datová vrstva, která se stará o udrºování dat v pam¥ti a poskytuje p°ístup k nim. Pak tu máme samostatnou t°ídu pro kaºdý druh dat (agent, p°ekáºka, ze¤). Jelikoº je pot°eba ukládat dosavadní pr·b¥h pohybu agenta, má kaºdý agent je²t¥ odkaz na t°ídu k tomu ur£enou. Poslední t°ídou je t°ída pro akcelera£ní strukturu, tedy uniformní m°íºku. Sou£ástí tohoto modulu je i balík tinyXML-2, který je vyuºíván pro na£tení kon gura£ního souboru a uloºení souboru obsahujícího popis pr·b¥hu simulace pro vizualiza£ní aplikaci. Celkový class diagram je vid¥t na obrázku 3.2.
3.3.3
Simula£ní model
Úkolem simula£ního modelu je algoritmicky popsat chování agent· na základ¥ jejich vlastností. P°i vyhledávání existujících zdroj· pro tuto práci byly
3.3.
SIMULANÍ APLIKACE
13
Obrázek 3.2: Class diagram simula£ní aplikace
nalezeny 3 r·zná p°ístupy (viz 2.1.1). Nejzajímav¥ji p·sobí metoda zaloºená na analýze videí nato£ených p°i reálných situacích (popsána v [13]). P°i vhodném zvolení zdrojových videí by m¥la poskytovat velice v¥rné výsledky, ale je zde riziko malé variability mezi jedotlivými agenty v podobných situacích a také jsme omezeni pouze na scény, pro které máme odpovídající zdrojové video. Dal²í nevýhodou je nutnost zpracování tohoto videa, kterou je velice komplikované n¥jak automatizovat. Druhý p°ístup spo£ívá v odhadování nekolizních sm¥r· na základ¥ lokálního okolí agenta a jeho dosavadního vývoje (popsán v [10]). Jeho výhodou je moºnost vysoké parametrizace agent· a dobrá vzájená interakce v p°ípad¥ mén¥ hustých dav·. Ale v p°ípad¥ hustých dav· nastává problém s ur£ením vhodného sm¥ru pohybu agenta. T°etí p°ístup reprezentuje vzájemné p·sobení v²ech objekt· scény pomocí sil. Tento p°ístup byl hodn¥ rozvíjen a vzniknul z n¥ho model HiDAC (popsán v [14]. Hlavní výhodou tohoto modelu je jeho jednoduchost a p°ímo£arost. Kaºdý agent m·ºe být snadno parametrizován, coº umoº¬uje rozmanité chování jednotlivých agent·. Nevýhodou jsou p°edev²ím n¥které parazitní vlivy z nihº se nejvýrazn¥ji projevují takzvané vybrace (krátkodobé zm¥ny pozice jen v okruhu jednoho bodu zpravidla jen v jednoum sm¥ru tam a zp¥t). Po zváºení výhod byl pro tuto práci jako výchozí vybrál HiDAC model a to p°edev²ím díky jeho p°ímo£arosti. Tento model je iterativní a tak se simulace zkládá z mnoha krok·, které reprezentují krátký £asový úsek. Kaºdý krok aktualizuje celou scénu na základ¥ výsledku p°edchozího kroku. Mimo samotných agent·, jejichº pohyb se snaºíme ur£it, simulaci ovliv¬ují i statické objekty ve scén¥. Pro zjednodu²ení jsou tyto objekty rozd¥leny do dvou skupin. První z nich jsou zdi, které jsou
14
KAPITOLA 3.
ANALÝZA A NÁVRH EENÍ
reprezentovány kvádrem, jehoº hrany jsou rovnob¥ºné vºdy s n¥jakou osou. Druhým druhem statických objekt· jsou p°ekáºky, které jsou aproximovány válcem, jehoº podstava je rovnob¥ºná s rovinou pohybu agent·. Toto zjednodu²ení zna£n¥ usnad¬uje výpo£ty a zárove¬ nep°iná²í veliké odchylky oproti reálným scénám (ºidle m·ºe být aproximována válcem bez v¥t²í odchylky, p°eváºná v¥t²ina st¥n v budovách mezi sebou svírá pravý úhel, a tak sta£í jen vhodn¥ nato£it celou scénu). Stejn¥ jako p°ekáºky jsou i agenti aproximováni válcem. Dal²í zjednodu²ení vyplývá z toho, ºe lidé neum¥jí létat, ale pohybují se vºdy po n¥jakém podkladu. To nám jejich pohyb zjednodu²uje na 2D problém (p°esto v²echny následující rovnice vyuºívají t°írozm¥rných vektor·). Pohyb agent· probíhá na rovin¥ dané osami x a z . Samotná simulace v kaºdém simula£ním kroku upraví pozici v²ech agent·. Zm¥nu pozice agenta ovliv¬uje jeho aktivní pohyb a síla, kterou na n¥j p·sobí objekty, ke kterým se moc p°iblíºil. Síla reprezentující aktivní pohyb agenta at i v kroku n (Fto i [n]) závisí na sm¥ru k cíli, kam chce dojít (Fi ), p°i£emº wa se snaºí vyhnout v²em p°ekáºkám o (Fob oi ), zdem w (Fwi ) a ostatním agento t·m j (Foa ji ). Zárove¬ nechce m¥nit sv·j sou£asný sm¥r pohybu (Fi [n − 1]). Kaºdou z t¥chto sil vynásobíme váhou (detailn¥ji popsány dále), která reprezentuje aktuální d·leºitost této síly pro agenta. Nakonec tyto síly se£teme dohromady a tak získáme výslednou sílu. to at at Fto i [n] = Fi [n − 1] + Fi [n]wi +
X
wa Fwa wi [n]wi +
w
X
ob Fob oi [n]wi +
o
X
oa Foa ji [n]wi
j6=i
Podstatný je ale jen sm¥r síly, a tak ji normalizujeme.
fito =
Fto i to |Fi |
(3.1)
(3.2)
Následn¥ výslednou pozici pi [n + 1] agenta i vypo£ítáme:
pi [n + 1] + pi [n] + αi vi [n]fito [n] + ri [n]
(3.3)
kde:
• vi [n] odpovídá rychlosti agenta. Tato rychlost je pro v²echny agenty nastavena na 0.1. • ri je výsledná síla °e²ící kolize mezi agentem a objekty v jeho okolí, která je popsána v kapitole 3.3.3.2 • α udává, zda se agent v tomto simula£ním kroku hýbe, nebo ne. (
α=
0 1
Pokud je uplatn¥no pravidlo pro zastavení nebo £ekání v ostatních p°ípadech
Pravidlo pro zastavení p°edchází vibracím agenta a pravidlo pro £ekání umoº¬uje °azení agent· do p°irozených front. Tato pravidla budou vysv¥tlena v kapitolách 3.3.3.3 a 3.3.3.4.
3.3.
15
SIMULANÍ APLIKACE
Obrázek 3.3: Oblast zájmu ºlutého agenta
Jednotlivé váhy ze vzorce 3.1 m¥ní význam jednotlivých sil na výsledný pohyb agenta. Tímto lze snadno dosáhnout rozdílnosti chování. Tohoto je vyuºito pro nastavení dvou vzor· chování. Jeden reprezentuje normální chování a druhý panika°ení. Toho je dosaºeno tak, ºe pro panika°ícího agenta je wat nastaveno výrazn¥ v¥t²í. Také je sníºena váha pro sílu pro p°edcházení kolizí s ostatními agenty woa . To zp·sobí ºe panika°ící agenti do sebe více strkají a snaºí se dostat nejp°ím¥j²í cestou k cíli.
3.3.3.1 Síla p°edcházení kolizí P°i cest¥ k cíli pohybu se musí agent vyhýbat pevným i pohyblivým objekt·m. Ze v²ech dal²ích objekt· ve scén¥ se musí agent vyhnout jen t¥m, které má p°ed sebou, a tudíº mu brání v cest¥. Pro zji²t¥ní, zda je p°ekáºka relevantní, nebo ne, slouºí obdelník zájmu agenta (£árkovaný obdelník na obrázku 3.3. Pro v²echny zdi, p°ekáºky a ostatní agenty zjistíme, zda leºí v oblasti zájmu daného agenta. V p°ípad¥, ºe leºí, tak na základ¥ vektoru mezi agentem a tímto objektem a sm¥ru, kterým se agent pohybuje, zjistíme sílu pro p°edcházení kolizí (avoid force). Zde rozli²ujeme, jestli se jedná o pevný objekt (ze¤ nebo p°ekáºka) nebo pohyblivý (jiný agent). Pro nepohyblivé objekty je výsledná síla závislá jen na vý²e zmín¥ných parametrech. Vzorec 3.4 popisuje získání vektoru síly pro p°edejití kolize mezi agentem a p°ekáºkou. V p°ípad¥ zdí je vzorec obdobný (3.5). Význam jednotlivých prom¥nných je patrný z obrázku 3.3. Pokud ze¤ nebo p°ekáºka neleºí v oblasti zájmu agenta, jsou tyto síly nulové.
Fob oi =
doi × vi × doi |doi × vi × doi |
(3.4)
16
KAPITOLA 3.
ANALÝZA A NÁVRH EENÍ
Obrázek 3.4: Výpo£et sil pro vyhnutí agent·
Fwa wi =
nwi × vi × nwi |nwi × vi × nwi |
(3.5)
Výpo£et síly pro p°edcházení kolizí s pohyblivými objekty (ostatní agenti) mimo vzájemné polohy závisí i na sm¥ru, kterým se pohybují. Navíc oproti statickým p°ekáºkám zde hraje roli i vzdálenost, kterou u statických objekt· nemusíme brát v úvahu, protoºe se nikam nep°esunou a budou p°ekáºet po°ád. V p°ípad¥, ºe se agent ocitne v oblasti zájmu jiného agenta, je vypo£ítán sm¥r te£né síly (3.6) a poté se upraví jeho velikost podle vzdálenosti a orientace pohybu agent·. Podle úhlu mezi sm¥rem pohybu agent· ur£íme, zda jdou ve shodném sm¥ru, nebo proti sob¥. Tento úhel je také pouºit pro simulaci lidského rozhodování, jak se vyhnout ostatním lidem. Toto spo£ívá v tom, ºe kdyº jdou dva lidé proti sob¥, tak v¥t²ina má tendenci uhýbat doprava (ze svého pohledu). Proto v p°ípad¥, ºe jsou vektory pohybu agent· tém¥° rovnob¥ºné, nastavíme te£ný vektor tak, aby sm¥°oval doprava. Na obrázku 3.4 je situace, kdy agent i detekoval ve své oblasti zájmu agenta j a k . Následn¥ se spo£ítají vektory vzdálenosti pro kaºdého z nich (dji a dki ). Agent j je vzdálen¥j²í neº agent k , ale na rozdíl od n¥j sm¥°uje sm¥rem k agentovi i. Proto mu bude p°i°azena vy²²í priorita, a tak bude mít na výsledný sm¥r pohybu agenta i v¥t²í vliv. Sm¥r te£né síly vypo£ítáme dle následujícího vzorce:
tji =
dji × vi × dji |dji × vi × dji |
(3.6)
Význam jednotlivých prom¥nných je patrný z obrázku 3.4. Abychom z tohoto dostali sílu, která ovliv¬uje pohyb agenta, musíme ji je²t¥ vynásobit dv¥ma skalárními váhami d o (3.7) Foa ji = tji wji wji d kde wji je váha pro vzdálenost agent·. Její hodnota roste se sniºující se vzdáleností agent·, protoºe £ím jsou agenti k sob¥ blíºe, tím je pot°eba v¥t²í zm¥na trajektorie, aby se minuli. Tato váha se spo£ítá podle vzorce: d wji =(
(dji − Di ) 2 ) 8
(3.8)
3.3.
17
SIMULANÍ APLIKACE
o reprezentuje význam vzájemné orientace sm¥ru pohybu agent·. Váha wji Slouºí k rozli²ení, zda sm¥°ují ve stejném sm¥ru, nebo proti sob¥.
( o wji
=
1.2 1.4
kdyº vi · vj > 0 v ostatních p°ípadech
(3.9)
Parametr Di reprezentuje maximální vzdálenost mezi agenty, p°i které m·ºe jeden být v oblasti zájmu toho druhého. Tato hodnota je p°ímo závislá na velikosti oblasti zájmu a polom¥ru agenta. Polom¥r agenta a ²í°ka syi oblasti zájmu (krat²í rozm¥r, kolmý na sm¥r pohybu) byly zvoleny jako 2 + εi . Délka q 2
oblasti zájmu sxi je 6. P°esný výpo£et by byl Di = syi + sxi 2 + syi , ale zde není pot°eba, aby byl spo£ítán úpln¥ p°esn¥, a sta£í nám zhruba p°ibliºná hodnota, tak je po£ítáno takto Di = syi + sxi + 0.3. εi je malá konstanta, která je pro kaºdého agenta jiná, £ímº je zaji²t¥na r·znorodost a díky £emuº nedochází k situacím, kdy by se agenti zasekli na jednom míst¥ z d·vodu rovnováhy sil.
3.3.3.2 Síla pro °e²ení kolizí Síla °e²ící kolize (repulsion force) p°ijde ke slovu v p°ípad¥, kdyº se agent dostane do blízkosti jiného objektu natolik, ºe dojde k jejich p°ekrytí. Tuto sílu ri z rovnice 3.3 spo£ítáme podle vzorce:
ri [n] =
X
X R_oa X R_ob R_wa Fji Fwi [n] + Foi [n] +
w
o
(3.10)
j6=i
R_wa R_ob kde Fwi [n] je odpudivá síla od zdi w, Foi [n] je odpudivá síla od p°eR_oa káºky o a Fji [n] je odpudivá síla od jiného agenta j . Tyto síly spo£ítáme takto: R_wa Fwi [n] = nwi (syi − dwi [n]) (3.11)
(pi [n] − po )(syi + ro − doi [n]) R_ob Foi [n] = doi [n]
(3.12)
(pi [n] − pj [n])(syi + rj − dji [n]) R_oa Fji [n] = dji
(3.13)
kde pi je pozice agenta i, pj je pozice agenta j , po je pozice p°ekáºky o. nwi je jednotkový kolmý vektor od zdi k agentovi i a dwi je vzdálenost st°edu agenta i od zdi w. syi je polom¥r agenta i, ro polom¥r p°ekáºky o, rj je základní polom¥r agenta j (rj = 2 + εmin = 1.95). doi je vzdálenost st°edu p°ekáºky o od st°edu agenta i. dji je vzdálenost st°ed· agent· j a i.
3.3.3.3 e²ení vibrací V pr·b¥hu simulací, kdy se snaºí jedním úzkým místem projít v¥t²í mnoºství agent·, se £asto stává, ºe n¥kte°í agenti vibrují mezi dv¥ma pozicemi.
18
KAPITOLA 3.
ANALÝZA A NÁVRH EENÍ
To je z d·vodu, ºe i po uplatn¥ní v²ech sil pro p°edcházení kolizím dojde k posunu sm¥rem k n¥jakému agentovi a následn¥ je zase odsunut zpátky. Toto chování je nep°irozené, a tak je nutné jej eliminovat. K tomuto slouºí pravidlo pro zastavení agenta (stopping rules). V p°ípad¥, ºe opakovan¥ (víc neº 3x) je sm¥r sou£tu v²ech odpudivých sil mezi agenty opa£ný v·£i sm¥ru pohybu agenta a sou£asn¥ agent nepanika°í, tak se toto pravidlo aktivuje. R_oa R_oa kdyº ((vi · Fi ) < −0.26) ∧ (|Fi > 0.4|) ∧ (¬panic) then aktivuj pravidlo zastavení
Po aplikování pravidla zastavení je nastavena α z rovnice 3.3 na 0, coº znamená, ºe pozice agenta bude m¥n¥na jen na základ¥ výsledné síly pro °e²ení kolizí. Toto pravidlo se vºdy aplikuje na 3 aº 7 následujících simula£ních krok·. Pouºití tohoto pravidla je pro n¥které druhy simulací nevhodné (p°edev²ím pro °ídké davy ve scén¥, kde není ºádné úzké místo, kterým by se najednou snaºilo projít více agent·), a proto lze jeho uplatn¥ní zakázat (viz 4.1).
3.3.3.4 azení do p°irozených front V b¥ºné (nepanika°ící) situaci lidé respektují po°adí a £ekají, neº odejde £lov¥k p°ed nimi. Tím vznikají p°irozené fronty. Pro dosaºení podobného efektu je vyuºito pravidlo pro £ekání. Toto pravidlo je podobné pravidlu pro zastavení. Kaºdý agent má p°ed sebou detek£ní oblast pro £ekání (te£kovaná kruºnice na obrázku 3.5 ). Pokud je n¥jaký jiný agent jdoucí stejným sm¥rem v této detek£ní oblasti, aktivuje se pravidlo pro £ekání. P°i tom se spustí £asova£ nastavený na n¥jakou náhodnou hodnotu (5 aº 44 simula£ních krok·). Toto pravidlo p°estane platit, kdyº uº v detek£ní oblasti není ºádný agent jdoucí stejným sm¥rem, nebo kdyº £íta£ dosáhne 0. Tento £íta£ slouºí pouze k zamezení uváznutí simulace v mrtvém bod¥. kdyº ( agent j je v detek£ní zón¥ agenta i) ∧((vi · vj ) > 0.996) ∧ (¬panic) then aktivuj pravidlo £ekání Stejn¥ jako u pravidla zastavení je po aktivování pravidla £ekání nastavena α z rovnice 3.3 na 0.
3.3.3.5 Roz²í°ení o události Dosud popsaný model p°edpokládal pr·b¥h simulace, kterou v jejím pr·b¥hu jiº neovliv¬ují ºádné dal²í vlivy. Tato práce má v²ak za cíl vytvo°it model podporující jednoduché události ovliv¬ující chování agent·. R·zných myslitelných událostí je nep°eberné mnoºství, ale v¥t²ina z nich se dá zjednodu²it pomocí událostí dvou druh·. První z nich je negativní, která na agenty p·sobí odpodiv¥ a druhá je pozitivní, která agenty p°itahuje. Pomocí
3.3.
SIMULANÍ APLIKACE
19
Obrázek 3.5: Detek£ní oblast pro pravidlo £ekání
t¥chto dvou princip· lze de novat velké mnoºství událostí a v p°ípad¥ jejich kombinování p°ibudou je²t¥ dal²í (nap°íklad rozbití výlohy obchodu lze simulovat sloºením krátké negativní události ihned následované dlouhotrvající pozitivní). Oba druhy událostí mají n¥které spole£né atributy. T¥mito atributy jsou místo, kde k dané události do²lo a následn¥ rádius který ovliv¬uje. Samoz°ejm¥ je de nuje i £as jejich za£átku a p°ípadn¥ i konce. Negativní událost je pro realizaci jednoduºsí. Kdyº se po dobu trvání takové události agent ocitne v oblasi p·sobení této události, tak se mu nejprve za£ne m¥°it krátký £asový úsek reprezentující reak£ní dobu agenta. Pokud se i po jeho uplynutí agent stále nachází v oblasti p·sobení události, tak se mu zm¥ní vzor chování na paniku a do£asn¥ zm¥ní sm¥r, kterým se hodlá pohybovat sm¥rem od místa této události. P°esn¥ to popisune následující vzorec pi − pe (3.14) Fat i = |pi − pe | kde:
• Fat i je výsledná síla ur£ující sm¥r, kterým se chce agent v tomto simula£ním kroku pohybovat • pi je aktuální poloha agenta • pe je st°edová pozice místa negativní události Doba na kterou bude mít agent zm¥n¥ný vzor chování a sm¥r, kterým se snaºí pohybovat je nahodn¥ ur£ena z £asového intervalu, který je atributem této události. Pozitivní událost na agenty p·sobí tak, ºe je p°im¥je dojít se podívat k místu události, zde n¥jakou dobu stát a pozorovat a násldn¥ pokra£ovat za p·vodním cílem své cesty. Stejn¥ jako negativní událost ovliv¬uje pouze agenty ve své oblasti p·sobnosti. Pro kaºdého takového agenta se nejprve ur£í zda na n¥j bude tato událost p·sobit nebo jestli ji bude trvale ignorovat. Pravd¥podobnost tohoto je ur£ena na základ¥ parametr· události a vlastností
20
KAPITOLA 3.
agenta.
ANALÝZA A NÁVRH EENÍ
then kdyº (Rand(0..100) · pignore ) < pignore i e ignoruj událost e
kde:
• Rand(0..100) je náhodné £íslo od 0 do 100 • pignore je citlivost agenta na události i je základní proavd¥podobnost, ºe bude tato událost ignorována • pignore e Pokud agent tuto událost ignoruje, tak se chová jako by ve scén¥ v·bec nebyla. V opa£ném p°ípad¥ se agent ozna£í, ºe je pod vlivem události a upraví se jeho sm¥r zamý²leného pohybu sm¥rem k události podle následujícího vzorce. pe − pi Fat (3.15) i = |pe − pi | kde:
• Fat i je výsledná síla ur£ující sm¥r, kterým se chce agent v tomto simula£ním kroku pohybovat • pi je aktuální poloha agenta • pe je st°edová pozice místa negativní události V p°ípad¥, ºe se takovýto agent dostane do p°ímé blízkosti místa události (tato vzdálenost je atributem události), tak se mu na dobu v rozmezí intervalu ur£eném v de nici události aktivuje pravidlo zastavení a ozna£í se jako £ekající na tuto udáslos. Po vypr²ení tohoto £asu se p·sobící událost p°idá mezi ignorované, aby ho uº nemohla znovu ovlivnit, agent se ozna£í, ºe není pod vlivem a ºe ne£eká na ºádnou událost a obnoví se mu jeho p·vodní cíl cesty. Kdyº se jeden agent sm¥°ující k události p°iblíºí k druhému agentu, který je ozna£en jako £ekající na tuto událost, tak je první také ozna£en jako £ekající na tuto událost a za£ne se mu m¥°it £as. Pokud tento £as p°ekro£í limit po který je agent ochotný £ekat v davu (vlastnost agenta z de nice) neº se dostane k místu p·sobení události, tak se tato událost p°idá pro daného agenta mezi ignorované, agent se ozna£í, ºe není pod vlivem ani ºe ne£eká na ºádnou událost a obnoví se mu jeho p·vodní cíl cesty.
3.4 Vizualiza£ní aplikace 3.4.1
Pouºité technologie
Ze t°í základních sm¥r·, jak dále pokra£ovat, byla hned z po£átku zavrºena moºnost vytvo°it celou aplikaci od základu jen na základních gra ckých knihovnách, jako jsou DirectX nebo OpenGL. Toto °e²ení by m¥lo
3.4.
VIZUALIZANÍ APLIKACE
21
výhodu v naprosté kontrole nad chováním aplikace a moºností ji pln¥ ovliv¬ovat. Také by se samotnou aplikací bylo ²í°eno jen nezbytné minimum, coº by m¥lo kladný vliv na mnoºství místa zabíraného na disku. Také by bylo moºné dosáhnout v¥t²í efektivity, protoºe by program byl p°esn¥ na míru pot°ebám a neztrácel by se výkon na obecných voláních funkcí, které jsou ve výsledku nepot°ebné. Nevýhodou by byla pracnost. Navíc by byla tvo°ena spousta funkcionality, která uº v n¥jaké podob¥ existuje a je dostupná voln¥ k uºití. Tato negativa byla rozhodující, pro£ se touto cestou nevydat. Nehled¥ na to, ºe n¥která pozitiva jsou jen teoretická, protoºe se dá o£ekávat, ºe jiº existující °e²ení, které je pouºíváno uº n¥kolik let a stále se vyvíjí, bude dob°e optimalizované. Druhou variantou bylo vyuºít n¥jaký z program· ur£ených primárn¥ pro modelování. V tomto sm¥ru byl zkoumán hlavn¥ Blender a p°edev²ím £ást Blender game. Vyuºití tohoto konceptu by umoº¬ovalo vytvo°ení prost°edí pro simulaci p°ímo v tomto editoru a jen jej exportovat v podob¥ kon gura£ního souboru pro simula£ní aplikaci. Výhodou by byla veliká variabilita scén a moºnost snadno ovlivnit výsledný gra cký dojem. Aby vytvo°ení scény nebylo moc komplikované, bylo by pot°eba vytvo°it základní stavební kameny (uni kovaná ze¤, p°ekáºka, agent), které by se jen poskládaly do výsledné scény. Ale stále by z·stala moºnost tyto kameny nevyuºít a místo toho si vytvo°it vlastní. Z nich by byly samoz°ejm¥ kladeny nejv¥t²í nároky na agenty, protoºe ti musejí být animovaní, takºe by museli vºdy obsahovat p°edem danou kostru, na kterou by se animace uplat¬ovala. Nevýhodou tohoto sm¥ru je, ºe nau£it se ovládat takovýto editor a dále pracovat se scénou pomocí skriptovacího api není nic lehkého i p°es zna£né mnoºství návod·. Toto by bylo £asov¥ p°íli² náro£né, a tak i p°es mnoho výhod tohoto konceptu od n¥j bylo upu²t¥no. Poslední variantou bylo pouºití n¥kterého z voln¥ dostupných 3D engin·. Základním poºadavkem bylo, aby umoº¬oval snadné nahrávání model·, p°ehrávání skeletálních animací a moºnost jejich ovliv¬ování. Prvním ze zkoumaných bylo OGRE. Jedná se o komplexní 3D engine s orientací na scénu. Poskytuje nadstavbu nad základním 3D api. Podporuje DirectX i OpenGL. Bez problém· spl¬uje ve²keré poºadavky, které jsou na n¥j v rámci této práce kladeny. Hlavní výhodou je velké mnoºství tutoriál·, které snadno seznámí s pouºitím tohoto enginu. Základní api pro ovládání je velice jednoduché, ale podporuje i pokro£ilej²í funkce. Také je zde p°ítomno mnoºství demo aplikací, které ukazují, co lze vytvo°it a jsou sou£ástí základního balíku ve form¥ zdrojových kód·. Pro pouºití model· pouºívá vlastní formát, ale existují pluginy do v¥t²iny b¥ºných modelovacích nástroj· na export do tohoto formátu. Dal²í výhodou je multiplatformnost. OGRE je ²í°eno jako open source pod MIT (p°esn¥ji X11) licencí. Z dal²ích engin· byl zkoumán Havok. Tento engine je ve vlastnictví Intelu a je také aktivn¥ vyvíjen. Stejn¥ jako pro OGRE i pro Havok existuje spousta demo aplikací a návod·. Na rozdíl od OGRE není ²í°en jako open source a v n¥kterých p°ípadech je jeho vyuºití limitováno. Také podporuje
22
KAPITOLA 3.
ANALÝZA A NÁVRH EENÍ
jen Windows platformu. I kdyº tyto nevýhody nejsou pro tuto práci nijak zvlá²´ limitující, tak oproti OGRE nep°iná²í ºádné podstatné výhody. Na základ¥ tohoto se ukázalo OGRE jako nevhodn¥j²í volba.
3.4.2
Návrh aplikace
Tato aplikace je co do návrhu vnit°ní struktury zna£n¥ jednodu²²í neº simula£ní aplikace. To vyplývá z toho, ºe jejím cílem je jen p°evést záznam v jazyce pro popis pohybu agent· ve scén¥ a zobrazit výslednou animaci. K tomu v²emu bude vyuºívat jiº existující moºnosti OGRE. Funkcionalitu aplikace tak lze rozd¥lit do dvou vrstev. První z nich je p°e£tení jazyka a jeho zpracování do podoby pot°ebné pro kontrolu pr·b¥hu výsledného zobrazení. Druhou je zobrazovací £ást, která bude na základ¥ na£tených dat aktualizovat práv¥ zobrazenou scénu v závislosti na £ase.
Kapitola 4 Realizace Jak bylo zmín¥no jiº v návrhu, skládá se celá práce ze £ty° blok· (znázorn¥no na obrázku 3.1). Kaºdý z t¥chto blok· je samostatným prvkem. Tyto prvky na sebe navazují, a tak se vzájemn¥ ovliv¬ují. Nejprve bude popsána struktura kon gura£ního souboru, který je na za£átku tohoto °et¥zce. Poté bude popsáno fungování simula£ní aplikace a zp·sob zaznamenání pohybu agent·. Na to následuje popis jazyka pro záznam pohybu agent·. Nakonec bude popsána vizualiza£ní aplikace.
4.1 Kon gura£ní soubor Kon gura£ní soubor slouºí pouze k po£áte£nímu nastavení scény a vlastností agent·. Jak bylo zmín¥no v návrhu, tak jde o XML soubor. Také v²e co obsahuje vychází z p°ímo z poºadavk· navrºeného modelu. Ve²keré de nice jsou rozd¥leny do skupin dle druhu de nice. První skupinou jsou globální nastavení simulace. Zde je moºnost nastavit po£áte£ní hodnotu generátoru pseudonáhodných £ísel (element randomSet obsahující tuto hodnotu). To je z d·vodu, ºe simulace by m¥la být opakovatelná. Tento element je nepovinný. V p°ípad¥, ºe nebude p°ítomen, je po£áte£ní hodnota generátoru náhodných £ísel nastavena na p°edem neodhadnutelnou hodnotu (a dal²í b¥h dle shodného kon gura£ního souboru m·ºe probíhat odli²n¥). Dal²í globální vlastností simulace je povolení aplikování pravidla pro zastavení. K tomu slouºí element stopRule, jenº o£ekává 0 pro zakázání, 1 pro povolení. Tento element je také nepovinný a v p°ípad¥ jeho absence je pravidlo pro zastavení povoleno. Druhou skupinou je po£áte£ní nastavení statických prvk· scény. Nejprve jsou popsány zdi. Jelikoº ve scén¥ nemusí být ºádná ze¤, je celá tato skupina nepovinná. Na ukázce 4.1 je vzorové de nování jedné zdi. Element walls je souhrnný element pro tuto skupinu. Jeho obsahem musí být jeden nebo 23
24
KAPITOLA 4.
REALIZACE
více element· wall, které de nují jednotlivé zdi. Samotná ze¤ je de nována pomocí sou°adnic dvou bod· v prostoru (vrcholy na t¥lesové úhlop°í£ce). Pro zápis jejich sou°adnic slouºí elementy x1, y1, z1, x2, y2, z2. Pro simulaci jsou podstatné jen hodnoty sou°adnic x a z. Sou°adnice v ose y ur£ují vý²ku zdi a projeví se pouze ve výsledné vizualizaci.
<w a l l s >
<w a l l >
<x1>−30
0 −31 <x2>30
5 −30
<w a l l s > ukázka 4.1: de nice zdí
Dále jsou zde nastaveny parametry p°ekáºek. P°ekáºky stejn¥ jako zdi nemusí ve scén¥ být, a tak je i tato skupina nepovinná. P°íklad de nování p°ekáºky je na ukázce 4.2. obstacles je souhrnným elementem pro v²echny p°ekáºky. Samotnou p°ekáºku reprezentuje element obstacle. Kaºdá p°ekáºka je de nována pozicí st°edu (elementy x a z) a polom¥rem (element r). Pozice v ose y není pot°eba, protoºe simulace probíhá na rovin¥ dané osami x a z a tudíº vý²ka p°ekáºky není podstatná.
<x>4 9 3 ukázka 4.2: de nice p°ekáºek T°etí skupinou kon gura£ních dat je de nice agent·. Ta jako jediná musí být vºdy p°ítomna. To je z d·vodu, ºe pokud by ve scén¥ nebyl ºádný agent, nebylo by co simulovat. Na ukázce 4.3 je zobrazeno, jak by vypadala de nice s jedním agentem. Element agent zaznamenává v²echny kon gura£ní údaje o agentovi. Jeho poloha je ur£ena elementem pos a po£áte£ní nato£ení elementem ori. Oba tyto elementy obsahují (povinn¥) elementy x a z, jejichº
4.1.
25
KONFIGURANÍ SOUBOR
hodnota reprezentuje pozici / orientaci. Tyto elementy jsou povinné. Velikost agenta lze ovlivnit pouºitím nepovinného elementu Dsize. Obsah tohoto elementu odpovídá hodnot¥ ε. Pokud tento element není pouºit, je tato hodnota nastavená náhodn¥ v intervalu ±0.05. Proto je doporu£eno hodnotu tohoto elementu nastavovat také v tomto intervalu. Dále je moºné nastavit po£áte£ní druh chování agenta. K tomu slouºí element behavior. Jeho hodnoty mohou být GO nebo PANIC. Dal²í vlastností agenta je koe cient, kterým je násobena ²ance, ºe ignoruje pozitivní událost. Tento koe cient je obsahem nepovinného elementu ignoreKoeficient. Pokud není de nován je tento koe cient nastaven náhodn¥ v rozmezí od 0.9 do 1.1. Poslední element targets je povinný a obsahuje seznam bod·, kterými má agent projít (cíle pohybu). Kaºdý bod je dán elementem target, který obsahuje sou°adnice tohoto bodu (elementy x a z) a druhou mocninu vzdálenosti, na kterou se tento bod povaºuje za dosaºený (element dist2ToPass). Tento element je nepovinný a v p°ípad¥ jeho absence je tato hodnota nastavena na 0.8. Jednotlivé cíle pohybu bude agent dosahovat v po°adí, jak jsou zde uvedeny.
<pos>
<x>0 30 <x>0 −1
0.02 GO <x>0 −60 0.8 ukázka 4.3: de nice agent· Poslední skupinou pro kon guraci je popis událostí. Ty jsou popsány v elementu events a jelikoº ve scén¥ nemusí být ºádný de nován je tento element nepovinný. Jednotlivé události jsou de novány pomocí elementu eventGroup,
26
KAPITOLA 4.
REALIZACE
který obsahuje jednu nebo více díl£ích událostí. Pro v²echny tyto díl£í události jsou nejprve de novány jejich spole£né atributy, kterými jsou pozice (element pos obsahující elementy x a z), oblast p·sobení de novaná polom¥rem (element seeDist) a plocha, kterou tato událost p°ímo zabírá (element size). V²echny tyto elementy jsou povinné. Samotné díl£í události jsou de nované elementem event (m·ºe být jednou nebo vícekrát), který obsahuje samostatné nastavení pro tyto díl£í události. T¥mi jsou druh události (element type - 0 pro negativní, 1 pro pozitivní), doba za£átku p·sobení události (element start), doba trvání události (element duration), £asový interval po jakou bude ovliv¬ovat daného agenta (elementy minInterestTime a maxInterestTime). Význam tohoto intervalu je pro oba druhy událostí odli²ný a je popsán v návrhu 3.3.3.5. Pro pozitivní událost je zde pot°eba je²t¥ de novat vzdálenost ve které se agenti zastaví (de nováno elementem lookDist) a základní ²anci, ºe tato událost bude ignorována (element ignoreChance - ur£uje ²anci v procentech). Na ukázce 4.4 je vid¥t vzorová de nice sloºené události.
<e v e n t s > <eventGroup> <pos>
<x>20 1
<s e e D i s t >60 <s i z e >3.5 <event> 0 <s t a r t >9 1.5 <m inIn ter estT ime >1.866 <maxInterestTime >3 <event> 1 <s t a r t >10.5 100 6 15 <m inIn ter estT ime >6 <maxInterestTime >10 ukázka 4.4: de nice událostí
4.2.
SIMULANÍ APLIKACE
27
Kompletní seznam v²ech element· a jejich popis shrnuje tabulka v p°íloze B.1.
4.2 Simula£ní aplikace Simula£ní aplikace nejprve na£te vý²e zmín¥ný kon gura£ní soubor a podle n¥ho vytvo°í prost°edí simulace. Samotná simulace probíhá p°esn¥ podle modelu popsaného v návrhu. Tato simulace probíhá cyklicky dokud není simulace ukon£ena uºivatelem. Pr·b¥h jednoho kroku simulace je vid¥t na ukázce 4.5 obsahující pseudokód tohoto kroku. Po ukon£ení simulace je záznam pohybu a stejn¥ tak i popis scény uloºen. Z d·vodu naprosté opakovatelnosti simulace a také pro udrºení shodné kvality bez závislosti na dostupném výpo£etním výkonu simulace p°edpokládá b¥h t°iceti simula£ních krok· na jednu vte°inu reálného £asu.
Pro vsechny agenty ( a ) { zpracujUdalostiOvlivnujici (a ); vypoctiSilyVuciZdemVOkoli ( a ) ; vypoctiSilyVuciPrekazkamVOkoli ( a ) ; vypoctiSilyVuciAgentuVOkoli ( a ) ; uplatniPravidlaZastaveniACekaniPro ( a ) ; upravVysledouPolohu ( a ) ; aktualizujZaznamPohybu ( a ) ; } ukázka 4.5: simula£ní krok Ze v²ech £ástí pr·b¥hu simulace jediný záznam nevychází p°ímo z modelu. P°i n¥m je pot°eba °e²it n¥kolik díl£ích problém·. Prvním z nich je samotné rozd¥lení pohybu na jednotlivé p°ímo£aré £ásti, které se budou zaznamenávat. Dále je pot°eba je²t¥ ur£it orientaci agenta pro kaºdou £ást pohybu. Nakonec je je²t¥ pot°eba provést ltrování p°íli² £asté zm¥ny sm¥ru pohybu, coº je zp·sobeno parazitními "vibracemi". Jelikoº je celý proces simulace iterativní, tak i záznam pohybu agent· funguje iterativn¥. Samotné zaznamenávání probíhá pomocí fronty, do které se zaznamenávají kompletní £ásti p°ímo£arého pohybu. K zaznamenání jedné £ásti slouºí struktura obsahující po£áte£ní a koncový £as, po£áte£ní a koncovou pozici a sm¥r pohybu. V kaºdém kroku se zjistí úhel, který svírá vektor zm¥ny polohy od posledního kroku s vektorem orientace aktuáln¥ zaznamenávaného pohybu. Pokud je odchylka men²í neº 10◦ , povaºuje se pohyb za p°ímo£arý a jen se aktualizuje koncový £as a pozice aktuálního pohybu (ale neaktualizuje se sm¥r). V opa£ném p°ípad¥ je aktuální pohyb povaºován
28
KAPITOLA 4.
REALIZACE
Obrázek 4.1: P°evod pozic na p°ímo£arý pohyb a orientaci
za ukon£ený. Následn¥ je jako aktuální pohyb vytvo°en pohyb nový, který má po£áte£ní pozici a £as shodnou s koncovou pozicí a £asem ukon£eného pohybu. Kone£ná pozice a £as je nastavena sou£asnými hodnotami a sm¥r pohybu odpovídá zm¥n¥ pozice za poslední simula£ní krok. V p°ípad¥, ºe aktuáln¥ ukon£ený pohyb trval pouze jeden simula£ní krok se je²t¥ zkontroluje odchylka sm¥ru minulého a nov¥ vytvá°eného pohybu. Pokud je tato odchylka men²í neº 10◦ , nastaví se orientace uzavíraného pohybu stejn¥ jako je orientace minulého pohybu (názorn¥ patrné z obrázku 4.1, kde jsou v horní £ásti jednotlivé pozice a ve spodní jejich p°evedení na pohyb a ²ipkou znázorn¥na orientace). Toto vede k zna£né redukci p°íli²ného otá£ení agent· v pr·b¥hu pohybu. Následn¥ je práv¥ uzav°ený pohyb vloºen do fronty. Celý tento proces je patrný z pseudokódu ukázky 4.6
4.2.
SIMULANÍ APLIKACE
29
Queue moveParts ; MovePart a k t u a l P a r t ; aktualizujZaznamPohybu ( Agent A) { i f ( u h e l (A. pos −a k t u a l P a r t . l a s t P o s , a k t u a l P a r t . o r i ) < 10◦ ) { a k t u a l P a r t . l a s t P o s = A. pos ; a k t u a l P a r t . l a s t T i m e = getTime ( ) ; }else { i f ( ( a k t u a l −>l a s t T i m e − a k t u a l −>s t a r t T i m e ) == 1 && u h e l ( moveParts . l a s t ( ) . o r i , a k t u a l . o r i ) < 10◦ ) { a k t u a l −>o r i e n t a c e = moveParts . l a s t ( ) . o r i ; } moveParts . push ( a k t u a l ) ; a k t u a l = new MovePart ; a k t u a l . l a s t P o s = A. pos ; a k t u a l . l a s t T i m e = getTime ( ) ; a k t u a l . s t a r t P o s = moveParts . l a s t ( ) . l a s t P o s ; a k t u a l . s t a r t T i m e = moveParts . l a s t ( ) . l a s t T i m e ; a k t u a l . o r i = a k t u a l . l a s t P o s − a k t u a l −>s t a r t P o s ; } } ukázka 4.6: Záznam pohybu Druhou £ástí záznamu je jiº zmín¥né ltrování orientace a samotný záznam. Tato £ást ltrování je nutná, protoºe nastavování orientace p°i d¥lení pohybu ne p°ímo£aré £ásti od ltruje jen p°íli²né zm¥ny orientace p°i pohybu zhruba jedním sm¥rem (dochází k nim p°edev²ím v p°ípad¥, ºe jdou dva agenti zasebou nebo p°i obcházení p°ekáºek). Pokud v²ak dojde k parazitním vibracím, tak agent m¥ní polohu v krátkých intervale p°edev²ím v protich·dných sm¥rech okolo jednoho místa. V takovém p°ípad¥ je nutné, aby orientace neodpovídala sm¥ru podle zm¥ny polohy, ale byla nastavená stále jedním sm¥rem. Proto p°ed zápisem do xml projdeme v²echny záznamy £ástí pohybu a pro v²echny krátké £ásti (vzdáleností po£áte£ního a koncového bodu nebo dobou mezi po£átkem a koncem této £ásti pohybu) provedeme kontrolu, jak je vzdálen konec následujícího pohybu od za£átku aktuáln¥ zkoumaného (p°ípadn¥ zapamatovaného bodu, pokud jich je krátkých n¥kolik v °ad¥). Pokud je tato vzdálenost malá, tak nastavíme orientaci aktuální £ásti jako má orientaci p°edchozí záznam (a zapamatujeme si bod za£átku). V opa£ném p°ípad¥ nastavíme orientaci schodnou s orientací následující £ásti pohybu. P°ehledn¥ je to vid¥t v ukázce pseudokódu 4.7.
30
KAPITOLA 4.
REALIZACE
pro vsechny MovePart m z moveParts { i f (m. l e n g t h < 1 | | m. d u r a t i o n < 0 . 3 s ) { i f ( exist ( pivot )) { i f ( l e n g t h ( p i v o t , moveParts . next (m) . l a s t P o s ) < max ( 1 . 5 , m. l e n g t h · 2 ) ) { m. o r i = moveParts . prew (m) . o r i ; }else { m. o r i = moveParts . next (m) . o r i ; delete pivot } }else { i f ( l e n g t h (m. s t a r t P o s , moveParts . next (m) . l a s t P o s < max ( 1 , m. l e n g t h · 2 ) { m. o r i = moveParts . prew (m) . o r i ; p i v o t = m. s t a r t P o s ; }else { m. o r i = moveParts . next (m) . o r i ; delete pivot } } }else { delete pivot ; } } ukázka 4.7: Filtrování pohybu Samotný zápis je jen uloºením takto upravených £ástí pohybu v jazyce pro zápis pohybu.
4.3 Jazyk pro záznam pohybu agent· Jazyk obsahuje dv¥ £ásti. První popisuje po£áte£ní stav scény a druhá je samotný záznam pohyb· agent·. Nastavení pozice zdí a p°ekáºek je zde
4.3.
JAZYK PRO ZÁZNAM POHYBU AGENT
31
shodné jako u kon gura£ního souboru (ukázky 4.1 a 4.2). Pro nastavení po£áte£ní polohy agent· slouºí element agents, který obsahuje nastavení v²ech agent· (p°íklad je na ukázce 4.8). Kaºdý element agent reprezentuje jednoho agenta. Tento element má atribut name, který reprezentuje jméno a musí být unikátní. Slouºí k p°i°azení jednotlivých pohyb· k agent·m. Poloha agenta je dána elementy x a z. Poslední element r slouºí k nastavení po£áte£ního nato£ení (v radiánech). Poslední po£áte£ních de nic scény je de nice událostí. V²echny události jsou de novány v elementu events pomocí element· event. Kaºdá událost má de novanou svou st°edovou polohu elementy x a z a £as po£átku a konce pomocí element· start a end. Jedna takto popsaná událost odpovídá událostem spadající do jedné skupiny událostí de nované v kon gura£ním souboru. P°íklad de nic událostí je v ukázce 4.9.
<x >0.00000 10.00000 0 <x >0.00000 − 10.00000 3.14159 ukázka 4.8: de nice pozice agent· na za£átku animace
<e v e n t s > <event> <x >0.00000 − 28.00000 <s t a r t >0.00000 <end >0.00000 ukázka 4.9: de nice události Pohyb agent· je zaznamenán v elementu mov. Ukázka 4.10 je p°íkladem, jak m·ºe taková de nice vypadat. Kaºdá £ást pohybu je reprezentována elementem m. V tomto elementu je de nována cílová pozice tohoto pohybu (elementy x a z), po£áte£ní a koncový £as pohybu (elementy b a e) ve vte°inách.
32
KAPITOLA 4.
REALIZACE
Nakonec zde m·ºe být nepovinné nastavení orientace agenta (elementy ox a oz). Pokud není nastaveno nato£ení agenta, tak je nato£en sm¥rem k cíli pohybu. Atribut a elementu m je referencí na jméno agenta, jehoº pohyb je takto zaznamenáván. Kompletní seznam v²ech element· a atribut· v£etn¥ jejich popisu je shrnut v tabulce v p°íloze B.2.
<mov> <m a="0"> <x> − 23.82436 2.83693 <s >0.00000 <e >7.83333 − 0.07257 0.99736 <m a="1"> <x> − 18.69974 − 4.04178 <s >0.00000 <e >6.36667 ukázka 4.10: záznam pohybu agent·
4.4 Vizualiza£ní aplikace Tato aplikace slouºí k výslednému 3D zobrazení pohybu agent·. Staví na OGRE enginu. Mimo vyuºití vlastností enginu je²t¥ vyuºívá t°ídu BaseApplication z tutoriál·. Tato t°ída se stará o inicializaci okna a správu událostí (pohyb ve scén¥, ukon£ení programu). Proto je rodi£em hlavní t°ídy této aplikace. Po startu aplikace je na£ten soubor obsahující záznam pohybu agent·. Na jeho základ¥ je vytvo°ena a zobrazena scéna. Také jsou p°ipraveny objekty obsluhující pohyb agent·. Na£tení a práce s p°ekáºkami a zdmi je velice jednoduché, protoºe jsou po celou dobu scény nem¥nné a tak sta£í jen vytvo°it objekt scény a p°idat ho do grafu scény a o zbytek se uº postará engine. V p°ípad¥ p°ekáºek se jedná o válcovitý model. Zdi jsou vytvo°eny pomocí p¥ti navzájem kolmých otexturovaných ploch (rovin). Spodní plocha zdi není vytvá°ena, protoºe stejn¥ nikdy nebude vid¥t. Pouºitá textura se ur£í na základ¥ velikosti zdi a v p°ípad¥, ºe pro danou velikost je k dispozici více textur, tak je vybrána náhodn¥.
4.4.
VIZUALIZANÍ APLIKACE
33
Na£tení a zpracování událostí je komplikovan¥j²í, protoºe se ve scén¥ neprojevují po celou dobu b¥hu. Proto je p°i na£tení jen vytvo°en pot°ebný objekt a do grafu scény je p°idán aº v £ase za£átku p·sobení události. Po uplynutí £asu konce p·sobení události je tento objekt ze scény zase odebrán. Samotný místo události je zobrazováno pomocí £ásticového systému kou°e. Nejkomplikovan¥j²í je na£tení vstupních dat pro agenty. Nejprve jsou p°e£teny de nice po£áte£ních pozic agent· a na jejich základ¥ jsou vytvo°eny kontrolní objekty pro jednotlivé agenty. Tyto objekty jsou uloºené jednorozm¥rném poli z d·vodu rychlého p°ístupu p°i následném b¥hu, protoºe v kaºdém zobrazovacím kroku musí být aktualizovány. Také je vytvo°ena hash mapa mezi jménem agenta a indexem v tomto poli pro rychlé p°i°azení de nic pohybu ke správným objekt·m. Nakonec jsou na£teny v²echny £ásti pohybu v²ech agent· a na základ¥ hash mapy p°i°azeny ke správným agent·m. Pro uloºení jednotlivých £ástí pohybu v objektu reprezentujícího agenta je vyuºita fronta. Model pro jednotlivé agenty je vybrán náhodn¥ ze v²ech dostupných model·. Tyto modely jsou de novány v kon gura£ním souboru (models.cfg), jehoº struktura je popsána v p°íloze C. P°i samotném b¥hu aplikace je pot°eba jen aktualizovat polohu agent· a kontrolovat za£átek £i konec p·sobení událostí. V p°ípad¥ událostí sta£í jen u v²ech neza£atých kontrolovat, zda jiº neuplynul £as jejich za£átku. Pokud ano, tak se p°idají do scény a p°idají mezi za£até. Pro za£até se kontroluje zda neuplynul £as konce a v p°ípad¥, ºe uplynul, tak se zase vy°adí ze scény a uº se o n¥ dále není nutné starat. Kontrola pohybu agent· je o n¥co sloºit¥j²í. Nejprve se pro kaºdého agenta zjistí, která £ást pohybu má být zobrazena. To probíhá postupným vybíráním z fronty pohybu, dokud nenarazí na pohyb, jehoº konec je²t¥ nenastal. V p°ípad¥, ºe nenastal ani jeho za£átek, tak nastavíme pozici agenta na koncovou pozici p°ede²lého pohybu. Jinak spo£ítáme pomocí lineární interpolace aktuální pozici a podle ní nastavíme polohu agenta.
34
KAPITOLA 4.
REALIZACE
Kapitola 5 Testování a výsledky Byl vytvo°en model, který se snaºí simulovat realistické chování dav·. Dále byl navrºen jazyk pro záznam pohybu jednotlivých agent·, který je získán touto simulací. A nakonec byla vytvo°ena aplikace interpretující tento jazyk a zobrazující celou simulaci ve 3D. Ob¥ aplikace jsou implementovány jednovláknov¥. Samotný model je upravený HiDAC model. Snahou bylo odstranit n¥které parazitní vlastnosti modelu sociálních sil a zárove¬ umoºnit snadný záznam pro pot°eby jazyka pro popis pohybu agent· po scén¥ a plnohodnotné 3D zobrazení. Tento model byl dále roz²í°en o moºnost událostí ovliv¬ující chování agent· ve svém okolí. Videa nahraná z n¥kolika ukázkových simulací jsou na CD p°iloºeném k této práci.
5.1 Metody testování Testování funk£nosti lze rozd¥lit do dvou hlavních skupin. První je testování realisti£nosti simulací a tím i smysluplnosti modelu a druhou je testování výkonu. Testování realisti£nosti je oproti testování výkonu zna£n¥ problemati£t¥j²í. To je dáno tím, ºe testování výkonu jsou v podstat¥ strojové testy, ale p°i testování realisti£nosti záleºí na samotném pr·b¥hu simulace a výsledném vzhledu. Nejprve je pot°eba ur£it, pro které scény jsou navrºený model a jeho implementace vhodné. Jelikoº není implementováno ºádné vy²²í °ízení agent·, nelze simulovat scény, ve kterých se cíle agent· m¥ní v pr·b¥hu simulace. Tedy nelze simulovat scény, ve kterých v pr·b¥hu simulace dojde k n¥jaké zásadní zm¥n¥ (nap°íklad uzav°ení východu a podobn¥). Také ve²kerá interakce mezi agenty je omezena jen na to, aby se dokázali vyhnout. Z tohoto vyplývá, ºe sou£asná podoba modelu nedokáºe úpln¥ reáln¥ simulovat scény kaºdodenních situací, kdy se mohou potkávat známí lidé. V takové situaci totiº lidé m¥ní své chování a cíle své cesty v závislosti na tom, koho práv¥ potkali (zastaví se a povídají si spolu, jeden zm¥ní sv·j cíl tak, ºe doprovází toho druhého...). 35
36
KAPITOLA 5.
TESTOVÁNÍ A VÝSLEDKY
Na základ¥ t¥chto omezení byli vytvo°eny £ty°i testovací scény. První dv¥ jsou bez událostí a druhé dv¥ obsahují n¥jakou událost. První scéna simuluje pr·b¥h odchodu lidí z místnosti (nap°íklad z d·vodu evakuace). Druhá scéna je simulace dvou proti sob¥ jdoucích skupin lidí, které se vzájemn¥ neznají. T°etí scéna je simulace chování lidí na ulici, kdyº dojde k jednoduché události jako je nap°íklad rozbití výlohy. O£ekávané chování lidí je, ºe nejprve odb¥hnou polekan¥ od místa události a poté se jdou podívat, co se to stalo. Poslední testovací scéna se ulice podél které jsou obchodní stánky. O£ekávané chování je, ºe se n¥kte°í agenti na chvíli zastaví u n¥jakého stánku. Ob¥ poslední scény p°edpokládají, ºe se v²ichni agenti navzájem neznají a tak nemají d·vod se spolu vzájemn¥ bavit. Sm¥rodatným vyhodnocením t¥chto scén je realisti£nost simulace pro £lov¥ka (pozorovatele). Testování výkonu se v p°ípad¥ obou aplikací zabývá výpo£etními nároky a u jazyka pro popis pohybu pam¥´ovou náro£ností. Za ú£elem testování byly vytvo°eny dv¥ v¥t²í testovací scény. U t¥chto scén nejde o jejich realisti£nost, ale jen o otestování výkonu. U simula£ní aplikace jsou nároky na výkon m¥°eny v po£tu simula£ních krok· provedených za vte°inu. V p°ípad¥ vizualiza£ní aplikace je to dáno po£tem snímk· zobrazených za vte°inu. Pam¥´ové nároky jazyka pro popis pohybu jsou dány místem, které zabírá soubor, v n¥mº je uloºen.
5.2 Výsledky testování Záznamy výsledku v²ech £ty° testovacích scén pro zji²t¥ní realisti£nosti simulace jsou na p°iloºeném CD v adresá°i video. Ve v²ech testovacích scénách p·sobí výsledná trajektorie realisticky. Jediný ru²ivý element je nevhodné nato£ení agent· p°i n¥kterých £ástech simulace. To je zp·sobeno tím, ºe orientace agenta se primárn¥ ur£uje podle sm¥ru jeho pohybu a tak v p°ípad¥, ºe by agent m¥l d¥lat del²í úkroky £i kroky zp¥t, tak uº dojde k jeho nato£ení. Chování agent· p°i událostech je odpovídající o£ekávání, ale i zde dochází k nato£ení agenta nevhodným sm¥rem v p°ípad¥, ºe je zastaven u pozitivní události a n¥jaký z agent· do n¥j "²´ouchne". Dále u v²ech scén, kde nejdou v²echny agenti zhruba jedním sm¥rem m·ºe dojít k do£asnému zastavení dvou agent· vedle sebe na n¥kolik simula£ních krok· v p°ípad¥, ºe mají shodn¥ nastavenou velikost. Testování výkonu probíhalo na notebooku s dvoujádrovým procesorem AMD Turion II P520 s frekvencí 2.3GHz a gra ckou kartou ATI Mobility Radeon HD 5470 s 1GB vlastní pam¥ti. Za tímto ú£elem byly otestovány 3 scény. První byla testována scéna odpovídající ulici se stánky, která byla pouºita i pro otestování realisti£nosti. Tato scéna obsahuje 80 agent·. Dále byli otestovány dv¥ scény obsahující davy jdoucí proti sob¥, které byly vytvo°eny pro ú£ely testování. Tyto scény obsahují 500 a 1000 agent·. Výsledky pro testování simulace a zobrazení jsou shrnuté v tabulce 5.2.
5.3.
37
INTERPRETACE VÝSLEDK
scéna
po£et agent·
simula£ních krok·
snímk· za vte°inu
ulice
80
57
225
2 skupiny
500
11
60
2 skupiny
1000
6
35
Tabulka 5.1: Testy výkonu aplikací Velikost záznamu pohybu agent· je pro scénu obsahující 1000 agent· zhruba 3MB na 25s.
5.3 Interpretace výsledk· Z výsledk· testování vyplývá, ºe navrºený model je smysluplný pro zamý²lené scény. T¥mi mohou být nap°íklad ne°ízená evakuace, pr·chod n¥kolika skupin turist· p°es jedno místo a podobn¥. Také systém událostí funguje dle o£ekávání. Umoº¬uje relativn¥ jednoduchou cestou simulovat rozli£né situace. Sou£asná implementace není úpln¥ vhodná pro simulaci b¥ºného provozu na ve°ejném prostranství z d·vodu, minimální vzájemné interakce agent·. Dal²í omezení v tomto sm¥ru je nutná p°ítomnost v²ech agent· od po£átku do konce simulace, coº znemoº¬uje simulovat dlouhodob¥j²í scény pohybu lidí jen v rámci men²í oblasti zájmu (nap°íklad park, nám¥stí). Pro takové druhy scén by bylo nutné vytvo°it generátor p°icházejících agent· z míst mimo oblast zájmu a také opou²t¥ní scény (ru²ení jiº nepot°ebných agent·). Z výkonnostních test· vyplývá, ºe ob¥ aplikace jsou dostate£n¥ rychlé pro simulaci scén, pro které je primárn¥ cílen. Ob¥ v¥t²í scény jsou navíc z hlediska výkonu nejhor²ími moºnými, protoºe výkon závisí nejvíce na "hustot¥" simulovaného davu. Scénu obsahující 500 agent· lze simulovat jen zhruba t°ikrát zpomalen¥ oproti reálnému £asu (simulace p°edpokládá 30 simula£ních krok· za vte°inu). Také i v¥t²í scéna, která uº p°esahuje o£ekávaný rozsah simulací, je simulována jen zhruba p¥tkrát zpomalen¥. Také je z toho patrné, ºe výkon má zhruba lineární sloºitost, coº je o£ekávané. Vizualiza£ní aplikace je i pro scénu obsahující 1000 agent· stále plynulá. A to jsou pouºité modely pro zobrazení agent· dosti sloºité. Velikost výstupního souboru není v dne²ní dob¥ problémem, ale pro v¥t²í scény, které by zachycovaly del²í £asový úsek, by výsledné soubory mohly být neprakticky veliké. To by ²lo °e²it n¥jakým druhem komprese dat.
38
KAPITOLA 5.
TESTOVÁNÍ A VÝSLEDKY
Kapitola 6 Záv¥r Poda°ilo se vytvo°it funk£ní koncept dvouúrov¬ové simulace chování dav·. První úrovní je simula£ní aplikace. Tato si na£te scénu z kon gura£ního souboru a provede její simulaci. Výsledek této simulace je zapsán v navrºeném jazyce pro popis pohybu agent·. Druhou úrovní je vizualiza£ní aplikace, která interpretuje tento jazyk a zobrazí simulaci ve 3D. Ukázalo se, ºe tento koncept rozd¥lení simulace a zobrazení do dvou samostatných blok·, propojených jazykem zaznamenávajícím pr·b¥h simulace, je funk£ní. Také z testování vychází, ºe navrºený model dává smysluplné výsledky a není p°itom p°íli² náro£ný na prost°edky (v rámci o£ekávaného rozsahu scén). Tím byly spln¥ny cíle této práce. Navrºený model je vhodný p°edev²ím pro bezpe£nostní simulace a to koresponduje i s vhodností dvouúrov¬ového konceptu, jehoº pouºití vyplývá ze zadání. Vhodnost konceptu vychází z toho, ºe je moºné p°i návrhu n¥jaké budovy zprvu brát v potaz jen data ze samotné simulace a aº p°i skoro nálním stavu kontrolovat chování pomocí vizualiza£ní aplikace. Moºností navazující práce je n¥kolik. První z nich by bylo zam¥°it se na výkon p°edev²ím samotné simula£ní aplikace. Zde se naskýtá zna£ná moºnost zrychlení výpo£tu rozd¥lením do více vláken. Dal²í místo, kde by mohlo dojít k snadným optimalizacím, je implementace uniformní m°íºky. Tyto optimalizace ale vzhledem k typ·m o£ekávaných scén, pro které model dob°e funguje, nep°inesou ºádný zásadní uºitek vzhledem k výpo£etnímu výkonu sou£asných po£íta£·. Druhým sm¥rem na zlep²ování je zkvalitn¥ní simulace a vizualizace. U simulace by to bylo p°edev²ím vylep²ení ohledn¥ nastavování orientace agent· (lep²í °e²ení úkrok· a couvání). Dal²í moºnost roz²í°ení simula£ního modelu by byla v r·zných £ástech vy²²ího °ízení agent·, na které se tato práce nezam¥°uje. T¥mi by mohlo být komplexn¥j²í zadávání cíl· jednotlivých agent· a s tím související hledání zp·sobu jak jich dosáhnout (od plánování tras dosaºení cíle cesty aº po komplexní rozhodovací systém m¥n¥ní cíl· na základ¥ r·zných podn¥t·). Dal²í roz²í°ení modelu by mohlo spo£ívat v mechanizmu interakce agent· mezi sebou (rozhovory, doprovázení, 39
40
KAPITOLA 6.
ZÁV
R
ptaní na cestu). Také systém událostí by mohl být roz²í°en o globální události nebo o pohyblivé události (t°eba pr·chod celebrity nebo út¥k zlod¥je). U vizualizace je asi nejzna£n¥j²í moºností roz²í°ení p°idání realisticky animovaných model· agent· místo statických. Druhým zásadním roz²í°ením by mohl být systém lep²í variability vyobrazených scén (a´ uº n¥jakým lep²ím zp·sobem kon gurace nebo podporou nahrazení £ásti £i celé statické £ásti scény 3D modely). Velice speci ckým sm¥rem dal²ího vývoje by bylo umoºn¥ní interpretace jazyka online. To by umoºnilo, aby simulace b¥ºela na n¥jakém výkonném serveru a po síti by se odesílaly informace vizualiza£ní aplikaci. V takovém p°ípad¥ by sou£asná podoba jazyka zabírala p°íli² mnoho místa a muselo by se vyuºít n¥jaké metody komprese dat. To by bylo nutné i v p°ípad¥ pot°eby provád¥t n¥jaké dlouhotrvající simulace.
Literatura [1]
Blender
org/>.
[online]. [cit. 3. 5. 2012]. Dostupné z:
[2]
CSG - Crowd Simulation Group
[3]
GAMMA - Geometric Algorithms for Modeling, Motion, and Animation
[4]
Havok
[5]
Lua
[6]
Object-Oriented Graphics Rendering Engine
[7]
Simple DirectMedia Layer
[8]
TinyXML-2
[9]
[online]. [cit. 12. 10. 2012]. Dostupné z: . [online]. [cit. 12. 10. 2012]. Dostupné z: .
com/>.
[online]. [cit. 3. 5. 2012].
Dostupné z:
[online]. 4 2012. [cit. 3. 5. 2012]. Dostupné z: . stupné z: .
//www.libsdl.org/>.
[online]. [cit. 3. 5. 2012]. Do-
[online]. [cit. 3. 5. 2012]. Dostupné z:
[online]. 4 2012. [cit. 3. 5. 2012]. Dostupné z: .
[online]. [cit. 3. 5. 2012]. Dostupné z: . Xerces-C++
[10] GUY, S. J. LIN, M. C. MANOCHA, D. Modeling Collision Avoidance Behavior for Virtual Humans. AAMAS '10 Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Sys-
. 2010, 2, s. 575582.
tems: volume 2
[11] HELBING, D. FARKAS, I. J. VICSEK, T. Simulating Dynamical Features of Escape Panic. Nature. 2000, 407, s. 487490. [12] HELOIR, A. KIPP, M. EMBR A Realtime Animation Engine for Interactive Embodied Agents. Intelligent Virtual Agents. 2009, s. 393 404. 41
42
LITERATURA
[13] LERNER, A. CHRYSANTHOU, Y. LISCHINSKI, D. Crowds by Example. Computer Graphics Forum. 2007, 26, s. 655664. [14] PELECHANO, N. ALLBECK, J. BADLER, N. Controlling Individual Agents in High-Density Crowd Simulation. SCA '07 Proceedings of the 2007 ACM SIGGRAPH/Eurographics symposium on Computer animation
. 2007, s. 99108.
[15] POLANA, R. NELSON, R. Low Level Recognition of Human Motion (Or How to Get Your Man Without Finding his Body Parts). Motion of Non-Rigid and Articulated Objects, 1994., Proceedings of the 1994 IEEE
. 1994, s. 7782.
Workshop on
[16] The Khronos Group. GLUT - The OpenGL Utility Toolkit [online]. [cit. 3. 5. 2012]. Dostupné z: . [17] ULICNY, B. THALMANN, D. Crowd simulation for interactive virtual environments and VR training systems. Computer Animation and Simulation 2001. 2001, s. 163170.
Dodatek A Slovní£ek pojm· z zkratek 2D/3D agent api (3D) engine parser SAX
DOM
XML
Dvou/t°í rozm¥rný prostor Jednotlivec z davu, jehoº chování je simulováni Aplika£ní rozhraní, ur£uje zp·sob jak ovliv¬ovat nebo vyuºívat danou knihovnu/program z jiného programu £i pluginu Knihovny poskytující nadstavbu nad základním 3D api. Zpravidla se starají o na£ítání model· a textur, správu scény a usnad¬ují manipulaci s ní. knihovna obstarávající p°e£tení textu a jeho zpracování. (Simple API for XML). Toto je metoda pro proudové zpracování XML dokument·. Dokument je rozd¥len na základní prvky (po£áte£ní a koncové zna£ky, obsah element·...). P°i na£tení tohoto prvku je vyvolaná odpovídající událost. Na základ¥ zpracování t¥chto událostí dojde k na£tení dokumentu. Objektový model dokumentu (document object model) je reprezentace XML jako strom, kdy jednot prvky (elementy, atributy...) jsou uzly tohoto stromu. P°i tomto p°ístupu je celé XML p°e£teno a uloºeno v pam¥ti. Roz²i°itelný zna£kovací jazyk (Extensible Markup Language). Je pod zá²titou W3C.
43
44
DODATEK A.
SLOVNÍEK POJM Z ZKRATEK
Dodatek B Podrobná de nice jazyk· B.1 Kon gura£ní soubor Následující tabulka shrnuje seznam v²ech element·, které mohou být v kon gura£ním souboru. element randomSet stopRule agents obstacles walls events
element
agent
Ko°enové elementy popis po£áte£ní nastavení generátoru náhodných £ísel, nepovinný 0 nebo 1 zakázání (0) nebo povolení (1) pravidla zastavení, nepovinný defaultn¥ 1 agent + obsahuje popis jednotlivých agent·, povinný obstacle * obsahuje popis jednotlivých p°ekáºek, nepovinný wall * obsahuje popis jednotlivých zdí, nepovinný eventGroup * obsahuje popis jednotlivých událostí obsahuje celé £íslo
Vno°ené elementy obsaºen v
obsahuje pos ori targets Dsize ? ignoreKoe cient ? behavior ?
45
agents
popis
popis jednoho agenta
46
DODATEK B.
PODROBNÁ DEFINICE JAZYK
agent eventGroup
Dsize
x z x z desetinné £íslo
ignoreKoe cient
desetinné £íslo
agent
behavior
GO nebo PANIC
agent
targets
target +
agent
pos ori
target obstacle
wall
x z dist2ToPass ? x z r x1 y1 z1 x2 y2 z2
agent agent
de nuje po£áte£ní pozici agenta de nuje po£áte£ní sm¥r nato£ení agenta de nuje zm¥nu polom¥ru agenta, nepovinný defaultn¥ -0.05 aº 0.05 de nuje koe cient upravující ²anci na ignorování kladné události, nepovinný defaultn¥ 0.9 aº 1.1 de nuje zda agent panika°í nebo ne, nepovinný defaultn¥ GO obsahuje seznam míst kudy má agent projít
targets
de nuje cíl pohybu agenta
obstacles
de nuje jednu p°ekáºku
walls
de nuje jednu ze¤
x
desetinné £íslo
z
desetinné £íslo
dist2ToPass
desetinné £íslo
pos ori target obstacle pos ori target obstacle target
r x1
desetinné £íslo desetinné £íslo
obstacle wall
x sou°adnice pozice/sm¥ru
z sou°adnice pozice/sm¥ru de nuje druhou mocninu vzdálenosti na kterou je cíl pohybu povaºován za dosaºený, nepovinný defaultn¥ 0.8 de nuje polom¥r p°ekáºky sou°adnice po£átku zdi v ose x
B.1.
47
KONFIGURANÍ SOUBOR
y1
desetinné £íslo
wall
z1
desetinné £íslo
wall
x2 y2 z2
wall wall wall events
popis jedné sloºené události
seeDist
desetinné desetinné desetinné pos seeDist size event + desetinné
sou°adnice po£átku zdi v ose y sou°adnice po£átku zdi v ose z sou°adnice konce zdi v ose x sou°adnice konce zdi v ose y sou°adnice konce zdi v ose z
£íslo
eventGroup
size
desetinné £íslo
eventGroup
maximální vzdálenost na kterou je agent v oblasti p·sobení události de nuje velikost p°ekáºky, která zabírá místo události
eventGroup
£íslo £íslo £íslo
type
type start duration lookDist ? ignoreChance ? minInterestTime maxInterestTime 0 nebo 1
start
desetinné £íslo
event
duration
desetinné £íslo
event
lookDist
desetinné £íslo
event
ignoreChance
desetinné £íslo
event
minInterestTime
desetinné £íslo
event
maxInterestTime
desetinné £íslo
event
event
eventGroup
de nuje díl£í £ást události
event
de nuje druh události (0 negativní, 1 pozitivní) de nuje po£áte£ní £as p·sobení události de nuje dobu trvání události (0 pro nekone£nou) de nuje vzdálenost ve které se agenti zastaví, nepovinný defaultn¥ 5 (jen pro pozitivní události) de nuje ²anci na ignorování události v procentech, nepovinný defaultn¥ 15 (jen pro pozitivní události) de nuje minimální dobu, po kterou je agent pod vlivem události de nuje maximální dobu, po kterou je agent pod vlivem události
48
DODATEK B.
PODROBNÁ DEFINICE JAZYK
B.2 Jazyk pro popis pohybu Následující tabulka shrnuje seznam v²ech element·, které mohou být v jazyce pro popis pohybu. @ znamená atribut místo elementu (@name je atribut name). element agents
obsahuje agent +
obstacles
obstacle *
walls
wall *
move
m+
events
event *
element
obsahuje x z r @name x z r x1 y1 z1 x2 y2 z2 x z start end x z b e ox oz @a
agent
obstacle
wall
event
m
Ko°enové elementy popis obsahuje popis jednotlivých agent·, povinný obsahuje popis jednotlivých p°ekáºek, nepovinný obsahuje popis jednotlivých zdí, nepovinný obsahuje popis jednotlivých £ástí pohybu, povinný obsahuje popis jednotlivých událsotí Vno°ené elementy obsaºen v popis agents
popis jednoho agenta
obstacles
de nuje jednu p°ekáºku
walls
de nuje jednu ze¤
events
de nuje jednu událost
mov
de nuje jeden pohyb
B.2.
49
JAZYK PRO POPIS POHYBU
x
desetinné £íslo
z
desetinné £íslo
r
desetinné £íslo
agent obstacle event m agent obstacle event m agent
r x1
desetinné £íslo desetinné £íslo
obstacle wall
y1
desetinné £íslo
wall
z1
desetinné £íslo
wall
x2 y2 z2 b
desetinné desetinné desetinné desetinné
wall wall wall m
e
desetinné £íslo
m
ox
desetinné £íslo
m
oz
desetinné £íslo
m
start
desetinné £íslo
event
end
desetinné £íslo
event
@name @a
text text
agent m
£íslo £íslo £íslo £íslo
x sou°adnice pozice
z sou°adnice pozice de nuje po£áte£ní nato£ení agenta v radiánech de nuje polom¥r p°ekáºky sou°adnice po£átku zdi v ose x sou°adnice po£átku zdi v ose y sou°adnice po£átku zdi v ose z sou°adnice konce zdi v ose x sou°adnice konce zdi v ose y sou°adnice konce zdi v ose z de nuje £as po£átku pohybu ve vte°inách de nuje £as konce pohybu ve vte°inách de nuje sm¥r nato£ení agenta v pr·b¥hu pohybu, x sou°adnice vektoru, nepovinný (v páru s oz), defaultn¥ odpovídá sm¥ru pohybu de nuje sm¥r nato£ení agenta v pr·b¥hu pohybu, z sou°adnice vektoru, nepovinný (v páru s ox), defaultn¥ odpovídá sm¥ru pohybu de nuje za£átek p·sobení události (ve vte°inách) de nuje konec p·sobení události (ve vte°inách) de nuje jméno agenta (ID) de nuje pro kterého agenta je tento pohyb ( reference na ID)
50
DODATEK B.
PODROBNÁ DEFINICE JAZYK
Dodatek C Popis kon gura£ního souboru vizualiza£ní aplikace Kon gura£ní soubor models.cfg slouºí k ur£ení, které modely agent· se pouºijí pro vizualizaci. Jedná se vý£et t¥chto model· a nastanení po£áte£ních parametr·, kterými jsou rotace a posun. Syntaxe je vid¥t v ukázce C.1. ModelX_name musí být jméno souboru (v£etn¥ p°ípony) obsahující popis modelu, který je v OGRE formátu. Rotace je po£áte£ní oto£ení modelu ve stupních (podle osy Y). Sou°adnice x, y a z udávají po£áte£ní posunutí modelu. Pro správnou funk£nost musí být model i v²echny jím pouºívané zdroje (popis materiál·, textury) uloºené v adresá°ích, které jsou de nované v resources.cfg (základní kon gura£ní soubour pro OGRE aplikaci). Na ukázce C.2 je p°íklad kon gura£ního souboru.
model1_name | tab | r o t a c e | tab | x | s p a c e | y | s p a c e | z model2_name | tab | r o t a c e | tab | x | s p a c e | y | s p a c e | z ukázka C.1: syntaxe kon gura£ního soubory
man1 . mesh man2 . mesh man3 . mesh woman1 . mesh woman2 . mesh woman3 . mesh
90 90 90 90 90 90
−60 0 − 87.5 3 . 5 0 − 62.5 1 3 . 5 0 −146 5 0 −25 8 . 5 0 − 97.5 8 . 5 0 − 177.5
ukázka C.2: p°íklad kon gura£ního souboru
51
52DODATEK C.
POPIS KONFIGURANÍHO SOUBORU VIZUALIZANÍ APLIKACE
Dodatek D Instala£ní a uºivatelská p°íru£ka D.1 Pouºívání alikací Pro instalaci aplikací sta£í p°ekopírování adresá°· /bin, /data a /media na poºadované místo. Pro spu²t¥ní ukázkových scén jsou p°ipraveny dávkové soubory v adresá°i /bin (jak pro simulaci tak pro zobrazení) a poté soubor /start.bat, p°es který lze spustit simulace pro libovolnou p°ipravenou scénu a následn¥ její vizualizace. Vizualiza£ní aplikace spu²t¥ná p°es tyto dávkové soubory bere data z umíst¥ní kam je zapisuje simula£ní aplikace spu²t¥ná p°es tyto soubory. Ukázkové kon gura£ní soubory jsou umíst¥ny v adresá°i /data/con g. Výstup v jazyce pro popis pohybu agent· po scén¥ pro tyto ukázkové scény je v adresá°i /data/move. Ve²keré data vyuºívané vizualiza£ní aplikací jsou v adresá°i /media
D.1.1
Simula£ní aplikace
Tato aplikace pro sv·j b¥h vyuºívá knihovny GLUT a OpenGL. Pro samotný b¥h nemá ºádné speciální pot°eby a m¥la by bez problém· b¥ºet na v²ech dne²ních po£íta£ích. Spou²tí se p°íkazem /bin/Release/CrowdSimulation.exe [vstupní soubor] [výstupní soubor]. Druhý parametr je cesta k souboru kam se má zapsat výstup simulace v jazyce pro popis pohybu agent·. V p°ípad¥ ºe není p°ítomen je pouºit soubor mov.xml. Prvním parametr je cesta ke kon gura£nímu souboru. V p°ípad¥ ºe není uvedena pouºije se soubor in.xml. V pr·b¥hu simulace je moºné pohybovat se scénou klávesami WSAD (nahoru, dolu, doleva a doprava). K p°iblíºení a oddálení slouºí klávesy + a -. Klávesou I se zobrazí/skryje obdelník zájmu agent· a klávesou O se zobrazí/skryje orientace. V p°ípad¥ kompilace aplikace s nastaveným makrem preprocesoru _DEBUG_STEPS slouºí klávesa U k provedení kroku simulace (neprobíhá pr·b¥ºn¥). Aplikace se ukon£uje klávesou Escape. P°i ukon£ení 53
54
DODATEK D.
INSTALANÍ A UIVATELSKÁ PÍRUKA
aplikace se uloºí do výstupního souboru v²e co prob¥hlo. Obarvení agent· reprezentuje jejich aktuální stav. Zelen¥ jsou panika°ící agenti, £erven¥ agenti v b¥ºném (nepanika°ícím stavu), mod°e agenti s aktivním pravidlem £ekání a ºlut¥ agenti s aktivním pravidlem zastavení.
D.1.2
Vizualiza£ní aplikace
Ani tato aplikace pro b¥h nemá ºádné speciální poºadavky a tak by m¥la b¥ºet na v²ech b¥ºných po£íta£ích. Jen je pot°eba mít nainstalováno DirectX verze 9 (ve windows xp není b¥ºn¥ p°ítomen, v nov¥j²ích uº ano). Spou²tí se p°íkazem /bin/Release/CrowdVisualize.exe [vstupní soubor]. Jako parametr o£ekává cestu k souboru s jazykem pro popis pohybu agent· scénou. Pokud není pouºit ºádný parametr bude pouºit soubor mov.xml. Také vyuºívá soubor resources.cfg pro de nici zdroj· (v²echny jsou v /media) a models.cfg pro ur£ení, které modely bude vyuºívat pro zobrazení agent·. Po spu²t¥ní se na£te vstupní soubor a zobrazí po£áte£ní scéna. Samotná animace se odstartuje mezerníkem (klávesa SPACE). Ve scén¥ je moºné se pohybovat pomocí kláves WSAD (dop°edu, dozadu, doleva a doprava) a my²i (pohyb natá£í kameru). Pro ukon£ení slouºí klávesa Escape.
D.2 Kompilace ze zdrojových kód· V adresá°ích /src/CrowdSimulation a /src/CrowdVisualize jsou projekty pro Microsoft Visual Studio 2008. Pro kompilaci simula£ní aplikace není pot°eba nic zvlá²tního. Pro spu²t¥ní je pot°eba mít nastavenou cestu k /src/CrowdSimulation/GL/glut32.dll. Pro úsp¥²nou kompilaci vizualiza£ní aplikace je nutné mít nainstalován OGRE engine (/OGRE) a nastavenou prom¥nnou prost°edí OGRE_HOME na cestu ke ko°enovému adresá°i OGRE. Zkompilovaná aplikace se kopíruje do umíst¥ní OGRE_HOME/bin/Debug nebo OGRE_HOME/bin/Release dle druhu kompilace a p°ípadný debuggování se spou²tí z tohoto umíst¥ní (nastaveno v projektu).
Dodatek E Obsah p°iloºeného CD | OGRE | bin | | Release | | | CrowdSimulation.exe | | ` CrowdVisualize.exe | | %name%-anim.bat | ` %name%.bat | data | | con g | ` move | documentation | media | src | text | video | ReadMe.txt ` start.bat
adresá° obsahující instala£ní soubor OGRE SDK pro Microsoft Visual Studio 2008 adresá° obsahující spustitelné verze program· binárka simula£ní aplikace binárka vizualiza£ní aplikace spou²t¥cí dávka pro vizualizace ukázkových dat (místo %name% je jméno t¥chto dat) spou²t¥cí dávka pro simulaci ukázkových dat (místo %name% je jméno t¥chto dat) ukázkové kon gura£ní soubory pro simulaci ukázkové soubory pro vizualizaci (vznikly simulací ukázkových kon gura£ních soubor·) dokumentace vygenerovaná doxygenem adresá° obsahující zdroje pro vizualiza£ní aplikaci (textury, modely...) adresá° obsahující zdrojové kódy k jednotlivým aplikacím a projekty pro Microsoft Visual Studion 2008 adresá° obsahující tento text v .PDF i zdrojové (.tex) podob¥ adresá° obsahující videa nahraná p°i vizualizaci ukázkových scén dávka pro spou²t¥ní libovolné simulace z ukázkových dat a následn¥ její vizualizace
55
