POSEIDON NAVIGATION PROJECT

OTDK dolgozat

POSEIDON NAVIGATION PROJECT iNtelligent Map with Rules of Traffic

Készítette: BED

K DÁVID, SZIRBIK FERENC

KONZULENSEK: VÁMOSSY ZOLTÁN (DOCENS), MOLNÁR ANDRÁS (ADJUNKTUS)

2004. november 8. Budapesti M szaki F iskola – Neumann János Informatikai F iskolai Kar

Informatikai és Automatizált Rendszerek szakirány

POSEIDON NAVIGATION PROJECT

IAR

TARTALOMJEGYZÉK

TARTALOMJEGYZÉK TARTALOMJEGYZÉK................................................................................................................2 1. FEJEZET - CÉL MEGHATÁROZÁSA .....................................................................................5 2. FEJEZET - AZ IRODALOMKUTATÁS ÉS ÉRTÉKELÉSE ..........................................................7 2.1 - AZ ÚTKERESÉSR L ÁLTALÁBAN ...................................................................................7 English ......................................................................................................................7 Magyar......................................................................................................................7 2.2 - ÚTKERESÉS A JÁTÉKOK VILÁGÁBAN [2]........................................................................7 2.2.1 - Szimulációs program: From Game To Map.......................................7 2.2.2 - Csapdák ........................................................................................................8 2.2.3 - Algoritmusok alapja ..................................................................................8 2.2.4 - Dijkstra algoritmusa és a Best-First-Search.....................................9 2.2.5 - Az A* algoritmus .....................................................................................10 2.3 - A HULLÁMTOVÁBBTERJESZTÉSES ALGORITMUS [3] .................................................... 11 2.3.1 - Legrövidebb út .........................................................................................11 2.3.2 – Hullám-továbbterjesztéses algoritmus finomítása....................... 13 2.3.3 - Legbiztonságosabb út, Voronoi diagramm ...................................... 16 2.3.4 - Megjegyzések ........................................................................................... 18 2.3.5 - Implementálás ......................................................................................... 18 2. 4 - GRÁFOK, MINIMÁLIS KÖLTSÉGTÉRÍTÉS FESZÍT FA, ÉS A LEGRÖVIDEBB ÚT [4] .......... 20 2.4.1 - Néhány definíció ......................................................................................20 2.4.2 - Gráfok .........................................................................................................20 2.4.3 - Gráfok ábrázolása ................................................................................... 20 2.4.4 - Minimális költségtérítés feszít fa ..................................................... 22 Algoritmusa ........................................................................................................... 22 2.4.5 - Legrövidebb út [4] ..................................................................................23 A legrövidebb út fogalma ..................................................................................... 23 Az algoritmus lényege .......................................................................................... 23 Az algoritmus részletesebben ............................................................................... 25 Az algoritmus pszeudokódja ................................................................................ 25 2.4.6 - Szimulációs program: Graphs and spanning trees ...................... 26 2.4.7 - Megjegyzések ........................................................................................... 26 2.5 - A POSEIDON NAVIGATION PROJECT ÉS A GPS ............................................................ 27 2.5.1 - A globális helymeghatározó rendszer a GPS [7]...........................27 Egy kis történelem ................................................................................................. 27 Mi a helyzet ma? ....................................................................................................27 Van számos m hold felettem, van egy vev m, mib l fogja tudni a m hold, hogy hol vagyok?...................................................................................................28 A kommunikáció ...................................................................................................28 Ha ez ilyen jó, akkor miért a pontatlanság, mik a felmerül hibák? ................. 29 A hibák adottak, szerencsére van megoldásuk is, mi jöhet még? ..................... 30 A GPS felhasználása térképprogramok esetén ................................................... 30 2.5.2 - A tesztelt GPS készülékek .................................................................... 30 2.5.3 - µ-Blox MS1E GPS vev modul [5].......................................................30 Rövid ismertet ...................................................................................................... 30 A készülék megbízhatósága ................................................................................. 31 76/2.


IAR

TARTALOMJEGYZÉK

Feléledési id k ....................................................................................................... 31 Technikai áttekintés ............................................................................................... 32 ködési feltételek ...............................................................................................32 Kimeneti tüskék leírása .........................................................................................32 Soros Interfész Jel................................................................................................... 33 Speciális táp-tüskék ............................................................................................... 33 Jel meghatározás .................................................................................................... 33 A feszültségszint-konvertáló áramkör................................................................. 34 A soros port ............................................................................................................34 A GPS készüléket és a PocketPC-t összeköt elektronika.................................35 Megjegyzés ............................................................................................................. 35 A tesztszoftver ....................................................................................................... 35 2.5.4 - A Garmin eTrex Vista készülék [6].................................................... 36 A választott protokoll a GPS készülékkel való kommunikációhoz .................. 36 Talker sentences – Közl mondatok..................................................................... 36 Proprietary sentences – Gyártóspecifikus mondatok ......................................... 36 Query sentences – Lekérdez mondatok............................................................. 36 Az adatok lekérdezésének megvalósítása ........................................................... 37 A soros portról történ olvasás ............................................................................ 38 2.6 - DESTINATOR 3 AVAGY MIT TUD A PIAC JELENLEG?....................................................40 3. FEJEZET - A HARDWARE ÉS A SOFTWARE .....................................................................41 3.1 - A KEZDET..................................................................................................................41 3.2 - A FEJLESZT I KÖRNYEZET ......................................................................................... 41 3.3 - POCKET PC TESZTKÉSZÜLÉK......................................................................................42 3.4 - AZ ELS FUTÓ PROGRAM ........................................................................................... 43 3.5 - GPS TESZTKÉSZÜLÉK ................................................................................................43 3.6 - A .NET RÖVID BEMUTATÁSA ..................................................................................... 44 3.7 - ÚJ PROGRAMNYELV ÉS FEJLESZT I KÖRNYEZET .......................................................... 45 3.8 - A SOFTWARE ALAPVET MODULJAINAK LEÍRÁSA (0. RENDSZERTERV) ......................... 45 3.8.1 - Nulladik rendszerterv modulljai ..........................................................45 3.8.2 - Az egyes modulok kapcsolata ............................................................. 46 3.8.3 - Egyes modulok leírása ...........................................................................46 3.8.3.1 - Adatbeviteli modul .................................................................................. 46 3.8.3.2 - Kapott adat értelmezése .......................................................................... 46 3.8.3.3 - Felhasználói felület modul ......................................................................46 3.8.3.4 - Térképkezel modul ................................................................................ 46 3.8.3.5 - Adatbázis .................................................................................................. 47 3.8.3.6 - Software frissítések kezelése ................................................................... 47 3.9 - A RENDSZER ÖSSZEÁLL (1. RENDSZERTERV) ............................................................... 47 3.10 - AZ ELKÉSZÜLT GPS .................................................................................................48 3.10.1 - A Pocket PC és a GPS összekötése .................................................48 3.10.2 - Kommunikáció tesztelés .....................................................................49 Teszt I...................................................................................................................... 49 Teszt II .................................................................................................................... 49 Teszt III ................................................................................................................... 49 Teszt IV ...................................................................................................................49 3.11 - MIKROSZKÓP ALATT A GRÁF FELÜLET ...................................................................... 49 76/3.

POSZEIDON NAVIGATION PROJECT

IAR

CÉL MEGHATÁROZÁSA

4. FEJEZET - GRAPHS AND SPANNING TREES.....................................................................52 4.1 - A PROGRAMRÓL ÁLTALÁBAN ..................................................................................... 52 4.2 - FELHASZNÁLÓI KÉZIKÖNYV ....................................................................................... 52 4.2.1 - Új gráf létrehozása ................................................................................. 52 4.2.2 - Gráf megnyitása ...................................................................................... 54 4.2.3 - Globális beállítási lehet ségek ............................................................ 54 4.2.4 - Lokális beállítások ................................................................................... 55 4.2.5 - Új gráf pont felvétele .............................................................................55 4.2.6 - Új él felvétele a gráfba .......................................................................... 56 4.2.7 - Gráf pontok és élek módosítása illetve törlése..............................56 4.2.8 - Gráf tulajdonságainak utólagos beállítási lehet sége ................. 57 4.2.9 - Az aktuális súly illetve gráf pont adat beállítása...........................57 4.2.10 - Gráf mentése..........................................................................................57 4.2.11 - Kapcsolatmátrix generálása ..............................................................57 4.2.12 - Legrövidebb út meghatározása Dijkstra algoritmusa alapján 58 4.3 - FEJLESZT I DOKUMENTÁCIÓ ......................................................................................58 4.3.1 - A programról ............................................................................................. 58 4.3.2 - A TObject3D osztály ...............................................................................58 4.3.3 - A TGraph osztály .....................................................................................59 4.3.3.4 – Algoritmusok ........................................................................................... 60 4.3.4 – A TypeUnit további részei .................................................................... 61 4.4 - TESZTELÉS ................................................................................................................ 62 4.5 - BEÁGYAZÁS A POSEIDON NAVIGATION PROJECT-BE ...................................................62 5. FEJEZET – A PPC ÉS A GPS ÖSSZEKAPCSOLÁSA..........................................................63 5.1. A HARDVERES KAPCSOLAT..........................................................................................63 5.1.1 Rövid ismertetés .........................................................................................63 5.2 SZOFTVERES ILLESZTÉS ...............................................................................................63 5.2.1 PC és GPS eszköz közötti kommunikáció – az els lépések ......... 63 5.2.2 PC és GPS eszköz közötti kommunikáció – programfejleszt i környezetekb l .......................................................................................................64 5.2.3 Az NMEA GPS kód kezelése.....................................................................66 5.2.4. A GPS koordináták alapján pozícionálás térképen ......................... 68 6. EREDMÉNYEK ÖSSZEFOGLALÁSA .................................................................................... 70 7. FEJEZET - IRODALOM JEGYZÉK ...................................................................................... 72 7.1 - IDÉZETEK, FORRÁSOK ................................................................................................ 72 7.2 - KÉPEK, GRAFIKÁK ..................................................................................................... 73

76/4.


IAR


1. FEJEZET - 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 GPS (globális helymeghatározó rendszer) – mint az elmúlt évek talán egyik legnagyobb technikai csodája – a navigálás területén nyújt rendkívül pontos információkat számunkra, gyakorlatilag azonnal. Egy GPS vev készülék által szolgáltatott jelekb l az átlagos ember nem képes információt kinyerni, azonban egy számítógéppel összekötve, az adatokat egy térképen megjelenítve a navigáció egy új dimenzióját nyithatja meg számunkra. Természetesen nem vihetünk magunkkal egy asztali számítógépet vadvízi evezés, vagy hegymászás során, így egy PDA, azon belül is a többfeladatos Microsoft Windows Mobile operációs rendszert futtató Pocket PC a megfelel cél-hardware és software környezet a feladat megoldására. Egy interaktív térkép nem csupán azt képes megmondani nekünk, hogy jelenleg hol vagyunk a térképen, hanem megtanítható útkeresésre is, ezzel segítve tájékozódásunkat a világban. Az útkeresés kérdésköre nagyon szerteágazó, hisz az ember más utat választ, ha siet, mást, ha kerülni akarja a rossz min ség földutat és mást, ha a legrövidebbet szeretné megkapni. Ugyancsak nem mindegy az eredmény szempontjából, hogy egy gráf, avagy egy grafikus interface-en keresztül jutunk el célunkhoz, avagy a kett kombinációjával. 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. Ezt a modern rendszerekben, és így a mienkben is egy GPS készülék segítségével a felhasználó gyorsan beazonosíthatja. Amennyiben nem rendelkezik GPS készülékkel, egy egyszer keres funkció segítségével ezt a pontot az ember maga is kijelölheti. 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 szoftveres megoldást alkalmazunk majd, hiszen több mint valószín , hogy az illet annak a környezetnek a közelében van, amit az elmúlt pár percben megjelölt a GPS, vagy a felhasználó a jelenlegi helyzetének, így a szoftver felajánl egy közeli pontot valahol az el koordináta, és az el leg kijelölt cél között, a keresett úti cél és a felhasználó sebességét figyelembe véve. Ezt azután az ember módosíthatja, de ekkor már valószín leg ismer s neki a környék. Az útkeresés e pont és a cél pont között zajlik majd. Ezt 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ó közepére nincs út, avagy az autópálya négy sávja közepére. 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 76/5.

POSZEIDON NAVIGATION PROJECT

IAR


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 (több szint: minden közlekedési módszernek külön gráf-háló). Lehet e 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 ket, 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.

76/6.


IAR

IRODALOMKUTATÁS

2. FEJEZET - AZ IRODALOMKUTATÁS ÉS ÉRTÉKELÉSE A következ rész az irodalomkutatást öleli fel. Az els részében az útkeresés, a másodikban a GPS alkalmazásának a lehet ségeit vizsgálja. Az ezekkel kapcsolatos észrevételek és értékelések a leírás során folyamatosan kerültek beszerkesztésre.

2.1 - AZ ÚTKERESÉSR

L ÁLTALÁBAN

Egy egyszer idézettel kezdeném az útkeresésr l szóló fejezetet, mely rávilágít a probléma fontosságára, és hogy nem véletlenül egy külön alfejezet az irodalomkutatásban. A fordítás nem szó szerint történt, a saját szavaimmal próbáltam elmondani valami hasonlót. English Pathfinding is one of the most visible types of Artificial Intelligence in video games. Few things make a game look "dumber" than bad pathfinding. Fortunately, pathfinging is mostly a "solved" problem. If you ask most game developers "How to I do pathfinding?", the vast majority will answer "A*". [1] Magyar 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.

2.2 - ÚTKERESÉS A JÁTÉKOK VILÁGÁBAN [2] „The problem we're trying to solve is to get a game object from the starting point to a goal [2]”. Azaz 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. 2.2.1 - Szimulációs program: From Game To Map Terveim között szerepel a fent leírtak megvalósítása. Valami olyasmi szimulációs programot képzeltem el, mely 1.0-ás verzióban egy testre, és 2D-ben akadályokkal övezett területet ad megoldást különféle algoritmusok alapján. A 2.0-ás verziót akkor nevezem majd „kész”-nek, ha a fent leírt dolgokat „ellenségekkel” övezett területen is végrehajtja. Ellenségnek nevezem a mozgó akadályokat. A következ (3.0) verzióban már 3D-ben szimulálva hajtom végre ugyanezt, majd a végs verzióban újfent el jönnek az ellenségek. Amit ebb l a térképprogramba fel tudunk majd használni, az a 3.0-ás verzió, ám roppant hasznos lehet egy jól m köd 4.0-ás is, más feladatok megoldására. „.[…] avoiding obstacles, avoiding enemies, and minimizing costs (fuel, time, distance, equipment, money, etc.) [2]” 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 76/7.


IAR

IRODALOMKUTATÁS

az algoritmusnak, szintúgy ellenségeket (mondjuk autókat: ha gyalog megyünk, nem mehetünk rá az útra sem). É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. 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” rendelkezik. „At one extreme, a sophisticated pathfinder coupled with a trivial movement algorithm would find a path when the object begins to move and the object would follow that path, oblivious to everything else. [2]” Bonyolultan szép az élet, azaz 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 RTS játékban gondolkozunk) – mozognak, így minden ilyen ellenség pontot újra kell vizsgálni minden megtett lépés után, és a legrövidebb, avagy legkisebb költségekkel rendelkez utat újra számolni. Fontos dolog az is, hogy nehogy beragadjunk, és pár adott pont között mozogjunk, „emlékezet” segítségével erre el re fel kell készítenünk algoritmusunk. Ez a memória, változó méret lehet, egy dinamikus lista segítségével a gyakorlatban az „élethez” lehet majd igazítani. 2.2.2 - Csapdák

[1. ábra – Csapda] Az [1. ábra]-n szürkével jelölt területet nevezhetjük csapdának. Ugyanis az els 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élt. Természetesen, ha a cél a szürke részen belül van, akkor az nem csapda abban a szituációban. 2.2.3 - Algoritmusok alapja Számos útkeres algoritmus a [2. ábra]-hoz hasonló grid-et használ. A 2D-s képen jelöltek a kapcsolódási pontok, azaz hogy honnan hova lehet eljutni. A 76/8.


IAR

IRODALOMKUTATÁS

gyorsabb algoritmus é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 elképzelhet ennek lassúsága)

[2. ábra – Grid] 2.2.4 - Dijkstra algoritmusa és a Best-First-Search „Dijkstra's algorithm is guaranteed to find a shortest path from the starting point to the goal, as long as none of the edges have a negative cost. [2]”. Azaz Dijkstra algoritmusa garantálja nekünk a legrövidebb út megtalálását a start és cél pont között. [3. ábra – Dijkstra] A [3. ábra]-n látható a kiinduló pont középen, és a kék célpont. A kékes színek azok a területek, amelyeket az algoritmus „szkennelt”. A Best FirstSearch (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. „BFS is not guaranteed to find a shortest path [2]”, azaz a BFS nem garantálja a legrövidebb utat, de sokkal rövidebb id alatt talál megoldást. A [4. ábra]-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.

[4. ábra - Best first serach] 76/9.


IAR

IRODALOMKUTATÁS

Ez mind nagyon szép, de nézzük most olyan példát, amikor a térképen akadályok vannak: az [5. ábra] bal oldalán Dijkstra algoritmusát, míg a jobb oldalán a BFS-t láthatjuk.

[5. ábra – Akadályok] „The trouble is that BFS is greedy and tries to move towards the goal even if it's not the right path. [2]” A lényeg, hogy bár a BFS egyszer esetekben gyorsnak nhet, egy kis probléma esetén a futási id már sokkal kevésbé szembet 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 algoritmus el nyeit egyesíti. 2.2.5 - Az A* algoritmus „A* can guarantee a shortest path [2]”. 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: „A* is the most popular choice for pathfinding [2]” (a legnépszer bb algoritmus), mivel rendkívül rugalmas, és széles körben használható.

[6. ábra - A* algoritmus] Egy kis magyarázat a [6. ábra]-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ért távolságot. 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. A technikai, matematikai és implementálási részleteket a From Game To Map fejleszt i kézikönyvében olvashatóak lesznek.1

Jelen dokumentáció készültekor a From Game To Map szimulációs program, és így a hozzá tartozó leírás sem készült el. E feladatok megvalósítása egy kés bi fázisban fog el kerülni. 1

76/10.


IAR

IRODALOMKUTATÁS

2.3 - A HULLÁMTOVÁBBTERJESZTÉSES ALGORITMUS [3] Valójában két technikáról van szó, mely nagyon hasonló ötleten alapszik. Maga az el 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 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. Ellenben itt 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. 2.3.1 - Legrövidebb út Nézzük, hogy is m ködnek ezek az algoritmusok. A [7. ábra]-n fogunk vizsgálódni. 254 254

255

254 254 254 254 254

0

[7. ábra – 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).

76/11.


IAR

El ször a hullám-továbbterjedéses algoritmust nézzük. 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 [8. ábra].

IRODALOMKUTATÁS

9 9 9 9 9 9 9 9 10 255

8 8 8 8 8 8 8 9 10 11

8 7 7 7 7 7 8 9 10 11

8 7 6 6 6 254 254 254 254 254

8 7 6 5 5 5 5 5 5 5

8 7 6 5 4 4 4 4 4 4

8 254 254 5 4 3 3 3 3 3

8 7 6 5 4 3 2 2 2 2

8 7 6 5 4 3 2 1 1 1

8 7 6 5 4 3 2 1 0 1

[8. ábra - Egyszer hullám] 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 most 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 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 lehetséges példa a [9. ábra]. 4 3 2

5 1

6 7 8

[9. ábra - Prioritási sorrend] Minél nagyobb a prioritása adott iránynak, annál túlél bb lesz, ha dönteni kell. A [9. á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 [10. ábra]-n a fenti prioritási sor, és a térképünk által meghatározott utat látjuk.

76/12.


9 9 9 9 9 9 9 9 10 255

8 8 8 8 8 8 8 9 10 11

IAR

8 7 7 7 7 7 8 9 10 11

8 7 6 6 6 254 254 254 254 254

8 7 6 5 5 5 5 5 5 5

IRODALOMKUTATÁS

8 7 6 5 4 4 4 4 4 4

8 254 254 5 4 3 3 3 3 3

8 7 6 5 4 3 2 2 2 2

8 7 6 5 4 3 2 1 1 1

8 7 6 5 4 3 2 1 0 1

[10. ábra - 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 ([11. ábra]). [11. ábra - Második megoldás] 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 is látszik, 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 8 7 6 kezdtem a hullám-továbbterjesztéses 1 5 algoritmus leírását, hogy „nem biztosítja 2 3 4 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. 9 9 9 9 9 9 9 9 10 255

8 8 8 8 8 8 8 9 10 11

8 7 7 7 7 7 8 9 10 11

8 7 6 6 6 254 254 254 254 254

8 7 6 5 5 5 5 5 5 5

8 7 6 5 4 4 4 4 4 4

8 254 254 5 4 3 3 3 3 3

8 7 6 5 4 3 2 2 2 2

8 7 6 5 4 3 2 1 1 1

8 7 6 5 4 3 2 1 0 1

2.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 ([12. ábra]).

76/13.


17 16 15 14 13 14 15 16 17 255

16 15 14 13 12 13 14 15 16 17

IAR

15 14 13 12 11 12 13 14 15 16

14 13 12 11 10 254 254 254 254 254

13 12 11 10 12 11 254 9 11 10 254 8 10 9 8 7 9 8 7 6 8 7 6 5 7 6 5 4 6 5 4 3 5 4 3 2 6 5 4 3

IRODALOMKUTATÁS

9 8 7 6 5 4 3 2 1 2

8 7 6 5 4 3 2 1 0 1

[12. ábra - Négyirányú hullám] Bár az rögtön szembet nik, hogy több súlyra volt szükségünk, mint az el esetben, de ez nem befolyásolja az algoritmus futási idejét, és a megoldás ([13. ábra]) valamivel életszer bb lesz (itt is a már sokszor használt nyolcirányú prioritási sort alkalmazva). 17 16 15 14 13 14 15 16 17 255

16 15 14 13 12 13 14 15 16 17

15 14 13 12 11 12 13 14 15 16

14 13 12 11 10 254 254 254 254 254

13 12 11 10 12 11 254 9 11 10 254 8 10 9 8 7 9 8 7 6 8 7 6 5 7 6 5 4 6 5 4 3 5 4 3 2 6 5 4 3

9 8 7 6 5 4 3 2 1 2

8 7 6 5 4 3 2 1 0 1

[13. ábra - 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 – SQRT(2) súlyt kapnak. Ez egy nagyon csúnya 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 az el algoritmusokhoz), így egy közelít értékkel célszer számolni, mondjuk 7/5-el (1.4 az ~1.4142 helyett)([14. ábra]), melyet aztán felszorozva 5-el ([15. ábra]) minden egyes mez re egész számot kapunk, melyekkel a processzor gyorsabban „tud” számolni.

76/14.


12,20 11,80 11,40 11,00 10,60 11,00 11,40 11,80 12,80 255,00

11,20 10,80 10,40 10,00 9,60 10,00 10,40 11,40 12,40 13,40

10,80 9,80 9,40 9,00 8,60 9,00 10,00 11,00 12,00 13,00

IAR

10,40 9,40 8,40 8,00 7,60 254,00 254,00 254,00 254,00 254,00

10,00 9,00 8,00 7,00 6,60 6,20 5,80 5,40 5,00 5,40

IRODALOMKUTATÁS

9,60 9,80 8,80 8,40 8,00 8,60 254,00 7,80 7,40 7,00 7,60 254,00 6,80 6,40 6,00 6,60 6,20 5,80 5,40 5,00 5,60 5,20 4,80 4,40 4,00 5,20 4,20 3,80 3,40 3,00 4,80 3,80 2,80 2,40 2,00 4,40 3,40 2,40 1,40 1,00 4,00 3,00 2,00 1,00 0,00 4,40 3,40 2,40 1,40 1,00

[14. ábra - Pontos hullám] 61 59 57 55 53 55 57 59 64 1275

56 54 52 50 48 50 52 57 62 67

54 49 47 45 43 45 50 55 60 65

52 47 42 40 38 1270 1270 1270 1270 1270

50 45 40 35 33 31 29 27 25 27

48 43 38 33 28 26 24 22 20 22

49 1270 1270 31 26 21 19 17 15 17

44 39 34 29 24 19 14 12 10 12

42 37 32 27 22 17 12 7 5 7

40 35 30 25 20 15 10 5 0 5

[15. ábra - Felszorzás] 61 59 57 55 53 55 57 59 64 1275

56 54 52 50 48 50 52 57 62 67

54 49 47 45 43 45 50 55 60 65

52 47 42 40 38 1270 1270 1270 1270 1270

50 45 40 35 33 31 29 27 25 27

48 43 38 33 28 26 24 22 20 22

49 1270 1270 31 26 21 19 17 15 17

44 39 34 29 24 19 14 12 10 12

42 37 32 27 22 17 12 7 5 7

40 35 30 25 20 15 10 5 0 5

[16. ábra - Pontos megoldás] A megoldás ([16. á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 esetben ez 16 volt, ami nyilvánvalóan pontatlanabb távolság érték.

76/15.


IAR

IRODALOMKUTATÁS

2.3.3 - Legbiztonságosabb út, Voronoi diagramm Nézzünk most meg egy másik hullám-továbbterjesztéses algoritmust. Ennek tehát a lényege a legbiztonságosabb út megkeresése. Itt a fentiek alapján már nem fogok 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 ([17. á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. 254 254 254 254 254 254 254 254 254 254 254 254 254 1 254 1 254 1 254 1 254 1 254 1 254 1 254 1 254 1 254 255

1 2 2 2 2 2 2 2 2 1

1 2 3 2 1 1 1 1 1 1

1 2 3 2 1 254 254 254 254 254

1 2 2 2 1 1 1 1 1 1

1 1 1 1 2 2 2 2 2 1

1 254 254 1 2 3 3 3 2 1

1 1 1 1 2 3 3 3 2 1

1 2 2 2 2 2 2 2 2 1

1 1 1 1 1 1 1 1 0 1

254 254 254 254 254 254 254 254 254 254

254 254 254 254 254 254 254 254 254 254 254 254

[17. ábra - A legbiztonságosabb út hulláma] A prioritási mátrixunk legyen itt is a már megismert ([9. ábra]). Mindezek után a lehet legbiztonságosabb utat a [18. ábra] mutatja. 254 254 254 254 254 254 254 254 254 254 254 254 254 1 254 1 254 1 254 1 254 1 254 1 254 1 254 1 254 1 254 255

1 2 2 2 2 2 2 2 2 1

1 2 3 2 1 1 1 1 1 1

1 2 3 2 1 254 254 254 254 254

1 2 2 2 1 1 1 1 1 1

1 1 1 1 2 2 2 2 2 1

1 254 254 1 2 3 3 3 2 1

1 1 1 1 2 3 3 3 2 1

1 2 2 2 2 2 2 2 2 1

1 1 1 1 1 1 1 1 0 1

254 254 254 254 254 254 254 254 254 254

254 254 254 254 254 254 254 254 254 254 254 254

[18. ábra - 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

76/16.


IAR

IRODALOMKUTATÁS

keressük a gráfban, akkor a lehet legbiztonságosabb és legrövidebb utat fogjuk megkapni. Ezt próbálja szimulálni a [19. ábra]. 254 254 254 254 254 254 254 254 254 254 254 254 254 255 1 1 1 1 1 1 1 1 254 1 2 2 2 1 254 1 1 1 254 1 2 3 2 1 254 254 254 254 254 1 2 2 1 1 254 1 1 1 254 1 1 1 1 254 254 1 2 2 254 1 254 254 254 254 254 1 2 2 254 1 1 254 1 1 1 1 2 2 254 1 1 254 1 2 2 2 2 2 254 1 1 254 1 2 2 2 2 2 254 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 0

254 254 254 254 254 254 254 254 254 254

254 254 254 254 254 254 254 254 254 254 254 254

[19. ábra - 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 [20. ábra] mutatja be.

[20. ábra - Á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. Nézzük prioritási sor nélkül ([21. ábra]). 254 254 254 254 254 254 254 254 254 254 254 254 254 255 1 1 1 1 1 1 1 1 254 1 2 2 2 1 254 1 1 1 254 1 2 3 2 1 254 254 254 254 254 1 2 2 1 1 254 1 1 1 254 1 1 1 1 254 254 1 2 2 254 1 254 254 254 254 254 1 2 2 254 1 1 254 1 1 1 1 2 2 254 1 1 254 1 2 2 2 2 2 254 1 1 254 1 2 2 2 2 2 254 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 0

254 254 254 254 254 254 254 254 254 254

254 254 254 254 254 254 254 254 254 254 254 254

[21. ábra - Prioritási sor nélküli megoldás] Az így kapott gráfból bármely bejárással a legbiztonságosabb utat kapjuk meg. A színekkel azért jelöltem az egyes lépéseket, hogy egyértelm legyen, hogy a 255-ös mez 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 [22. ábra] mutatja be. 76/17.


IAR

IRODALOMKUTATÁS

[22. ábra - 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: 1. Van olyan pont, amin még nem jártam. 2. 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). 2.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. 2.3.5 - Implementálás Kicsit rátérek arra, hogy ezen algoritmusok miképpen építhet k be m köd programokba2. 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 valahogyan modellezni. A célnak létezik egy i, és j koordinátája. Ezen koordináták körül „koncentrikus” négyzetekkel végighaladunk, és minden esetben a környékén lév kisebb koncentrikus négyzet elemeit vizsgálva a lehet A From Game To Map leírásában részleteiben is találkozhatunk majd az implementációval, de a dokumentáció jelenlegi állapotában ez a leírás nem elérhet . 2

76/18.


IAR

IRODALOMKUTATÁS

legkisebb értékhez adunk hozzá 5-öt (1*5), vagy a pontosabb eredmény érdekében az átlós értékekhez 7-et (1.4*5), a többihez 5-öt, és ezek után keressük meg a legkisebb új értéket, amit beírunk az aktuális helyre.

76/19.


IAR

IRODALOMKUTATÁS

2. 4 - GRÁFOK, MINIMÁLIS KÖLTSÉGTÉRÍTÉS ÚT [4]

FESZÍT FA, ÉS A LEGRÖVIDEBB

2.4.1 - Néhány definíció Hurok él: olyan él, melynek kezd és végpontja azonos csúcsból indul, illetve érkezik. Szomszéd pontok: A és B szomszéd pontok, ha a gráfban van él A és B között Fokszám: Megadja, hogy egy adott pontra hány él illeszkedik. Izolált pont: olyan pont, amelyre nem illeszkedik él, azaz fokszáma nulla. Többszörös élek: Ugyanazon kezd és végpontokat tartalmazzák. 2.4.2 - Gráfok Sokféle gráf létezik (a gráf egy absztrakt adatszerkezet), és mindegyiknek megvan a maga felhasználási területe. Csak felsorolás szinten nézzük ezeket végig: Egyszer összefügg gráf Egyszer nem összefügg gráf Irányított összefügg gráf Irányított nem összefügg gráf Súlyozott összefügg gráf Súlyozott nem összefügg gráf Irányított és súlyozott összefügg gráf Irányított és súlyozott nem összefügg gráf Speciális gráf (hurokmentes, minimum távolság limit, többszörös élek stb…) Természetesen a teljesség igényével azokat írtam fel, amelyekkel én már találkoztam. A térképprogramhoz nekünk egy súlyozott és irányított összefügg gráfra lesz szükségünk, ami nem hurokmentes, tartalmazhat többszörös éleket, és az összefügg sége néhány speciális esetben megbomolhat, de a hatékonyság miatt az ilyen helyzeteket kerülni kell. 2.4.3 - 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 [23. ábra] mutatja. X 1 2 3 4 5 6 7

1 H I H I H H H

2 I H I H H I H

3 H I H I I H H

4 I H I H H H H

5 H H I H H I I

6 H I H H I H I

7 H H H H I I H

[23. ábra - Kapcsolatmátrixos ábrázolás] 76/20.


IAR

IRODALOMKUTATÁ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. 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 [24. ábra] alapján lehet elképzelni.

[24. ábra - Szomszédsági lista] Ezt a tárolási elemet nevezik szomszédsági listának. A harmadik lehetséges módszert már nem rajzolom fel, de könnyen el lehet képzelni egy teljesen dinamikus struktúrát, melynél a statikus mutató vektort felváltja egy olyan dinamikus adatszerkezet, mely elemeinek két mutató mezeje van. 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 [25. ábra] prezentálja (a gráf ábrája nem méretarányos). X 1 2 3 4 5 6 7

1 0 20 0 10 0 0 0

2 0 0 25 0 0 0 0

3 0 0 0 0 35 0 0

4 10 0 5 0 0 0 0

5 6 7 0 0 0 0 40 0 35 0 0 0 0 0 0 15 0 0 0 30 17 30 0

[25. ábra - 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. Megjegyzés: természetesen nem véletlen a fenti példa. Ez az az adatszerkezet, amit egy térképprogramban leginkább fel lehet majd használni. Ott, ahol többszörös élek vannak, az élek hossza egyenl hosszúságú. Ez jelöli a kétirányú utcát, amit 76/21.


IAR

IRODALOMKUTATÁS

csupán két gráf-ponttal jelölünk meg (ha mondjuk 2x4 sáv van, akkor azt négy gráfponttal el nyösebb megjelölni). Minden egyes gráf pontban három értéket tárolunk: két koordinátát, valamint egy tengerszintt l mért magasságot. 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 a programot. 2.4.4 - 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 fa-grá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). Algoritmusa MinfeszFa(i) PriSorInit(Sor) Segéd.pont:=i Segéd.súly:=0 PriSorBa(Sor,Segéd) Érintett(i):=0 Ciklus PriSorBól(Sor,Segéd) i:=Segéd.pont ÉletBeilleszt(Fa,Érintett(i),i) Ciklus j:=1-t l N-ig Ha A(i,j)>0 akkor Ha Érintett(j)=NEMÉRINTETT akkor Segéd.pont:=j Segéd.súly:=A(i,j) PriSorba(Sor,Segéd) Érintett(j):=i különben VanRövidebb(Sor,j,A(i,j),Volt) Ha Volt akkor Érintett(j):=i elágazás vége elágazás vége elágazás vége Ciklus vége amíg nem(PriSorÜres(Sor)) Eljárás vége

76/22.

POSEIDON NAVIGATION PROJECT Megjegyzések: NEMÉRINTETT

Életbeilleszt (G,x,y) VanRövidebb (Sor,a,b,Volt)

IAR

IRODALOMKUTATÁS

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. a G gráfba az x,y pontok közé élet illeszt be 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.

2.4.5 - Legrövidebb út [4] A legrövidebb út fogalma 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? Ennél 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 a neves holland matematikus Dijkstra 1959-ben közölt algoritmusa, ezért itt is ezt ismertetem. 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 76/23.


IAR

IRODALOMKUTATÁS

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 ([26. ábra]).

76/24.


IAR

IRODALOMKUTATÁS

[26. ábra - A legrövidebb út algoritmus] 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 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. Az algoritmus pszeudokódja LegrövidebbÚt (A, kezd , vég, N) Init(állapot) aktuális:=kezd állapot[aktuális].hossz:=0 állapot[aktuális].címke:=VÉGLEGES ismétlés SzomszédokBejárása(A,N,aktuális,állapot) aktuális:=Minimum(állapot,N) állapot[aktuális].címke:=VÉGLEGES amíg aktuális=vég EredményKiírása(állapot,kezd ,vég) Eljárás vége

76/25.


IAR

IRODALOMKUTATÁS

SzomszédokBejárása(A,N,aktuális,állapot) Ciklus i:=1-t l N-ig Ha (A[aktuális,i]<>0) és (állapot[i].címke=IDEINGLENES) akkor Ha (állapot[aktuális].hossz+A[aktuális,i])<állapot[i].hossz akkor állapot[i].el :=aktuális állapot[i].hossz:= állapot[aktuális].hossz+A[aktuális,i] Elágazás vége Elágazás vége Ciklus vége Eljárás vége A fenti algoritmusban ’A’ jelöli a gráf kapcsolatmátrixát, ’N’ pedig a gráf pontjainak számát. 2.4.6 - 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 ismertettett 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. A részletek a program fejleszt i kézikönyvében olvashatók3. 2.4.7 - 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 (maguk a számértékek pontos méréssel, és esetlegesen nagyon pontos GPS koordináták segítségével lesznek kiszámolva). 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. Mondjuk az autópálya kap egyes értéket méterenként, a földút meg mondjuk 3,5-öt méterenként (az értékek paraméterek, valószín leg a tesztelés fogja véglegesíteni ket). Így amikor az ember 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…).

3

Jelen dokumentáció elkészültekor a teljes szimulációs program még nincsen kész.

76/26.


IAR

IRODALOMKUTATÁS

2.5 - A POSEIDON NAVIGATION PROJECT ÉS A GPS 2.5.1 - A globális helymeghatározó rendszer a GPS [7] 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! 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. 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. Mi a helyzet ma? Szerencsére nekünk már egyszer bb dolgunk van. Csupán 24 darab Block II-es 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 kil ni, 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 Islandon, Diego Garcia-án, Kwajalein-en és Colorado Springs-en. Ezen állomások költségvetése nem olcsó dolog mégis azoknak, akik használják a GPS-t, ezért sem kell fizetniük. 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.

76/27.


IAR

IRODALOMKUTATÁS

Van számos m hold felettem, van egy vev m, mib l fogja tudni a m hold, hogy hol vagyok? Ez a sok fejlett készülék nekünk "összesen" annyira elég, hogy a m hold és a vev távolságát meg tudjuk határozni. Ezzel persze a halandó ember nem tudna mit kezdeni, kapna egy húszezer akármennyi é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 kiszámolja 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 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. Ilyen egyszer ... :) 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ó!). A kommunikáció A NAVSTAR m holdak két viv frekvenciát használnak a kommunikációra, az L1-t és az L2-t. Az el bbi 1575,42 MHz-en szállít üzeneteket, és a szinkronizáláshoz szükséges ál-vé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 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

76/28.


IAR

IRODALOMKUTATÁS

kódra. A P kód körülbelül tízszer pontosabb, és sokkal ellenállóbb a zavarokkal szemben. Ha ez ilyen jó, akkor miért a pontatlanság, mik a 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. Nem célom itt most a matematikai okfejtés, de a lényeg, 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 csinál 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 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 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". 76/29.


IAR

IRODALOMKUTATÁS

A hibák adottak, szerencsére van megoldásuk is, mi jöhet még? Mondjuk az, hogy szándékosan zavarják a GPS jeleket, hogy ne adjanak pontos megoldást! Sajnos ez nem viccnek szánt mondat, 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 2000-ben 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. 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... 2.5.2 - A tesztelt GPS készülékek Programunk a GPS segítségével képes tudatni a felhasználóval az aktuális helyzetét. A GPS megismeréséhez két készüléket vizsgáltunk meg: egy µ-Blox és egy Garmin gyártmányú vev t. 2.5.3 - µ-Blox MS1E GPS vev modul [5] Rövid ismertet A készülék SiRFStar I/LX architektúrásra épül. Központi processzora egy Hitachi Risc CPU. Számítógéppel egy kétirányú soros interfészen keresztül lehet vele kommunikálni.

76/30.


IAR

IRODALOMKUTATÁS

[27. ábra - A SiRFStar architektúra elvi felépítése] A GPS modul méretei: 82,5*32mm. Lehet séget ad teljes GPS jelfeldolgozásra a küls antenna és a soros interfész között. A vev készülék egy kívülr l kapott +5V-os feszültségforrás segítségével m ködik. A készülék ezt bels feszültség-átalakító segítségével a m ködéséhez szükséges CMOS kompatibilis 3,3V-os szintre redukálja. Folyamatos üzemben teljesítményfelvétele: 0,75W. A készülék három m ködési módot támogat: Normál mód, TricklePower mód, Egyéni beállítási mód. A készülékhez egy kívülr l csatlakoztatható alacsony fogyasztású aktív antenna kapcsolódik. Az antennához szükséges feszültséget (4,75V) a készülékb l nyeri. A Hitachi processzor lehet séget ad egyéb felhasználó által szükségesnek ítélt funkcionalitás tulajdonságok hozzáadására. A készülék megbízhatósága A GPS megbízhatósága a GPS kialakításának egyik funkciója a szatellit elhelyezkedés és a kiválasztó lehet ség mellett. Feléledési id k Egy GPS különböz feléledési módokat ismer, amik az un. Time-To-First-Fix (TTFF) id nagyságában különböznek. A feléledési id k definíció szerint: Hideg indulás (Cold start), Meleg indulás (Warm start), Forró indulás (Hot start) és „Újra megszerzés” (Reacquisition). (Ebb l a jelenleg használható mód a Hideg feléledés, mivel a többihez küls elem feszültsége szükséges, hogy a kalibrációs és egyéb adatok megmaradjanak a modul memóriájában.)

76/31.


IAR

IRODALOMKUTATÁS

Technikai áttekintés

[28. ábra - Abszolút maximum értékek] FONTOS! A panel nincs túláram, feszültségtüskék és inverz áram ellen védve! ködési feltételek

[29. ábra - M ködési feltételek] Ezek a feltételek hatással lehetnek a készülék megbízhatóságára. Kimeneti tüskék leírása

[30. ábra - Kimeneti tüskék leírása I]

76/32.

[31. ábra - Kimeneti tüskék leírása II]


IAR

IRODALOMKUTATÁS

Soros Interfész Jel Az interfész ki- és bemenetei (TX_A, RX_A, TX_B, RX_B) m ködési feszültségszintje 3,3V CMOS kompatíbilis jelszint. Az RX_A és az RX_B bemenetek toleránsak az 5V-os szinttel, és a kimenetek is 5V kompatibilisak. Ha RS-232-es jelszint szükséges, biztosítani kell egy jelszint-átalakítót (pl: MAX232 IC). A soros A kimenten kerül küldésre a SiRF bináris poziciós adat, a B bemeneten a korrekciós adatokat lehet feltölteni. Az NMEA 0183 kódolású adat opcionális a SiRF helyett. A beállításokat SiRF kódolással lehet feltölteni, de a különleges beállításokhoz szükség van a készülék firmware-jének frissítésére. A nem használt soros portokat nyitva lehet hagyni.

[32. ábra - A soros port általános sebesség-beállítása] Speciális táp-tüskék Küls elemet kell kapcsolni a Vbat bemenetre, hogy engedélyezni lehessen az RTC m veletet, az SRAM frissítést, illetve a GPS meleg és forró indítását. Jel meghatározás

[33. ábra - A GPS panel csatlakozótüskéinek számozása]

76/33.


IAR

IRODALOMKUTATÁS

A feszültségszint-konvertáló áramkör Alapja egy MAX232 IC (vagy ezzel kompatibilis, pl. a [34. ábra]-n látható ICL232), amely tartalmaz két adat csatornát, és egy feszültség-átalakítót. A kapcsoláshoz kell még négy db 2,2 F-os kondenzátort is. A kapcsolási rajz egy adatcsatornával megvalósítva:

[34. ábra – RS232/GPS készülék jelszint átalakító] Az RS232-es csatlakozónak csak a 2-es és a 3-as tüskéjét kellett ehhez felhasználni. A GPS készülék vezetékének 2(Vcc), 3(Tx_A), 5(Rx_A), 8(GND) ereit használtam. A tápfeszültséget a számítógép tápegységér l vettem le, így nem kellett külön áramkört ehhez építeni, és megfelel en stabil és tüskementes feszültséget tudtam használni. A soros port Funkció

Leírás

száma 1

CD

Carriel Data

2

RxD

Recieve Data

3

TxD

Transmit Data

4

DTR

Data Term. Ready

5

GND

Signal Ground

6

DSR

Data Set Ready

7

RTS

Request To Send

8

CTS

Clear To Send

9

RI

Ring Indicator

[35. ábra - A soros port (RS232) t kiosztása] 76/34.

[36. ábra - A soros port]


IAR

IRODALOMKUTATÁS

A GPS készüléket és a PocketPC-t összeköt elektronika Mikor a PPC és a GPS készüléket megpróbáltuk összeilleszteni, akadályba ütköztünk. A két készüléket nem lehetett egyszer en összekötni, kellett hozzá egy soros-port fordító áramkör, aminek kapcsolási rajza a [37. ábra]-n látható. Az asztali számítógéphez történ csatlakoztatás esetén nem ütköztünk hasonló akadályba.

[37. ábra: A GPS-PPC-t összeköt elektronika] Az áramkör csak akkor m ködik, ha adatfolyamszer jelsorozat érkezik a GPS készülékb l. Mivel az NMEA mondatokat ilyen módon közli a GPS készülék, ezért ez pont megfelel a projekt céljaihoz. Nem utolsó sorban a megvalósítása sem költséges (~200Ft, tokozással együtt). A boltokban kapható eszközök bár szélesebb körben használhatóak, de áruk több ezer forint is lehet. Megjegyzés Az áramkör megépítésére azért volt szükség, mert a kapott csatlakozóval nem ködött megfelel en, mint kés bb kiderült, a benne lév SMD IC egyik lábáról letört a forrasztás, valamint egy másik lába is levált. A tesztszoftver A készülék gyártójának honlapjáról letöltött specifikáció alapján használtam a szintén onnan szerzett -Center nev programot. A fenti kapcsolás segítségével ködött a készülék 7 m holdat talált meg, ebb l 5-r l tudott navigációs adatokat leolvasni. A koordináták: 19,035° 47,553° Tengerszint feletti magasság: 168,4m

76/35.


IAR

IRODALOMKUTATÁS

2.5.4 - A Garmin eTrex Vista készülék [6] Ez egy teljesen felhasználóbarát, kézi készülék beépített térképpel, útvonalkövetéssel, helymeghatározással és egyéb hasznos funkciókkal. A számunkra szükséges adatokat speciális átalakító kábel segítségével tudjuk letölteni, szintén az RS-232-es porton keresztül. Ez a készülék is támogatja többek közt az NMEA 0183-as protokollt is, aminek segítségével le tudjuk a készülékb l kérdezni a szükséges GPS adatokat. A választott protokoll a GPS készülékkel való kommunikációhoz Az általam tesztelt GPS készülékekr l a megfelel adatokat többféle protokoll segítségével lehet lekérni. Mind a µ-Blox, mind a Garmin készülék támogatja az NMEA 0183-as kommunikációs szabványt, valamint mindkett támogat egyéb, a készülék speciális lehet ségeinek kihasználását segít szabványokat (pl. GARMIN, GARMIN DGPS; SiRF). Az á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. Talker sentences – Közl mondatok Általános formája: $ttsss,d1,d2,…, A mondat forrását és tartalomra vonatkozó azonosítót a ’$’ jel utáni öt karakter adja meg, ahol ’tt’ a ’talker’, a beszél azonosítója, míg az ’sss’ a ’sentence identifier’, a mondat-azonosító. Az adatok ez után vessz vel elválasztva követik egymást. Ha egy adat nem áll rendelkezésre, a helye üres lesz, azaz a megfelel helyen nem lesz a vessz k között semmilyen karakter. A mondat tartalmazhat nyolcvannál több karaktert is plusz $, , . A mondat végén, a soremelés el tt van egy ellen rz mez , ami egy ’*’ jelb l és egy kétjegy hexadecimális számból áll, ami a karakterek XOR (Exclusive OR) kapcsolatából áll el . Ez a mez a mondat egészére vonatkozik, kivéve a ’$’ és a ’*’ jeleket. Proprietary sentences – Gyártóspecifikus mondatok Általános formája: $Piii,d1,d2,…. A ’$P’ jelöli, hogy a mondat gyártóspecifikus. A ’iii’ jelöli a gyártó azonosítóját (pl. GRM – Garmin Corporation; SRF – -Blox SiRF protocol). Ezután következnek a gyártó által meghatározott adatok, majd a sorzáró jelek. Query sentences – Lekérdez mondatok Általános formája: $ttllQ,sss, A ’tt’ jelöli, hogy mi a ’talker’, közl eszköz. Az ’ll’ jelzi, mi a ’listener’ hallgató eszköz. A ’Q’ mondja meg, hogy a mondat lekérdez típusú, az ’sss’ pedig, hogy melyik közl mondatot várja hallgató eszköz. A GPS eszköz addig fogja ismételni egy másodpercenként a kért mondatot, amíg más utasítást nem kap.

76/36.


IAR

IRODALOMKUTATÁS

Az adatok lekérdezésének megvalósítása A megfelel NMEA mondatok: A mi feladatunk szempontjából a ’Talker sentences’, a közl mondatfajta lesz a legfontosabb, mivel ennek segítségével lehet lekérdezni a GPS koordinátákat. A hosszúsági és szélességi fokok lekérdezésére a $GPGGA kódú mondatot, illetve a $GPGLL-lel kezd t tudjuk felhasználni. A $GPGGA a ’Global positioning system fixed data’ jelölése, vagyis a GPS javított adatokat küldi a készülék ebben az üzenetben. Formáját a [] mutatja.

[38. ábra - $GPGGA mondat felépítése] – lsd. [39. ábra] táblázata – ez a megvalósítás nem támogatja a geoid korrekciókat, az értékek WGS84 elliptikus magasság

a

b

[39. ábra - $GPGGA mondat kiegészítés Pozíció-javítást jelz értékek (Position Fix Indicator) A $GPGLL ’Geographic Position - Latitude/Longitude’ adatokkal a GPS készülék a hosszúsági és szélességi fokot adja meg. Formáját a [[40. ábra] mutatja.

76/37.


IAR

IRODALOMKUTATÁS

[40. ábra - $GPGLL mondat felépítése Az utóbbi NMEA mondatot jobban tudjuk hasznosítani, mert ebben minden elégséges információ megtalálható. A checksum, azaz a hibaellen rz mondatokat ki lehet sz rni.

kód segítségével az esetleges hibás NMEA

[41. ábra – Az ellen rz kód számítása]

A soros portról történ olvasás Az általam kommunikálni.

tesztelt

GPS

készülékekkel soros porton keresztül

lehet

[42. ábra - Soros port szükséges beállításai] Az els tesztet a Windows Hyper Terminal-jával végeztem. Ennek segítségével meg tudtam vizsgálni az egymás után fogadott NMEA mondatokat. A soros port beállítását az NMEA szabványleírásból vettem. Második lépésként kerestem egy soros port komponenst a Delphi 7 fejleszt i környezethez. Több ilyen komponens kipróbálása után ’d3k's ComDrv32’ komponenst választottam, ugyanis ez t nt a legegyszer bben kezelhet nek, és egyéni felhasználók számára ingyenesen felhasználható, így nincsenek benne korlátozások. A komponens ZIP állományba tömörítve lehet letölteni. A kitömörítés után a komponenst a ’CPDReg.dcu’ és a ’ComDrv32.dpk’ állományok betöltésével tudtam a 76/38.


IAR

IRODALOMKUTATÁS

Delphi komponensei közé installálni. Ezután a komponens ikonja megtalálható lesz a System komponenspalettán. (A komponens honlapja megtalálható a http://www.mdlive.com/d3k/delphi4 Internetes honlapon). A komponens a beállított COM portról a megjelen adatot egy pufferbe írja. Ha ebben a pufferben van adat, a komponens OnRecieveData, illetve az OnRecievePacket eseménye aktivizálódik, és ezek segítségével lehet a soros portra érkezett adatokat lekezelni. Jelen esetben ez egy string-kezelést jelent. A metódusok paraméterei: Sender: a metódust hívó osztály azonosítója DataPtr/PacketPtr: az adatfolyam elejére mutató pointer DataSize: Cardinal típusú adat, a pufferben lév adatfolyam hossza

76/39.


IAR

IRODALOMKUTATÁS

2.6 - DESTINATOR 3 AVAGY MIT TUD A PIAC JELENLEG? 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, 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. 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, 3Ds és madártávlatos néz pontra is. Megadhatjuk, hogy a térképen nappali, avagy éjjeli színeket akarunke látni, valamint menüb l tudunk betölteni új ország térképet. [43. ábra - Destination 3 - Német verzió (4 kép)]

76/40.


IAR

RENDSZERTERV

3. FEJEZET - A HARDWARE ÉS A SOFTWARE 3.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. 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-nk ezek után természetesen 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 lehetessen 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!

[44. ábra - Pocket PC 2003 Emulator]

3.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 a másik fejleszt i környezet: Microsoft eMbedded Visual C++ 4.0. Ennek segítségével WM2003-ra lehet programokat írni C# vagy Visual Basic nyelven. Mi a C#-ot választottuk. 76/41.


IAR

RENDSZERTERV

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.

3.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 mio Digiwalker 339-es 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. [45. ábra - mitac Mio 339 DigiWalker]

76/42.


3.4 - AZ ELS

IAR

RENDSZERTERV

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. [46. ábra - Els program (5 kép)]

3.5 - GPS TESZTKÉSZÜLÉK Az eddig rendelkezésünkre álló készülékek listája az irodalomkutatásban olvasható. Ahhoz, hogy a Pocket PCn eredményesen tudjuk kihasználni a GPS-ben rejl lehet ségéket, szükségünk lesz egy hozzá csatolható GPS készülékre. Amíg ez nem áll rendelkezésünkre, a [47. ábra] látható GPS-el fogunk dolgozni (valamint az µBlox-al). [47. ábra - GPS]

76/43.


IAR

RENDSZERTERV

3.6 - 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 [48. á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.

[48. ábra - A .NET Fejlesztési Platform] Az á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 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. 76/44.


IAR

RENDSZERTERV

A .NET támogatja a fogalmi adatmodelleket, valamint az UML is. Így már a tervezés magas szintjén is segítségünkre lehet. A modellvezérelt architektúra a .NETre 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 Pascal és C# szintaktikával képes dolgozni, és fordítani .NET alá.

3.7 - Ú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 fogunk elkészíteni.

3.8 - A SOFTWARE ALAPVET

MODULJAINAK LEÍRÁSA (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. 3.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

76/45.


IAR

RENDSZERTERV

3.8.2 - Az egyes modulok kapcsolata

[49. ábra - 0. rendszerterv: PPC]

[50. ábra - 0. rendszerterv: System] 3.8.3 - Egyes modulok leírása 3.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ó. 3.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. 3.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. 3.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.

76/46.


IAR

RENDSZERTERV

3.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, és el nyeiket egyesítjük. 3.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ó.

3.9 - A RENDSZER ÖSSZEÁLL (1. RENDSZERTERV) A 0. rendszertervhez képest kicsit pontosítsuk, és ugyanakkor er sítsük meg, hogy mi is lesz a programunk alapja. Ezt mutatja be az [51. ábra].

[51. ábra - 1. rendszerterv szerinti program váza] 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 53. á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 1-1 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 76/47.


IAR

RENDSZERTERV

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! Mondok 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 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 é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 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 PC-re tudunk másolni.

3.10 - Az elkészült GPS 3.10.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 ([52. ábra]), valamint elkészült a technikailag kompatibilis GPS is.

76/48.


IAR

RENDSZERTERV

[52. ábra - Soros szinkronizáló kábel Mitac Mio PDA-hoz] 3.10.2 - Kommunikáció tesztelés Teszt I A GPS és a PPC összekötöttük, és egy saját alkalmazást futtattunk rajta, mely a soros portról olvassa a GPS koordinátákat. Az alkalmazás nem kapott bemen jeleket. Teszt II Szintén összekötöttük a GPS-t és a PPC-t, de a Destinator 3 programot használtuk. Teszt III 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. Teszt IV 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.

3.11 - MIKROSZKÓP ALATT A GRÁF FELÜLET A Graphs and Spanning trees nev segédalkalmazás alapjai már megvannak, bár már 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. Az [53. ábra] azon alapvet jellemz ket mutatja be, mely közös mind statikus, mind dinamikus esetben.

[53. ábra - 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) 76/49.


IAR

RENDSZERTERV

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 az [54. ábra].

[54. ábra - 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 eldöntött dolog, mivel egy még szintén bizonytalan adattag sorsa sincs eldöntve: 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 (55. ábra)). Még nem beszéltem 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 ([53. á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 ([54. ábra]) azonban már csak az el tömbök által tárolt rekordoknak megfelel értékeket tárolja.

76/50.


IAR

RENDSZERTERV

[55. ábra - A TGraph osztály 1. rendszertervbeli alakja II.]

76/51.


IAR

RENDSZERTERV

4. FEJEZET - GRAPHS AND SPANNING TREES 4.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áfhá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.

4.2 - FELHASZNÁLÓI KÉZIKÖNYV 4.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áthatunk (C melléklet (02)-es ábra, továbbiakban „Melléklet: C/02”). 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.

76/52.


IAR

RENDSZERTERV

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 térkép program szimulációjához is kelleni fog. Beállíthatjuk a tárolás típusát (Storage), hogy statikus, avagy dinamikus legyene, 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éklet:C/03). 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? 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 itt tároljuk majd az olyan kiegészít információkat, mint pl. 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íz elem 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 fog megvalósulni. 76/53.


IAR

RENDSZERTERV

Ezt a két listát még a kés bbiekben is tudjuk majd szerkeszteni. 4.2.2 - Gráf megnyitása A [File|Open graph] hatására egy standard file megnyitó ablakban a (*.grp) file-okat tudjuk 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. 4.2.3 - Globális beállítási lehet ségek A program számos beállítási lehet séggel rendelkezeik, 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éklet: C/05). 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 tudjuk beállítani (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éklet: C/06). 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: 76/54.


IAR

RENDSZERTERV

Maximális elemszáma a súlyvektornak és a pontokban tárolható adat tömbnek (Max item of weights and data). Legfeljebb ennyi gráf-pont lehet a gráfunkban (Max graph points). Legfeljebb ennyi él lehet a gráfunkban (Max graph edges). 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éynegesen magasabb, mint a gráf-pontok maximális száma (Max graphic points). Az irányított él esetén maga az él is tartalmaz további grafikai pontokat (a nyíl miatt)! Az el alapján a maximális grafikai élek száma is korlátozott (Max graphic edges). A program által használt egyedi szoftveres 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 arm of 3D objects). 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 (Max graphic points of each shapes). Ugyanitt le tudjuk olvasni a sémák listáját tároló szöveges file nevét (Shape List file name), valamint az alapértelmezett könyvtárát a sémáknak (Shape files directory) és a gráfoknak (Save directory). 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 nehezkes, célszer kipróbálni, hogy módosításukkal mi változik a képen. 4.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 automatiusan 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. 4.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 (Melléklet: C/07). 76/55.


IAR

RENDSZERTERV

A pont koordinátáinak (coordinates) (X,Y,Z) felvétele történehet manuálisan, de van lehet ség az (X,Y) sík vizuális megadására is a ’#’ gombra kattintva (Melléklet: C/08). 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 vetzió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áfpont 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 az szerkesztsi 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). 4.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])(Melléklet: C/09). 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éklet: C/10). 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. 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. 4.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]). Minegyik esetben egy listából ki kell választanunk, melyik elemmel szeretnénk dolgozni. Grafikus kijelölésre a jelenlegi verzióban 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éklet: C/11)! 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.

76/56.


IAR

RENDSZERTERV

4.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éklet: C/12). 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 álala. A csomópont adatvektorát, valamint a súlyvektort is tetszés szerint módosíthatjuk. 4.2.9 - Az aktuális súly illetve gráf pont adat beállítása Egyszerre nem jeleníthatü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átaszani fog. Ezt a [Format|Set current weight] menüpontban illetve a [Format|Set current data] menüpontban tehetjük meg (Melléklet: C/13). 4.2.10 - Gráf mentése A programban nincs automatikus mentés, és figyelmeztetni sem figyelmeztet mentésre. 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 állapot el fog veszni. A gráf átnevezésével (4.2.8 fejezet) ez a probléma elkerülhet . 4.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 (Melléklet: C/14). 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

76/57.


IAR

RENDSZERTERV

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. Az elkészült kapcsolatmátrix ellen rizhet a [Pathfinding|Show relation matrix] menüpontra kattintva (Melléklet: C/15). 4.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 (Melléklet: C/16) a kiindulási (Start point) és a cél pontot (Destination Point) lehet megadni az útkeres algoritmusnak (a ’Set’ gombra kell kattintani). 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 (Melléklet: C/17).

4.3 - FEJLESZT

I DOKUMENTÁCIÓ

4.3.1 - A programról A Graphs and spanning trees alkalmazás Borland Delphi 7 környezetben készült Pascal szintaktikával. 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 19 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 dolgozzák át. Az összes grafikai hatását bekapcsolva a gépet meglehet sen „visszafogja”. A TObject3D osztály már sokkal érdekesebb, egy egyedi szoftveres 3D objektumok tárolásáért, és kezelésért felel s. Részleteivel a 4.3.2-es fejezet foglalkozik. Végül a TGraph osztály maga a gráf, minden adatával és m veletével. Erre a 4.3.3 fejezetben térünk ki. 4.3.2 - 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éklet: D/01). METÓDUS InitObject3D DataInit

76/58.

TÍPUS Eljárás Eljárás

LEÍRÁS Inicializálja a példányt. Inicializálja a példány pontjait, és éleit.

POSEIDON NAVIGATION PROJECT AddArm AddEdge AddPoint AddPointColor AddPointWithLabel DataStart SetVector3D SetPoint4D SetCoords InitRotateUgamma InitRotXAlpha InitRotYAlpha InitRotZAlpha SetTrans

Eljárás Eljárás Eljárás Eljárás Eljárás Eljárás Függvény Függvény Függvény Eljárás Eljárás Eljárás Eljárás Függvény

SetNegativMatrix SetInvTrans SetTransponalt Multiplication3x1_3x3 Multiplication4x1_4x4Single Multiplication4x1_4x4 Multiplication4x1_4x4Coords DrawObject MoveManipulator GetVectorLength SetNormalVector

Függvény Függvény Függvény Függvény Függvény Függvény Függvény Eljárás Eljárás Függvény Függvény

IAR

RENDSZERTERV

Egy elemet ad hozzá a példányhoz. Egy élet ad hozzá egy adott elemhez. Egy pontot ad hozzá egy adott elemhez. Egy pont színét adja hozzá egy adott ponthoz. Egy pontot ad hozzá az elemhez felirattal együtt. Rögzíti az adatbevitelét egy elemnek. Egy TVector3D típusú változó értékeit állítja be. Egy TPoint4D típusú változó értékeit állítja be. A koordináta tengelyeket állítja be. Az U tengely körüli forgatás mátrixát állítja be. Az X tengely körüli forgatás mátrixát állítja be. Az Y tengely körüli forgatás mátrixát állítja be. Az Z tengely körüli forgatás mátrixát állítja be. Három tengely és egy eltolás alapján egy TTrans típusú változó értékeit állítja be. Negál egy mátrixot. Invertál egy mátrixot. Transzponál egy mátrixot. Mátrixokat szoroz (3x1_3x3). Mátrixokat szoroz (4x1_4x4). Mátrixokat szoroz (4x1_4x4). Mátrixokat szoroz (4x1_4x4). Kirajzolja a példányban tárolt elemeket. Forgatja a beállított értékek alapján a példány elemeit. Visszaadja egy TVector3D típusú változó hozzsát. Meghatározza egy TVector3D típusú változó normálvektorát.

4.3.3 - 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éklet: D/02). METÓDUS InitGraph AddItemRecArray AddPoint DeletePoint EditPoint AddEdge DeleteEdge EditEdge Draw PathfindingDijkstra DijkstraNeighbours DijkstraMinimum InitEdgeWay SearchEdge

TÍPUS Eljárás Eljárás Eljárás Eljárás Eljárás Eljárás Eljárás Eljárás Eljárás Eljárás Eljárás Függvény Eljárás Függvény

LEÍRÁS Inicializálja a gráfot. Egy elemet hozzáad egy TRecArray típusú vektorhoz. Egy gráf pontot hozzáad a gráfhoz. Egy élet hozzáad a gráfhoz. Szerkeszt egy gráf pontot. Szerkeszt egy élet a gráfban. Logikailag töröl egy élet a gráfból. Logikailag töröl egy gráf pontot. Kirajzolja a gráfot. Dijkstra legrövidebb út keres algoritmusa. Dijkstra algoritmusához szükséges. Dijkstra algoritmusához szükséges. Törli (inicializálja) a megtalált utat (nem lesz kijelölt út). Két pont közötti él sorszámát adja vissza, amennyiben létezik.

76/59.


IAR

RENDSZERTERV

4.3.3.4 – Algoritmusok A Draw() és a PathfindingDijkstra algoritmusa kulcsfontosságú az osztály szempontjából, így ezek forráskódját teljes terjedelmében közlöm. A Draw() terjedelméb l adódóan a Melléklet D függelékébe került. Dijkstra algoritmusának pszeudó kódja már szerepelt az irodalomkutatásban is. Most nézzük meg Delphi 7 forrását. PROCEDURE TGraph.PathfindingDijkstra ( Var

StartPoint DestinationPoint Var PFArray

: Word; : Word; : TPFArray );

i : Integer; act : Word; Begin For i:=1 To (PointsNum) Do Begin PFArray[i].Length:=High(Integer); PFArray[i].Prev:=0; PFArray[i].Status:=FALSE; End; act:=StartPoint; PFArray[act].Length:=0; PFArray[act].Status:=TRUE; REPEAT DijkstraNeighbours(PFArray,act); act:=DijkstraMinimum(PFArray); PFArray[act].Status:=TRUE; UNTIL (act=DestinationPoint); End; PROCEDURE TGraph.DijkstraNeighbours ( Var

Var PFArray act

: TPFArray; : Word );

i : Integer; Begin For i:=1 To (PointsNum) Do Begin If (RelationMatrix[act,i]<>0) And (Not(PFArray[i].Status)) Then Begin If (PFArray[act].Length+RelationMatrix[act,i])<(PFArray[i].Length) Then Begin PFArray[i].Prev:=act; PFArray[i].Length:=PFArray[act].Length+RelationMatrix[act,i]; End; End; End; End;

76/60.


IAR

RENDSZERTERV

FUNCTION TGraph.DijkstraMinimum ( PFArray : TPFArray ) : Word; Var min : Double; minH : Integer; i : Integer; find : Boolean; j : Integer; Begin find:=FALSE; i:=0; REPEAT Inc(i); If (Not(PFArray[i].Status)) Then Begin min:=PFArray[i].Length; minH:=i; find:=TRUE; End; UNTIL (find); If (find) Then Begin For j:=i To (PointsNum) Do Begin If (min>PFArray[j].Length) And (Not(PFArray[j].Status)) Then Begin min:=PFArray[j].Length; minH:=j; End; End; End; If (find) Then Begin Result:=minH; End Else Begin Result:=0; End; End; 4.3.4 – A TypeUnit további részei A TypeUnit további lényeges részei a (Melléklet: D/03)-ban olvashatóak. ALPROGRAM CopyGraph

TÍPUS Eljárás

LoadShapeList LoadShape InitPair SearchPair SaveGraphToFile OpenGraphFromFile

Eljárás Eljárás Eljárás Függvény Eljárás Eljárás

LEÍRÁS Egy gráf attribútumait egy másik gráf attribútumaiba másolja. Betölti a minták listáját az adott file-ból. Egy mintát tölt be a TObject3D osztály egy példányába. Inicializálja a segédtömböt. A TPair-hez kapcsolódóan párokat keres. Kimenti a statikus gráfot file-ba. Betölti a statikus gráfot file-ból.

76/61.


IAR

RENDSZERTERV

4.4 - TESZTELÉS A Budapesti M szaki F iskolának és környékének térképét modellezzük le a közeljöv ben, és ezen teszteljük a már elkészült, és a majd elkészül algoritmusokat.

4.5 - BEÁGYAZÁS A POSEIDON NAVIGATION PROJECT-BE A TGraph és esetlegesen a TObject3D osztály terveink szerint beépíthet lesz a Pocket PC-n futó alkalmazásunkba. „Legrosszabb” esetben ezen algoritmusokat C#ba át kell írni, de lehet ség van Borland Delphi 8 .NET-ben, avagy Borland Delphi 2005-ben .NET Frameworkre fordítani az osztályokat (kisebb módosítások mellett). Az így elkészült *.dll file-okat ezután Visual Studio .NET-ben minden probléma nélkül tudjuk használni. Az alkalmazás gyenge pontja jelenleg a statikus tárolás. EL fog készülni egy olyan C# osztálykönyvtár, mely képes megnyitni a Graphs and spanning trees gráfjait, és ezeket átalakítja saját dinamikus formátumára. Ezt a formátumot utána már a Pocket PC-n futó alkalmazásunk is kényelmesen fogja tudni kezelni, a Borland Delphis program pedig a térképek szerkesztésére kiválóan alkalmas.

76/62.


IAR

RENDSZERTERV

5. FEJEZET – A PPC ÉS A GPS ÖSSZEKAPCSOLÁSA 5.1. A HARDVERES KAPCSOLAT 5.1.1 Rövid ismertetés A -Blox panel illetve a Garmin kézi készülék egy speciális kábel vagy jelszint átalakító elektronika segítségével kapcsolható számítógéphez. Az átalakító elektronika kimenete és a kábel egyik vége RS232-es „female” csatlakozó. A PC-hez való csatlakoztatás igen egyszer , mivel az azon lév csatlakozóaljzat RS232-es „male” típusú. A csatlakoztatás után a következ kben leírt módon lehet szoftveresen illeszteni a két készüléket. A Pocket PC-hez történ csatlakoztatás során egy problémába ütköztünk, mivel a PPC és a GPS kábelének csatlakozója „female” típusú, így nem lehet a kett t összekötni. A megoldás egy fordító áramkör, aminek felépítését a … részben már tárgyaltunk. Kezdetben ez nem állt rendelkezésünkre, így a megoldás egyfajta emulálás lett, de azóta sikerölt a közvetlen GPS-PPC kapcsolatot létrehozni. A módszer lényege, hogy az asztali PC-n egy program fut, amely egy el re felvett GPS adatsort küld a soros kimenetére (comx).

5.2 SZOFTVERES ILLESZTÉS (Megjegyzés: a dotNETFramework könyvtárban található a .NET Framework telepít -állománya. Telepítése szükséges lehet az egyes példaprogramok futtatásához.) 5.2.1 PC és GPS eszköz közötti kommunikáció – az els lépések Miután sikerült a -Blox GPS panelhez egy jelszint-átalakító áramkört szerkeszteni a 2.5.3. fejezetben leírtak szerint, ki kellet próbálni, hogy az eszköz köd képes lett-e. Ezt els ként a Microsoft Windows-ba beépített Hyper Terminal segítségével volt legkönnyebb leellen rizni. A Hyper Terminal beállításait elvégezve a GPS dokumentációja alapján és csatlakoztatva a GPS készüléket a PC soros COM (RS232) portjainak egyikéhez, a Hyper Terminal ablakában megjelentek karaktersorozatok. Az els alkalommal a szabványos NMEA kódot nem sikerült felismerni az ASCII kódfolyamban. Ennek oka az volt, hogy a Hyper Terminal átviteli sebesség beállítása hibásan 9600bpm-re (bit per másodperc) lett állítva. A hiba korrigálása után a képerny n kezdetben hibás ASCII karaktersorok jelentek, meg, majd mikor megjelent az els ’$’-jel, már soronként olvashatóak voltak a szabványos NMEA mondatok. A próba sikeresen meg lett ismételve a Garmin készülékkel is. A Hyper Terminal helyes beállítása: Átviteli sebesség: 4800bpm Adatbitek: 8 bit Paritás: Nincs Stopbitek: 1 bit Átvitelvezérlés: Hardveres A többi beállítást az alapértelmezett értékeken lehet hagyni. 76/63.


IAR

RENDSZERTERV

5.2.2 PC és GPS eszköz közötti kommunikáció – programfejleszt i környezetekb l Borland Delphi 7 Az els fejleszt i környezet, amit a projekt kezdeti id szakában használni kezdtünk, a Borland cég Delphi 7 eszköze volt. A feladat megoldásának el segítéséhez sikerült egy COM port-ot kezel komponenst letölteni az internetr l próbafelhasználás céljából (http://www.mdlive.com/d3k/delphi4 - sajnos a legutóbbi próbálkozáskor már nem sikerült az oldalt elérni). A komponenscsomagot egy ZIP-file tartalmazta. Ezt kibontva egy tetsz leges könyvtárba, már lehetett telepíteni a komponenst. Ennek módja: 1. A Borland Delphi7 ’Component Install Componenent’ menüjét megnyitni; 2. A megjelen ablakban a ’Unit file name:’ helyre a ZIP-file-ban található ’CPDrv.pas’ állományt kell kijelölni a megfelel elérési úttal; 3. A ’Package file name:’ sorba a ’ ComDrv32.dpk’ állományt kell kijelölni a megfelel elérési úttal; 4. Ha az eljárás sikeres, a ’System’ komponenspalettán megjelenik egy ’Serial’ feliratú ikon, melyet a kívánt formra helyezve használhatunk. Ezek után be kell állítani a komponens tulajdonságait: 1. A ’BaudRate’ mez ben be kell állítani a ’br4800’-as értéket (a ’BaudRateValue’ mez automatikusan átíródik, így azzal nem kell foglalkoznunk); 2. A ’DataBits’ mez ben a ’ db8BITS’ felirat kell, hogy látszódjon (alapértelmezett); 3. A ’HwFlow’ paramétert ’ hfNONERTSON’ értékre kell állítani; 4. A ’Port’ tulajdonságnál ki kell választani, a PC melyik portjára kapcsoltuk a GPS eszközt (a ’PortName’ tulajdonság automatikusan átíródik); 5. A ’StopBits’ értéket ’sb1BITS’-re kell állítani (alapértelmezett); 6. A többi tulajdonság maradhat az alapértelmezett értékeken. A felhasznált eseménykezel függvény a soros port-ról érkez adat lekérésére: procedure TForm1.CommPortDriver1ReceiveData(Sender: TObject; DataPtr: Pointer; DataSize: Cardinal); Sender: az eseményt kiváltó osztály; DataPtr: az adatsor els elemének memóriacímére mutató pointer; DataSize: az adatsor hossza byte-ban.

76/64.


IAR

RENDSZERTERV

Visual Studio .NET 2003 A fejlesztés kés bbi szakaszában a Microsoft cég Visual Studio .NET 2003-as környezetét használtuk, mely segítségével a C# nyelven írt kódokat tudtuk fordítani mind Microsoft Windows 9x,NT,ME,200x,XP , mind Microsoft Windows CE (Pocket PC 2003) operációs rendszerek alá. (Az els próbálkozások Microsoft e… Visual C++ -ban voltak, de a felhasználás bonyolultsága miatt a C# nyelvet választottuk.) A szükséges komponenscsomagot a http://www.franson.biz/ honlapról sikerült beszerezni egy 15 napos próbalicensszel együtt, amely tartalmazza a PC-s és PPC-s környezet alatti fejlesztéshez szükséges DLL állományokat, valamint példaprogramokat. A DLL-ek beimportálása a következ képpen történik: 1. A SerialToolsNET.zip állományt kicsomagolása egy megfelel könyvtárba. 2. A Visual Studio .Net 2003 fejleszt i környezetben a már meglév projektbe be kell importálni a ’SerialNET.dll’ állományt. (’Project Add Reference’ ablakban). FONTOS, hogy PC-s program fejlesztése esetén a ’Desktop Framework’ könyvtárból, míg PPC-s fejlesztés esetén a ’Compact Framework’ könyvtárból töltsük be a DLL-t. Ezek után a SerialNET névteret használva elérhetjük a komponens minden tulajdonságát. A port inicializálása: --------------------------------------------------------------SerialNET.License license = new SerialNET.License(); license.LicenseKey = " [LicenseKey] "; //licensz-kulcs megadása ComPort1.ComPort = 0; //A megfelel soros port számának megadása ComPort1.BaudRate = 4800; // Az átviteli sebesség ComPort1.Handshake = none; ComPort1.Parity = SetialNET.Parity.No; //paritás ComPort1.StopBits = SerialNET.StopBits.One; //Stopbitek száma ComPort1.ByteSize = 8; //byte méret ComPort1.Timeout = 2000; //id túllépés ComPort1.Enabled = false; //a port m ködésének tiltása ComPort1.MultiThreading = true; /*Többszálú m ködés engedélyezése, hogy több *eseménykezel t lehessen egyszerre ugyanahhoz az *eseményhez rendelni */ ComPort1.OnRead += new SerialNET.OnRead(ComPort_OnRead); //Eseménykezel hozzárendelése az OnRead eseményhez ---------------------------------------------------------------

76/65.


IAR

RENDSZERTERV

A Compact Framework fejlesztésekhez az inicializálást hasonlóan kell elvégezni, csak a többszálú m ködést nem kell engedélyezni. 5.2.3 Az NMEA GPS kód kezelése

Az alapok A legels lépés az volt, miután a kommunikáció megvalósult a PC és a GPSpanel között, hogy a beérkez kódot lekezeljük. A megvalósításhoz tudni kell, hogy a GPS eszköz az NMEA mondatokat nem egyben, hanem 10-20 karakter hosszú string-ekben küldi. Emiatt a mondatok nem biztos, hogy a fogadott karaktersor elején fognak kezd dni, illetve a végén befejez dni. A problémát egy egyszer algoritmussal meg lehet oldani: --------------------------------------------------------------private string _Sentence; private void ComPort_OnRead(string Data) { for( int i=0;i0) { NMEA_decoding NMEA = new NMEA_decoding(); NMEA.setSentence(Line.Trim('\r','\n')); if(NMEA.isChecksumOK()) { ... /* Az NMEA mondat feldolgozása */ ... } else { _Sentence = "The sentence is not correct!"; } Line=""; } Line += data[i].ToString(); } } ---------------------------------------------------------------

Az NMEA mondatok feldolgozása – alapvet algoritmusok A ’Checksum’ ellen rz kód kinyerése a kódból: Ehhez tudni kell, hogy ez a kód az NMEA mondat végén, annak els részét l ez ’*’ karakterrel elválasztva található. Hossza két byte. Tehát a kód: --------------------------------------------------------------byte i = 7; //az els 6 karakter (byte) az NMEA azonosító do 76/66.


IAR

RENDSZERTERV

{ i++; //számlálás }while ( (Sentence[i]!='*') && (i<Sentence.Length)); /*számlálásnak vége, ha elértük a ’*’ karaktert, vagy az * NMEA mondat végét */ string t=""; // az ellen rz kódot tároló karakterlánc t = t+Sentence[i+1]+Sentence[i+2]; //hozzáf zzük a megfelel karaktereket a krakterlánchoz --------------------------------------------------------------Az ellen rz kód és az NMEA mondat összehasonlítása: Az ellen rz kódot a GPS készülék úgy állítja el , hogy az ellen rz kód és ’*’ karakter nélküli NMEA mondat sorban minden karaktert kizáró kapcsolatba hoz, és az így kapott két byte-os értéket karakterláncként hozzáf zi az NMEA mondathoz, és így küldi feldolgozásra. Tehát, ha szeretnénk az NMEA mondatot összehasonlítani az ellen rz kóddal, akkor el kell végezni a kizáró vagy kapcsolatot a mondat karaktereinek hexadecimális értékeivel és összehasonlítani az el leg kinyert ellen rz kóddal. A programkód: --------------------------------------------------------------byte i = 1; int Chks = 0; //az általunk létrehozott ellen rz kód nullázása while( Sentence[i]!='*' && i<Sentence.Length ) /*a ciklus leáll, ha elértük a ’*’ karaktert, vagy a karaktersorozat végét* / { Chks = Chks ^ Sentence[i]; //a kizáró vagy kapcsolat elvégzése i++; } if ( Chks==Checksum ) /*a segédváltozó és az NMEA mondat végér l megszerzett *hibaellen rz kód összehasonlítása */ { ChecksumOK=true; return true; } else { ChecksumOK=false; return false; } --------------------------------------------------------------Az NMEA mondat paraméterei: 76/67.


IAR

RENDSZERTERV

Ha sikerült megállapítani, hogy az NMEA mondatunk helyes, akkor már ki tudjuk nyerni bel le a szükséges paramétereket. Ehhez tudnunk kell, hogy az egyes paraméterek egymástól vessz vel vannak elválasztva. A programkód: --------------------------------------------------------------byte i=0, j=0; while (i<Sentence.Length-1 && j!=ParamNumber) //ParamNumber: a kívánt paraméter helye a mondatban { if (Sentence[i]==',') j++; i++; } string s = ""; if ( i==Sentence.Length-1 ) s="EOL"; // End of Line else { while(Sentence[i]!=',' && Sentence[i]!='*' && i<Sentence.Length-1) { s = s+Sentence[i]; i++; } } if (s!=",") return s; else return ""; --------------------------------------------------------------A C# nyelvben a karakterláncban lév ’Checksum’ értéket átkonvertálni egész értékké a következ képpen lehet (ez a probléma a legels k között merült fel a C# nyelv tanulása során, ugyanis Borland Delphi környezetben lehet használni hexadecimális értékeket): int iChecksum = Byte.Parse(sChecksum, System.Globalization.NumberStyles.HexNumber); 5.2.4. A GPS koordináták alapján pozícionálás térképen Miután sikeresen fogadtunk adatot a GPS eszköz fel l, és értelmeztük az NMEA mondatokat, a kapott adatok közül a hosszúsági (longitude) azaz X (vízszintes) tengely menti és szélességi (latitude), azaz Y (függ leges) tengely menti koordináták alapján egy bitmap képen meg kell jelölni a kapott pozíciót. Ehhez a feladathoz szükséges legalább három koordinátát ismernünk a kiválasztott térképen. Igazából négy koordináta kell a számításokhoz, de a negyediket az els és a harmadik koordináta alapján úgy, hogy vesszük az els hosszúsági és a bitképen lév X koordinátáját, illetve a harmadik szélességi és a bitképen lév Y koordinátáját. Mivel a GPS eszközr l ddmm.mmmm illetve dddmm.mmmm formátumban jelennek meg a szélességi illetve hosszúsági koordináták (d= fok, m=fokperc), át kell alakítani valós számformátummá, amit megtehetünk a következ módon: Latitude = dd+(mm.mmmm)*5/3 Longitude = ddd+(mm.mmmm)*5/3 76/68.


IAR

RENDSZERTERV

Ezek után már ki tudjuk számítani a keresett X-Y értékeket. A koordináták jelölése: Longx: az x-edik hosszúsági érték; Latx: az x-edik szélességi koordináta; Xx: az x-edik X-koordináta a bitképen; Yx: az x-edik Y-koordináta a bitképen; x = 1, 2, 3, 4 Az így kapott négyszer négy szám alapján meg kell határozni, hogy a bitképen egy pixelre mekkora távolság jut. Az X irányú felbontást jelöljük delX-szel, az Yirányút delY-nal. Így a számítás: delX=(Long2-Long1)/(X2-X1) delY=(Lat4-Lat3)/(Y3-Y4) A következ lépés, hogy meghatározzunk egy viszonyítási pontot. Ez tetsz leges lehet, most legyen a bal fels pont. A két koordináta legyen: Lat0 és Long0. A képletek: Lat0=Lat4+Y4*delY Long0=Long1-X1*delX Az így kapott értékeket a következ képletekbe behelyettesítve megkaphatjuk az egyes szélességi és hosszúsági érték párokhoz tartozó XY képkoordinátákat: Y=(Lat0-Lat)/delX X=(Long-Long0)/dely Megjegyzés: az implementálás során az negatív Y értékeket kaptunk, amit úgy sikerült megoldani, hogy a kép magasságának (Height) értékéhez hozzá lett adva a kapott Y érték. Így már helyes pozíciót rajzolt ki a program. A példaprogram ehhez a részhez PNPgrafikus.zip állományban találhatók. Ez program feltöltve egy PPC készülékbe, egy betöltött bitképen megjeleníti a tartózkodási helyünket, ha sikerült kapcsolódnia GPS készülékhez, vagy egy emulátorhoz. Be kell állítani a bitképhez rendelt viszonyítási pontokat, valamint a soros port tulajdonságait (ezek alapbeállítása úgy van megadva, hogy a PC-n lév emulátort használni lehessen). A bitképet érdemes feltölteni a PPC-n lév Dokuments mappába.

76/69.


IAR

RENDSZERTERV

6. EREDMÉNYEK ÖSSZEFOGLALÁSA

[56. ábra - A m köd program]

[57. ábra - Az összekapcsolt készülékek]

Sikeresen megvalósítottuk az elérni kívánt célokat, aminek egy Pocket PC-n köd program lett a végeredménye. 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 leg megrajzolt, vagy beolvasott térképet feltölteni). A feltöltés a Microsoft ActiveSync programmal egyszer en elvégezhet . 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 lehet a célpont majd a kés bbiekben). A végleges program teljes mértékben .NET Framework platformon m ködik. Ennek megvalósításában segítségünkre volt a Microsoft Visual Studio .NET 2003 és a Borland Delphi 8-as fejleszt i környezetek. Tervünkben nem szerepel a teljes ország, de még teljes Budapest térképe sem, ett l függetlenül a programot felkészítjük városon belüli, és városokon kívüli útvonalkezelésre is. Az elkészült Graphs and spanning trees programban elkészítettük a Budapesti szaki F iskola, és környékének térképét. A továbbiakban f leg ezen fogunk

76/70.

POSEIDON NAVIGATION PROJECT dolgozni (speciális készíteni).

esetekhez

IAR pedig

kitalált

RENDSZERTERV

térképeket/gráfhálókat

fogunk

76/71.


IAR

RENDSZERTERV

7. FEJEZET - IRODALOM JEGYZÉK 7.1 - IDÉZETEK, FORRÁSOK [1]

[2]

[3]

[4]

[5]

Internetes oldal URL: http://www.aiguru.com/pathfinding.htm Szerz : MICHAEL ZAROZINSKI (webmester) Dátum: 2004. május 15. oldal: http://www.aiguru.com Internetes oldal URL: http://theory.stanford.edu/~amitp/GameProgramming/ Szerz : AMIT J. PATEL Dátum: 2004. május 15. oldal: http://www-cs-students.stanford.edu/~amitp/gameprog.html El adás Címe: Intelligens Rendszerek II - Robotok El adó: MOLNÁR ANDRÁS Dátum: 2004. március Helyszín: Budapesti M szaki F iskola (Magyarország) El adás honlapja: http://mobil.nik.bmf.hu/tantargyak/ir2.html Hasonló témájú oldal: http://www.ccg.leeds.ac.uk/james/aStar/ El adás Címe: Számítástechnika III El adó: PROF. ÖVEGES FERENC Dátum: 2001 Helyszín: Lovassy László Gimnázium (Magyarország) Honlap: www.lovassy.hu/online/ µ-Blox MS1E GPS vev modul Forrás I. – PDF dokumentum Címe: The NMEA 0183 Standard Szerz : KLAUS BETKE Dátum: 2000. május, újraszerkesztve 2001. augusztus Letöltve: 2004. március 11. Forrás II. – PDF dokumentum Címe: Protocol Specification – µ-blox GPS-MS1 and GPS-PS1 Szerz : -Blox Corp Dátum: 2000. április 4. URL: http://www.u-blox.com/ Letöltve: 2004. március 04. Forrás III. – PDF dokumentum Címe: -Center Evaluation Software User's Guide Szerz : -Blox Corporation Dátum: 2001. március 15. URL: http://www.u-blox.com Letöltve: 2004. március 04. Forrás IV. – PDF dokumentum Címe: µ-Blox PS1E GPS Reciever Module Datasheet 76/72.


[6]

[7]

IAR

RENDSZERTERV

Szerz : PATRIK EGGENBERGER Dátum: 2002. január 9. URL: http://www.u-blox.com/ Letöltve: 2004. március 04. Garmin eTrex Vista készülék Címe: Garmin eTrexVista personal navigator - Owner’s manual and reference guide Szerz : Garmin Ltd. Dátum: 2002. szeptember URL: http://www.garmin.com Típus: PDF-dokumetum Letöltve: 2004. március El adás Címe: Intelligens Rendszerek II - GPS El adó: MOLNÁR ANDRÁS Dátum: 2004. május Helyszín: Budapesti M szaki F iskola (Magyarország) El adás honlapja: http://mobil.nik.bmf.hu/tantargyak/ir2.html

7.2 - KÉPEK, GRAFIKÁK [1. ábra – Csapda] ................................................................................................................8 [2. ábra – Grid] .....................................................................................................................9 [3. ábra – Dijkstra] ...............................................................................................................9 [4. ábra - Best first serach]...................................................................................................9 [5. ábra – Akadályok] ........................................................................................................ 10 [6. ábra - A* algoritmus] ................................................................................................... 10 [7. ábra – Térkép]............................................................................................................... 11 [8. ábra - Egyszer hullám] .............................................................................................. 12 [9. ábra - Prioritási sorrend]..............................................................................................12 [10. ábra - Els megoldás] ................................................................................................. 13 [11. ábra - Második megoldás] ......................................................................................... 13 [12. ábra - Négyirányú hullám] ........................................................................................ 14 [13. ábra - Jobb megoldás] ................................................................................................14 [14. ábra - Pontos hullám] ................................................................................................. 15 [15. ábra - Felszorzás]........................................................................................................ 15 [16. ábra - Pontos megoldás] ............................................................................................15 [17. ábra - A legbiztonságosabb út hulláma] ..................................................................16 [18. ábra - A legbiztonságosabb út] .................................................................................16 [19. ábra - Másik térkép] ................................................................................................... 17 [20. ábra - Ábra pontosítása] ............................................................................................17 [21. ábra - Prioritási sor nélküli megoldás] .....................................................................17 [22. ábra - A keletkezett gráf] ........................................................................................... 18 [23. ábra - Kapcsolatmátrixos ábrázolás].........................................................................20 [24. ábra - Szomszédsági lista] ......................................................................................... 21 [25. ábra - Súlyozott, irányított gráf]................................................................................ 21 [26. ábra - A legrövidebb út algoritmus] .........................................................................25 76/73.


IAR

RENDSZERTERV

[27. ábra - A SiRFStar architektúra elvi felépítése] ......................................................... 31 [28. ábra - Abszolút maximum értékek] .......................................................................... 32 [29. ábra - M ködési feltételek] ........................................................................................ 32 [30. ábra - Kimeneti tüskék leírása I] [31. ábra - Kimeneti tüskék leírása II] ............. 32 [32. ábra - A soros port általános sebesség-beállítása] ...................................................33 [33. ábra - A GPS panel csatlakozótüskéinek számozása] .............................................33 [34. ábra – RS232/GPS készülék jelszint átalakító] ........................................................ 34 [35. ábra - A soros port (RS232) t kiosztása] [36. ábra - A soros port] ...................... 34 [37. ábra: A GPS-PPC-t összeköt elektronika] ........................................................35 [38. ábra - $GPGGA mondat felépítése] .......................................................................... 37 [39. ábra - $GPGGA mondat kiegészítés .........................................................................37 [40. ábra - $GPGLL mondat felépítése............................................................................. 38 [41. ábra – Az ellen rz kód számítása] ...........................................................................38 [42. ábra - Soros port szükséges beállításai] ....................................................................38 [43. ábra - Destination 3 - Német verzió (4 kép)] ............................................................40 [44. ábra - Pocket PC 2003 Emulator] .............................................................................. 41 [45. ábra - mitac Mio 339 DigiWalker] ............................................................................. 42 [46. ábra - Els program (5 kép)]...................................................................................... 43 [47. ábra - GPS] .................................................................................................................. 43 [48. ábra - A .NET Fejlesztési Platform]........................................................................... 44 [49. ábra - 0. rendszerterv: PPC].......................................................................................46 [50. ábra - 0. rendszerterv: System] .................................................................................. 46 [51. ábra - 1. rendszerterv szerinti program váza].......................................................... 47 [52. ábra - Soros szinkronizáló kábel Mitac Mio PDA-hoz] ........................................... 49 [53. ábra - A TGraph osztály 1. rendszertervbeli alakja I.] ............................................ 49 [54. ábra - A pontok és az élek adatai az 1. rendszerterv alapján] ................................50 [55. ábra - A TGraph osztály 1. rendszertervbeli alakja II.] ........................................... 51 [56. ábra - A m köd program] [57. ábra - Az összekapcsolt készülékek] ...............70 [59. ábra - A m köd program] ...................................... Hiba! A könyvjelz nem létezik. [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13]

Csapda Forrás: HTTP://THEORY.STANFORD.EDU/~AMITP/GAMEPROGRAMMING/ Grid Forrás: HTTP://THEORY.STANFORD.EDU/~AMITP/GAMEPROGRAMMING/ Dijkstra Forrás: HTTP://THEORY.STANFORD.EDU/~AMITP/GAMEPROGRAMMING/ Best-first-search Forrás: HTTP://THEORY.STANFORD.EDU/~AMITP/GAMEPROGRAMMING/ Akadályok Forrás: HTTP://THEORY.STANFORD.EDU/~AMITP/GAMEPROGRAMMING/ A* algoritmus Forrás: HTTP://THEORY.STANFORD.EDU/~AMITP/GAMEPROGRAMMING/ Térkép Forrás: saját kép Készítette: BED K DÁVID Egyszer hullám Forrás: saját kép Készítette: BED K DÁVID Prioritási sorrend Forrás: saját kép Készítette: BED K DÁVID Els megoldás Forrás: saját kép Készítette: BED K DÁVID Második megoldás Forrás: saját kép Készítette: BED K DÁVID Négy irányú hullám Forrás: saját kép Készítette: BED K DÁVID Jobb megoldás Forrás: saját kép Készítette: BED K DÁVID

76/74.

POSEIDON NAVIGATION PROJECT [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27]

[28]

[29]

[30]

[31]

[32]

[33]

[34] [35]

IAR

RENDSZERTERV

Pontos hullám Forrás: saját kép Készítette: BED K DÁVID Felszorzás Forrás: saját kép Készítette: BED K DÁVID Pontos megoldás Forrás: saját kép Készítette: BED K DÁVID A „legbiztonságosabb út” hulláma Forrás: saját kép Készítette: BED K DÁVID A legbiztonságosabb út Forrás: saját kép Készítette: BED K DÁVID Másik térkép Forrás: saját kép Készítette: BED K DÁVID Ábra pontosítása Forrás: saját kép Készítette: BED K DÁVID Prioritási sor nélküli megoldás Forrás: saját kép Készítette: BED K DÁVID A keletkezett gráf Forrás: saját kép Készítette: BED K DÁVID Kapcsolatmátrixos ábrázolás Forrás: saját kép Készítette: BED K DÁVID Szomszédsági lista Forrás: saját kép Készítette: BED K DÁVID Súlyozott, irányított gráf Forrás: saját kép Készítette: BED K DÁVID Legrövidebb út algoritmus Forrás: El adás jegyzet Készítette: PROF. ÖVEGES FERENC 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], 2002. Január 9., PDF dokumentum, http://www.ublox.com/, (letöltve: 2004. 03. 04.), 5. oldal Abszolút maximum értékek Forrás: Patrik Eggenberger (µ-Blox Corp.): ’µ-Blox PS1E GPS Reciever Module Datasheet’, [GPS. G1-PS1-00002-B], 2002. Január 9., PDF dokumentum, http://www.ublox.com/, (letöltve: 2004. 03. 04.), 10. oldal M ködési feltételek Forrás: Patrik Eggenberger (µ-Blox Corp.): ’µ-Blox PS1E GPS Reciever Module Datasheet’, [GPS. G1-PS1-00002-B], 2002. Január 9., PDF dokumentum, http://www.ublox.com/, (letöltve: 2004. 03. 04.), 10. oldal Kimeneti tüskék leírása I Forrás: Patrik Eggenberger (µ-Blox Corp.): ’µ-Blox PS1E GPS Reciever Module Datasheet’, [GPS. G1-PS1-00002-B], 2002. Január 9., PDF dokumentum, http://www.ublox.com/, (letöltve: 2004. 03. 04.), 11. oldal Kimeneti tüskék leírása II Forrás: Patrik Eggenberger (µ-Blox Corp.): ’µ-Blox PS1E GPS Reciever Module Datasheet’, [GPS. G1-PS1-00002-B], 2002. Január 9., PDF dokumentum, http://www.ublox.com/, (letöltve: 2004. 03. 04.), 11. oldal A soros port általános sebesség-beállítása Forrás: Patrik Eggenberger (µ-Blox Corp.): ’µ-Blox PS1E GPS Reciever Module Datasheet’, [GPS. G1-PS1-00002-B], 2002. Január 9., PDF dokumentum, http://www.ublox.com/, (letöltve: 2004. 03. 04.), 11. oldal A GPS készülék csatlakozótüskéinek számozása Forrás: Patrik Eggenberger (µ-Blox Corp.): ’µ-Blox PS1E GPS Reciever Module Datasheet’, [GPS. G1-PS1-00002-B], 2002. Január 9., PDF dokumentum, http://www.ublox.com/, (letöltve: 2004. 03. 04.), 12. oldal RS232/GPS készülék jelszint átalakító Forrás: Internet Készítette: Szirbik Ferenc A soros port (RS232) t kiosztása 76/75.


[36] [57] [38]

[39]

[40]

[41]

[42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57]

IAR

RENDSZERTERV

Készítette: Szirbik Ferenc A soros port Készítette: Szirbik Ferenc A GPS-PPC-t összeköt elektronika Forrás: Steven D. Wormley: http://www.wormley.com/axim/ $GPGGA mondat felépítése Forrás: 2. µ-Blox Corp., ’Protocol Specification – µ-blox GPS-MS1 and GPS-PS1’, 2000. április4., PDF dokumentum, http://www.u-blox.com/, (letöltve: 2004. 03. 04.), 40. oldal $GPGGA mondat kiegészítés Forrás: 2. µ-Blox Corp., ’Protocol Specification – µ-blox GPS-MS1 and GPS-PS1’, 2000. április4., PDF dokumentum, http://www.u-blox.com/, (letöltve: 2004. 03. 04.), 41. oldal $GPGLL mondat felépítése Forrás: 2. µ-Blox Corp., ’Protocol Specification – µ-blox GPS-MS1 and GPS-PS1’, 2000. április4., PDF dokumentum, http://www.u-blox.com/, (letöltve: 2004. 03. 04.), 41. oldal Az ellen rz kód számítása Forrás: 2. µ-Blox Corp., ’Protocol Specification – µ-blox GPS-MS1 and GPS-PS1’, 2000. április4., PDF dokumentum, http://www.u-blox.com/, (letöltve: 2004. 03. 04.), 39. oldal Soros port szükséges beállításai Készítette: Szirbik Ferenc Pocket PC 2003 Emulátor Forrás: Az emulátorról készített képerny kép m ködés közben. MitacMio 339 DigiWalker Forrás: www.mitac.com Els program Forrás: Emulátorról készült képerny képek, valamint digitális fényképez géppel készült felvételek. GPS Forrás: 0. rendszerterv: PPC Forrás: saját kép Készítette: Bed k Dávid és Szirbik Ferenc 0. rendszerterv: System Forrás: saját kép Készítette: Bed k Dávid és Szirbik Ferenc Destinator 3 – Német verzió Forrás: Internet A .NET Fejlesztési Platform Forrás: MS Visual Studio .net Induló Készlet (Starter Kit) DVD Készítette: Nacsa Sándor és Dr. Cheref Hassan 1. rendszerterv szerinti program váza Készítette: Bed k Dávid Soros szinkronizáló kábel Mitac Mio PDA-hoz Forrás: www.mitacpda.hu A TGraph osztály 1. rendszertervbeli alakja I. Készítette: Bed k Dávid A pontok és az élek adatai az 1. rendszerterv alapján Készítette: Bed k Dávid A TGraph osztály 1. rendszertervbeli alakja II. Készítette: Bed k Dávid Az összekapcsolt készülékek Készítette: Szirbik Ferenc A m köd program Készítette: Szirbik Ferenc

76/76.

POSEIDON NAVIGATION PROJECT

Recommend Documents