POSEIDON NAVIGATION PROJECT

POSEIDON NAVIGATION PROJECT Térkép alkalmazás Pocket PC platformra, GPS támogatással

SZAKDOLGOZAT

Budapesti Műszaki Főiskola Neumann János Informatikai Főiskolai Kar Informatikai Automatizált Rendszerek Szakirány Szerzők Bedők Dávid és Szirbik Ferenc Jelen dolgozat szerzője Bedők Dávid Kozulensek Vámossy Zoltán (docens) és Molnár András (adjunktus) Dátum 2006. február 04.

Poseidon Navigation Project Budapesti Műszaki Főiskola Neumann János Informatikai Főiskolai Kar Informatikai Informatikai és Automatizált Rendszerek Szakirány 2002 - 2006

1 Tartalomjegyzék 1 TARTALOMJEGYZÉK............................................................................................................................2 2 ELŐSZÓ......................................................................................................................................................5 3 CÉL MEGHATÁROZÁSA .......................................................................................................................6 4 IRODALOMKUTATÁS ............................................................................................................................8 4.1 4.2 4.2.1 4.2.2 4.2.3 4.2.4 4.2.5 4.3 4.3.1 4.3.2 4.3.3 4.3.4 4.3.5 4.4 4.4.1 4.4.2 4.4.3

AZ ÚTKERESÉSRŐL ÁLTALÁBAN ....................................................................................................8 ÚTKERESÉS A JÁTÉKOK VILÁGÁBAN [2] ........................................................................................8 Szimulációs program: From Game to Map .............................................................................8 Csapdák ...................................................................................................................................9 Algoritmusok alapja.................................................................................................................9 Dijkstra algoritmusa és a Best-First-Search .........................................................................10 Az A* algoritmus ...................................................................................................................12 A HULLÁM-TOVÁBBTERJESZTÉSES ALGORITMUS [3] ..................................................................13 Legrövidebb út.......................................................................................................................13 Hullám-továbbterjesztéses algoritmus finomítása .................................................................15 Legbiztonságosabb út, Voronoi diagramm ............................................................................17 Megjegyzések .........................................................................................................................20 Implementálás........................................................................................................................20 GRÁFOK ......................................................................................................................................21 Gráfok ábrázolása .................................................................................................................21 Súlyozott és irányított gráf tárolása.......................................................................................22 Minimális költségtérítésű feszítőfa.........................................................................................23

4.4.3.1

4.4.4

Algoritmusa................................................................................................................................ 23

Legrövidebb út [5].................................................................................................................24

4.4.4.1 4.4.4.2 4.4.4.3 4.4.4.4 4.4.4.5

Az algoritmus lényege................................................................................................................ 24 Az algoritmus részletesebben..................................................................................................... 26 Az algoritmus pszeudokódja ...................................................................................................... 26 Szimulációs program: Graphs and spanning trees...................................................................... 27 Megjegyzések ............................................................................................................................ 27

4.5 GLOBÁLIS HELYMEGHATÁROZÓ RENDSZER [6] ...........................................................................28 4.5.1 Egy kis történelem .................................................................................................................28 4.5.2 Mai helyzet.............................................................................................................................28 4.5.3 Pozíció meghatározás............................................................................................................28 4.5.4 A kommunikáció ....................................................................................................................29 4.5.5 Felmerülő hibák.....................................................................................................................29 4.5.6 Zavarás ..................................................................................................................................30 4.5.7 A GPS felhasználása térképprogramok esetén ......................................................................30 4.6 TESZTELT GPS KÉSZÜLÉKEK ......................................................................................................31 4.6.1 µ-Blox MS1E GPS vevőmodul ...............................................................................................31 4.6.2 Garmin eTrex Vista készülék .................................................................................................32 4.6.3 NMEA 0183 kommunikációs szabvány ..................................................................................32 4.7 DESTINATOR 3.............................................................................................................................33 5 RENDSZERTERV ...................................................................................................................................34 5.1 5.2 5.3 5.4 5.5 5.6

A KEZDET ....................................................................................................................................34 A FEJLESZTŐI KÖRNYEZET ..........................................................................................................34 POCKET PC TESZTKÉSZÜLÉK .......................................................................................................35 AZ ELSŐ FUTÓ PROGRAM .............................................................................................................35 A .NET RÖVID BEMUTATÁSA ......................................................................................................36 ÚJ PROGRAMNYELV ÉS FEJLESZTŐI KÖRNYEZET..........................................................................37

2/107


5.7 AZ ELKÉSZÜLT GPS KÉSZÜLÉK ...................................................................................................37 5.7.1 A Pocket PC és a GPS összekötése ........................................................................................37 5.7.2 Kommunikáció tesztelés.........................................................................................................38 5.8 0. RENDSZERTERV .......................................................................................................................38 5.8.1 Nulladik rendszerterv modulljai ............................................................................................38 5.8.2 Az egyes modulok kapcsolata ................................................................................................38 5.8.3 Modulok leírása.....................................................................................................................39 5.8.3.1 5.8.3.2 5.8.3.3 5.8.3.4 5.8.3.5 5.8.3.6

5.9 5.10

Adatbeviteli modul..................................................................................................................... 39 Kapott adat értelmezése ............................................................................................................. 39 Felhasználói felület modul ......................................................................................................... 39 Térképkezelő modul................................................................................................................... 39 Adatbázis ................................................................................................................................... 39 Software frissítések kezelése...................................................................................................... 39

1. RENDSZERTERV .......................................................................................................................40 A GRÁF MODELL .........................................................................................................................41

6 GRAPHS AND SPANNING TREES ......................................................................................................44 6.1 A PROGRAMRÓL ÁLTALÁBAN ......................................................................................................44 6.2 FELHASZNÁLÓI KÉZIKÖNYV ........................................................................................................45 6.2.1 Új gráf létrehozása ................................................................................................................45 6.2.2 Gráf megnyitása ....................................................................................................................47 6.2.3 Globális beállítási lehetőségek ..............................................................................................47 6.2.4 Lokális beállítások .................................................................................................................48 6.2.5 Új gráf pont felvétele .............................................................................................................48 6.2.6 Új él felvétele a gráfba ..........................................................................................................49 6.2.7 Gráf pontok és élek módosítása illetve törlése.......................................................................50 6.2.8 Gráf tulajdonságainak utólagos beállítási lehetősége...........................................................50 6.2.9 Az aktuális súly illetve gráf pont adat beállítása ...................................................................50 6.2.10 Gráf mentése .....................................................................................................................51 6.2.11 Kapcsolatmátrix generálása .............................................................................................51 6.2.12 Legrövidebb út meghatározása Dijkstra algoritmusa alapján..........................................52 6.2.13 Szerkesztés gyorsítása.......................................................................................................53 6.2.14 Tömegesen felvett élek és gráf pontok módosítása és törlése............................................55 6.2.15 Útkeresés egyszerűbb formája ..........................................................................................55 6.3 FEJLESZTŐI DOKUMENTÁCIÓ .......................................................................................................56 6.3.1 A TObject3D osztály ..............................................................................................................56 6.3.2 A TGraph osztály ...................................................................................................................57 6.3.2.1 6.3.2.2

6.4 6.5

Algoritmusok ............................................................................................................................. 58 A TypeUnit további részei ......................................................................................................... 60

TESZTELÉS ..................................................................................................................................60 BEÁGYAZÁS A POSEIDON NAVIGATION PROJEKTBE ....................................................................60

7 FROM GAME TO MAP..........................................................................................................................61 7.1 FELHASZNÁLÓI KÉZIKÖNYV ........................................................................................................61 7.1.1 Új terület létrehozása ............................................................................................................61 7.1.2 Terület szerkesztése ...............................................................................................................62 7.1.3 Beállítási lehetőségek ............................................................................................................64 7.1.4 Terjes terület törlése ..............................................................................................................64 7.1.5 Hullámrajzolás ......................................................................................................................64 7.1.6 Útkeresés ...............................................................................................................................65 7.1.7 Prioritási sor beállítása.........................................................................................................66 7.2 FEJLESZTÉSI KÉZIKÖNYV .............................................................................................................67 7.2.1 A CTerritory osztály ..............................................................................................................67 7.2.2 Az osztály attribútumai illetőleg tulajdonágai .......................................................................68

3/107


7.2.3 7.2.4

Osztálymetódusok ..................................................................................................................69 Hullám-továbbterjesztés algoritmusa ....................................................................................70

8 GRAPHS AND SPANNING TREES MINI C# VÁLTOZAT ..............................................................73 8.1 GRAPHS .NET ...............................................................................................................................73 8.2 GRAPHPDA.................................................................................................................................74 8.3 C# OSZTÁLYOK ...........................................................................................................................75 8.3.1 CWorkFileName osztály ........................................................................................................75 8.3.2 CFileGraph osztály................................................................................................................76 8.3.3 CGraph osztály ......................................................................................................................76 9 A POCKET PC ÉS A GPS ÖSSZEKAPCSOLÁSA..............................................................................77 10 EREDMÉNYEK .....................................................................................................................................78 11 MELLÉKLETEK...................................................................................................................................80 11.1 GRÁFOK [4].................................................................................................................................80 11.1.1 Egyszerű gráf ....................................................................................................................80 11.1.2 Izomorfia...........................................................................................................................80 11.2 GRAPHS AND SPANNING TREES ...................................................................................................80 11.3 TOBJECT3D OSZTÁLY .................................................................................................................88 11.3.1 A konstansok .....................................................................................................................88 11.3.2 Típusok..............................................................................................................................88 11.3.3 Változók ............................................................................................................................89 11.3.4 Az osztály ..........................................................................................................................90 11.4 TGRAPH OSZTÁLY .......................................................................................................................91 11.4.1 A konstansok .....................................................................................................................91 11.4.2 A változók..........................................................................................................................91 11.4.3 A típusok ...........................................................................................................................92 11.4.4 Az osztály ..........................................................................................................................94 11.5 TYPEUNIT ...................................................................................................................................94 11.5.1 További típusok.................................................................................................................94 11.5.2 További eljárások illetve függvények ................................................................................95 11.6 FROM GAME TO MAP ..................................................................................................................95 11.7 GRAPHSDOTNET NAMESPACE ..................................................................................................100 11.7.1 Struktúrák........................................................................................................................100 11.7.2 CGraph osztály ...............................................................................................................104 12 IRODALOMJEGYZÉK ......................................................................................................................107

4/107


2 Előszó Jelen dolgozat a Budapesti Műszaki Főiskolai Neumann János Informatikai Főiskolai Karán készült 2004 elejétől 2006 májusáig. Az időszak elején kezdtük el mindketten (Bedők Dávid és Szirbik Ferenc) az Informatikai Automatizált Rendszerek Szakirányt, Vámossy Zoltán Tanár úr vezetésével. A szakirányt megelőzően alapvető ismereteket sajátítottunk el gimnázium illetőleg szakközépiskola alatt, valamint a főiskola első három félévében Turbo Pascal 7 valamint Borland Delphi 7 környezetben, megismerkedve az objektum orientált programozás csírájával. Tanulmányaink ezután kezdtek el rohamos ütemben gyorsulni. Továbbfejlesztettük az OOP-ben eddig megszerzett tapasztalatainkat, megismerkedtünk alapvető képszerkesztési algoritmusokkal, valamint a három dimenziós megjelenítés legegyszerűbb formáival. Programozási ismereteinket a Delphi 7 mellett Microsoft C#.net környezetben is kamatoztattuk. A Poseidon Navigation Project elnevezésű dolgozat készítése során számos hasznos, és életünk során bizonyosan hasznunkra váló ismeretet, tapasztalatot gyűjtöttünk össze. 2004. őszén a Budapesti Műszaki Főiskolán megrendezésre kerülő XXIX. Tudományos Diákköri Konferencián II. helyezést értünk el az Informatikai Rendszerek Szekcióban, majd ezen tanév tavaszán, 2005-ben az Országos Tudományos Konferencián is azonos eredményt szereztünk (Műszaki Tudományi Szekció, Alkalmazott Számítástechnika tagozat).

5/107


3 Cél meghatározása A lehető legrövidebben megfogalmazva egy PDA-ra (tenyérgépre) fogunk elkészíteni egy navigációs programot, mely GPS koordináták segítségével a felhasználó igényeinek és a közlekedési szabályoknak megfelelően „járható” utakat keres. A térképkészítésnek fantasztikus történelme van, nem véletlenül. Az embert mindig is érdekelte, hogy hol helyezkedik el a világban, és bár mindenre választ nem képes adni, egy fokkal közelebb kerül az igazsághoz, hogyha lejegyzi az eddig látott „világokat”, és azok elérését, hogy legközelebb is el tudjon jutni oda. Később aztán ezt mások is felhasználhatják arra a célra, hogy számukra idegen helyekre eljussanak, és ott eligazodjanak. Ma már ott tartunk, hogy olyan helyeket is képesek vagyunk feltérképezni, ahova eddig még ember nem jutott el, és sok olyat is, ahova képtelenség is lenne. A GPS, azaz globális helymeghatározó rendszer segítségével pontos adatot kapunk arra nézve, hogy hol helyezkedünk el bolygónk felszínén. Ezt felhasználva software-es támogatást adhatunk a felhasználó kezébe a tájékozódását segítve ezzel. Nem szükséges elemeznie a bonyolult térképeket. Számára csupán az a fontos, hogy eljusson a kívánt céljába. A program, melyet elkészítettünk, és jelen dolgozatban bemutatunk, pont ebben segít neki. Hogy mindezen támogatás mindig elérhető legyen számára, a programot egy Pocket PC-re készítjük el, mely méreténél fogva arra lett tervezve, hogy bárhol, bármikor használhassuk. A kézi-számítógépeknek több nagy csoportjuk is van, az általunk választott gépek valójában egy mini x86-os utasításkészletre épülő lebutított asztali PC-k, melyeken Microsoft Windows Mobile 2003 többfeladatos operációs rendszer futtatnak. Egy térképprogram esetében mit is jelent az a probléma, hogy útkeresés? Ismerünk egy adott pontot (kiindulási pont), ahol éppen mi állunk (GPS szolgáltatja, avagy manuálisan választható). Megjegyezzük, hogy a GPS pontossága vitatható, sőt sokszor nem is határozható meg, mivel a vevő nem lát elég műholdat, avagy azok túl közel vannak egymáshoz képest, így a látott holdak közül „kidob” a készülék párat. Ilyen esetekben software-es megoldást alkalmazunk majd. Ez azért lehetséges, mert több mint valószínű, hogy az illető annak a pontnak a közelében van, amit az elmúlt pár percben megjelölt a GPS, így a software felajánl egy közeli pontot valahol az előző koordináta, és egy kijelölt cél között, természetesen a felhasználó sebességét is figyelembe véve. Az útkeresés eme előbb említett pont és a cél pont között zajlik majd. Utóbbit vagy kijelöli az illető a térképen (rámutat), avagy beírja szövegesen, hogy mit keres. Miután a program a kérdésekkel egyértelműen beazonosított egy pontot (ami szintén szerepel a térképen) akkor az útkeresés folyamata elindulhat. Ha a térképen lévő pontokat gráf pontoknak tekintjük, akkor az útkeresés a gráf pontjai közötti utak megtalálását jelenti, amennyiben azok léteznek (egy adott térképen szinte mindig létezik út két pont között, lehetne mondani, de ez nem minden esetben van így: pl. ha valaki gyalogosan közlekedik, akkor a folyó, avagy az autópálya négy sávjának közepére nincs út. Ettől függetlenül a program egy figyelmeztetés mellett amennyiben az adott lehetőségekkel út nem létezik, keres alternatív lehetőségeket, tervünk szerint). Van egy olyan lehetőség is, miszerint a térképet grafikusan képzeljük el, és mint „képet” dolgozza fel a program. Ezt nevezzük pixeles megoldásnak. Ez valószínűleg sokkal pontosabb utat tud meghatározni, ámde felmerül ezzel olyan probléma, hogy GPS koordinátákat képtelenség minden képponthoz tárolni. Mindkét módszernek vannak előnyei, és hátrányai is, ezért talán a legjobb megoldás, ha az előnyüket kivéve egy hibrid módszer megvalósítását tűzzük ki célul. A GPS adatokat egy több szintű gráf-háló tárolja majd (több szint: minden közlekedési módszernek külön gráfháló).

6/107


Lehetőség lesz gráfok unióját is venni annak érdekében, hogy olyan esetekben is találjon a program utat, mikor egy szinten belül erre nincs mód. Mindezekre rákerül egy információgazdag grafikus felület, mely színek segítségével tárol adatokat. Ennek van egy váza, ami tartalmazza azon pontokat, amelyek minden eszköz számára megközelíthetetlenek. Ilyen például egy folyó (híd nélküli része), vagy egy ház alapja. Erre kerülnek rá a közlekedési módszerek különféle sémái. Pl. ha gyalog vagyunk, akkor azon utak jelennek meg, amik gyalogosan elérhetők, a többi út ugyanolyan akadály marad, mint mondjuk a ház alapja. Itt is lehetőség lesz arra, hogy minden felület sémát felhasználjunk, és az uniójuk szerint keressünk utat (vagy bármelyik N uniója szerint). Maga az útkeresés egy végletekig egyszerűsített modell arra nézve, hogy mi „általa” megtaláljuk „helyünket a világban”. Tervezzük, hogy térképprogramunkat felruházzuk – a lehetőségekhez mérten – számos KRESZ és gyakorlati szabállyal, ezzel is javítva a térképprogram hétköznapokban való felhasználásának eredményességét. Így az elején már csak egy dolgot kell tisztázni, hol lesz a kapcsolat a gráf és a grafikus megoldás között? A felhasználó a grafikus felületet látja, amin külön pontok jelzik azon pixeleket, melyek gráf pontok is. Útkeresésnél a felhasználó dönthet, hogy melyik út jelenjen meg, vagy rábízza a készülékre a dolgot. Valahogy így fogalmaztuk meg az ötleteinket, illetve célkitűzéseinket 2004-ben. Ezek után kezdődött a munka tényleges része, melyben természetesen a fenti célok elérésre törekedtünk, azonban néhol be kellett látnunk, hogy nem minden realizálható a mi szintünkön. A Poseidon Navigation Project fejlesztése több fázisban történt. Fél év irodalomkutatást követően elkezdtük kidolgozni a megvalósítás lehetőségeit, illetőleg elkezdtük begyűjteni a szükséges hardware eszközöket. Hardware szempontjából két különféle Pocket PC kézi-számítógéppel dolgoztunk. Mindegyiken Microsoft Windows Mobile 2003 operációs rendszer futott. Ezeken kívül természetesen szükségünk volt a GPS adatokat szolgáltató GPS készülékre, melyből szerencsére többet is tudtunk tesztelni. A hardware eszközök kommunikációját soros port segítségével oldottuk meg, kezdeti sikertelenségek és átmeneti megoldások után. A software mag fejlesztése két irányban haladt. Az egyik irány az adatok tárolását és az útkeresést tűzte ki célul. Ehhez Borland Delphi 7 környezetben készítettünk PC-n futó alkalmazásokat. A másik irány a Pocket PC-n lévő tényleges program fejlesztése volt, melyre a .net framework lehetőségeit kihasználó Microsoft Visual Studio .net C# nyelvét választottuk. A megvalósult program bár nem teljesíti mindazt, amit a cél meghatározásakor kitűztünk, de egy általunk mért térképrészleten valós időben, GPS adatokat felhasználva legrövidebb utat képes meghatározni, és megjeleníteni Pocket PC-n!

7/107


4 Irodalomkutatás Egy nagyobb munka előtt minden esetben célravezető körülnézni, hogy mások milyen megoldást alkalmaztak hasonló helyzetben. Érdemes feldolgozni ezen eredményeket, és megjelölni azon részeket, melyeket majdnem mi is alkalmazni fogunk. Nem szabad azonban figyelmen kívül hagyni, hogy törekszünk munkánk során valami újat is hozzáadni a már létező megoldásokhoz, így néhány esetben fel kell hívni a figyelmet a rendszerek és a rendszerünk különbségeire, az ebből adódó előnyökre és hátrányokra.

4.1

Az útkeresésről általában

Az útkeresés problémája az élet sok területén felmerül. Mi a játékok világán keresztül ismerjük meg kicsit alaposabban. Az útkeresés az egyik legkeresettebb mesterséges intelligencia típus a számítógépes játékokban. Sok mindentől függ, hogy egy játék jó lesz-e. Egy ilyen fontos tényező az alkalmazott útkereső algoritmus. Szerencsére ez a probléma ma már többnyire megoldott, de azért az ember nap mint nap találkozhat félresikerült alkotásokkal, melyekben nem gondolták végig, hogy ennek milyen nagy jelentősége van.

4.2

Útkeresés a játékok világában [2]

Azt a problémát járjuk körül, hogy egy játékban hogyan lehet egy adott objektumot egy másik (cél) pontba vinni. A téma így megfogalmazva, hogy egy adott pontot hogy lehet eljuttatni egy másikba, teljes mértékben a térképprogram grafikus felületébe illik, hiszen ott is ugyanez a feladat. 4.2.1 Szimulációs program: From Game to Map Az útkeresés problémájának bemutatására két szimulációs program fog elkészülni. Ezek közül az egyik a számítógépes játékokhoz hasonlóan fog működni (ennek elnevezése From Game to Map). A tervek szerint legelső verziójában egy testre, és két dimenzióban akadályokkal övezett területen ad megoldást különféle algoritmusok alapján. A következő verzió a fent leírt dolgokat „ellenségekkel” övezett területen is végrehajtja. Ellenségnek nevezzük a mozgó akadályokat. Az ezt követő verzióban már három dimenzióban szimulálva hajtom végre ugyanezt, majd a végső programban újfent előjönnek az ellenségek. Amit ebből a térképprogramba fel tudunk majd használni, az a harmadik verzió, ám roppant hasznos lehet egy jól működő végleges is, más feladatok megoldására. A „játék” szempontjából tárgyalom én is a problémát, persze ettől könnyű elvonatkoztatni. Akadályokat el kell tudnia kerülni az algoritmusnak, szintúgy ellenségeket (például autókat: ha gyalog megyünk, nem mehetünk rá az útra). És ha lehet minimalizálni kell a költségeket. Ez egy összetett kérdés, mivel adott utaknak különféle költségei lehetnek, attól függően, hogy milyen nézőpontból vizsgáljuk. Nézzünk erre egy egyszerű példát: van egy távolság, ami autópályán haladva 50 km távolságban van, de létezik egy földút is, amin haladva 20km alatt el tudjuk érni célunkat. Autópályán haladva 100 km/h-val tudunk haladni, míg földúton esetleg csak 30-al (1. ábra).

8/107


Ábra 1 Súlyozás A sok fékezés és rossz utak miatt a földúton járművünk kétszer annyit fogyaszt, mint a kényelmes autópályán. Mindezek után, ha a legrövidebb utat akarjuk, akkor a földutat választjuk, ismerve kocsink tulajdonságait, de a hosszabb autópálya a benzin, a kocsi állapota szempontjából megfelelőbb „költségekkel” rendelkezhet. Fel kell készülni arra az esetre is, hogy az objektumok – a későbbiekben nevezzük ezeket átvitt értelemben „ellenségnek” (de ide értve saját társainkat is, ha mondjuk egy stratégiai játékban gondolkozunk) – mozognak, így minden ilyen ellenség pontot újra meg kell vizsgálni minden megtett lépés után, és a legrövidebb, avagy legkisebb költségekkel rendelkező utat is újra szükséges számolni. Fontos dolog az is, hogy nehogy beragadjunk, és pár adott pont között mozogjunk oda-vissza. „Emlékezet” segítségével erre előre fel kell készítenünk algoritmusunkat. Ez a memória változó méretű lehet, tapasztalatok útján fogjuk a megfelelő mélységet beállítani. 4.2.2

Csapdák

Ábra 2 Csapda (Forrás: http://theory.stanford.edu/~amitp/GameProgramming/) A 2. ábrán szürkével jelölt területet nevezhetjük csapdának. Ugyanis a felső képen azt láthatjuk, hogy a kiinduló ponttól észleljük a célt, de mikor odaérünk, rájövünk, hogy akadály van előttünk. Amennyiben látjuk előre a teljes akadályt, avagy elérünk egy olyan pontot (detect obstacle here), ahonnan már látjuk, akkor a csapdát elkerülve sokkal rövidebb úton elérhetjük a célunkat. 4.2.3 Algoritmusok alapja Számos útkereső algoritmus a 3. ábrához hasonló gridet használ. A két dimenziós képen jelöltek a kapcsolódási pontok, azaz hogy honnan hova lehet eljutni. A gyorsabb algoritmus

9/107


érdekében ezt a módszert érdemes megfontolni, és felhasználni a térkép grafikus felületén, hogy ott sem minden pixelt veszünk figyelembe, hanem mesterségesen felosztott grid pontokat! (esetleg lehetőség van a teljesen pontos pixeles felosztásra is, ahol nemcsak derékszögű irányváltások léteznek, hanem 360 fokosak is, de nem kizárt ennek túlzott bonyolultsága és lassúsága).

Ábra 3 Grid 4.2.4 Dijkstra algoritmusa és a Best-First-Search Dijkstra algoritmusa garantálja nekünk a legrövidebb út megtalálását a start és cél pont között.

Ábra 4 Dijkstra (Forrás: http://theory.stanford.edu/~amitp/GameProgramming/) A 4. ábrán látható a kiinduló pont középen, és a kék célpont a színezett rész szélén. A kékes színek azok a területek, amelyeket az algoritmus megvizsgált. A Best First-Search (továbbiakban BFS) algoritmus ehhez nagyon hasonlóan működik, de tartalmaz számos heurisztikát, hogy pl. milyen messze van a cél. A BFS nem garantálja a legrövidebb utat, de sokkal rövidebb idő alatt talál megoldást. Az 5. ábrán a sárga pont jelöli, hogy magas heurisztikus értéke van, azaz messze van a céltól, és fekete jelöli az alacsonyat.

10/107


Ábra 5 Best first serach (Forrás: http://theory.stanford.edu/~amitp/GameProgramming/) Eddig egy egyszerű szituációt vizsgáltunk, de figyeljük meg, mi történik olyan esetben, amikor a térképen akadályok vannak: a 6. ábra felső részén Dijkstra algoritmusát, míg alsó részén a BFS-t láthatjuk.

Ábra 6 Akadályok (Forrás: http://theory.stanford.edu/~amitp/GameProgramming/) A lényeg, hogy bár a BFS egyszerű esetekben gyorsnak tűnhet, egy kis „probléma” esetén a futási idő már sokkal kevésbé szembetűnőbb, ám a megoldás „jósága” nem is hasonlítható Dijkstra útkereső algoritmusához. Nézzünk most egy olyan algoritmust, mely a fenti két megoldás előnyeit egyesíti!

11/107


4.2.5 Az A* algoritmus Az A* („A csillag”) algoritmus garantálja számunkra a legrövidebb utat, sőt, ezen kívül heurisztikákat is tartalmaz! Tehát lényegében teljesíti azt, amit fentebb írtam: előnyöket egyesít. Nemhiába ez az algoritmus a legnépszerűbb manapság. Az A* rendkívül rugalmas, és széles körben használható.

Ábra 7 A* algoritmus (Forrás: http://theory.stanford.edu/~amitp/GameProgramming/) Egy kis magyarázat a 7. ábrához: a sárga (h) szín jelöli a céltól való távolságot, a cián (g) pedig a kezdőponttól méret. N csúcs van a képen, g(n) reprezentálja az út súlyát a kezdőponttól minden csúcsra. H(n) pedig a heurisztikus értékét képviseli minden pontnak. Így a legrövidebb út f(n) előáll g(n) és h(n) összegeként.

12/107


4.3

A Hullám-továbbterjesztéses algoritmus [3]

Valójában két technikáról van szó, mely nagyon hasonló ötleten alapszik. Maga az előző fejezetben említett grid itt is létezik, és itt is hasonló elven tudjuk eldönteni az akadályok helyzetét. Ráadásul az előző fejezetben tárgyalt Dijkstra algoritmusa is ránézésre egyféle hullámterjedést mutatott be, és az is rögtön ki fog derülni, hogy az övé gyorsabban szolgáltat eredményt, mivel ott nem szükséges az egész területet előre ismerni, így szükségtelen bejárni is. Mielőtt előreszaladnánk, térjünk vissza a hullám-továbbterjesztéses algoritmusokhoz. Előre elkészítünk egy mátrixot a teljes térképre nézve. A mátrix elemei itt is bizonyos szempont szerinti heurisztikákat fognak tartalmazni. A hullám-továbbterjesztéses algoritmus egy legrövidebb utat fog megtalálni, avagy egy lehetséges ilyen utat, a legbiztonságosabb út algoritmus pedig azt az utat adja meg, ami a lehető legjobban elkerüli az akadályokat. Azon, hogy egy algoritmus heurisztikákat tartalmaz, azt értjük, hogy ráérzésre kipróbálunk egy lehetőséget a számunkra elérhető számos útból, majd ha megtéve ezt a lépést előrébb jutottunk célunk felé, akkor meghagyjuk, különben visszalépünk. 4.3.1 Legrövidebb út Nézzük, hogy is működnek ezek az algoritmusok. A 8. ábrán fogunk vizsgálódni.

Ábra 8 Térkép A célunk az, hogy a lehető legmagasabb heurisztikus értékkel rendelkező ponttól (a kiinduló pont a legmagasabb értékű, hiszen ez van a legmesszebb a céltól a mi szempontunkból!) eljussunk a legalacsonyabb pontig, a 0-ig, azaz a célig (heurisztikus értéket azonosítom a céltól való távolsággal, ami nem teljesen egyértelmű megfeleltetés). A cél távolsága a céltól 0. Az akadályokat egyel alacsonyabb értékkel jelöljük, mint a start pontot, de ennek csak az algoritmus szempontjából van lényeges szerepe (minden cellaérték a példában egy byte-os adatot képes tárolni, ezért vannak így a határok).

Ábra 9 Feltöltés

13/107


Először a hullám-továbbterjedéses algoritmust vizsgáljuk meg. Legelső lépésben fel kell töltenünk a mátrixunk még üres mezőit. A céltól fogunk elindulni, és minden szomszédos pontra feljegyezzük, hogy milyen messze van a céltól, azaz mekkora a heurisztikus értéke. Így fog kialakulni a hullámunk. Ezt mutatja a 9. ábra. Feltesszük természetesen, hogy átlósan is tudunk menni, azaz minden esetben, ha nincs akadály, nyolc irány közül választhatunk. A lehetséges út esetében nincs garantálva az, hogy ez a legrövidebb út lesz, mivel ez fog függni a konvencióktól. Az út úgy fog felállni, hogy a kiindulási ponttól elindulunk, és mindig a legalacsonyabb heurisztikus pont felé fogunk lépni. A hullám tulajdonsága miatt arra, hogy beakadjunk két pont között, nincs esély, hiszen biztos, hogy lesz legalább egy, egyel alacsonyabb pont minden mező szomszédságában. Miért is van szükség járulékos szabályokra? Előfordulhat, ráadásul elég sűrűn, hogy egy adott pontból több irányba is tudunk menni! Ahhoz, hogy egyértelmű utat tudjunk meghatározni, ilyenkor meg kell tanítani az algoritmust arra, hogy melyik utat válassza. Ezért egy prioritási sorrendet érdemes felállítani a nyolc lehetséges irány között. Erre egy példát mutat a 10. ábra.

Ábra 10 Prioritási sorrend Minél nagyobb a prioritása adott iránynak, annál túlélőbb lesz, ha dönteni kell. A 10. ábra táblázatának a függvényében fog változni maga az út is, ezért nem biztosítható, hogy a legrövidebb utat fogjuk megtalálni. Ezen prioritási kiosztásnak a lehetőségei végesek, így esetlegesen megoldás az, hogy minden lehetőségre megnézzük az utakat, és a legrövidebbet ebből ki tudjuk választani, de ez meglehetősen lassú megoldás. Esetleg ha még gyorsabb megoldást akarunk, nem alkalmazunk prioritási sort, hanem véletlenszerűen fogunk döntéshelyzetben választani. Így is biztos, hogy találunk utat a kiindulási pont és a cél között, és nincs szükség konvenciók meghatározására. A 11. ábrán a fenti prioritási sor, és a térképünk által meghatározott utat látjuk.

Ábra 11 Első megoldás Példaképpen nézzünk meg egy másik megoldást is egy másik prioritási mátrix alapján (12. és 13. ábra).

14/107


Ábra 12 Második megoldás

Ábra 13 Második prioritási sor A példából is jól látszik, hogy bár egyértelműen más utat találtunk meg, ez is tíz közbülső lépést tartalmaz. Ebből következtethetünk arra, hogy a prioritási mátrixok közötti különbség szinte mérhetetlen, így nem érdemes az összes lehetséges utat megkeresni, és kiválasztani belőlük a legrövidebbet. Még abban sincs különbség a két eset között, hogy hányszor léptünk átlósan, mindkét esetben kilencszer történt ez meg. Úgy kezdtem a hullám-továbbterjesztéses algoritmus leírását, hogy „nem biztosítja a legrövidebb utat”. Ez hamis feltevés volt, csupán azért állítottam, mert nem voltam meggyőzve arról, hogy a prioritási mátrix egy viszonylag általános esetben nem befolyásolja az eredményt. Mivel a fent vázolt algoritmusnak létezik hatékonyabb változata is, gyorsan át is térek azok tárgyalására. 4.3.2 Hullám-továbbterjesztéses algoritmus finomítása A fenti eredményeket tudjuk pontosítani, amennyiben a hullám terjedését nem nyolc irányba követjük el, hiszen így az átlós iránynak megegyező súlya van a „vízszintes”, avagy „függőleges” iránnyal. Nézzünk egy olyan példát, mikor a hullám csak négy irányban terjed (14. ábra).

Ábra 14 Négyirányú hullám

15/107


Bár az rögtön szembetűnik, hogy több súlyra volt szükségünk, mint az előző esetben, de ez nem befolyásolja az algoritmus futási idejét, és a megoldás (15. ábra) valamivel életszerűbb lesz (itt is a már sokszor használt nyolcirányú prioritási sort alkalmazva).

Ábra 15 Jobb megoldás Ebben az egyszerű példában a kapott megoldás egyetlen egy pontban tér el az első esettől, mégpedig a cél előtt két átlós lépés helyett itt két vízszintes mozgás is elég volt, ami azt jelenti, hogy rövidebb utat kaptunk! Ezek után lehet még jobban pontosítani a számításokat. Most 4+4 irányban fog terjedni a hullámunk, ahol a „vízszintes” és „függőleges” terjedés egységnyi, míg az átlós irányok – kiszámítva a négyzet átlójának méretét – 2 súlyt kapnak. Ez egy nagyon „olvashatatlan” irracionális szám, a számítógép megfelelően nagy térkép esetén nem adna elfogadható időn belül megoldást a számítások időigénye miatt (viszonyítva előző algoritmusunkhoz). Emiatt egy közelítő értékkel célszerű számolni, mondjuk 7/5-el (7/5 = 1.4 az ~1.4142 helyett)(16. ábra), melyet aztán felszorozva öttel (17. ábra) minden egyes mezőre egész számot kapunk, melyekkel a processzorok gyorsabban képesek műveleteket végrehajtani.

Ábra 16 Pontos hullám

16/107


Ábra 17 Felszorzás

Ábra 18 Pontos megoldás A megoldás (18. ábra) megegyezik az előbb kapott eredménnyel, azonban sokkal általánosabb esetben ez még pontosabb megoldást szolgáltat. Ha összeadjuk az út során érintett súlyokat, és elosztjuk 5-el az eredményt, akkor kisebb számot kapunk, mint a négy irányú hullám esetében. Ez a kapott szám a súlyokra nézve pontosabb, bár az út fizikailag nem lesz rövidebb (ebben a példában). Az első pont amire „rálépünk” 12,40-es súlyú (62/5), míg az előző esetben ez 16 volt, ami nyilvánvalóan pontatlanabb távolság érték. 4.3.3 Legbiztonságosabb út, Voronoi diagramm Nézzünk most meg egy másik hullám-továbbterjesztéses algoritmust. Ennek a lényege a legbiztonságosabb út megkeresése. Itt a fentiek alapján már nem fogunk kételkedni abban, hogy ez e a lehető legbiztonságosabb út. A módszer itt is nagyon hasonló, csak most úgy fogunk eljutni a célhoz, hogy mindig a lehető legnagyobb értéket választjuk. Ez azért lesz így, mivel most a hullámokat az akadályoktól (254-es pontoktól) fogjuk kezdeni terjeszteni, így a heurisztikus értékek az akadályoktól mért távolságot fogják jelenteni. Minél nagyobb ez a szám, annál messzebb vagyunk tőlük. Nézzük a mátrix feltöltését (19. ábra), figyelembe véve most azt is, hogy a térkép széle is akadálynak számít, így nekünk azt is a lehető legjobban el kell kerülnünk.

17/107


Ábra 19 A legbiztonságosabb út hulláma A prioritási mátrixunk legyen itt is a már megismert (10. ábra). Mindezek után a lehető legbiztonságosabb utat a 20. ábra mutatja.

Ábra 20 A legbiztonságosabb út A fenti példából egy nagyon fontos dolog hiányzik! Mégpedig az, hogy a legbiztonságosabb út keresése közben mi nem egy utat kapunk (a fenti eset kivétel), hanem egy gráfot! Egy adott utat úgy kapunk, ha ennek a gráfnak egy adott (pl. mélységi) bejárását felírjuk. A kapott eredmények közül, ha a legrövidebb utat keressük a gráfban, akkor a lehető legbiztonságosabb és legrövidebb utat fogjuk megkapni. Ezt próbálja szimulálni a 21. ábra.

18/107


Ábra 21 Másik térkép Ebben az esetben is prioritási sort használtam, az elején lévő kacifántos gráf értelmezését a 22. ábra mutatja be.

Ábra 22 Ábra pontosítása De ha gráfokról van szó, akkor nincs is szükség itt most prioritási sorra! Jól látszik, hogy a térképen lefelé haladva is van egy hasonlóan biztonságos út, azt mi mégsem találtuk meg. A 23. ábra ezen pontosításokat mutatja.

Ábra 23 Prioritási sor nélküli megoldás Az így kapott gráfból bármely bejárással a legbiztonságosabb utat írhatjuk fel. A színekkel azért jelöltem az egyes lépéseket, hogy egyértelmű legyen, hogy a 255-ös mezőből gráf él csak a kettes mezőhöz vezet, így onnan nem is mehetünk egyik egyesre sem a gráf bejárása során. A keletkezett gráfot a 24. ábra mutatja be.

19/107


Ábra 24 A keletkezett gráf Egyetlen egy járulékos szabályt vezettem be a gráf háló felépítése közben: amikor egy pontra nézem a szomszédokat, hogy adott pontból merre lehet továbbhaladni, akkor két változat létezik: - Van olyan pont, amin még nem jártam. - Nincs olyan pont, amin még nem jártam. Az első esetben a szabályom az volt, hogy ilyen esetben minden olyan ponthoz tartozik él, amin még nem jártam, és amin már jártam, ahhoz nem tartozik. A második esetben pedig minden olyanhoz vezet él, amin már jártam. A fenti járulékos szabályok bevezetésével a legrövidebb, legbiztonságosabb utak mindegyikét meg lehet határozni (megjegyzem, hogy a járulékos szabályokra biztosan más lehetőség is van, hogy hasonló eredményt kapjunk). 4.3.4 Megjegyzések A fent ismertetett legbiztonságosabb út megkeresésére biztosan létezik másféle algoritmus is, itt csak azért említettem meg, mert hasonlóan működik a legrövidebb utat szolgáltató algoritmushoz. 4.3.5 Implementálás Kicsit rátérek arra, hogy ezen algoritmusok miképpen építhetők be működő programokba. Felmerül a kérdés, hogy minden esetben szükségünk van-e arra, hogy a teljes térképet előre „kiszámoljuk”. Én úgy vélem nincs. Dijkstra algoritmusa alapján addig terjesztjük a hullámunkat, amíg a hullám egyik pontja el nem éri a kiindulási pontunkat (255). Ezek után az út keresése már egyértelmű. A hullám terjedését kell még modelleznünk. A pontos specifikáció a From Game to Map elnevezésű szimulátor program leírásában megtalálható.

20/107


4.4

Gráfok

Az ábrázolt térképünk adatai alapvetően GPS koordinátákból fognak adódni. Ezen három dimenziós koordinátákat néhány mért adat segítségével arányosan számolni is lehetséges „kis területű” térképek esetén. Mi is képesek leszünk mérni ilyen adatokat, mivel a programunk teszteléséhez olyan kis területet választunk ki, melynél a Föld geoid alakúsága nem számottevő, illetőleg a domborzat megközelítőleg sík! Miután az adataink rendelkezésre állnak, a következő felmerülő probléma ezen adatok tárolási módja. Egy olyan adatszerkezetet volt érdemes választanunk, melynél az adatok egymáshoz viszonyított kapcsolata is könnyedén tárolható. Így kézenfekvő volt a gráf adatszerkezet választása (természetesen a térképprogramok nagyon nagy százaléka is gráf alapú tárolással dolgozik). Gráfnak tekintünk véges sok pontból (csúcsból) álló halmazt, melyek vonalakkal, ún. élekkel vannak összekötve. A matematika nyelvén megfogalmazva mindezt: G(V,E) gráf egy rendezett pár, ahol V egy nem üres halmaz, a pontok halmaza, E pedig a V halmazból képzett pont-párok egy halmaza. Ez utóbbit az élek halmazának nevezzük [4]. Sokféle gráf létezik, egy térképprogram esetén azonban nekünk egy súlyozott és irányított, összefüggő gráfra lesz szükségünk. A teljesség igénye nélkül a következő alap gráf típusok léteznek: - Egyszerű gráf - Irányított gráf - Súlyozott gráf - Irányított és súlyozott gráf Minden típusból létezik összefüggő, és nem összefüggő is. Irányított gráfnak azt nevezzük, mikor az élek E(G) halmaza rendezett párok egy halmaza. Térképprogram esetén a gráfnak nem feltétele a hurokmentesség, és tartalmazhat többszörös éleket is. Néhány speciális esetben a gráf összefüggősége is megbomolhat. A gráfokkal kapcsolatos pár további definíció a dolgozathoz tartozó mellékletek között megtalálható. Az irodalomkutatás szempontjából a gráfok ábrázolását, és tárolását vizsgáljuk meg. 4.4.1 Gráfok ábrázolása Erre is többféle módszer létezik, és a legtöbb esetben függ a gráf típusától. Nézzünk először egy egyszerű gráfot, amit statikus adatstruktúrával tárolunk (nagyon redundáns megoldás). A kapcsolatmátrixszal történő tárolást a 25. ábra mutatja.

Ábra 25 Kapcsolatmátrixos ábrázolás Talán jól látszik az ábráról pár dolog: - Egy adott i, j a mátrixban I (igaz) vagy H (hamis) érétket vehet fel. - Adott i, j igaz lesz, ha i és j között létezik él.

21/107


- A főátlón lévő értékek mindig hamisak, amennyiben a gráfban nincsenek hurok élek. - A statikus mátrix a főátlóra szimmetrikus. Lehetőség van dinamikus tárolásra is, ezt a 26. ábra szemlélteti.

Ábra 26 Szomszédsági lista Ezt a tárolási formát nevezik szomszédsági listának. A harmadik lehetséges módszer nagyon hasonló az előzőhöz. Egy teljesen dinamikus struktúra, melynél a statikus mutató vektort felváltja egy olyan dinamikus adatszerkezet, mely elemeinek két mutató mezeje van. 4.4.2 Súlyozott és irányított gráf tárolása Tegyük fel, hogy az új gráfunk súlyozott és irányított, vannak benne többszörös élek. Ekkor a kapcsolatmátrixát a 27. ábra prezentálja (a gráf ábrája nem méretarányos).

Ábra 27 Súlyozott, irányított gráf Ami látszik a kapcsolatmátrixról: - Megszűnt a szimmetria az irányítottság miatt. - Csak ott szimmetrikusak az értékek, ahol többszörös él van. - Ott, ahol nincs él, ott 0 szerepel. Térképprogram esetén minden egyes gráf pontban minimálisan három értéket fogunk tárolni: két koordinátát, valamint egy tengerszinttől mért magasságot (GPS szolgáltatja mindegyiket). A súlyokat egy segédprogram fogja kiszámítani, figyelembe véve mind a három értéket. Az irányítottság adataira meg kell tanítani majd a programot (pl. egyirányú utca).

22/107


4.4.3 Minimális költségtérítésű feszítőfa A feszítőfa fogalma: Egy G gráfnak egy másik F gráf feszítőfája, ha F tartalmazza G összes pontját, további pontokat nem tartalmaz és G élei közül annyit tartalmaz, amennyi F-et összefüggővé teszi, de F körmentes (fa). A minimális költségű feszítőfa fogalma: Egy G gráf minimális költségű feszítő fája az a fagráf, amely feszítőfája G-nek, és G összes lehetséges feszítőfája közül éleinek összes hossza a legkisebb (elképzelhető több megoldás is). 4.4.3.1

Algoritmusa

Megjegyzések: NEMÉRINTETT Az az érték, amely jelzi, hogy egy adott pontot a bejárás során már érintettünk, vagy sem. Kezdetben Érintett() vektor minden eleme ezt tartalmazza. Életbeilleszt (G,x,y) A G gráfba az x,y pontok közé élet illeszt be. VanRövidebb (Sor,a,b,Volt) Megvizsgálja, hogy szerepel-e az „a” pont a prioritási sorban, ha igen, akkor megvizsgálja, hogy a „b” súlynál nagyobb-e az ott szereplő pont súlya. Ha igen, akkor kicseréli ezt a pontot az „a” pontra, amelynek „b” a súlya. Ha a sor így módosul, akkor ’Volt’ igaz lesz.

23/107


4.4.4 Legrövidebb út [5] A legrövidebb út fogalmát kétféleképpen értelmezhetjük: A kiindulópontból a végpontig milyen úton kell haladnunk, hogy kevesebb csomóponton lépjünk át, mint bármely más úton? Ennél a feladatnál akár súlyozatlan, akár súlyozott, kezelhetjük úgy a gráfot, mintha éleinek hosszúsága (súlya) egységnyi lenne. A kiindulópontból a végpontig milyen úton kell haladnunk, hogy az utat alkotó élek összes hossza kisebb legyen, mint bármely más út esetén? Ez a feladat természetesen súlyozott gráfot feltételez. Egyértelműen látszik, hogy a második eset sokkal általánosabb, ráadásul a térképprogramhoz is ez van közelebb, így ezzel foglalkozok a továbbiakban. A probléma megoldására számos algoritmust dolgoztak ki. Ezek közül alapvetőnek számít Dijkstra 1959-ben közölt algoritmusa, ezért itt is ezt ismertetem. 4.4.4.1 Az algoritmus lényege Lássuk el a gráf minden pontját egy címkével, amely a következő adatokat tartalmazza: a pillanatnyilag ismert legrövidebb úton az adott pont milyen távolságra van a kiindulóponttól (kezdetben legyen ez az adat minden pont esetén végtelen nagy) az adott pontnak melyik az a szomszédos pontja, amely felől haladva az előbbi távolságot kaptuk Egy csomópont címkéje kétféle lehet: ideiglenes: még lehetséges, hogy más irányból rövidebb utat is találunk hozzá a kiindulópontból állandó: a kiindulópontból már minden hozzá vezető utat megvizsgáltunk, s rövidebb út nem lehetséges Az algoritmus lényege az, hogy meghatározzuk minden pont legrövidebb távolságát a kiindulóponttól számítva, s mivel minden pont címkéje tartalmazza azt is, hogy ezen úton melyik pont előzi meg, a végponttól visszafelé haladva meghatározhatjuk a két pont közötti legrövidebb utat. Nézzük ezt most egy példán keresztül (28. ábra).

24/107


25/107


Ábra 28 A legrövidebb út algoritmus 4.4.4.2 Az algoritmus részletesebben 1. Inicializáljuk a gráf-pontok legrövidebb útjait tároló adatszerkezetet. 2. Az aktuális pont legyen a kiinduló pont 3. Járjuk be az aktuális pont minden ideiglenes szomszédját (szélességi bejárás). Ha találunk olyan szomszéd pontot, amelyhez az aktuális pont felől rálépve rövidebb úton jutnánk el a kiinduló ponttól, mint a címkében rögzített korábbi irányból, akkor e pont címkéjét módosítjuk. A módosítás: a kezdőponttól mért távolságnak beírjuk az új irányból mért távolságot, a megelőző pont helyére pedig az aktuális pontot. 4. A gráf összes ideiglenes címkéjét megvizsgálva kiválasztjuk azt a pontot, amely az ideiglenesek közül a legrövidebb úton érhető el a kezdőpontból, vagyis azt, amelyiknek a címkéjében a hosszúság értéke a legkisebb. E pont címkéjét véglegesre állítjuk, ezzel jelezve, hogy e ponthoz nem vezethet a már bejegyzettnél rövidebb út. 5. Legyen most az így kiválasztott pont az aktuális. 6. Ismételjük a 3. résztől a műveletet egészen addig, amíg az aktuális pont azonos nem lesz a végponttal. 4.4.4.3

Az algoritmus pszeudokódja

26/107


A fenti algoritmusban ’A’ jelöli a gráf kapcsolatmátrixát, ’N’ pedig a gráf pontjainak számát. 4.4.4.4 Szimulációs program: Graphs and spanning trees A gráf témakörébe számos algoritmus tartozik: bejárások, keresések, az eddig ismertetett algoritmusok valamint ezek továbbfejlesztése. A Graphs and spanning trees nevű alkalmazás ezen eljárásokat fogja össze, teszteli, valamint a gráfok elkészítésért is felelős lesz. 4.4.4.5 Megjegyzések A példákban úgy szerepeltek a súlyozott gráfok, hogy minden élnek a súlya meghatározta az él által összekötött két gráf-pont távolságát. Ez mindenképpen fontos dolog, mindenképpen tárolva is lesz a térképprogramban, hiszen így lehet majd arányosan ábrázolni a térképet. Ezen felül minden egyes élnek lesz más súlya is! Például lesz egy olyan számérték, ami azt határozza meg, hogy az úton milyen gyorsan lehet közlekedni. Például az autópálya kap egyes értéket, adott földút pedig 5-öt (a maximálisan megengedett/lehetséges haladási sebesség reciprokával arányos számok). Így amikor a felhasználó legrövidebb utat keres, a program különféle utakat fog neki javasolni, és megmondja, hogy melyiket milyen célra szánta (legrövidebb út, legrövidebb idő alatt megtehető út, csúcsforgalmat elkerülő út, közlekedési lámpákat elkerülő út, stb…).

27/107


4.5

Globális helymeghatározó rendszer [6]

Ma olyan korban élünk, mikor a technika vívmányai, eredményei a médián keresztül, mint szenzáció, mindenki számára elérhetővé válnak. Ez az alfejezet a GPS technikai részleteit vizsgálja, melyek kevésbé ismertek a felhasználók körében. Mielőtt a GPS kisebb-nagyobb részleteit bemutatnám, azért azt meg kell jegyezni, hogy nem ez az egyetlen navigációs eszköz manapság. Oroszország a GLONASS-t (Global Navigation Satellite System), míg Európa az EGNOS-t (European Geostationary Navigation Overlay System) üzemelteti. Ráadásul együttes használatukkal még pontosabb eredmény érhető el! 4.5.1 Egy kis történelem A GPS-t ma már használják pontosabb térképek készítésére, földmérésre, és természetesen a legszélesebb körben mozgó járművek navigálására, de ez nem mindig volt így. Mint elég sok minden, ez is katonai célokból jött létre, ma azonban gyakorlatilag mindenki számára elérhető, és ingyenes! Az Amerikai Védelmi Hivatal indította kifejlesztését, egyértelműen katonai, hadászati célokból. Bár maga az ötlet fantasztikus, a megvalósítása szinte lehetetlen! Egy helymeghatározó készüléknek elsősorban pontosnak, gyorsnak, kicsinek, bárhol, bármikor elérhetőnek kell lennie. Jelenleg a GPS az, ami a felsorolt követelményeket a lehető legjobban teljesíti. Pár száz évvel ezelőtt iránytűkkel, szextánssal, térképpel, egy órával, vonalozóval valamint kis hozzáértéssel lehetett mindazt elérni, amire ma sokkal gyorsabban szakértelem nélkül is bárki képes. Például tengerpartok mellé világítótornyokat építettek, építenek (!), melyekben egy körbe forgó lámpa segítségével lehet meghatározni az északi irányt. 4.5.2 Mai helyzet Szerencsére nekünk már egyszerűbb dolgunk van. Csupán 24 darab Block II-es műholdat kellett fellőnünk 20240 km magasságba világítótornyok építése helyett. Ezen holdak neve NAVSTAR, és a Rockwell International gyártotta őket. Súlyuk az űrben mérve 862 kg, nyitott napelemekkel 5,2 méter hosszúak. Tizenkét óra alatt kerülik meg a Földet, tervezett élettartamuk 7,5 év. A jövőben majdan 21 darab Block II Martin Marietta műholdat fognak kilőni. Sajnos nem elég e műholdakat körülbelül elhelyezni, majd otthagyni. Nagyon pontos koordinátákon kell mozogniuk, hiszen így tudunk majd a Földön is pontos eredményekhez jutni (egy TV műhold esetében ekkora pontosságra nincs szükség). Sajnos az űrben e műholdak ütköznek kis törmelékekkel, érik őket egyéb természeti jelenségek (Nap gravitáció, napszél nyomása, stb.), melyek miatt változtatják pályájukat. Hogy ilyenkor korrigálni lehessen a hibát, öt földi követő állomást építettek fel: Hawaii-on, Ascension Island-on, Diego Garcia-án, Kwajalein-en és Colorado Springs-en. Az állomások módosító jeleket küldenek a műholdaknak, melyek ezt figyelembe véve a vevők felé is elküldik az igazítást. 4.5.3 Pozíció meghatározás Ezek a készülékek nekünk "összesen" annyira elégendőek, hogy a műhold és a vevő távolságát meg tudjuk határozni. Ezzel az átlag ember nem tudna mit kezdeni, kapna egy húszezer körüli értéket, de ha már több műholdról van ilyen adatunk, akkor a vevőbe épített kis számítógép meghatározza helyettünk az eredményt. Ha egy hold adatait fogjuk (X távolságot), akkor abból annyi információt tudunk, hogy egy X sugarú gömbön helyezkedünk el valahol. Ha már két távolságunk van, akkor két gömb metszéspontjain állunk, ami egy kör (vagy egy pont), így már lényegesen pontosabb adatunk van. Minél több a látott műholdak száma, annál pontosabb lesz helyzetünk meghatározása. A holdak úgy vannak elhelyezve, hogy elvileg a Földön bárhonnan öt holdat láthatunk! (Ez áll a GPS

28/107


vezértervben, melyet 1994. márciusában, a 24. műhold fellövése után adtak ki.) Ha három holdról kapunk távolság-információt, akkor már csak két pont között kell döntenie a vevőnek, és általában ilyen esetben az egyik pont vagy nagyon a felszín alatt, vagy felszín felett van, így könnyen kizárható. Ha nem lehet kiszűrni, akkor a negyedik műhold adatiból már csak az a pont jöhet szóba, ahol állunk. Ahhoz, hogy távolságot tudjunk mérni, nagyon pontos időmérő eszközre van szükségünk mind a műholdakon, mind a vevőn (a rádiójel futási idejét kell mérni, ami 300 000 km/h sebességű). Minden egyes műholdon egy atomóra üzemel, mely szinkron jeleket küld a vevők felé, hogy a vevők órája is teljesen pontos legyen. Ha épp a fejünk felett található a műhold, akkor 0,06 másodperc az az idő, amit mérnie kell a műholdnak, ezért van szükség az atomórára. De ettől még nem kapnánk pontos megoldást! Egyszerre kell tudnia az eredményt mind a vevőnek, mind az adónak, de ahhoz, hogy ez megtörténhessen, szintén rádiójelekkel kell kommunikálniuk és ez sajnos időbe telik. Az adó és a vevő közötti késleltetés meghatározásával ki tudjuk számolni a pontos távolságot. Ehhez a vevőt késleltetett üzemmódba kell állítani, mikor is a vevő szinkronba állítja a kapott két jelet (Ezt egy ál-véletlen kód segítségével teszi meg (pseudo random code), és ez azért is jó megoldás, mert így az összes műhold egyetlen frekvencián képes kommunikálni, ráadásul még a gyenge jelek erősítésére is használható!). 4.5.4 A kommunikáció A NAVSTAR műholdak két vivőfrekvenciát használnak a kommunikációra, az L1-t és az L2t. Az előbbi 1575,42 MHz-en szállít üzeneteket, és a szinkronizáláshoz szükséges álvéletlen kódot, az utóbbi pedig 1227,60 MHz-en sokkal pontosabb, katonai ál-véletlen kódot tartalmaz (erre még visszatérünk majd). Minden egyes műholdnak saját ál-véletlen kódja van, így tudjuk egyértelműen azonosítani az adót. A polgári GPS C/A kódot használ (Coarse Acquisition), míg a katonai P (Precise) kódot. A P kód sokkal pontosabb, 266,4 naponta ismétlődik. Minden héten vasárnap éjfélkor (GPS hét kezdete) egy kód generálása megtörténik, mely modulálja mindkét vivőfrekvenciát, de ezt katonai célok miatt titkosították (a titkosított P kódot nevezzük Y kódnak). Sok esetben a P kód meghatározása sokkal bonyolultabb, ezért katonai alkalmazás során is először C/A kódot kérnek, majd utólag térnek át P kódra. A P kód körülbelül tízszer pontosabb, és sokkal ellenállóbb a zavarokkal szemben. 4.5.5 Felmerülő hibák Előfordulhat, hogy a műholdak óráit nem sikerül szinkronba állítani. Ekkor egy kis geometria segítségével mégis meg tudjuk határozni a pontos helyzetünket. Hogyha az órák nincsenek szinkronban, akkor három távolságinformációból a két pont helyett hatot kapunk, mely két hármas csoportra oszlik, és a csoportok egy kis háromszöget alkotnak. A vevő számítógépe nem tesz mást, csak olyan ál-méréseket (pszeudo-méréseket) végez, mely kihozza azt az állapotot, hogy csak két pontunk legyen a hat helyett (a fenti példánál maradva). A vevő ezután a többi mérésre is ezt az igazítást fogja alkalmazni. Sajnos azonban felmerülnek olyan hibák is, amiket nem ilyen egyszerű kiküszöbölni. A rádiójelnek át kell haladnia az ionoszférán és a troposzférán is. Az ionoszféra a Föld légkörének 50-500 km-ig terjedő része. Itt ionizált részecskék vannak, melyek a rádiójelben geometriai töréseket idéznek elő, így a mért idő nem fog megegyezni a távolsággal! Ennek kiküszöbölésére matematikai modelleket alkotnak, mely a fellépő hibákat kompenzálja. A troposzféra a földi légkör alsó 50 km-e, elektromosan semleges, telített vízgőzből áll. Hőmérséklete és légnyomása változó, viszonylag kisebb hibát okoz, de ezzel is számolnunk kell a pontos eredmény érdekében. A matematikai modellezés lényege, hogy a tipikus légkör alapján megjósolják, hogy adott napon hogyan fog törni a rádiójel. Ebben a gond csak az, hogy tipikus légkör nem létezik. A GPS vevőnek figyelnie kell azt is, hogy milyen szögben lépett a légtérbe az adott jel, hiszen más és más hosszúságú utat tesz meg a rádióhullám az alsó 500 km-en ennek függvényében (és ezt felhasználja a matematikai

29/107


modell során). Egy másik módszer a két különböző frekvencián való mérés, és ebből a hiba korrigálása, de ezt ma még csak a fejlettebb készülékek tudják, ráadásul a polgári készülékek nem képesek az L2 jeleit fogadni! És még mindig nincs vége a váratlan hibáknak, melyek a kapott helyzetünk pontatlanságát és esetleges eltévedésünket segítik elő. A Föld felszínéről a jelek visszaverődnek, és ez azt eredményezi, hogy a vevő egyszerre kap sok különböző eredményt, tehát el kell dönteni, most melyik volt az, amelyik nem visszaverődés útján érkezett (ez olyasmi, mint televízió esetén a szellemkép). A tervezett, ideális működés esetén a GPS jel a műholdtól a vevőig egyenes vonal mentén terjed. Az eddig elsoroltak után mi már nem élhetünk álomvilágban, ezért léteznek ma már olyan vevők, mely a kapott jelek közül képesek kiválasztani a közvetlent, azaz amelyik nem verődött vissza sehonnan (persze az ilyen készülékek drágábbak). Már volt szó arról is, hogy kaphatunk jeleket nagyon nagy beesési szöggel (ilyenkor az ionosz- és troposzférában hosszabb utat tesz meg a jel). Ha két ilyen holdról kapunk távolságadatot, akkor előfordulhat, hogy nem egy pont lesz a metszés, hanem egy tekintélyes felület, mely akár több tíz méter is lehet! Ennek angol elnevezése Geometric Dilution of Precision (GDOP). A vevő rendelkezésére áll azon holdak adatai, amelyeket lát, de nem fogja minden esetben az összest felhasználni! Ha két hold közel van egymáshoz, akkor ettől csak pontatlanabb lesz az eredmény, így az egyiket "eldobja". 4.5.6 Zavarás Sajnálatos módon a GPS jeleit mesterségesen is zavarják, mivel a polgári GPS mindenki számára elérhető, így valamilyen módon védekezni kell a terroristák, ellenséges erőkkel szemben, nehogy a GPS-t fel tudják használni támadásaik során. Ezt a zavarást SA-nak nevezik (Selective Availability, szelektív hozzáférés), és abból áll, hogy hibás pályainformációkat küldenek fel a műholdaknak. Ezzel az SA lett a legnagyobb hibaforrás az egész rendszerben. 1996-ban az Egyesült Államok kormánya úgy döntött, hogy 2000ben majd felülvizsgálja a szelektív hozzáférés szükségességét, és 2000. május 2.-án Clinton elnök megszüntette a GPS jelek szándékos zavarását. A pontosság ezzel tízszeresére nőtt, és körülbelül innentől éli fénykorát a GPS technológia. 4.5.7 A GPS felhasználása térképprogramok esetén Azonnal gondolhatnánk, hogy ezek után térképet könnyen tudunk készíteni, és pontossága kellően magas mérésszám esetén fantasztikusan jó lesz! Azért figyelembe kell venni néhány apróságot. A térképek készítésekor csalnak a térképészek, mivel a Föld felszíne nem 2D-s, mégis ki kell feszíteni egy felületre. A GPS koordinátákból összerakott térképpel ezt nem lehet megtenni ilyen módon! A PDA-k segítségével ellenben nem akadály a 3D-s térkép készítése, és a lehetőségek itt messze nem érnek ezzel véget...

30/107


4.6

Tesztelt GPS készülékek

Az útkeresés kiindulási koordinátáját egy GPS készülék segítségével határozza meg az Poseidon Navigation Project. Ezekkel az eszközökkel, szaktársam Szirbik Ferenc foglalkozott, a részletek az ő dolgozatában ovashatóak. 4.6.1 µ-Blox MS1E GPS vevőmodul Két készülék tesztjével foglalkozott. Első lépésként egy µ-Blox MS1E GPS vevőmodult használt fel, és rakott össze belőle egy soros porton keresztül PC-vel kommunikáló GPS készüléket.

Ábra 29 A SiRFStar architektúra elvi felépítése (Forrás: Patrik Eggenberger (µ-Blox Corp.): ’µ-Blox PS1E GPS Reciever Module Datasheet’, [GPS. G1-PS1-00002-B]) A készülék soros porton keresztül kommunikál egy asztali számítógéppel, de ugyanerre nem képes egy Pocket PC esetén. E probléma megoldására egy összekötő elektronikát is épített szaktársam.

Ábra 30 Összekötő elektronika

31/107


(Forrás: Steven D. Wormley: http://www.wormley.com/axim/) A GPS készülékek többféle jelet küldenek a vevők részére. Ezek egyike az NMEA 0183-as kódolású adat, melyet a mi alkalmazásunk is felhasznál a pontos három dimenziós koordinátáink meghatározásához. 4.6.2 Garmin eTrex Vista készülék Második teszt készülékünk egy teljesen felhasználóbarát kézi GPS vevő volt, mely beépített térképpel, útvonalkövetéssel, és egyéb hasznos tulajdonságokkal rendelkezik (természetesen nagy LCD kijelzője van). Ez a készülék is soros porton keresztül kommunikál számítógépekkel, és szintén ismeri az NMEA 0183-as protokollt. 4.6.3 NMEA 0183 kommunikációs szabvány Egy általánosan elfogadott szabvány az NMEA 0183, amit minden GPS készülék ismer. Az adatokat karaktersorozatok, más néven mondatok formájában lehet lekérdezni. Minden mondat ’$’ jellel kezdődik, és a (<Soremelés>) jelekkel záródik. Általánosságban három mondatfajtát különböztetünk meg: ’Talker sentences’ – közlő mondatok, ’Proprietary sentences’ – gyártóspecifikus mondatok és ’Query sentences’ – lekérdező mondatok. A további részletek Szirbik Ferenc dolgozatában olvashatóak.

32/107


4.7

Destinator 3

A Destinator 3 egy hasonló képességekkel bíró program, mint amit mi is meg fogunk valósítani, így érdemesnek tartottuk arra, hogy végignézzük, mit is tud pontosan. Egy külső – PC-re telepíthető – alkalmazással tudunk térképeket feltölteni Pocket PC-re. A tesztelt verzióban Magyarország térkép volt. A programot autós használatra tervezték és természetesen felhasználja a GPS jeleit a navigáláshoz. A vezetőt tájékoztatja arról, hogy hol, merre kell lefordulnia az útról. Ezen kívül figyeli a jármű sebességét is, és felhívja a figyelmet arra, ha a felhasználó túllépte a megengedett sebességhatárt.

Ábra 31 Destinator 3 Lehetőség van metrikus, és nem metrikus mértékegység kiírásra, betűtípus beállítására, és hogy mik jelenjenek meg a térképen (fák, távolságok, stb.). Be lehet állítani, hogy a térkép a haladási iránnyal együtt forogjon-e, vagy sem, közelítsen-e menet közben, vagy sem. Útvonal tervezéséhez kétféle lehetőséget ad: meg tudja határozni a legrövidebb, és a leggyorsabb utat! Be lehet állítani, hogy milyen hangutasításokat adjon a program (pl.: vezessen óvatosan, túllépte a sebességhatárt, stb.). Lehet a felhasználói felülethez sémákat illeszteni. Lehet útvonalat felvenni, és később többször is megtekinteni. Többféle nézetet támogat a program. Lehetőségünk van 2D-s, 3D-s és madártávlatos nézőpontra is. Megadhatjuk, hogy a térképen nappali, avagy éjjeli színeket akarunk-e látni, valamint menüből tudunk betölteni új ország térképet. Összefoglalva egy nagyon hasznos alkalmazás, a világ számos országában használják navigálási célokra.

33/107


5 Rendszerterv 5.1

A kezdet

Az olyan térképprogramot, mely GPS támogatással rendelkezik, nincs értelme elkészíteni PC-re, mindenképpen Pocket PC-ben, vagy PALM-ban kell gondolkodni. Mi ettől függetlenül mindkét platformra megvalósítjuk, ráadásul két különböző nyelven! És hogy mindezt miért? Hogy eredményt tudjunk felmutatni, és hogy tudjuk tesztelni algoritmusainkat már a kezdeti stádiumban is. Amint egy stabil verzió futni fog a PDA-n, felhagyunk a PC-s verzió továbbfejlesztésével.

Ábra 32 Pocket PC emulátor PC-n A munkát párhuzamosan kezdjük két platformon, két nyelven. PC-re Borland Delphi 7 rendszerben dolgozunk, és elkészítünk egy saját készítésű Pocket PC emulátort, mely a mi térképprogramunkra lesz kihegyezve. A választott PDA ezek után a Pocket PC, és azon is Windows Mobile 2003 operációs rendszer. Ez az op. rendszer a Pocket PC 2002 utódja, sokan Pocket PC 2003-nak is nevezik, épp e miatt (Megjegyzem, hogy hivatalosan mind a Pocket PC 2003, mind a Windows Mobile 2003 név létezik, a legvalószínűbb oka ennek az, hogy két különböző verzióról van szó. A továbbiakban én a WM2003-at fogom használni, és mindkét rendszerre értem az így elhangzottakat.). A két rendszer nem kompatibilis egymással! A 2003 utasításkészlete sok helyen eltér a 2002-étől. Ez azt jelenti, hogy lehet olyan programot találni, ami mindegyiken elfut, de stabilan mindegyiken csak az működik, amelyiket az adott rendszerre optimalizáltak. Természetesen a WM2003 verziót is PC-n írjuk, az erre megfelelő programok segítségével. A fordítást pedig ott is két platformra végezzük el: egy PC-s emulátor program számára és egy Pocket PC számára. A kettő különbözik egymástól, de csak a fordításnál kell beállítani, így a kód ugyanaz marad. Tehát összefoglalva: három verziót készítünk: az egyiket Delphi 7 nyelven írjuk, és ez az algoritmusok tesztelésére szolgál, a másodikat egy PC-s Pocket PC emulátor számára, melyen WM2003 rendszer fut, hogy ott is lehessen tesztelni a programot, ahol nincs kéznél Pocket PC, valamint megvalósítjuk Pocket PC valós hardware-re is, hogy használni lehessen!

5.2

A fejlesztői környezet

A Borland Delphi 7 rendszere elég jól ismert programozó körökben, nincs szükség arra, hogy ezt részletesebben bemutassuk itt (http://www.borland.hu). Ami érdekesebb lehet, az

34/107


a másik fejlesztői környezet: Microsoft eMbedded Visual C++ 4.0. Ennek segítségével WM2003-ra lehet programokat írni C++ nyelven. Ahhoz, hogy működjön a fenti fejlesztői környezet, jó pár kiegészítőre is szükségünk van. Szerencsére a Microsoft ehhez nagy támogatást ad a http://www.microsoft.com/ downloads/search.aspx?displaylang=en Internetes oldalon (a magyar oldalon sajnos lényegesen kevesebb program érhető el). Ezen kiegészítők nagy része ingyenes, egyedül az eMbedded Visual C++-hoz van szükség sorozat számra. Ahhoz, hogy feltelepítsük a fejlesztői felületet, szükségünk van Windows CE Manager programra (Windows CE az összefoglaló neve a Microsoft által Pocket PC-re gyártott operációs rendszereknek). Ezt az eMbedded automatikusan feltelepíti, amennyiben még nincs a gépünkön. Mindezek után fel kell telepíteni a Microsoft eMbedded Visual C++ Service Pack 3-at, mivel csak így képes kezelni az emulátor programot. Mivel emulátorunk még ettől nincs, ezt is fel kell telepíteni: Microsoft Pocket PC 2003 SDK. Végül a Windows Mobile 2003 Second Edition Emulator Images for Pocket PC – WWE-t kell felraknunk a gépünkre. Ha mindezzel elkészültünk, akkor már semmi nem akadályoz bennünket abban, hogy Pocket PC-re alkalmazásokat fejlesszünk. A fent felsorolt programok az MS Windows letöltés oldalán megtalálhatóak.

5.3

Pocket PC tesztkészülék

Sajnos a Pocket PC-k processzora sem egyezik meg teljesen, ezért mikor lefordítjuk a programot, ezt figyelembe kell vennünk. Tesztkészülékünk egy Mitac Mio Digiwalker 339es PDA, Intel PXA255 400Mhz-es ARMv4-es processzorral. Ebből az ARM v4 a fontos nekünk, ilyen rendszereken fog működni a térképprogramunk.

Ábra 33 Mitac Mio 339

5.4

Az első futó program

Nagyon nehéz elkezdeni valamit tervezni, amennyiben nincs kézzelfogható „bizonyíték” arra, hogy reális időn belül meg is tudjuk azt valósítani. Ezért elkészítettünk egy teszt programot, mely egy a fejlesztői környezetbe beépített „Hello világ” programot tartalmaz, kisebb módosításokkal. Az elkészült „programot” mind emulátorra, mind ARM processzorra is lefordítottam, és teszteltem működését.

35/107


Ábra 34 Első futó program

5.5

A .NET rövid bemutatása

A Microsoft 2002. február 13-án hivatalosan is bejelentette a .NET fejlesztési platformot, valamint kiadta a Visual Strudio .NET-et. A 35. ábra Nacsa Sándor (Microsoft Magyarország) és Dr. Charaf Hassan előadásán készült kép egy egyszerűsített változatát mutatja be.

Ábra 35 A .NET fejlesztési platform A 35. ábra architektúrálisan futtatási szempontból, kliens-szerver alapokon keresztül mutatja be a .NET fejlesztési platformot. A „Windows Forms”-ok prezentálják az ábrán a

36/107


már a Visual Studioban eddig is megszokott formok egyszerű tervezését és készítését futási és fordítási időben egyaránt (mint ahogyan Borland Delphi rendszerben is). Ez a felület azonban nemcsak PC-re, hanem számos egyéb extra tulajdonságokkal rendelkező készülékkel is kompatibilis, így példának okáért a Smart Device-okkal is (SmartPhone és Pocket PC), ami a mi esetünkben nagyon hasznos lesz! Ami ellenben újdonság, hogy az ASP.NET-et szintén űrlapok segítségével tudjuk kezelni. Úgynevezett web-szerver kontrollokat tudunk elhelyezni, melyek a programozó helyett sok mindent elvégeznek. Ez az ASP.NET kapcsolatot tart a böngészők legkülönfélébb változataival (MS Internet Explorer, Mozilla, stb.) beleértve a mobil és Smart Device eszközök termékeit is! Így egy böngésző független felületen dolgozhatunk. Az ADO már eddig is létezett, a .NET-es változatával hatékonyan és egyszerűen el tudjuk érni az adatbázisainkat (speciális felületen). Három rétege van ennek a platformnak. Az első az adatréteg, mely az ADO.NET-et, valamint az adatbázist foglalja magában. A második az úgynevezett üzleti, logikai réteg (Business Logic): web-szolgáltatások, ASP.NET, applikációk és a Windows formok tartoznak ide. Az utolsó réteg pedig a megjelenítési réteg, mely a vékony (böngészők) és az erőforrásokban gazdag klienseket fogja össze. A .NET támogatja a fogalmi adatmodelleket, valamint az UML-t is. Így már a tervezés magas szintjén is segítségünkre lehet. A modellvezérelt architektúra a .NET-re leképződik. Mi kell mindahhoz, hogy a .NET-ben való munkát el tudjuk kezdeni? Semmi különös, csupán egy .NET FrameWork, valamint egy ASCII szövegszerkesztő, és már fordíthatjuk is programjainkat. Persze sokkal kényelmesebb és gyorsabb munkát érünk el, hogyha beszerezzük a Visual Studio .NET-et, melyben Visual Basic, C++, C# és J# nyelveken dolgozhatunk. Egy adott „team”-ben az egyes osztályok akármelyik nyelven lehetnek, a .NET integráltságával ez nem okoz problémát. Közel 4500 alkalmazási program interfaceét kapjuk kézhez, számos namespace-t, és óriási osztály hiearchiát, amennyiben a .NET-et választjuk. Ma azt mondják, hogy a Visual Basic és a C++ között nincs különbség, de az is biztos, hogy a C# az, mely a .NET kedvenc nyelve. A Borland Delphi 8 a Win32 alkalmazások mellett már támogatja a .NET alapú fejlesztéseket, ellenben a Borland Delphi 2005 már nem csak hogy támogatja, hanem a Delphit beillesztette a Visual Studio .NET nyelvei közé! A Borland Delphi 2005 Delphi (Pascal) és C# szintaktikával képes dolgozni, és fordítani .NET alá.

5.6

Új programnyelv és fejlesztői környezet

A Visual Studio .NET és a Borland Delphi 2005 lényegesen korszerűbb fejlesztői környezet, mint a Microsoft eMbedded Visual C++, ezért alkalmazásunkat C# nyelven a két említett .NET-es környezetben fogjuk elkészítni Pocket PC-re. A .NET felülete lehetőséget biztosít számunkra ahhoz, hogy a PC-s és a Pocket PC-s verzió között minimális különbség lehessen, ezért a PC-s verzió elkészítése feleslegesség válik! Az egyes modulok tesztelésére szolgáló programok egy részét, illetve egyes szimulációs programokat Borland Delphi 7 alatt, avagy C# nyelven fogjuk elkészíteni.

5.7

Az elkészült GPS készülék

5.7.1 A Pocket PC és a GPS összekötése Minden adott ahhoz, hogy teszteljük a gyakorlatban programunk perifériáját, a GPS-t. A teszt PDA továbbra is egy Mitac Mio 339-es Pocket PC Windows Mobile 2003 operációs rendszerrel, beszereztünk hozzá egy soros adatkábelt (36. ábra), valamint elkészült a technikailag kompatibilis GPS is.

37/107


Ábra 36 Soros szinkronizáló kábel Mitac Mio PDA-hoz 5.7.2 Kommunikáció tesztelés Először a GPS és a PPC-t összekötöttük, és egy saját alkalmazást futtattunk rajta, mely a soros portról olvasta a GPS koordinátákat. Az alkalmazás nem kapott bemenő jeleket. Ezután Szintén összekötöttük a GPS-t és a PPC-t, de a Destinator 3 programot használtuk, mely szintén beépített lehetőségként képes kommunikálni GPS hardware-rel. Volt egy olyan tesztünk is, mikor egy PPC-hez való billentyűzet driver-rel is próbálkoztunk, melynek leírásában az állt, hogy segítheti soros portra kötött eszközök kommunikációját a PPC-vel. Legvégül pedig egy GPSGate nevű program segítségét is kipróbáltuk. Ez egy virtuális soros portot hoz létre, melyet aztán minden soros portot olvasó program elér. A GPSGate próbálkozik olvasni az adatokat.

5.8

0. Rendszerterv

A Delphis modell és a Pocket PC-s modell 0. rendszerszinten megegyezik. Törekeszünk arra, hogy minél később váljon ketté a két program funkcionalitása. Célunk az, hogy a Delphis program és a PPC-s verzió ugyanazon bemenő paraméterek esetén ugyanazt az eredményt szolgáltassa azonos körülmények között. 5.8.1 Nulladik rendszerterv modulljai Adatbeviteli modul GPS értelmezése Felhasználói felület Térképkezelő modul Adatbázis Software frissítések kezelése 5.8.2

Az egyes modulok kapcsolata

38/107


Ábra 37 PPC

Ábra 38 System 5.8.3

Modulok leírása

5.8.3.1 Adatbeviteli modul A felhasználó saját helyzetét kétféleképpen tudja meghatározni: vagy a GPS által vett jelet használja fel, vagy saját maga jelöli ki a térképen a jelenlegi pozícióját. Mindkét esetben az információt értelmezni kell: erre szolgál a GPS értelmező modul, és a felhasználó felületen egy keresés funkció. 5.8.3.2 Kapott adat értelmezése A GPS jelet nem minden esetben használja fel a program, hiszen előfordulhatnak olyan helyzetek, mikor egyértelműen eldönthető, hogy az éppen vett GPS jel nem pontos, vagy pontatlanabb, mint a korábbi jel. 5.8.3.3 Felhasználói felület modul A felhasználó ezen keresztül kommunikál a programmal, itt van lehetősége személyre szabni, és a legapróbb részletekig beállítani. 5.8.3.4 Térképkezelő modul Az irodalomkutatásban már leírt módon, gráfok és grafikus térképek segítségével a software a felhasználó igényei szerint utat határoz meg. Ehhez felhasználja az adatbázist és a bemenő paramétereket is. 5.8.3.5 Adatbázis Kidolgozunk egy saját, erre a feladatra kihegyezett adatábrázolást megalkotni, melyhez kezelő függvényeket készítünk. Megvizsgálunk már létező adatbázis struktúrákat, ámbár nem tervezzük adatbázis motor használatát. 5.8.3.6 Software frissítések kezelése A program széleskörű támogatást ad a felhasználónak. Új térképeket, új modulokat és útkeresési algoritmusokat tud majd betölteni programjába. A program része egy Internetes oldal is, ahonnan a frissítéseket elérheti a felhasználó.

39/107


5.9

1. Rendszerterv

A 0. rendszertervhez képest kicsit pontosítsuk, és ugyanakkor erősítsük meg, hogy mi is lesz a programunk alapja.

Ábra 39 1. rendszerterv modellje A GPS-től kapott adatokat két különböző felület kaphatja meg: a gráf, és a grafikus felület. Mindkét rész saját útkereső résszel rendelkezik, és mindegyik más hatékonyságú eredményt adhat számos keresési feltétel alapján. A grafikus felület a megoldást önmagán képes megmutatni, a gráf alapú azonban az átláthatóság kedvéért egy képre még leképeződik. Az 39. ábráról csupán egyetlen átmeneti állapot hiányzik. Ez pedig egy gráftól és grafikus felülettől független térképkezelő rész! A grafikus térképet – mely mindösszesen egy kép – összekötjük közvetlenül a GPS-el is! Egy segédmotor a kép és a GPS koordináták között 11 leképzést fog végrehajtani. Természetesen így útkeresésről szó sem lehet, hiszen csak azt kapjuk meg eredményül, hogy jelenleg a térképen itt állunk. A gráf alapú megoldás ebbe teljes mértékig képes lesz beékelődni. Nem lehet minden pixelnek eltárolni a GPS koordinátáit, így látszólag az eredmény pontatlanabb lehet. Azonban ne felejtsük el, hogy a GPS sem mindig ad pontos megoldást, és azt sem tudjuk, hogy mikor ad pontosat! Ellenben kellő számú gráf pont felvételével, pontos mérések illetve számítások utáni feltöltésével egy olyan vázat kapunk, melyre elképzeléseink szerint a gyakorlatban használható eredményt tudunk adni! Nézzünk egy példát: a felhasználó autóval közlekedik, ezt a program is tudja (akár a sebességből, akár megadott információ). A mért GPS koordinátákat összehasonlítja a gráf pontjaiban tárolt adatokkal. Adott szituációban például három gráf pont van majdnem azonos távolságra a mért eredménytől (kb. 10-20 méter sugarú kör, ami a GPS pontatlanságával azonos lehet). Ebből ki tudjuk zárni azokat, melyek nem úttesten vannak, hiszen a gráf pont sok más információ mellett ilyen adatokat is tárol, valamint az előző gráf pontok segítségével, kellő biztonsággal lehet a felhasználónak mondani, hogy hol található a járműve. A gráf pontokban tárolt GPS koordinátákat azután a már megismert elkészített módszerekkel a grafikus térképre vetítjük, és ezzel már el tudjuk kerülni az olyan pontatlanságból adódó szituációkat, hogy az autó helyzetét a járdára helyezzük. A képként kezelt térképet a továbbiakban statikus térképnek nevezzük, és a grafikus felület magját alkotó térképet pedig dinamikusnak. Végül is mi a szerepe a grafikus felületnek, és a dinamikus térképnek? Az eddigiek után kijelenthető, hogy valójában nem sok. Egy kapcsolat itt is létezik a gráf pontok, és a térkép között, így a GPS pontossága ezáltal nem javítható. Azonban a gráf pontokat összekötő

40/107


élek egyenesek. Nincs olyan, hogy egy él „bekanyarodik”, nincs ilyen jellegű információ tárolva. Így a számított út hossza egy közelítés (ami azonban a gyakorlatban megfelelő pontosságú lehet). A dinamikus térkép az egyes gráf pontokat köti össze futási időben (adott közlekedési eszköz függvényében), megkeresve közöttük az adott feltételnek megfelelő utat (pl. legrövidebb út). További előnye a grafikus felületnek, hogy általunk készített térképekkel dolgozik, így a térképen azon dolgokat tudjuk látványosan kiemelni, ami számunkra fontosak (szintén annak függvényében, hogy milyen eszközzel utazunk). Valamint lehetőség van egyéni térkép készítésére is például egy erdőről, vagy bármiről, amit pár órás munka után egy PC-s segédprogrammal el tudunk készíteni, és a Pocket PCre tudunk másolni.

5.10

A Gráf modell

A Graphs and Spanning trees nevű segédalkalmazás alapjai már megvannak, bár még csak statikusan működnek a legalapvetőbb funkciók. A jövőben a tevékenységek bővítése és a globális dinamikusság szerepel a kitűzött célok között. A 40. ábra azon alapvető jellemzőket mutatja be, mely közös mind statikus, mind dinamikus esetben.

Ábra 40 A TGraph osztály 1. rendszertervbeli alakja I Minden gráf esetén tárolunk pár adminisztrációs adatot, mint a neve, vagy mint egy rövid megjegyzés a gráfról. A típusa négyféle lehet: - Simple (egyszerű) - Guided (irányított) - Weighted (súlyozott) - GuidedWeighted (irányított és súlyozott) A Continuos egy tetszőleges időben kiszámított érték, mely megadja, hogy a gráf összefüggő-e, avagy sem. Amennyiben a MultipleWeight értéke igaz, minden egyes élen nem csupán egy súly szerepelhet, hanem egy súlyvektor (természetesen csak súlyozott gráf esetén van ennek értelme). A PointsArray tartalmazza a gráf pontok, az EdgesArray az élek adatait. Ezeket részletezve mutatja a 41. ábra.

41/107


Ábra 41 A pontok és az élek adatai az 1. rendszerterv alapján Minden egyes pont esetén tároljuk a három térbeli koordinátáját (Z a magasság), egy sorszámot, mely azonosítja és egy opcionális nevet (AllowName határozza meg, hogy létezik-e ilyen név). Az élek esetén tároljuk, hogy az adott él mely két pontot köti össze (PointOne, PointTwo), valamint itt is létezik Serial, Name és AllowName. A Directivity adja meg az irányítottságot. Ha értéke 1, akkor az egyes pont felé mutat, ha 2, akkor a kettes felé. Az értéke nulla a nem irányított gráf esetén. Egy speciális eset, mikor a gráf irányított, és az irányítottság értéke nulla. Ilyenkor mindkét irányba mutat a gráf (Ez még nem teljesen meghatározott álláspont, mivel egy további bizonytalanság is fennáll: MultipleEdges. Ez meghatározza, hogy lehetséges-e két pont között több él. Egyelőre nincs ez a tulajdonság felvéve az 1. rendszertervbe. Még nem volt szó a DataArray-ről, és a WeightsArray-ről. Ezek szerepelnek a gráfban is, a pontokban és az élekben külön-külön is. Azonban nem azonos típusúak, csupán azonos logikai szinten vannak (egy feladatkörhöz tartoznak)! A gráf DataArray és WeightsArray (41. ábra) olyan rekordokból álló tömb, melyben minden elemnek van egy neve (ItemName), típusa (ItemType) valamint alapértelmezett értéke (DefaultValue). A típus lehet egész szám, valós szám avagy szöveg. A DataArray tömbben ezen elemek meghatározzák, hogy minden egyes gráf pontban milyen adatokat tudunk tárolni. A WeightsArray ennek megfelelően azon elemeket tárolja, melyek meghatározzák, hogy a súlyvektorban milyen súlyokat tárolhatunk minden egyes él esetén. Az egyes éleken és gráf pontokon belül lévő DataArray és WeightsArray (42. ábra) azonban már csak az előző tömbök által tárolt rekordoknak megfelelő értékeket tárolja.

42/107


Ábra 42 A TGraph osztály 1. rendszertervbeli alakja II

43/107


6 Graphs and spanning trees 6.1

A programról általában

A Graphs and spanning trees (Gráfok és feszítőfák) alkalmazás egy szimulációs program. Modellezni lehet vele a gráfok problémakörébe tartozó feladatokat. Elkészítésének alapvető célja a Poseidon Navigation Project nevű térképprogram gráf alapú térképének, és ezen való útkeresésének megvalósítása. Mivel a térképprogramhoz használt gráf szerkezete az összetettebb kategóriába tartozik, ezért felmerülhet a kérdés, hogy miért van szükség egy olyan program elkészítésére, mely ennél lényegesen egyszerűbb gráfokat is kezel. A válasz a hatékonyságban és a tervezésben keresendő. Ha egy megírt útkereső algoritmus csak egy típusú gráfra működik hatékonyan, akkor a gráf esetleges szerkezeti változásai a megírt összes algoritmus működőképességét veszélyeztetik. Valamint amennyiben van egy olyan adatszerkezetünk, mely megvalósítja a lehető legegyszerűbb gráf-hálót, és a hozzá tartozó műveleteket, könnyű továbbfejleszteni a bonyolultabb esetekre is! Az alkalmazás egy úgynevezett MDI Application, azaz egy többdokumentumos alkalmazás, mint például a Microsoft Word, vagy az Adobe Photoshop. Ebből következik, hogy egyszerre több gráffal is tudunk dolgozni általa, és mindegyiket egymástól függetlenül tudjuk kezelni. A gráfnak tudunk új csomópontokat, új éleket felvenni, módosítani, avagy törölni. Be tudjuk állítani a gráf típusát, tulajdonságait és bizonyos mértékig konvertálni is tudunk gráfokat. Személyre szabhatjuk, hogy a három dimenzióban mozgó gráfunk képén milyen információk jelenjenek meg, és mindezek milyen színnel, betűtípussal, stb. Képesek vagyunk adott feltételek megadása mellett kapcsolatmátrix készítésére, valamint ha ezt megtettük, akkor Dijkstra algoritmusa segítségével meg tudjuk bármely két pont között határozni a legrövidebb utat (adott súly szerint). A program a későbbiekben szomszédsági listák elkészítésére is alkalmas lesz, valamint többféle útkereső algoritmust fog tudni kezelni. Mélységi és szélességi bejárás alapján tudunk majd információt keresni, és lehetőségeink között lesz a gráf alapján egy feszítőfa elkészítése is. Az útkeresés során számos információt tudunk gyűjteni, mely listázása nehézkesen átlátható. Tervbe van véve egy script nyelv elkészítése, melynek segítségével a töménytelen információt szűrni fogjuk tudni.

44/107


6.2

Felhasználói kézikönyv

Ábra 43 Képernyőkép 6.2.1 Új gráf létrehozása A [File|New graph] (File menü New graph parancsa) hatására a gráf tulajdonságait beállító ablakot láthatjuk (44. ábra). Itt számos adatot megadhatunk, mely a gráfunk működését a jövőben erősen befolyásolni fogja. Vannak olyan tulajdonságok, melyek csak itt állíthatóak, és vannak, melyek módosítására a program későbbi részén is lesz lehetőség.

45/107


Ábra 44 Új gráf létrehozása A gráf nevét (Name of graph) mindenképp adjuk meg, különben NonameGraph lesz a munkánk neve, és amennyiben ezt a nevet meghagyjuk, a következő NonameGraph felülírhatja ezen gráfunkat (amennyiben nem adunk meg nevet, a program figyelmeztet minket, hogy a későbbiekben ne felejtsük beállítani). A gráf neve lesz elmentés után egy könyvtár neve, benne számos különböző kiterjesztésű file-lal, melyeknek a nevük szintén az itt megadott (a gráf betöltéséhez természetesen minden file-ra szükségünk lesz). A gráf típusát se felejtsük el beállítani (Type of graph). Négy alapvetően különböző gráfot ismer a program. Az egyszerű gráf (Simple graph) pontokból, és azokat összekötő élekből áll. Az irányított gráf (Guided graph) éleinek irányítottságot adhatunk, a súlyozott gráf esetén (Weighted graph) pedig súlyértékeket. Az utolsó lehetőség az utóbbi kettő kombinációja (Guided weighted graph), mely a Poseidon Navigation Project térképeinek elkészítéséhez lesz kiemelkedően fontos. Beállíthatjuk a tárolás típusát (Storage), hogy statikus, avagy dinamikus legyen-e, de ez a lehetőség még nincs kihasználva. Egyelőre minden gráf teljesen statikus adatszerkezetekből épül fel. A többszörös élek (Multiple edges) engedélyezése, illetve tiltása még szintén nincs implementálva. Nagyon fontos, és csak itt megadható tulajdonsága egy gráfnak a grafikus mérete! Ez egy kép méretét jelenti, melyre a gráf csomópontokat elhelyezhetjük három dimenzióban. Minimálisan ez az érték 300 (nem is enged a program kisebb értéket megadni), azaz egy 300x300x300-as kockában tudunk dolgozni, mégpedig koordináták nyelvén szólva mind az X, Y és Z tengely esetén az értelmezési tartomány a (-150;150) intervallum. Egy megjegyzést is tárolhatunk minden gráf esetén (Comment), melynek a megadása természetesen nem kötelező. Mindezek mellett lehetőségünk van két lista elkészítésére is még szintén ebben az ablakban: gráf pontok adatai (Data of graph points) és súlyvektor beállítása (Multiple weights). Mindkét esetben tíz elemet vehetünk fel a listába (statikus esetben), és minden elemnek beállíthatjuk a nevét (Item name), típusát (Item type) és alapértelmezett értékét (Default value)(Mellékletek: 69. ábra). A név alapján tudjuk majd azonosítani. Az alapértelmezett érték megadása nem kötelező (ha nem adjuk meg, beállít helyettünk egy értéket a program). De mire is jók ezek nekünk?

46/107


Minden gráf pont esetén tárolhatunk tíz különféle értéket az adott típusnak megfelelően, melyeket aztán script programok írása esetén fel tudunk használni, és/vagy modellezés során hasznos információkkal tudjuk ellátni a gráfunk csúcspontjait. Térképprogram esetén például, itt tárolhatjuk majd az olyan kiegészítő információkat, hogy az adott pont most egy járdán van-e, avagy egy zebrán, stb. Az élek esetén ugyanezen az elven működik a súlyvektor megadása. Nem csupán egy súly tartozhat egy élhez, hanem minden élhez egy maximum tízelemű vektor tartozik (statikus esetben). Térképprogram esetén egyik súly tárolhatja a két gráf pont közötti út hosszát, egy másik az adott úton a maximális haladási sebességet, a harmadik azonosíthatja a felület típusát (aszfalt, földút, stb.), stb. Lényegében a KRESZ szabályok figyelembevétele e két lista segítségével megvalósulhat! Ezt a két listát még a későbbiekben is tudjuk majd szerkeszteni. 6.2.2 Gráf megnyitása A [File|Open graph] hatására egy standard file megnyitó ablakban a (*.grp) file-okat tudunk megnyitni. Ez egy szöveges állomány, mely lényegében a gráf alapvető tulajdonságait tárolja. Szükséges, hogy abban a könyvtárban, ahonnan megnyitottuk a *.grp file-t, legyen további öt azonos nevű állomány is (*.das, *.dat, *.edg, *.pnt, *.was)! Ezen állományok mind egytől egyik binárisak. 6.2.3 Globális beállítási lehetőségek A program számos beállítási lehetőséggel rendelkezik, melyek minden megnyitott gráfra hatással vannak. Ezeket a [Setting] menüben találhatjuk. Nézzük elszőször a [Setting|Show information on graph] menüpontot. Itt azokat a vizuális tényezőket tudjuk beállítani, mely a gráfunkon megjelenő adatok kinézetét befolyásolják (Mellékletek: 71. ábra). A gráf grafikai megjelenése és azon információk, melyek a gráfon megjelennek egymástól függetlenül kezelhetők. Meg lehet adni, hogy az egyes gráf pontoknál, valamint az egyes élek esetén milyen információ jelenjen meg. Beállíthatjuk, hogy a pontok illetve élek sorszáma (Serial of graph points/Serial of graph edges), avagy neve (Name of graph points if allow/Name of graph edges if allow) jelenjen meg, és lehetőségünk van kikapcsolni mindenféle információ megjelenítését is (none). Továbbá megadhatjuk, hogy valamelyik adatmező, illetve súlymező jelenjen meg (One datum of graph points/One weight of graph edges). Amennyiben a gráf pontok vagy az élek nevét állítjuk be, és vannak olyan pontok/élek, melyeknek nincs beállítva név érték (majd később visszatérünk arra, hogy mit lehet beállítani az egyes pontok és élek esetén), akkor nem jelenik meg semmi az adott pontnál/élnél. Meg lehet adni a gráfok hátterének színét (Background color), valamint hogy a gráfon megjelenő szövegek háttere felülírja-e a képet, vagy ne (érdemes kipróbálni, hogy ki melyik variációt látja át jobban)(Texts overwrite the graphics). A gráfon megjelenő feliratok színét egyesével meg tudjuk adni. Ehhez kattintsunk az adott rádiógomb melletti kis színezett téglalapra. Van arra is lehetőségünk, hogy egy kattintásra minden él és gráf-pont színét egy előre megadottra állítsunk be (Use adjusted colors). Ezáltal bináris képet kaphatunk (ha kikapcsoljuk a feliratokat, vagy beállítjuk azokat is erre a színre). Az élek és a gráf-pontok színét egyesével tudjuk majd beállítani felvételükkor. Mindenféle felirat betűtípusa egységes. Ezt a „Set font” gombra kattintva tudjuk beállítani. Utolsó lehetőségként - ebben a menüben - az út színét adhatjuk meg (Way color). Ez lesz a színe azon éleknek, melyek az útkeresés eredményében „részt vesznek”. Térjünk át a [Setting|Global constants] menüpontra. Itt a legtöbb tényező csak információt közöl a felhasználóval, beállítani egyáltalán nem, vagy majd csak a program későbbi verzióban lesz lehetséges (Mellékletek: 72. ábra).

47/107


A statikus jellegből adódóan gráfunknak vannak bizonyos számbeli korlátai. Ezeket átállítani csak forráskód szinten lehet, ezért a felhasználó csak mint információ láthatja. Nézzük ezek magyarázatát sorban: Max item of weights and data: Maximális elemszáma a súlyvektornak és a pontokban tárolható adat tömbnek. Max graph points: Legfeljebb ennyi gráf-pont lehet a gráfunkban. Max graph edges: Legfeljebb ennyi él lehet a gráfunkban. Max graphic points: Egy adott gráf-pont nem csupán egy grafikai pontnak felel meg, mivel egy kis 3D-s objektummal jelöljük meg a képen. Emiatt egy felső korlátja van ennek is. Célszerűen ez a szám lényegesen magasabb, mint a gráf-pontok maximális száma. Az irányított él esetén maga az él is tartalmaz további grafikai pontokat (a nyíl miatt)! Max graphic edges: Az előző alapján a maximális grafikai élek száma is korlátozott. Max arm of 3D objects: A program által használt egyedi software-es 3D motor képes úgynevezett robotkar kezelésére. Egy konstans meghatározza azt, hogy maximum mennyi kartagja lehet a robotunknak. Ez fixen három ebben a programban, mivel nincs kihasználva a 3D motor ezen funkciója. Max graphic points of each shapes: Manuálisan tudunk készíteni egyedi mintákat arra nézve, hogy egy gráf-pont hogyan nézzen ki. Egy konstans tárolja, hogy egy ilyen minta maximum mennyi grafikai pontból állhat. A grafikai élek száma nincs korlátozva. Shape List file name, Shape files directory és Save directory: Ugyanitt le tudjuk olvasni a sémák listáját tároló szöveges file nevét, valamint az alapértelmezett könyvtárát a sémáknak és a gráfoknak. A jelenlegi verzióban még két változó értékét tudjuk leolvasni és módosítani (!) a „Global constants” menüben: az irányított él két grafikai paraméterét (Directivity Length és Directivity Length 2). Ezek funkcióját leírni nehézkes, célszerű kipróbálni, hogy módosításukkal mi változik a képen (a nyíl különböző mérete fog változni irányított gráfok esetén). 6.2.4 Lokális beállítások Létrehozva, avagy megnyitva egy új gráfot a menüsor kiegészül számos új elemmel. A [Local Setting] menüben a gráf forgatásáért felelős grafikai ablak egy vizuális effektjét tudjuk ki, illetve bekapcsolni (Allow animated frame/Forbid animated frame). Vizsgáljuk meg közelebbről a gráf forgatásáért felelős gombokat. Az X, Y, Z tengelyek körüli forgatásra vonatkozik a gráf megjegyzése alatt található hat nyomógomb. A szerkesztési mezőben megadható szám jelzi, hogy egy kattintásra hány fokot fordul el a gráf. A piros bal és jobb nyíl egy előre beállított ’u’ tengely körül forgatja a gráfot egy fokonként. A kis földgömbre kattintva automatikusan két tengely körül forogni fog a gráfunk (X és U tengely körül). A „Refresh” gomb bármikor hasznos lehet, ha úgy érzékeljük, hogy a módosításunk nem látható jelenleg még a gráfon. Ha a „Refresh” (frissítés) hatására sem jelentkezik a változás, akkor a hibát máshol keressük. 6.2.5 Új gráf pont felvétele Az [Edit|Add new junction (graph point)] menüpontra kattintva tudunk az aktuális gráfunkhoz új csomópontot felvenni. Itt kell beállítanunk mindent, ami a gráf ponttal kapcsolatos (45. ábra).

48/107


Ábra 45 Új gráf pont hozzáadása A pont koordinátáinak (coordinates) (X,Y,Z) felvétele történhet manuálisan, de van lehetőség az (X,Y) sík vizuális megadására is a ’#’ gombra kattintva (Mellékletek: 73. ábra) Az itt megjelenő pontok a már felvitt gráf pontokat jelképezik a könnyebb tájolás érdekében! A sorszám (serial) mező automatikusan generálódik, szerkeszteni nem tudjuk, azonban adhatunk egy egyedi azonosítót (nevet) a csomópontnak (name), amennyiben ezt engedélyezzük (Allow name). Már említettem, hogy minden ponthoz tartozik egy 3D-s objektum, mely grafikusan fogja jelölni a képen a csomópontot. Ezt a ’Design’ panelen tudjuk beállítani. A piros bal és jobb irányú nyilakkal tudunk váltani az elérhető minták között (shape). Ilyen mintákat manuálisan bárki képes készíteni (*.shp file-ok). A program későbbi verziójában lesz lehetőség program szinten is minták létrehozására. A gráf pont színét a színes téglalapra kattintva tudjuk beállítani. Minden gráf pont tartalmazhatja azon adatokat, melyek a gráf tulajdonságai között definiálva vannak. A bal oldali listában (Data of graph point) kiválasztva az adott elemet, majd a szerkesztési mezőbe egy értéket írva (Value), végül a ’Set’ gombra kattintva az adott csomópontnak felvittük az új adatát. A jobb oldali listában láthatjuk a beállított értékeket. Kezdetben ezek a gráf tulajdonságai között beállított alapértelmezett értékek lesznek (Default value). 6.2.6 Új él felvétele a gráfba Miután felvittünk pár csomópontot a gráfunkba, felmerülhet az igény élek elhelyezésére is ([Edit|Add bew edge])(46. ábra). Egy gráfban él csak két csomópont között mehet. Ezt a két pontot a ’List of points’ gombokra kattintva tudjuk megadni (Mellékletek: 74. ábra). Irányítatlan gráf esetén lényegtelen, hogy melyik az egyes, és melyik a kettes pont, ellenben irányított esetben a ’Directivity’ részben ennek szerepe van! Amennyiben egy irányított élnek nem állítunk be irányítottságot (none), akkor ez olyan lesz, mintha lenne egy él A-ból B-be, és B-ből A-ba is.

49/107


Ábra 46 Új él felvitele A sorszám (Serial), az egyedi azonosító (name, Allow name) és a szín megadása hasonlóan történik, mint a gráf pontjai esetén. A súlyvektort a gráf súlyvektor tulajdonsága alapján tudjuk feltölteni szintén még ebben az ablakban. 6.2.7 Gráf pontok és élek módosítása illetve törlése Utólag lehetőségünk van a felvitt gráf pontok és élek teljes szerkesztésére, és törlésére is ([Edit|Edit junction][Edit|Edit edge][Edit|Delete juction (with edges)][Edit|Delete edge]). Mindegyik esetben egy listából ki kell választanunk, melyik elemmel szeretnénk dolgozni. Grafikus kijelölésre itt még nincs lehetőség. Él esetén segédinformációként kiválasztáskor megjelenik az általa összekötött csomópontok sorszáma és neve is (Mellékletek: 75. ábra) A törlés logikai, azaz fizikailag az adott csomópont illetve él nem törlődik a gráfból, csak a felhasználó többé már se látni, se szerkeszteni nem tudja. A program jelenlegi verziójában a fizikai törlés még nem készült el. 6.2.8 Gráf tulajdonságainak utólagos beállítási lehetősége Ha utólag rájöttünk, hogy a gráfunk tulajdonságai nem a legoptimálisabbak feladatunk megoldására, néhány dolgot a [Data|Display data of graph] menüpont alatt át tudunk állítani (Mellékletek: 76. ábra). Adhatunk új nevet a gráfnak (gyakorlatilag így lehet elmenteni más néven a gráfot), megjegyzést és típust! A típus változásával óvatosan bánjunk, számos információt veszíthetünk általa. A csomópont adatvektorát, valamint a súlyvektort is tetszés szerint módosíthatjuk. 6.2.9 Az aktuális súly illetve gráf pont adat beállítása Egyszerre nem jeleníthetünk meg egy élen több információt, avagy egy csomópontban több adatot. Amennyiben a [Setting|Show information on graph] menüpontban az adat- illetve súlyvektor megjelenítését jelöltük be, akkor megadhatunk egy aktuális adatot, és egy aktuális súlyt, mely a gráfon grafikailag is látszani fog. Ezt a [Format|Set current weight] menüpontban illetve a [Format|Set current data] menüpontban tehetjük meg (Mellékletek: 77. ábra).

50/107


6.2.10 Gráf mentése A programban nincs automatikus mentés, és figyelmeztetni sem figyelmeztet mentésre (a jelenlegi verzió). A [File|Save graph] menüpontra kattintva a beállított gráf könyvtárba a megadott gráf névvel egy könyvtár jön létre, benne számos file-lal, melyek a gráfunk különböző adatait tárolják. Ha másodszor is elmentjük a programot azonos névvel, akkor a program figyelmeztet arra, hogy az előző állapot el fog veszni. A gráf átnevezésével (Fejezet: Gráf tulajdonságainak utólagos beállítási lehetősége) ez a probléma elkerülhető. 6.2.11 Kapcsolatmátrix generálása Számos ábrázolási formája létezik a gráfoknak. Amit a Graphs and spanning trees valósít meg, az egy teljesen egyedi TGraph nevű osztályon alapul. Lényegesen több információt képes tárolni ez a szerkezet, mint mondjuk egy hagyományos kapcsolatmátrix, bár tény, hogy maga a TGraph osztály megvalósítható lenne úgy is, hogy alapja egy kapcsolatmátrix! Ellenben egészen máshogy épül fel a TGraph osztály, melynek azonban része egyetlen statikus kapcsolatmátrix is. Az egyetlenen azért van hangsúly, mert minimum annyi mátrix kellene, amennyi súlyunk létezik. Mi itt generálni vagyunk képesek kapcsolatmátrixot egyetlen súly (vagy opcionálisan más adat) alapján a [Data|Static relation matrix] menüpontra kattintva (47. ábra).

Ábra 47 Statikus kapcsolatmátrix generálása A két legördülő lista segítségével be tudjuk állítani, hogy a gráf pontok sorszáma (Show serial of points), vagy a neve jelenjen-e meg (Show name of points if allow). Ha nem állítottunk be egy csúcspontnál nevet, akkor a sorszáma fog megjelenni. A másik legördülő listában szintén kiválasztható, hogy mely súly értékei jelenjenek meg a kapcsolatmátrixban. Sőt, megadható az is, hogy az élek sorszáma jelenjen meg, avagy a nevük! Természetesen ezen utóbbi esettel számolni nem tudunk, csupán egy nézetet biztosíthat számunkra, melyet a program későbbi verziójában majd ki fogunk tudni használni, ott ugyanis lehetőség lesz a kapcsolatmátrix szerkesztésével módosítani a gráf adatait! Bezárva az ablakot (OK gombra kattintva) kapunk egy visszajelzést, hogy a gráf kapcsolatmátrixa elkészült-e! Mivel ezzel a későbbiekben számolni fogunk, ezért nem készül kapcsolatmátrix hogyha nem valós számok szerepelnek a súly értékei között.

51/107


Az elkészült kapcsolatmátrix ellenőrizhető a [Pathfinding|Show relation matrix] menüpontra kattintva (Mellékletek: 78. ábra). 6.2.12 Legrövidebb út meghatározása Dijkstra algoritmusa alapján Ha elkészítettünk egy kapcsolatmátrixot, lehetőségünk van legrövidebb út keresésére. A program jelenlegi változatában Dijkstra algoritmusát implementáltam. A [Pathfinding|Simple pathfinding] menüpontra kattintva (48. ábra) a kiindulási (Start point) és a cél pontot (Destination Point) lehet megadni az útkereső algoritmusnak („Set” gomb segítségével), valamint be kell állítanunk, hogy az útkeresés során használja a már memóriában lévő kapcsolatmátrixunkat.

Ábra 48 Útkeresés kapcsoaltmárix segítségével A ’GO’ gombra kattintva az út (természetesen amennyiben létezik) elkészül. Az ehhez szükséges eredmény adatszerkezet megjelenik a szövegterületben (innen az algoritmus ismeretében számos plusz információ is leolvasható). Bezárva az ablakot (’OK’ gombbal) a gráfunkon a megtalált út a beállított színnel meg fog jelenni (49. ábra).

52/107


Ábra 49 Legrövidebb út A és C pont között Ezzel a rövid bemutatóval végig is szaladtunk a program legalapvetőbb funkcióin, azonban a program nem csak ezen funkciók megoldására képes! 6.2.13 Szerkesztés gyorsítása A legnagyobb probléma gráfok szerkesztése során az adatfelvitel. Ha nagy gráfot szeretnénk készíteni, nagyon sok időre van szükség, míg minden egyes gráf pontot felviszünk, és minden egyes ezekhez tartozó élet. A gyakorlatban azonban ezen pontok és élek tulajdonságainak nagyon nagy része megegyezhet. Ennek érdekében készültek a programhoz olyan szerkesztők, melyek pontok és élek egyidejű felvitelét teszik lehetővé az előbbi módszerhez viszonyítva rendkívüli sebességgel! Ez azt jelenti, hogy egy pár száz gráf pontból és pár száz élből elkészített gráf háló negyed óra alatt elkészíthető! Válasszuk ki az [Edit|Junctions and Edges Editor] elnevezésű menüpontot (50. ábra).

53/107


Ábra 50 Él és pont szerkesztő A megjelelő képernyő bal felső sarkában beállíthatjuk, hogy mit szeretnénk felvenni (Junctiont, azaz pontot, Edge-t, azaz élet), illetve hogy szeretnénk e grafikusan szerkeszteni a már felvitt elemeket (Edit mode)! Alatta kiválaszthatjuk, hogy a majd felvitt gráf pontok milyen grafikai formát öntsenek, illetve milyen színűek legyenek (a szín élekre is vonatkozik). Az „Edges and Junctions Data” résznél megadhatjuk a következő felviendő gráf pont, illetve él 3D-s Z koordinátáját (az X és Y koordinátákat grafikusan tudjuk majd beállítani!), valamint megadhatjuk az elem nevét is. Láthatunk két kijelölő négyzetet is. Ha az Edges mellett pipa van, az azt jelenti, hogy az ábrán az élek látszani fognak. Ugyanígy ha a Serials mellett is pipa van, akkor a gráf pontok sorszáma fog látszódni a 3D-s gráf vetületi képén! A Step mezővel az érzékenységet tudjuk beállítani. Ez majd arra lesz jó, hogy egyes pontokat azonosítsuk. Válasszuk ki legelőször a bal felső sarokban az új gráf pont felvételét (Junction). Állítsunk be minden számunkra szükséges információt, majd kattintsunk oda a képen, ami számunkra épp megfelelő (itt hívnám fel a figyelmet arra, hogy a képen azon gráf pontok, melyek nagyobbnak tűnnek, mint a többiek, velünk egy síkban vannak a Z tengelyt tekintve). A mellékletek között megtalálható 79. ábra épp ezt a folyamatot mutatja. Felvittünk egy új gráf pontot, mely automatikusan megkapta a sorban következő gráf pont sorszámát. Ezek után váltsunk át új gráf él felvitelére! Állítsuk be itt is az él színét, esetlegesen a nevét, majd kattintsunk a képen arra a gráf pontra, ahonnan az élünk kiindul, és az egér felengedése nélkül húzzuk oda, ahol az élünk vége lesz. Segítségképpen a bal oldalon látható Serial, X, Y és Z mezők változása jelzi, hogy a kurzor épp melyik koordinátájú gráf pont felett tartózkodik! Ezt a folyamatot a mellékletek közt megtalálható 80. ábra mutatja be. Ha mindent jól csináltunk, és az élek be rajzolása be van kapcsolva, azonnal meg is jelennek az új éleink!

54/107


Mindezek után még ugyanezen a képernyőn arra is képesek vagyunk, hogy egy gráf pont helyzetén változtassunk a térben! Ehhez válasszuk ki az „Edit mode”-ot, mint művelet a bal felső sarokban, kattintsunk egy tetszőleges gráf pontra a képen, majd a bal felső sarokban időközben megjelent mozgató gombokra kattintva figyeljük meg, ahogyan a gráf pontunk, a hozzá tartozó összes éllel együtt átdefiniálódik (Mellékletek: 81. ábra)! Az “OK” gombra kattintva az elvégzett műveletek érvényesülnek. 6.2.14 Tömegesen felvett élek és gráf pontok módosítása és törlése A fenti módszer kiegészítéseként az [Edit|Junctions and Edges Multi Editor] menüpontot kiválasztva (Mellékletek: 83. ábra) lehetőségünk van arra, hogy egy kattintással a középső listába felvett élek és gráf pontok színét, illetve nevét egységesen beállítsuk. 6.2.15 Útkeresés egyszerűbb formája Ahhoz hogy egy gráfokkal foglalkozó programot hatékonyan tudjuk kezelni, alapvetően szükséges az, hogy tisztában legyünk a gráfok matematikai alapjaival, hogy meg tudjuk mondani, hogy mi is az a kapcsolatmátrix. Ennek ellenére lehetőségünk van arra, hogy ne kelljen kapcsolatmátrixot generálnunk ahhoz, hogy a Dijkstra féle legrövidebb utat meghatározzuk egy adott súlyra nézve! A program képes dinamikusan létrehozni a kapcsolatmátrixnak a számára szükséges részét, így a kapcsolatmátrixot nem szükséges a memóriában tárolni, így elkészíteni sem (51. ábra). Ennek természetesen hátránya a sebesség lesz, de ez pár száz gráf pontot tartalmazó gráfok esetén nem számottevő. Ha kapcsolatmátrix nélkül keresünk utat, természetesen meg kell adnunk azt a súlyt is, melyet felhasználva a program dinamikusan kiszámolja majd a szükséges értékeket.

Ábra 51 Útkeresés kapcsolatmátrix nélkül

55/107


Mi az a lépés, mely segítségével még gyorsabbá tehetjük az útkeresést? Természetesen kézenfekvő, hogy az út hosszának automatikus megállapításával. Ha például egy térképhez készített gráf pontokat arányosan veszünk fel, avagy egy alakzatot méretarányosan modellezünk (azaz amit látunk, az körülbelül megfelel a valóságnak), akkor a program képes a pontok közötti 3D-s távolság kiszámolására minden egyes pontra nézve (Mellékletek: 84. ábra). Ugyanitt megtehetjük azt is, hogy egy megadott konstans értéket állítunk be minden él adott súlyára (a súlyt ki kell választani a listából, majd a „Set Constant” avagy a „Set Distance 3D” gombra kell kattintani a kívánt eredmény függvényében). Későbbi program verzióba bekerülhet olyan lehetőség is, hogy minden egyes súlyra megadott műveletet végrehajt a program (például kettővel való szorzás, stb.).

6.3

Fejlesztői dokumentáció

A Graphs and spanning trees alkalmazás Borland Delphi 7 környezetben készült. Microsoft Windows 32 bites környezet alatt futtatható. Többdokumentumos, úgynevezett MDIApplication, mely lehetővé teszi, hogy egy időben több gráfon dolgozzunk, és a gráfokat egymástól függetlenül tudjuk kezelni. Jelenleg 23 darab példánya van az alkalmazásnak a TForm osztályból, és három saját készítésű osztályt tartalmaz: TQWVWin, TObject3D és TGraph. Az első kettő grafikai osztályok. A TQWVWin a gráfok forgatásáért felelős panel grafikáját dolgozza át. Az összes grafikai hatását bekapcsolva a gépet meglehetősen „visszafogja”. A TObject3D osztály egy egyedi software-es 3D objektumok tárolásáért, és kezelésért felelős. Végül a TGraph osztály maga a gráf, minden adatával és műveletével. 6.3.1 A TObject3D osztály A Wevi3DUnit tartalmazza elsősorban a TObject3D osztály deklarációját, a hozzá tartozó típus deklarációkat, valamint a szükséges konstansokat és változókat (Mellékletek: TOjbect3D osztály).

56/107


Ábra 52 TObject3D osztály 6.3.2 A TGraph osztály A TypeUnit része többek között a TGraph osztály is, de itt megtalálható számos, a Graphs and spanning trees-ben használt további típusok deklarálása is (Mellékletek: TGraph osztály).

57/107


Ábra 53 TGraph osztály 6.3.2.1 Algoritmusok A PathfindingDijkstra() algoritmusa kulcsfontosságú az osztály szempontjából, így ennek forráskódja teljes terjedelmében szerep a dolgozatban. Dijkstra algoritmusának pszeudó-kódja már szerepelt az irodalomkutatásban is.

58/107


59/107


6.3.2.2 A TypeUnit további részei A TypeUnit további lényeges részei a mellékletekben olvashatóak.

Ábra 54 TypeUnit

6.4

Tesztelés

A Budapesti Műszaki Főiskola Neumann János Informatikai Karának 2005-ben létező központi épületének (a Nagyszombat utcai Árpád Gimnázium) és környékének a térképét modelleztük le a Graphs and spanning trees alkalmazás segítéségével. Ezen a térkép részleten fog majd utat keresni a PDA-n futó alkalmazás is!

6.5

Beágyazás a Poseidon Navigation Projektbe

A Pocket PC-n futó alkalmazást C# nyelven készítjük el. Ennek megfelelően szükséges lesz a TGraph osztály bizonyos részeinek átdolgozására ezen nyelvre (tárolás, útkeresés). A Graphs and Spanning Trees mentési módjai között megtalálható egy speciális mentés, mely minden egyes file-t Text típusú állományként ment el. Ez lehetőséget ad arra, hogy az ebben a programban megszerkesztett gráfot átvigyük a C# programba.

60/107


7 From Game to Map Az eredeti célok között szerepelt egy olyan útkereső eljárás is, mely nem adott, előre felvitt gráf/térkép pontok alapján számít lehetséges utat, hanem azon a felületen ad megoldást, melyet a felhasználó lát, azaz magán a grafikus térképen. Ehhez arra lett volna szükség, hogy egy saját, általunk készített vektorgrafikus térképet is elkészítsünk a gráf hálónk és a rá vetített statikus kép közé. Az ilyen térképen való útkeresésre a hullám-továbbterjesztéses algoritmusok lettek kiválasztva, ezzel foglalkozik az irodalomkutatás adott fejezete. Bár a végleges alkalmazásba nem épült bele, az útkeresés teszteléséhez elkészült a From Game to Map elnevezésű alkalmazás Microsoft Visual Studio .net környezetben, C# nyelven. E fejezet ennek rövid bemutatásával foglalkozik. A gráf szimulátorhoz hasonlóan ez is egy többdokumentumos, úgynevezett MDI alkalmazás, ellenben a felhasznált objektumok immáron teljesen dinamikusak! A részletek a fejlesztési útmutatóban olvashatóak.

Ábra 55 Képernyőkép

7.1

Felhasználói kézikönyv

7.1.1 Új terület létrehozása A program elindítása után a [File | New Territory] menüpont segítségével hozhatunk létre egy új területet, melyen aztán az útkeresést kipróbálhatjuk majd.

61/107


Ábra 56 Új terület létrehozása A megjelenő képernyőn (56. ábra) beállíthatjuk a területünk méreteit, illetőleg a nevét. Ezen kívül beállíthatjuk azt is, hogy a térkép egy pontja a képernyő mekkora pixel-méretű négyzetét foglalja el (CellX és CellY). Ez az érték a későbbiekben változtatható lesz. 7.1.2 Terület szerkesztése Az adatok beállítása után megjelenik egy üres terület, melyre felvihetjük a kiindulási, illetőleg cél pontunkat, valamint beállíthatjuk az akadályok helyzetét (57. ábra).

62/107


Ábra 57 Üres terület létrehozás után A felületen láthatjuk a beállított méreteket, illetőleg a terület nevét. Ezek szerkesztése esetén a GO nyomógombot megnyomva létrejön egy új terület (új példány), mely rendelkezik az eredeti (az ős) minden beállított értékével (ha kisebb értékeket adunk meg, akkor természetesen az adatok nem másolhatók át). A gyermekablakon látunk egy képet is, mely a területet az eredeti méretében mutatja be (egy területpont ténylegesen egy pixel méretű). A kis térkép alatt helyezkedik el két csúszka, mellyel a térképpontok méretét lehet beállítani. Az ablak alsó részén láthatjuk a kép, illetve a terület koordinátáit is, ahogyan mozgunk az egyes koordináták felett. Ez a lehetőség az eredeti 1:1 arányú képen is működik! A szerkesztés folyamata nagyon egyszerű. Csupán ki kell jelölnünk a leugró menüből az elhelyezni kívánt elem típusát, majd a képen a megfelelő helyre kattintva ennek elhelyezése megtörténik. A lehetőségek: - Start Point (Kezdő pont) - Destination Point (Cél pont) - Barrier (Akadály) - Erase (Törlés) Néhány elem típusa a térképen egy speciális jelentéssel bíró egész szám. Ezen értékek meg is jelennek a térképen. Így egy eleddig nem meghatározott mezőnek „0” értéke van, az akadályoknak egy nagyon magas szám (egy meghatározott .net egész-változótípus (a szimulátorban ez valós számként tárolódik) maximális értéke), a törölt mezőknek pedig egy nagyon alacsony. Kezdő illetőleg végpontból minden térképen csupán 1-1 lehet, így ezeket csak áthelyezni lehetséges. Az [Operation | Fill Territory] menüpontra kattintva az üresen hagyott mezők értéke „törlődik”, azaz feltöltődik egy adott értékhalmaz legkisebb elemével (ez jelenti, hogy a

63/107


mező értéke törölt), valamint a cél pont értéke „0” lesz. Ennek eredményét mutatja be a mellékletek között megtalálható 85. ábra. 7.1.3 Beállítási lehetőségek A [Setting | Color] hatására megjelenő párbeszédablakban beállíthatjuk az egyes elemek színét (akadály, kezdő pont, cél pont, írás, út illetőleg a háttér színét )(Mellékletek: 86. ábra). Ha zavaró hatással vannak a megjelenő értékek a terülten, és csupán a speciális mezők színét szeretnénk látni, kikapcsolhatjuk az értékek megjelenését a [View | Show values] segítségével. 7.1.4 Terjes terület törlése Lehetőségünk van arra is, hogy a teljes területet töröljük (a beállított akadályokkal együtt) az [Operation | Erase Territory] segítségével. 7.1.5 Hullámrajzolás A hullám-továbbterjesztéses algoritmusok lényege, hogy az útkeresés előtt előbb mindig hullámot határozunk meg, majd ezen keresünk utat egy maghatározott prioritási sor segítségével (lásd irodalomkutatás). A különféle hullámok meghatározásához a [Wave] főmenü használható. A „Simple Wave”, azaz egyszerű hullám az akadályok figyelmen kívül hagyásával a cél ponttól koncentrikus „körök” (négyzetek) segítségével hullámot terjeszt addig, amíg a kiindulási pontot el nem éri a hullám. Ez a megoldás csak teszt szerepet tölt be, gyakorlati haszna nincsen (Mellékletek: 87. ábra). A „Pathfinding Wave Basic” már egy használható megoldást ad, mely esetén a hullám szintén koncentrikus négyzetek formájában terjed, azonban az akadályok immáron figyelembe vannak véve (Mellékletek: 88. ábra). A „Pathfinding Wave 4 Directions” az előző hullámhoz képest annyival kifinomultabb, hogy itt az átlós irány egyel magasabb értékkel rendelkezik minden esetben, mint a szomszédos (Mellékletek: 89. ábra). A „Pathfinding Wave 8 Directions Real” már egy kifinomult megoldás, melyben az átlós irányok arányosan szerepelnek. Ilyen esetben a térképen szereplő értékek azonban valós számok, melyekkel a számolás egy valós program esetében lényegesen lassabb, mint egész számok esetén (a szimulációs program, itt az egész számok is valós értékekként vannak tárolva)(Mellékletek: 90. ábra). A „Pathfinding Wave 8 Directions Round” az előző módosított változata, melyben az átlós érték kerekítve vannak 2 -ről 1,4-re (Mellékletek: 91. ábra). Az utolsó hullám, és egyben a leggyorsabb és legpontosabb számítási eredményt adó (ebben az alkalmazásban) a „Pathfinding Wave 8 Directions Integer” menüpont hatására jeleníthető meg. Ebben az előző hullám értékei öttel fel vannak szorozva (58. ábra).

64/107


Ábra 58 Pontos hullám 7.1.6 Útkeresés Minden egyes megrajzolt hullám esetén lehetőségünk van legrövidebb utat keresni a [Pathfinding | Pathfinding with priority queue] menüpont segítségével. Az útkeresés menete minden esetben azonos. A cél ponttól elindulunk, és mindig a legkisebb értékű mezőre lépünk rá. A prioritási sornak ott van szerepe, ha több egyforma legkisebb mező létezik egy lépés során.

65/107


Ábra 59 Legrövidebb út Az alkalmazás által generálható legpontosabb hullámot felhasználva az 59. ábra mutatja be a legrövidebb utat. 7.1.7 Prioritási sor beállítása Lehetőségünk van a prioritási sor beállítására is a [Pathfinding | Priority queue] menüpont segítségével (60. ábra).

Ábra 60 Prioritási sor beállítása Minél kisebb érték szerepel adott helyen, annál nagyobb lesz a prioritása!

66/107


Ha a prioritási sor értékeinek végig 0 értéket állítunk be, akkor is lesz legrövidebb út, ugyanis semmi nem tiltja, hogy ne lehetne két, avagy az összes pontnak azonos prioritása. Ilyen esetben azonban a programkód dönti el (feldolgozási sorrendtől függ), hogy merre fog elhelyezkedni a legrövidebb utunk. A mellékletek között egy további, „nagyobb méretű” térképen meghatározott utat is meg lehet tekinteni.

7.2

Fejlesztési kézikönyv

Az alkalmazás hét Form-ból és két saját osztályból épül fel. Ezen utóbbi kettőt vizsgáljuk meg alaposabban. A CTerritory osztály tartalmazza a területtel kapcsolatos összes tulajdonságot illetőleg műveletet. A CTerritoryOperation a területek mentéséért, betöltéséért illetőleg a másolásukért felelős. 7.2.1 A CTerritory osztály A CTerritory.cs állományban lett implementálva a CTerritory osztály két struktúrával együtt.

67/107


7.2.2

Az osztály attribútumai illetőleg tulajdonágai

A NameOfTerritory a terület nevét, X és Y a méretét tárolja. A Territory egy két dimenziós valós számokból álló tömb. Valós, és nem szimulációs alkalmazásban itt egy egész számokból álló dinamikus tömb szerepelne, de itt a kevésbé hatékony problémák bemutatásának céljából ettől eltért a program. A cellX és cellY a megjelenítést befolyásolják. A StartPoint és a DestinationPoint az útkeresés kiindulási illetőleg cél pontját határozzák meg. Az útkereséshez szükséges prioritási sor is az osztályban van tárolva (PriorityQueue), valamint az út is (Way). Nyilvános attribútumként vannak felvéve az osztályba az egyes elemek színei. Mindegyik private attribútumhoz tartozik egy nyilvános tulajdonság (és mindegyik írható és olvasható):

68/107


7.2.3

Osztálymetódusok

Nézzük az egyes műveleteket táblázatos formában (61. ábra).

69/107


Ábra 61 CTerritory class 7.2.4 Hullám-továbbterjesztés algoritmusa A PathfindingWave függvény paraméterben megkapja, hogy mely segédeljárás fusson le a metóduson belül. A paraméter értékei a következők lehetnek: PathfindingWaveBasic (0) PathfindingWave4Directions (1) PathfindingWave8DirectionsReal (2) PathfindingWave8DirectionsRound (3) PathfindingWave8DirectionsInteger (4) Ezek közül az utolsó forráskódja szerepel a dolgozatban.

70/107


71/107


72/107


8 Graphs And Spanning Trees mini C# változat A Graphs and Spanning Trees nevű alkalmazás a gráf alapú térképek elkészítésére alkalmas. Mindehhez gyors és kényelmes, felhasználóbarát felületet biztosít. Ahhoz, hogy az elkészült gráf hálót fel tudjuk használni Pocket PC-n, és ott utat tudjunk keresni rajta, a TGraph osztály (Borland Delphi 7) ehhez szükséges részeit át kell írnunk C# nyelvre! A Graphs and Spannings Trees kétféle formátumban képes elmenteni az elkészített térképeket. Az egyik egy nagyrészt bináris file-okból álló csoport, míg a másik formátum teljesen szöveges állományokból épül fel. Ezen utóbbi alkalmas arra, hogy egy másik nyelven írt program is képes legyen beolvasni, és feldolgozni! Négy program készült el C# nyelven a fenti cél eléréséhez. Az első Graphs .net megvalósít egy PC-n futó alkalmazást, mely képes megnyitni egy gráf állományt, majd megjeleníti szövegesen listázva annak adatait. Ebben a programban van megvalósítva a CGraph osztály, mely a Borland Delphi 7 TGraph osztályának C# átirata. A Graph .net DLL az előző CGraph osztály DLL-be fordított változata, PC platformra. A GraphPDA DLL alkalmazás szintén a CGraph osztály DLL-be fordított változata, de Pocket PC platformra. A GraphPDA pedig a már Pocket PC-n futó, 2D grafikus megjelenítéssel rendelkező program, mely a megtalált út grafikus megjelenítésére is képes! Ez az alkalmazás lett az alapja a SmartPoseidon alkalmazásnak, melyet szaktársam Szirbik Ferenc készített el (ez tekinthető a Poseidon Navigation Project végleges programjának).

8.1

Graphs .net

Elindítva az alkalmazást az ’Open’ gombra kattintva *.grp állományokat tudunk megnyitni (62. ábra). A megnyitott file elérési útját szétbontja a program, és ezekből előállítja a szükséges *.das, *.dat, *.edg, *.pnt és *.was file-okat, melyeknek a *.grp file mellett kell lenniük (azonos file-névvel). A szükséges file-ok mindegyike szöveges állomány kell hogy legyen, erre a Graphs and Spanning Trees nevű alkalmazásban, mentéskor figyelni kell!

Ábra 62 Graph .net képernyőkép

73/107


A ’Start’ gombra kattintva megtörténik a gráf betöltése memóriába. Ezután a ’Graph’ nyomógomb hatására megjelennek a gráfunk adati szövegesen listázva (63. ábra).

Ábra 63 A gráf adatai szövegesen

8.2

GraphPDA

A GraphPDA alkalmazás felületét tekintve nagyon hasonlít a Graph .net programra (64. ábra).

Ábra 64 GraphsPDA képernyőkép Elindítás után a ’Dialog’ gombra kattintva egy *.grp file-t kell kiválasztanunk. Ezek után a ’Start’ gomb hatására a háttérben megtörténik a további file-ok pontos elérési útjainak meghatározása. A ’Begin’ gomb a gráf helyességét teszteli le. Ha minden rendben működik, akkor a NameOfGraph mezőben megjelenik a megnyitott gráf elnevezése. Kattintsunk az ’Open’ gombra, majd a [Menu | Show Graph] menüpontra.

74/107


Ábra 65 A 2D-s gráf Pocket PC-n A megjelenő ablakban (65. ábra) a Graphs and Spanning Trees 3D-s gráfjának két dimenziós változatát láthatjuk (a Z koordináta nincs figyelembe véve). A [PathFinding | Dijkstra] hatására pedig a szövegbeviteli mezőkben beállított pontok között a program utat keres, és sikeres út esetén egy ’OK’ felirat megjelenik.

8.3

C# osztályok

A felhasznált DLL-ben (GraphDotNetPDA.dll) három osztály lett implementálva. A CWorkFileName osztály egy elérési utat elemekre bont. A *.grp file elérési útjából így határozza meg a program a többi szükséges file elérését. A CFileGraph osztály a gráf megnyitásáért felelős, a CGraph oszály pedig a Borland Delphi 7-ben készített TGraph osztály átirata. 8.3.1 CWorkFileName osztály Négy nyilvános, statikus metódust tartalmaz az osztály:

Mivel a metódusok statikusok, nincs szükség objektum példányra a használatukhoz. A ’FullNameToDirName’ metódus a teljes elérési útból a teljes könyvtár elérést adja vissza. A ’FullNameToFileName’ a teljes elérési útból csupán a file nevét és kiterjesztését határozza meg. A ’FileNameToWithoutExtension’ visszadja az állomány nevéből a kiterjesztés nélküli megnevezést. És végül a ’FileNameToExtension’ visszaadja az állomány nevéből a kiterjesztését.

75/107


8.3.2 CFileGraph osztály A CFileGraph osztály felel a gráfok különböző állományainak megnyitásáért. Szintén statikus, nyilvános metódusokat tartalmaz.

Az OpenGraph metódus meghívása esetén minden további metódus meghívása is megtörténik, így elegendő ezen egy nyilvános metódust használni. A ToMyDouble nyelvi ütközések elkerülése miatt használatos (tizedesvessző illetve tizedespont használata). 8.3.3 CGraph osztály A CGraph.cs forrásállományban található a CGraph osztály GraphsDotNet névtér alatt. Ebben az állományban az osztály adattagjaihoz szükséges struktúrák is elhelyezkednek.

A struktúrák és a CGraph forráskódja a mellékletek között megtalálható.

76/107


9 A Pocket PC és a GPS összekapcsolása A fejezet bemutatja a PDA és a GPS készülék közti összekapcsolás szoftware-es megoldásait. Bemutatja az első próbálkozásokat GPS adatok kinyerésére HyperTerminalon keresztül (soros port), majd bemutat egy Delphi 7-ben írt programot a soros port kezelésére. Elkészült egy Microsoft Visual Studio 2003 .net-ben írt NMEA GPS kódot olvasó program is, mely az alapja a Poseidon Navigation Project Pocket PC-n futó alkalmazásának. Fontos lépés a GPS koordináták és a térkép pontjainak összerendelése. Erről is szól egy alfejezet. Mindezen részletek Szirbik Ferenc dolgozatában olvashatóak.

77/107


10 Eredmények Az elért végeredmény nem teljesít mindent, amit a cél meghatározásában kitűztünk magunk elé. Ennek ellenére alapjaiban az alkalmazás/alkalmazások működnek, és használhatóak.

Ábra 66 Az elkészült alkalmazás futás közben Elkészült egy, a térképek megrajzolására, szerkesztésére és adatfeltöltésére alkalmas program Borland Delphi 7 környezetben. Megvalósult egy a hullámtovábbterjesztéses algoritmusok bemutatását célzó útkereső program is Visual Studio 2003 .net-ben, bár ez nem épül bele a végső alkalmazásba. Készítettünk számos segédalkalmazást, mely soros portok kommunikációját teszteli, a térképek konvertálását végzi, avagy csak útkeresést szimulál Pocket PC-n, és asztali gépen egyaránt. A Smart Poseidon a végleges programunk. Ennek segítségével megjeleníthetünk egy tetszőleges térképet, és rajta megmutatja az éppen aktuális, vagy egy tetszőlegesen bevitt koordinátát. A kettő közötti legrövidebb utat a megadott feltételek szerint megtalálja. A program működéséhez szükséges, hogy előzetesen beállítsuk a soros portot, és megadjuk a szükséges három (illetve négy) koordináta összerendelést. A szükséges kép egy tetszőleges bittérkép lehet (*.bmp kiterjesztéssel) (természetesen érdemes előzőleg megrajzolt, vagy beolvasott térképet feltölteni). A program képes rá, hogy a PPC-n a egy tetszőleges pontra mutatva a térképen, megjelenítse annak koordinátáit, ez használható a cél pont kijelölésére.

78/107


Ábra 67 Kábeles kapcsolat a GPS és a Pocket PC között A program jelenlegi verziója nem foglalkozik közlekedési eszközökkel, KRESSZ szabályokkal és haladási sebességgel sem, de megvalósult a több szempont alapján működő útkeresés és a Budapesti Műszaki Főiskola egy épületének és környékének térképe, melyen a gyakorlatban is kipróbálható az alkalmazás.

79/107


11 Mellékletek 11.1

Gráfok [4]

Gráfokkal kapcsolatosan néhány definíciót érdemes megfogalmazni. Két él szomszédos, ha valamely csúcspontjuk közös. Ha két csúcsot egynél több él köt össze, akkor ezt többszörös élnek nevezzük. Egy másik speciális él a hurokél. Ennek kezdőpontja és végpontja megegyezik. Két csúcs szomszédes, hogyha éllel vannak összekötve. Egy pont izolált, ha nem illeszkedik rá él. Egy pont fokszáma a rá illeszkedő élek számát jelenti. Irányított gráfnak kifoka és befoka van. 11.1.1 Egyszerű gráf Egy gráf egyszerű gráf, hogyha nincs benne többszörös él vagy hurokél. A gráf teljes és egyszerű gráf, ha bármely két csúcsa szomszédos. 11.1.2 Izomorfia Két gráf izomorf, ha van csúcsai között olyan bijekció, hogy valahányszor két csúcs szomszédos az egyik gráfban, a nekik megfelelő pontok szomszédosak a másikban is. Összefüggőség A G gráfról akkor mondjuk, hogy összefüggő, ha bármely két csúcshoz tarozik G-beli út, mely a két csúcsot összeköti.

11.2

Graphs and Spanning Trees

A Graphs and Spanning Trees felhasználói kézikönyvének ismertetésekor számos képernyőkép segítheti a program funkcióinak megértését, azonban a dolgozat olvashatóságát rontja a sok képpel szabdalt szöveg. Ebből kifolyólag ezen képek itt kerülnek bemutatásra.

Ábra 68 Program indulása utáni képernyőkép

80/107


Ábra 69 Új elem hozzáadása a gráf-pontok illetve a súlyvektor listájába

Ábra 70 Egy létrehozott új gráf

Ábra 71 Megjelenítési beállítások

81/107


Ábra 72 Globális konstansok és változók

Ábra 73 Koordináta grafikus beállítása

Ábra 74 Gráf pont kiválasztása

82/107


Ábra 75 Él kiválasztása

Ábra 76 A gráf tulajdonságai

83/107


Ábra 77 Aktuális súly beállítása

Ábra 78 A kapcsolatmátrix

84/107


Ábra 79 Egy új gráf pont felvétele

Ábra 80 Új gráf élek felvitele

85/107


Ábra 81 Gráf pont grafikus mozgatása

Ábra 82 Műveletek véglegesítése

86/107


Ábra 83 Multi Editor

Ábra 84 Súlyok együttes szerkesztése

87/107


11.3

TObject3D osztály

11.3.1

A konstansok

A MAXPOINTS határozza meg, hogy maximálisan mennyi grafikai pont lehet az ábrán. A program ezen része is teljesen statikus működésre van felkészítve, a későbbi programverziók legfontosabb lépése a dinamikus tárolás megvalósítása lesz. A MAXEDGES értelemszerűen a maximálisan ábrázolható grafikai élek számát jelenti (a grafikai élek és pontok száma nem egyezik meg a gráf éleinek és pontjainak számával). A MAXARMS egy belső konstans, mely korlátozásával (3 a legkisebb értéke) a TObject3D osztály egy lényeges funkcióját elérhetetlenné tesszük. Képes lenne az osztály több elem tárolására (mindegyiket külön lokális koordinátarendszerben), és ezen elemeket egy osztálypéldány tagjaiként egymáshoz képest mozgatni, forgatni tudnánk. Ezt a MAXARMS határozza meg, hogy mennyi ilyen elem tárolható egy példányban. Az első elem nem tényleges elem, itt nem tárolhatunk adatot. Ez a bázis koordinátarendszer miatt szükséges. A másodikban tároljuk a tárgyainkat, és ennek biztonságos kezeléséhez (mutatók elérik még a következő elemet is) szükséges még egy elem. Ezért három az értéke minimálisan a MAXARMS-nak. Az ACCURANCY egy pontosság érték. Két valós számot az osztály már egyenlőnek tekint, ha ezen értéknél kisebb a különbség közöttük. 11.3.2

Típusok

88/107


A TTrans mátrix tartalmazza a transzformációs műveleteket (forgatás, eltolás, stb.). A TVector3D egy 3D-s vektor avagy egy pont tárolására alkalmas. A TPoint4D ehhez hasonlósan a homogén koordinátás alakban képes ugyanerre. A TCoords a koordinátatengelyek homogén koordinátás alakjait tárolja. A TPoints tömbben találhatók a grafikus pontok, a TEdges tömbben pedig a grafikus élek adatai. A TPointsColor minden pontra tárolja a színét, a TPointsLabel pedig egy feliratot, mely szintén megjelenhet, ha a beállítások ezt engedik. A TMatrix3x3 egy 3D-s környezetben tárolt mátrix. A TDataArray tárolja az egyes elemek (amiből a Graphs and spanning trees csak ténylegesen egyet használ) adatait. 11.3.3

Változók

A változók az egyes feliratok láthatóságát, illetve színét állítják be. A TEXTOVERWRITE igaz értéke esetén a feliratok háttere átlátszó lesz. Így bár több információ lesz az ábrán, ám ezek kevésbé olvasható formában jelennek meg.

89/107


11.3.4

Az osztály

90/107


11.4

TGraph osztály

11.4.1

A konstansok

A MAXITEM határozza meg, hogy statikus esetben egy élen mennyi súly, illetve egy pontban mennyi adat tárolható. A MAXGRAPHPOINTS és a MAXGRAPHEDGES a gráf pontjaira illetve éleire meghatározott statikus korlát. A MAXSHAPEPOINTS meghatározza, hogy egy gráf pont minta 3D-s objektuma maximálisan mennyi grafikai pontból állhat. A SHAPEDIRECTORY és a SAVEDIRECTORY az alapértelmezett könyvtárakat állítja be, míg a SHAPELISTFILENAME a minták listáját tároló file nevét. 11.4.2

A változók

A gráf irányítottságát grafikailag jelölni többféleképpen lehet. A DIRECTIVITYLENGTH és a DIRECTIVITYLENGTH2 változók lehetővé teszik, hogy hosszabb, illetve nagyobb nyilakat tudjunk megjeleníteni. A WayColor a megtalált út színét határozza meg.

91/107


11.4.3

A típusok

A TRec rekord tárolja a súlyvektor illetve a pontok adatainak tulajdonságait a gráf tulajdonságai között. A TRecArray vektor tárolja a TRec típusú elemeket a statikus súlyvektor és gráf pont adatvektor számára. A TGraphDataArray a pontok adatainak statikus vektora szinkronban TRecArray-el. A TGraphWeightsArray a statikus súlyvektor szinkronban TRecArray-el. A TPointRec rekord tárolja egy adott gráf pont tulajdonságait. Az ’Enable’ határozza meg, hogy logikailag törölt-e az elem, avagy sem. Az ’X’,’Y’ és ’Z’ a koordinátáit határozza meg, a ’Serial’ az automatikusan generálódó sorszámát, a ’Name’ a nevét, az ’AllowName’

92/107


ennek a létezését. A ’Shape’ az adott grafikai mintát tároló file neve, a ’Color’ pedig a gráf pont színe. A ’DataArray’ tárolja a TGraphDataArray-el szinkronban a gráf csomópontjaiban tárolt adatokat. A TEdgeRec rekord a gráf éleinek tulajdonságait tárolja. Az ’Enable’ itt is a logikai töröltségre utal, a ’Serial’, ’Name’, ’AllowName’ és ’Color’ szintén azonos jelentéssel bír, mint a gráf pontjai esetén ezt már láttuk. A ’PointOne’ és ’PointTwo’ határozza meg az él által összekötött két pont sorszámát. A ’Directivity’ ennek függvényében az irányítottságot jelölheti. Ha értéke ’0’, akkor nincs irányítottság. Irányított gráf esetében ez azt jelenti, hogy oda-vissza út létezik (ezt a későbbiekben le lehet majd tiltani, mivel előfordulhat olyan probléma, mely során ezt nem célszerű alkalmazni, azonban térkép program esetén a kétsávú utat ezzel tudjuk modellezni)! Az ’IsWay’ logikai változó igaz értéke esetén az adott él a legutolsó útszámítás során az eredmény része volt. Ilyenkor a színe a saját ’Color’ tulajdonsága helyett a ’WayColor’ lesz. A TPointsArray és a TEdgesArray tárolják a pontokat és az éleket statikus esetben. A TRelationMatrix a kapcsolatmátrix típusa. A TPFRec és a TPFArray Dijkstra legrövidebb út kereső algoritmusához szükséges. TPArray-ben fog keletkezni az eredmény.

93/107


11.4.4

Az osztály

11.5

TypeUnit

11.5.1

További típusok

A TPair egy segédtömb, mely a gráf pont minták gráfhoz illesztéséhez szükséges. A probléma, melyet meg kellett oldani, hogy egy TObject3D adatmezőit (minta) egy másik TObject3D típusba (a gráfba) kellett átmásolni. Ilyenkor a pontok sorszáma megváltozik, de mivel az élek is a pontok eredeti sorszáma alapján tárolódnak, ezért az éleket párosítani kellett a pontokkal.

94/107


11.5.2

További eljárások illetve függvények

11.6

From Game to Map

Ábra 85 Térkép szerkesztése

95/107


Ábra 86 Színek beállítása

Ábra 87 Simple Wave

Ábra 88 Pathfinding Wave Basic

96/107


Ábra 89 Pathfinding Wave 4 Directions

Ábra 90 Pathfinding 8 Directions Real

97/107


Ábra 91 Pathfinding Wave 8 Directions Round

Ábra 92 Egy nagyobb térkép példája

98/107


Ábra 93 Hullám egy nagyobb térképen

Ábra 94 Legrövidebb út egy nagyobb térképen

99/107


11.7

GraphsDotNet Namespace

11.7.1

Struktúrák

100/107


101/107


102/107


103/107


11.7.2

CGraph osztály

104/107


105/107


106/107


12 Irodalomjegyzék

107/107

POSEIDON NAVIGATION PROJECT

Recommend Documents