Multi-analýza a syntéza simulačného programu

Obsah práce

1.	Teoretické poznatky a metódy
2.	Multi-analýza a syntéza simulačného programu

Interakcia s užívateľom

1. MENU
   • (a) Ľavé tlačidlo myši + pohyb myši (výber z ponuky, nastavovanie)
   • (b) Klávesa ESC (ukončenie práce s programom - menu)
2. SIMULAČNÉ PROSTREDIE
   • Klávesa ESC (ukončenie práce v sim. prostredí, návrat do menu)
   • Klávesa F6 (začiatok simulácie vozidla)
   • Klávesa F10 (priama interakcia s vozidlom / UI )
3. VOZIDLO-PRIAMA INTERAKCIA
   • Klávesa L (odpočet k uhlu kolies [-])
   • Klávesa J (prípočet k uhlu kolies [+])
   • Klávesa V (prípočet k veľkosti rýchlosti)
   • Klávesa C (zmenšenie veľkosti rýchlosti)
   • Klávesa I (pohyb vpred určenou rýchlosťou)
   • Klávesa K (pohyb vzad určenou rýchlosťou)
4. KAMEROVÉ SYSTÉMY
   • Klávesa F2 (kamera 'Lietanie')
   • Klávesa F3 (kamera 'Prezentačná', len v režime s vozidlom)
   • Klávesa F4 (kamera 'Za vozidlom', len v režime s vozidlom)
   • Klávesa F5 (kamera 'Rotačná', len v režime s vozidlom)
5. KAMERA – LIETANIE
   • Klávesa W (posun kamery v smere vektora pozorovania)
   • Klávesa S (posun kamery v protismere vektora pozorovania)
   • Klávesa A (posun kamery v protismere vektora vpravo)
   • Klávesa D (posun kamery v smere vektora vpravo)
   • Klávesa R (zväčšenie rýchlosti posunu)
   • Klávesa E (zmenšenie rýchlosti posunu)

Menu

Konfiguračný súbor a parser konštruujúci menu

Základom pre vytvorenie menu podľa užívateľských požiadaviek je môj vlastný typ konfiguračného súboru. Pri zápise do konfiguračného súboru treba dbať na dodržiavanie niektorých pravidiel, ktorými sa riadi parser konštruujúci menu.

Obr. 18 Ukážka sekcie 'obrazky' konf. súboru konšt. menu

1. Pravidlá vyplývajúce z algoritmu parsera na úpravu tohto textu
   1. komentáre začínajú vždy znakom *
   2. ak má byť posledný údaj na riadku (najviac vpravo) textový reťazec, tak jeho posledný znak je prvý znak sprava po odstránení nežiaducich znakov ("\t \n\r") algoritmom parsera, čiže nepočítajme so zahrnutím týchto znakov ku koncu posledného reťazca v riadku
2. Pravidlá vyplývajúce zo spôsobu spracovania údajov
   1. súbor je logicky rozdelený do 2 sekcií, ktorých začiatky musia byť vyznačené záložkami 'obrazky:' alebo 'pic_stranky:' podľa obsahu pod ním ; každá sekcia sa môže nachádzať na ľubovoľnom mieste v súbore
   2. sekcia 'obrázky:' vždy začína (v danom poradí):
      • počtom obrázkov
      • jednotlivými adresami obrázkov daného počtu (poradie v akom sú adresy obrázkov zapísané určí im ich index, ktorý bude používaný v sekcii pic_stranky:')
   3. sekcia 'pic_stranky:' musí začínať vždy (v danom poradí):
      • počtom obrázkových stránok
      • indexom štartovacej stránky
      • Nasledujúci súbor pravidiel sa opakuje podľa počtu obrázkových stránok:
        • počet obrázkov v obrázkovej stránke
        • index predchádzajúcej stránky (z ktorej sme sa sem dostali), ak je -1, tak neexistuje predchádzajúcu stránka (prvá spustená stránka nemá predchádzajúcu)
        • Nasledujúci súbor pravidiel sa opakuje podľa počtu obrázkov v stránke:
          • • index obrázka (určený poradím adries v sekcii 'obrazky:')
            • počet oblastí v aktuálnom obrázku, ktoré budú používané ako tlačidlá
            • jeden zo symbolických názvov (left_w, center_w, rigth_w) , ktorý určí prvotnú polohu v okne vzhľadom na šírku okna
            • index obrázka, ktorý určí prípočet k prvotnej polohe vzhľadom na šírku (používa sa na relatívnu orientáciu vzhľadom na iný obrázok, ak je -1 tak neexistuje)
            • jeden zo symbolických názvov (bottom_h, center_h, over_h) , ktorý určí prvotnú polohu v okne vzhľadom na výšku okna
            • index obrázka, ktorý určí prípočet k prvotnej polohe vzhľadom na výšku (používa sa na relatívnu orientáciu vzhľadom na iný obrázok, ak je -1 tak neexistuje)
            • Nasledujúci súbor pravidiel sa opakuje podľa počtu tlačidiel v stránke (pzn.: počiatok súradnicového systému tlačidla je v ľavom hornom rohu obrázku, v ktorom sa nachádza):
              • súradnica ohraničujúca oblasť tlačidla zľava (os x)
              • súradnica ohraničujúca oblasť tlačidla zprava (os x)
              • súradnica ohraničujúca oblasť tlačidla zhora (os y)
              • súradnica ohraničujúca oblasť tlačidla zdola (os y)
              • index obrázku, ktorý sa vykreslí po vstúpení na oblasť (kurzorom myši) ohraničenú daným tlačidlom v danom obrázku a v danej obr. Stránke
              • index nasledujúcej stránky, na ktorú sa užívateľ dostane po kliknutí na toto tlačidlo(ak neexistuje označíme -1, index sa automaticky priradzuje podľa poradia obr. stránky v konfig. súbore)
              • boolovske ohodnotenie, či dané tlačidlo využíva nejakú reakciu (0/1)
              • ak predchádzajúci bod bol označený ako 1, treba vybrať 1 zo symbolických názvov, ktoré väčšinou samoopisujú svoje využitie (simulation, bpp_to_32bit, bpp_to_16bit, resolution_to_1024x768, resolution_to_800x600, resolution_to_640x480, volume_music_down, volume_music_up, volume_sound_down, volume_sound_up, play_song_united, play_song_breaking, play_song_war, play_song_black, gamma_down , gamma_up, to_fullscreen)

Obr. 19 Časť zo sekcie 'pic_stranky' konfiguračného súboru konštruujúceho menu

Všeobecný opis a využitie

Obr. 20 Konfiguračný súbor parametrov vykresľovania

Menu je flexibilné vďaka konštrukčnému konfiguračnému súboru, ktorý si užívateľ prepíše podľa svojich potrieb, ale podľa pravidiel opísaných v predchádzajúcej časti (pravidlá pre parser). Menu pozostáva z menších logických úsekov, ktoré označujeme ako obrázkové stránky. Každej stránke môžeme prideliť ľubovoľný počet obrázkov a index predchádzajúcej stránky (štartovacia stránka nemá ukazovateľ na predchádzajúcu stránku). Obrázok každej stránky má množstvo parametrov. Môžeme meniť polohu každého obrázka vzhľadom na polohu v okne a súčasne aj orientovať jeho polohu voči ostatným obrázkom v stránke.

Významnou vlastnosťou je, že každý obrázok môže pozostávať ešte z menších úsekov, tlačidiel, ktoré ešte viac rozširujú schopnosti menu. Tlačidlu môžeme priradiť určitý druh reakcie a index nasledujúcej stránky alebo len index na nasledujúcu stránku. Pod pojmom reakcia môžeme chápať napríklad zmenu rozlíšenia (užívateľ vyberá reakciu zadaním symbolického názvu). Index na nasledujúcu stránku zaznamenáva jedinečné číslo stránky, ktorá sa vykreslí po stlačení tlačidla (posun na ďalšiu úroveň).

Ďalej môžeme nastaviť, v ktorej časti obrázku sa bude tlačidlo nachádzať, zadaním 4 hodnôt (2 pre os X, 2 pre os Y), ktoré vytvoria ohraničenie. Na ukladanie informácií o rozlíšení, bitovej hĺbke (parametre vykresľovania) a ďalších používam konfiguračný súbor z knižnice Libconfig (Obrázok 20). Pri novom štarte programu sa tieto uložené informácie automaticky použijú ako prvotné nastavenia premenných. Prvotné nastavenie pre jednotlivé parametre je použité pri prvom spustení programu (Obrázok 20: premenná 'screen_first_time'), napríklad rozlíšenie by bolo 640x480.

Flexibilita menu sa prejavuje aj jednoduchosťou rozšírenia množiny reakcií alebo polôh v okne priamo v zdrojovom kóde. Programátor by len jednoducho vytvoril ďalšiu metódu a pridal adresu metódy do poľa prislúchajúceho množine adries reakcií/polôh a symbolický názov do množiny symbolických názvov reakcií/polôh. Následne môže použiť symbolický názov v konfiguračnom súbore. Grafický systém menu bol vytvorený vo Photoshop CS3 použitím rôznych pokročilých geometrických a filtračných metód.

Vozidlo

Vytvorenie vozidla

Obr. 21 Konfiguračný súbor vozidla

Jednotlivé časti vozidla sa vytvárajú (alebo sú na nich závislé) podľa užívateľom zapísaných hodnôt do konfiguračného súboru (Obrázok 21). Parametre, ktoré si užívateľ určuje:

1. polomer tela vozidla
2. výšku tela vozidla
3. polomer kolesa
4. šírka kolesa

Obr. 22 Vozidlo (XY)

Koštrukcia vozidla sa delí na dve časti, vytvorenie tela vozidla a podvozku. Telo vozidla pozostáva:

1. Valec uzatvorený na oboch koncoch dvoma diskami
2. Kužeľ

Tvorba podvozku je omnoho zložitejšia, pretože musí zohľadniť množstvo vzájomných zavislostí. Podvozok pozostáva :

1. 4 valce uzatvorené čiastočne na oboch koncoch diskami (kolesá vozidla, čiastočne uzatvorené, pretože každé koleso potrebujeme spojiť s telom)
2. 4 horizontálne valce úplne uzatvorené dvoma diskami (prechádzajú kolesami)
3. 8 úzkych vertikálnych valcov úplne uzatvorených dvoma diskami (vytvárajú spojenie medzi horizontálnym valcom a širokým vertikálnym valcom )
4. 4 široké vertikálne valce úplne uzatvorené dvoma diskami (vytvárajú spojenie medzi telom vozidla a 2 úzkymi valcami každého kolesa

Obr. 23 Vozidlo (XZ)

Polohy kolies (na osiach X, Z) musia byť vyjadrené relatívne k polohe aktuálneho ťažiska (poloha na Y sa neurčuje, vyplynie z rotácie (uhly na základe polohy kolies v teréne) vozidla okolo ťažiska – rotácia okolo X, Z ). Pre určenie polôh kolies (X,Z) využívam známy vzťah kružnice opísanej štvorcu. Strana štvorca, ktorému je opísaná kružnica (telo vozidla):

[math]a=\sqrt{2}*polomer\_tela[/math]

Pre polohy kolies v súradnicovom systéme vozidla (X, Z) potom platí:

[math]\begin{matrix} \check{l}av\acute{e}\_zadn\acute{e}=[-a/2,-a/2] \\ prav\acute{e}\_zadn\acute{e}=[-a/2,+a/2] \\ \check{l}av\acute{e}\_predn\acute{e}=[+a/2,-a/2] \\ prav\acute{e}\_predn\acute{e}=[+a/2,+a/2] \\ \end{matrix}[/math]

Obr. 24 Vozidlo (YZ)

Pohyb vozidla v teréne

Vozidlo môže byť riadené priamo užívateľom k ľubovoľnému cieľu alebo riadiacim algoritmom k určenému cieľu v teréne (cieľ určuje riadiaca trieda z jazyka Python). Tieto režimy majú spoločné tri algoritmy, ktoré majú za úlohu správnu interakciu s terénom a vykreslenie v teréne.

Prvý z nich (Pseudoalgoritmus 1) výpočíta nové ťažisko na osiach X, Z v súradnicovom systéme terénu a nový uhol natočenia kolies okolo vlastnej osi Z (algoritmus potrebuje poznať správny smer pohybu vozidla, jeho veľkosť aj FPS).

Pseudoalgoritmus 1

Druhý (Pseudoalgoritmus 11, pozri prílohu B) je omnoho komplikovanejší a preberá informácie z prvého. Počíta dotykové body kolies s terénom na osiach X, Y, Z, počíta súradnicu Y ťažiska, uhly natočenia vozidla okolo tohto ťažiska (rotácia okolo X, Z na základe polôh kolies v teréne), bod vrcholu kužeľa kontroluje správnosť výpočtu (či može existovať vozidlo v teréne na danej polohe).

Tento algoritmus (Pseudoalgoritmus 11) využíva aj algoritmus na výpočet výšky v teréne pre ľubovoľné aj desatinné hodnoty súradníc (Pseudoalgoritmus 10, príloha B). Pre desatinné súradnice X, Z je výška zistená z roviny (trojuholníka), v ktorej leží v teréne. Tieto 2 algoritmy sa vykonávajú len v prípade pohybu alebo pri prvej konštrukcii vozidla v teréne. Tretí algoritmus vykresľuje vozidlo na vypočítanom mieste v teréne s určenými uhlami (Pseudoalgoritmus 15, príloha B).

Vozidlo ovládané užívateľom

Komunikácia s vozidlom prostredníctvom klávesnice:

1. Žiadaná akcia: Rotácia kolies (360°). Reakcia v danom poradí:
   1. Natočenie kolies o žiadaný uhol
   2. Pseudoalgoritmus 15
2. Žiadaná akcia: Pohyb vpred/vzad určenou rýchlosťou. Reakcia v danom poradí:
   1. Záloha
   2. Pseudoalgoritmus 1
   3. Pseudoalgoritmus 11 => Úspech / Neúspech => Obnova
   4. Pseudoalgoritmus 15
3. Žiadaná akcia: Zmenšenie/zväčšenie veľkosti rýchlosti. Reakcia v danom poradí:
   1. Vykoná/Nevykoná sa
   2. Pseudoalgoritmus 15

Všetky detaily toku programu v tomto režime sú jasne zobrazené ako Vývojový_diagram 1, v prílohe C. Pseudoalgoritmus 11/15 nájdete v prílohe B.

Simulácia pohybu vozidla ovládaného UI k cieľu

Tok programu v tomto režime nájdete v prílohe C ako Vývojový_diagram 2.

1. Úloha : Nájsť cestu z bodu A do bodu B – správne navigovať vozidlo bez priameho zásahu užívateľa.
2. Predpoklady
   1. Terén, diskrétny 8-smerový priestor.
      1. bod terénu
         • priechodný - vyznačuje sa cenou cesty do cieľa, cenou cesty do cieľa cez najlepšieho suseda, vlastnou cenou >= 0 (výškou)
         • nepriechodný – prekážka, vyznačuje sa cenou cesty do cieľa = ꝏ, cenou cesty do cieľa cez najlepšieho suseda = ꝏ, vlastnou cenou < 0
           • prekážky vyplývajúce z ohraničenia terénu vzhľadom na vozidlo
           • prekážky vyplývajúce z max. rozdielu dvoch po sebe idúcich výšok ↔ vlastných cien (určované užívateľom)
      2. možnosť aproximovať body terénu podľa zvoleného polomeru (určované užívateľom) → prirodzenejší pohyb vozidla smerom k cieľu, ale aj zvačšená nepresnosť
   2. Vozidlo
      1. informácie o prostredí sú často nekompletné → riešenie využívajúce len počiatočné informácie môže byť nesprávne alebo neoptimálne
      2. aktualizácia informácií v každej novej pozícii vozidla na základe senzoru a iných prostriedkov (polomer senzoru určovaný užívateľom)
      3. preplánovanie cesty na základe nových podmienok (zmení sa cena dôležitého bodu)
3. Riešenie: Algoritmus D * Lite (finálna vezia), pravidelne zisťuje najkratšie cesty medzi súčasnou pozíciou vozidla a cieľovou pozíciou ako ceny prechodov v teréne, ktoré sa menia počas toho ako sa robot presúva smerom k cieľu

Užívateľ nastavuje tri parametre potrebné pre správne fungovanie mojej implementácie riadiaceho algoritmu D * Lite (konečná verzia):

1. polomer dosahu senzoru vozidla (Chebyshevova vzdialenosť)
2. polomer aproximácie bodu výškovej mapy (Chebyshevova vzdialenosť)
3. maximálny rozdiel výšok (súradnica Y) dvoch po sebe nasledujúcich bodov terénu (susedov)

Obr. 25 Konfiguračný súbor riadiaceho algoritmu

Výpočet heuristickej vzdialenosti medzi bodmi na základe Chebyshevovej vzdialenosti:

Pseudoalgoritmus 2

Chebyshevova vzdialenosť alebo vzdialenosť na základe maximálnej hodnoty sa často používa ako odhad euklidovskej vzdialenosti kvôli menšej časovej náročnosti výpočtu. Táto vzdialenosť je jednoducho maximum z rozdielov súradníc. S takouto funkciou výpočtu vzdialenosti je kruh v [math]R^2[/math] štvorec a guľa v [math]R^3[/math] je kocka.

Pre túto vzdialenosť medzi vektormi alebo bodmi p a q so štandardnými súradnicami [math]p_i a q_i[/math] platí :

[math]{{D}_{Chebyshev}}(p,q):=\underset{i}{\mathop{max}}\,({{p}_{i}}-{{q}_{i}})[/math],

zároveň sa rovná limite vzdialenosti v sústave

[math]{{L}_{p}}:\underset{k\to \infty }{\mathop{\text{lim}}}\,{{(\underset{i=1}{\overset{p}{\mathop \sum }}\,{{p}_{i}}-{{q}_{i}}^{p})}^{\frac{1}{p}}}[/math].

Obr. 26 Chebyshevova vzdialenosť (2D)

Výpočet ceny prechodu medzi stavmi

Cena prechodu z jedného bodu na druhý (priechodné body) sa počíta na základe klesania/ stúpania alebo rovnej cesty, pričom klesanie je považované za najvýhodnejšie. Čím je výraznejšie stúpanie tým aj cena cesty je väčšia a pod.

Pseudoalgoritmus 3

Výpočet množiny susedov bodu na určenej pozícii na základe Chebyshevovej vzdialenosti – informácie zo senzoru

Zahŕňa všetky možné body aj prekážky, ktoré spĺňajú vzdialenosť od centrálneho bodu a ohraničenie terénu (používaná mapa = pôvodná/aproximačná). Algoritmus (Pseudoalgoritmus 12 v prílohe B, obrázok 27) na zistenie kompletnej množiny prebieha v 2 fázach: Nájdenie všetkých možných susedov v kríži do danej vzdialenosti (1 súradnica nulová) a nájdenie všetkých susedov šikmo (nenulové súradnice X, Z).

Existencia suseda šikmo sa vždy určuje na základe kombinácie existencie obidvoch súradníc X, Z, čiže na základe existencie horizontálneho a vertikálneho suseda v kríži na uvažovaných súradniciach. Napríklad sused [3,3] je sused šikmo a existuje len ak existujú susedia v kríži [0,3] a [3,0]. Maximálny počet takýchto susedov som vypočítal ako [math]4*(vzdialenost+vzdialenos{{t}^{2}})[/math].

Obr. 27 Chebyshevov senzor vozidla

Výpočet a úprava hodnôt potrebných pre aproximáciu výškovej mapy

Ak má nastať aproximácia pôvodnej výškovej mapy, musí užívateľ zvoliť aproximačný polomer >0, následne sa odvodzujú a upravujú ďalšie potrebné hodnoty. Môže nastať aj zmenšenie šírky/výšky v teréne (ak nevyhovuje) tak, aby šírka/výška terénu bola násobkom strany aproximačného štvorca.

Stranu aproximačného štvorca som odvodil veľmi jednoducho. Zahrnieme do nej 1 centrálny bod a jeho 2 krídla, ktoré som odvodil ako 2*aprox_polomer. Najmenší index (prvá možná súradnica stredu aprox. štvorca) v pôvodnej mape som určil ako aprox"_" polomer(Ukážka aproximačných štvorcov pre polomer 2 je na obrázku 28).

[math]\begin{align} & \text{strana}\_\text{aprox}\_s\text{tvorca}\leftarrow 1+2\text{*aprox}\_\text{polomer} \\ & \text{najmensi}\_\text{index}\_\text{stredu}\_\text{aprox}\_s\text{tvorca}\leftarrow \text{aprox}\_\text{polomer} \\ & \\ & \text{pocet}\_\text{pixelov}\_\text{v}\_\text{aprox}\_s\text{tvorci}\leftarrow 4\text{*}(\text{aprox}\_\text{polomer}+\text{aprox}\_\text{polome}{{\text{r}}^{2}})+1 \\ & \text{sirk}{{\text{a}}_{\text{terenu}}}\leftarrow si\text{rk}{{\text{a}}_{\text{terenu}}}-(si\text{rk}{{\text{a}}_{\text{terenu}}}%\text{strana}\_\text{aprox}\_s\text{tvorca}) \\ & \text{vysk}{{\text{a}}_{\text{terenu}}}\leftarrow \text{vysk}{{\text{a}}_{\text{terenu}}}-(\text{vysk}{{\text{a}}_{\text{terenu}}}%\text{strana}\_\text{aprox}\_s\text{tvorca}) \\ & \\ & \text{sirk}{{\text{a}}_{\text{aprox}\_\text{mapy}}}\leftarrow \text{sirk}{{\text{a}}_{\text{terenu}}}/\text{strana}\_\text{aprox}\_\text{stvorca} \\ & \text{vysk}{{\text{a}}_{\text{aprox}\_\text{mapy}}}\leftarrow \text{vysk}{{\text{a}}_{\text{terenu}}}/\text{strana}\_\text{aprox}\_\text{stvorca} \\ \end{align}[/math]

Obr.28 Aproximačné štvorce

Nájdenie najbližšieho stredu aproximačného Chebyshevovho štvorca

Tento výpočet je potrebný ako prvý krok pre celkovú transformáciu do aproximačnej mapy. Každému bodu pôvodnej mapy (X, Z) môžeme priradiť pre neho najbližší centrálny bod aproximačného štvorca (Pseudoalgoritmus 4, obrázok 29).

Pseudoalgoritmus 4

Obr. 29 Nájdenie najbližšieho stredu aprox. štvorca

Transformácia z normálneho priestoru (pôvodná výšková mapa) do aproximačného priestoru (aproximačná výšková mapa), (Pseudoalgoritmus 5, Obrázok 30)

Pseudoalgoritmus 5

Obr. 30 Transformácia do aproximovaného priestoru

Transformácia z aproximačného priestoru (aproximačná výšková mapa) do normálneho priestoru (pôvodná výšková mapa)

Pseudoalgoritmus 6

Jednou veľkou nevýhodou takejto transformácie (Pseudoalgoritmus 6, obrázok 31), že transformované body sa budú len s určitou presnosťou približovať pôvodnej hodnote (ak neboli stredmi aproximačných štvorcov) , pretože sú „orezané“ ako stredy aprox. štvorcov. Ak by to tak nemalo byť, musel by sa zmeniť celý systém aproximácie, aby táto transformácia ponúkala reálnu hodnotu, z ktorej bola predtým vypočítaná.

Obr. 31 Transformácia do pôvodného priestoru

Výpočet výšky pre jeden aproximačný štvorec normálneho priestoru

Tento algoritmus (Pseudoalgoritmus 7) je triviálny, pretože v podstate vypočíta všetkých možných susedov do určenej vzdialenosti (aprox. polomer) vzhľadom na určený centrálny bod (Pseudoalgoritmus 12, príloha B). Následne vypočíta priemer výšky (1 bod aproximačného priestoru) vzhľadom na tento počet susedov + 1 (stred).

Pseudoalgoritmus 7

Vytvorenie aproximačnej výškovej mapy

Dáta aproximačnej mapy sa vytvoria tak (Pseudoalgoritmus 8), že sa prechádza celá pôvodná mapa v šírke/výške od najmenšej možnej súradnice aprox. štvorca, pričom inkrementácia pre šírku/výšku je zväčšenie o veľkosť strany aprox. štvorca. V každom takomto úseku sa vypočíta aproximácia pre celý 1 aproximačný štvorec (nemusí byť štvorec ak niektoré body sú mimo terénu – nebudú zahrnuté do výpočtu) pôvodnej mapy (Pseudoalgoritmus 7) a uloží sa ako hodnota do aproximačnej mapy.

Počiatočný index v šírke/výške pôvodnej mapy je aprox_polomer (pozri : 'Výpočet a úprava hodnôt potrebných pre aproximáciu výškovej mapy').

Pseudoalgoritmus 8

Posun vozidla na aktuálnu polohu ↔ najlepšieho nasledovníka predchádzajúcej polohy (Pseudoalgoritmus 13, príloha B)

Stavy, ktoré budú posudzované vzhľadom na aktuálnu situáciu (polohu vozidla), pričom práca prebieha v aktuálnom priestore ↔ pôvodný / aproximačný:

1. informácie zo senzoru
2. možná skupina bodov z minulej polohy vozidla, ktorí boli označení ako lokálne prekážky musia byť prehodnotení vzhľadom na aktuálnu polohu

Posudzovanie zistených stavov:

1. posudzovanie len v pôvodnom priestore
   1. Ak je priechodný ∧nie je už známy ako prekážka ∧spĺňa podmienku globálnej prekážky → globálna prekážka – platná stále (bezpečná zóna pre vozidlo vo forme nevizuálnych prekážok pri hraniciach diskrétneho terénu)
2. posudzovanie vo vlastnom priestore – pôvodný / aproximačný
   1. Ak je najbližší priechodný (heuristika = 1)∧nie je už známy ako globálna prekážka ∧nespĺňa podmienku maximálneho rozdielu výšok → lokálna prekážka
   2. (Ak je priechodný∧nie je už známy ako prekážka) ∧(je úplne nový ∨rozdielny voči pôvodnej hodnote) → priechodný bod

Interakcia medzi vozidlom a vysokoúrovňovým riadiacim algoritmom (Pseudoalgoritmus 14, príloha B)

Zjednodušený opis, v danom poradí bodov činnosti :

1. Výpočet celočíselneho štartovacieho bodu z aktuálnej polohy vozidla, v závislosti od možnosti zvoliť si aproximáciu výškovej mapy, čiže vypočítaná poloha bude jednoduchým zaokrúhlením (bez aproximácie) na najbližšie celé číslo alebo stredom aproximačného štvorca (aproximácia) s rozlišovaním prekážok
2. Vozidlo príjme informácie o nasledujúcej polohe bodu z D* Lite, musí podniknúť také kroky, aby ho dosiahol
   1. (Ak smer pohybu vozidla ∨opačný vektor k smeru vozidla – smer vzad) ∧smer k ponúknutému bodu (všetky tri sú jednotkové vektory charakteristické len smerom a dvojdimenzionálne- X, Z, počiatok majú v aktuálnej polohe ťažiska ) sú totožné, čiže uhol medzi 1 z vektorov pohybu vpred alebo vzad a vektorom smeru k bodu je 0, môže nastať posun v tomto smere k ponúknutému bodu (dopredu/dozadu) → pokračuje sa bodom B.III, inak pokračuj na B.II
   2. (Ak smer pohybu vozidla ∨opačný vektor k smeru vozidla) ∧vektor smeru k ponúknutému bodu nie sú totožné, čiže uhol medzi vektorom pohybu vpred/vzad a vektorom smeru k bodu nie je 0, nemôže nastať posun v tomto smere k ponúknutému bodu (dopredu/dozadu). Musí sa zabezpečiť natočenie kolies vozidla do správneho uhla tak, aby jeden z vektorov pohybu (výhodnejší z vpred/vzad na natočenie pre hľadaný smer) bol totožný s vektorom do budúcej polohy vozidla, k ideálnejšiemu vektoru pohybu sa pripočíta/odčíta malá koštanta (podľa FPS) tak, aby sa priblížil k hľadanému smeru, pokračujeme bodom B.I.
   3. Nastáva pohyb v správnom smere k bodu (vektor pohybu vpred alebo vzad je totožný so smerom k tomuto bodu), posunieme sa o malý kúsok (pripočíta/odčíta)
   4. Ak sme dosiahli požadovaný bod a nebol to cieľ tak D* Lite vypočíta a pošle nasledujúci najlepší bod v závislosti na rôznych parametroch, ak dosiahnutý bod je cieľ tak práca končí, ináč sa pokračuje bodom B.I.

Vykresľovanie vozidla

Jednotlivé časti vozidla sú hierarchicky usporiadané a uložené vo forme display listov. Počet všetkých častí je 22. Ich poloha je relatívne vyjadrená voči aktuálnej polohe ťažiska v teréne. Každá konštrukčná jednotka prislúcha podvozku alebo telu vozidla. Vyjadrenie správneho umiestnenia prebieha na základe maticového násobenia.

Obr. 32 Vozidlo v teréne

Terén

Vytvorenie terénu

Konštrukcia terénu je ovplyvnená mnohými požiadavkami, ktoré užívateľ zapisuje do konfiguračného súboru:

1. rozmery terénu – väčšinou ich užívateľ volí totožne s rozmermi výškovej mapy [môžu byť upravené v závislosti na polomere aproximácie pre D* Lite]
   1. výška
   2. šírka
2. počet podpriestorov – terén bude logicky rozdelený do podpriestorov (počet= počet šírkových * počet výškových), vo forme kvádru (8 bodov) a budú slúžiť na efektivizáciu vykresľovania terénu
   1. počet šírkových podpriestorov
   2. počet výškových podpriestorov
3. krok terénu – určuje koľký bod v poradí bude načítavaný pri prechádzaní šírkou a výškou mapy
4. počet susedov – Chebyshevov polomer, ktorý rozhoduje o množstve susedov pre aproximovanie každého pixelu ako centrálneho bodu

Obr. 33 Konfiguračný súbor terénu

Výšková mapa predstavuje obrázok v stupňoch 1 farby (1 byte na pixel), t.j. každý jeden pixel obrázku môže nadobúdať hodnotu od 0 do 255. Táto hodnota predstavuje vstupnú (bude sa pravdepodobne meniť) výšku bodu v teréne.

Postupnosť vykonania algoritmov pre správne vytvorenie terénu:

1. Vytvorenie správnych hraníc podpriestorov
   1. Zistenie hraníc šírkových podpriestorov
   2. Zistenie hraníc výškových podpriestorov
   3. Upravenie rozdelených hraníc šírkových podpriestorov podľa kroku terénu
   4. Upravenie rozdelených hraníc výškových podpriestorov podľa kroku terénu
2. Hlavný cyklus
   1. Konštrukcia bodov terénu v závislosti od množstva parametrov
3. Vytvorenie plynulej výšky v teréne
4. Výpočet správnych normálových vektorov pre každý bod vzhľadom na susedov
5. Dopočítanie výšok neexistujúcich celočíselných bodov terénu

Zistenie hraníc šírkových podpriestorov

Podpriestory rozdeľujú priestor do menších blokov. Tvorba šírkových podpriestorov (Pseudoalgoritmus 16 v prílohe B, obrázok 34) je prvým krokom k vytvoreniu podpriestorov, ktoré obsahujú rovnaký počet bodov vzhľadom aj na krok terénu. Algoritmus postupne rovnomerne prideľuje súradnice do jednotlivých šírkových podpriestorov, čiže posúva ich hranice. Horná hranica posledného ŠP sa po skončení výpočtov musí rovnať poslednej súradnici šírky terénu a zároveň dolná hranica prvého ŠP musí byť 0. Algoritmus zväčšuje veľkosti všetkých podpriestorov len ak má istotu, že má dostatočný počet iterácií vzhľadom na počet ŠP. Môže nastať situácia, že počet zostávajúcich iterácií (počet súradníc ktoré treba prerozdeliť) je menší ako celkový počet ŠP. V takomto prípade algoritmus určí, od ktorého ŠP má začať prerozdeľovať tak, aby sa dostal až k poslednému ŠP.

Obr. 34 Ukážka algoritmu (ZHŠP) na konkrétnych hodnotách

Upravenie rovnomerne rozdelených hraníc šírkových podpriestorov podľa kroku terénu

Tento algoritmus (Pseudoalgoritmus 9) sa aplikuje až po rovnomernom rozdelení do šírkových podpriestorov (Pseudoalgoritmus 16, príloha B).

Cyklus tohto algoritmu je vlastne prechádzanie šírky terénu po krokoch terénu. Kontroluje, či niektorý zo šírkových podpriestorov nemá svoju hornú hranicu menšiu ako je aktuálny index (násobok kroku terénu) v cykle. Ak táto podmienka platí tak musí nastať posunutie tejto hornej hranice na dobrú hodnotu (z predchádzajúceho cyklu) a zároveň v dôsledku nunosti naväzovania ŠP musí byť rovnako nastavená aj dolná hranica nasledujúceho ŠP.

Pseudoalgoritmus 9

Dopočítanie neexistujúcich výšok bodov terénu

Užívateľ v konfiguračnom súbore nastavuje veľkosť kroku terénu, ktorým sa dá jednoducho regulovať plynulosť terénu a zároveň aj pamäťové nároky. Lenže s aplikáciou kroku terénu >1vzniká potreba dopočítať ostatné neznáme výšky (ak [math](bo{{d}_{x}}%krok)\ne 0\vee (bo{{d}_{z}}%krok)\ne 0[/math] ), ktoré boli automaticky vylúčené z výškovej mapy (dopočítanie potrebné pre pohyb vozidla v teréne).

Základná myšlienka pre dopočítanie všetkých neznámych výšok (súradnica Y) celočíselných bodov (Pseudoalgoritmus 17 v prílohe B, obrázok 35) spočíva vo využití rovín (trojuholníkov), ktorými je terén vykresľovaný.

Algoritmus jednoducho zistí v ktorom štvorci v teréne sa nachádza hľadaný bod podľa jeho súradnic X, Z. Následne určí konkrétne, v ktorom trojuholníku. Pre nájdenie správneho trojuholníka sa využíva, že tieto 2 trojuholníky (tvoriace nájdený štvorec) majú 2 nezdieľané body (na obrázku 35 rozdielne). Stačí zistiť, ktorý z týchto rozdielnych bodov je bližšie k nášmu bodu a nájdeme aj hľadaný trojuholník. Potom sa pomocou rovnice roviny (z nájdeného trojuholníka) vypočíta hľadaná výška (súradnica Y) bodu.

Obr. 35 Dopočítanie neexistujúcich výšok terénu

Získanie pyramídy perspektívneho pohľadu

Pod pojmom získanie pyramídy pohľadu si predstavte matematické kroky, ktoré vedú k presnému vymedzeniu pojmu pyramída pohľadu v matematickej podobe. Parametre pyramídy počítame len raz, a to pred spustením renderingu. Týmto krokom dokážeme jednoducho zlepšiť efektivitu renderingu OpenGL aplikácie. Podpriestory terénu, ktoré sa nachádzajú mimo tejto pyramídy sa nevykreslia. Veď načo by sa vykresľovalo niečo, čo nevidieť ? Pyramída pohľadu je v skutočnosti pyramídou s odpíleným vrcholom. Takáto pyramída pozostáva zo 6 rovín, a to z blízkej, vzdialenej, ľavej, pravej, hornej a dolnej. Roviny sú zadefinované tak, že ich normálové vektory smerujú do vnútra pyramídy.

Súbor:.png

Obr.

Súbor:.png

Obr.