POSEIDON NAVIGATION PROJECT intelligent Map with Rules of Traffic

Rendszerterv Munkacím: PPC Live Map GPS, Útkeresés & Pocket PC

POSEIDON NAVIGATION PROJECT iNtelligent Map with Rules of Traffic

Készítette: BEDŐK DÁVID & SZIRBIK FERENC 2004. május 6. BMF-NIK IAR Budapesti Műszaki Főiskola – Neumann János Informatikai Főiskolai Kar

Intelligens Automatizált Rendszerek

POSEIDON NAVIGATION PROJECT

IAR

TARTALOMJEGYZÉK

TARTALOMJEGYZÉK TARTALOMJEGYZÉK ................................................................................................................... 2 CÉL MEGHATÁROZÁSA ............................................................................................................... 4 ANGOL-MAGYAR SZAKSZÓTÁR ................................................................................................. 6 AZ IRODALOMKUTATÁS ÉS ÉRTÉKELÉSE .................................................................................. 7 AZ ÚTKERESÉSRŐL ÁLTALÁBAN ............................................................................................. 7 English ............................................................................................................................. 7 Magyar............................................................................................................................. 7 ÚTKERESÉS A JÁTÉKOK VILÁGÁBAN [2] .................................................................................. 8 Az első szimulációs program: From Game To Map........................................ 8 Csapdák .......................................................................................................................... 9 Algoritmusok alapja ................................................................................................... 9 Dijkstra algoritmusa és a Best-First-Search (legjobbat először) ............. 9 Az A* algoritmus ....................................................................................................... 11 A HULLÁMTOVÁBBTERJESZTÉSES ALGORITMUS [3] ............................................................. 12 Legrövidebb út ........................................................................................................... 12 Hullámtovábbterjesztéses algoritmus finomítása......................................... 14 Legbiztonságosabb út.............................................................................................. 16 Megjegyzések ............................................................................................................. 19 Implementálás............................................................................................................ 19 GRÁFOK, MINIMÁLIS KÖLTSÉGTÉRÍTÉSŰ FESZÍTŐFA, ÉS A LEGRÖVIDEBB ÚT [4] ................... 20 Néhány definíció ........................................................................................................ 20 Gráfok ............................................................................................................................ 20 Gráfok ábrázolása ..................................................................................................... 20 Minimális költségtérítésű feszítőfa ..................................................................... 22 Algoritmusa ............................................................................................................... 22 Legrövidebb út ........................................................................................................... 23 A legrövidebb út fogalma ........................................................................................ 23 Az algoritmus lényege ............................................................................................. 23 Az algoritmus részletesebben ................................................................................. 25 Az algoritmus pszeudokódja .................................................................................. 25 A második szimulációs program: Graphs and spanning trees ................ 26 Megjegyzések ............................................................................................................. 26 A POSEIDON NAVIGATION PROJECT ÉS A GPS ...................................................................... 27 Bevezetés ..................................................................................................................... 27 µ-Blox MS1E GPS vevőmodul [5]........................................................................ 27 Rövid ismertető ......................................................................................................... 27 A készülék hitelessége.............................................................................................. 28 Feléledési idők ........................................................................................................... 28 Technikai áttekintés .................................................................................................. 29 Működési feltételek................................................................................................... 29 Kimeneti tüskék leírása ............................................................................................ 29 Soros Interfész Jel ...................................................................................................... 30 Speciális táp-tüskék .................................................................................................. 30 Jel meghatározás ....................................................................................................... 30 Fizikai specifikáció.................................................................................................... 31 48/2.


IAR

TARTALOMJEGYZÉK

A feszültségszint-konvertáló áramkör................................................................... 31 A soros port................................................................................................................ 32 A tesztszoftver........................................................................................................... 32 Megjegyzés................................................................................................................. 33 A Garmin eTrex Vista készülék [6] .................................................................... 33 A választott protokoll a GPS készülékkel való kommunikációhoz................... 33 Talker sentences – Közlő mondatok....................................................................... 33 Proprietary sentences – Gyártóspecifikus mondatok .......................................... 34 Query sentences – Lekérdező mondatok............................................................... 34 Az adatok lekérdezésének megvalósítása ............................................................. 34 A soros portról történő olvasás............................................................................... 35 A HARDWARE ÉS A SOFTWARE .............................................................................................. 37 A KEZDET.............................................................................................................................. 37 A FEJLESZTŐI KÖRNYEZET .................................................................................................... 37 POCKET PC TESZTKÉSZÜLÉK ................................................................................................ 38 AZ ELSŐ FUTÓ PROGRAM ...................................................................................................... 39 GPS TESZTKÉSZÜLÉK............................................................................................................ 39 A SOFTWARE ALAPVETŐ MODULJAINAK LEÍRÁSA ................................................................... 40 NULLADIK RENDSZERTERV MODULLJAI ................................................................................ 40 AZ EGYES MODULOK KAPCSOLATA ....................................................................................... 40 EGYES MODULOK LEÍRÁSA .................................................................................................... 40 Adatbeviteli modul .................................................................................................... 40 Kapott adat értelmezése ........................................................................................ 41 Felhasználói felület modul ..................................................................................... 41 Térképkezelő modul ................................................................................................. 41 Adatbázis ...................................................................................................................... 41 Software frissítések kezelése ............................................................................... 41 DESTINATOR 3 AVAGY MIT TUD A PIAC JELENLEG? ............................................................. 42 TESZTELÉS ............................................................................................................................... 43 SZEREPKIOSZTÁS .................................................................................................................... 44 BEDŐK DÁVID ...................................................................................................................... 44 SZIRBIK FERENC ................................................................................................................... 44 IRODALOM JEGYZÉK ................................................................................................................ 45 IDÉZETEK, FORRÁSOK ........................................................................................................... 45 KÉPEK, GRAFIKÁK................................................................................................................. 46 TOVÁBBI INFORMÁCIÓK A TÉMÁHOZ: ................................................................................... 48

48/3.


IAR

CÉL MEGHATÁROZÁSA

CÉL MEGHATÁROZÁSA Egy térképprogram esetében mit is jelent az a probléma, hogy útkeresés. Ismerünk egy adott pontot, 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. 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őző koordináta, és az előző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. A másik pont a cél. 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 utakat 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 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 ezen 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). Í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. Ha ez megvalósul, 48/4.


IAR

CÉL MEGHATÁROZÁSA

akkor a térképünk akár milliméter pontosan képes legrövidebb út meghatározására a grafikus felületen (a járda egyik szegélyéről folyamatosan megy át a másik szegélyre, ha ott már úgyis be kell kanyarodni, és ehhez hasonló dolgokra gondolok itt most, ami bár nem „életszerű”, ám az ember ezzel pontos információhoz jut. Természetesen az már részletkérdés, hogy mondjuk a fenti lehetőséget bekapcsolja-e az ember, vagy letiltja az ennyire precíz számításokat), és a lehető legjobban kihasználja a GPS-ben rejlő lehetőségeket.

48/5.


IAR

SZAKSZÓTÁR

ANGOL-MAGYAR SZAKSZÓTÁR Magyar szó/kifejezés útkeresés kiinduló pont cél elkerülendő (objektumok) elkerülendő ellenségek költségek minimalizálása objektum elkezd mozogni csapda csúcs feszítőfa

48/6.

Angol szó/kifejezés pathfinding starting point goal avoiding obstacles avoiding enemies minimizing costs object begins to move trap vertex spanning tree


IAR

IRODALOMKUTATÁS

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.

AZ ÚTKERESÉSRŐL ÁLTALÁBAN Az alábbi idézet a http://www.aiguru.com/pathfinding.htm oldalról származik. Talán 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, amiben nem gondolták végig, hogy ennek milyen nagy jelentősége van.

48/7.


IAR

IRODALOMKUTATÁS

Ú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 eljutatni, teljes mértékben a térképprogram grafikus felületébe illik, hiszen ott is ugyanez a feladat. Az első 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 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.

48/8.


IAR

IRODALOMKUTATÁS

Csapdák

[Ábra 1 – CSAPDA]

Az ábrá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. Algoritmusok alapja Számos útkereső algoritmus a [2]-es ábrá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 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) [Ábra 2 - GRID]

Dijkstra algoritmusa és a Best-First-Search (legjobbat először) „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.

48/9.


IAR

IRODALOMKUTATÁS

[Ábra 3 - DIJKSTRA]

A [3]. képen 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]-es ábrán a sárga pont jelöli, hogy magas heurisztikus értéke van, azaz messze van a céltól, és fekete jelöli az alacsonyat.

[Ábra 4 – BEST-FIRST-SEARCH]

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

[Ábra 5 - 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 tűnhet, egy kis probléma esetén a futási idő már sokkal kevésbé szembetűnőbb, ám a megoldás „jósága” nem is hasonlítható Dijkstra útkereső algoritmusához. Nézzünk most egy olyan algoritmust, mely a fenti két algoritmus előnyeit egyesíti. 48/10.


IAR

IRODALOMKUTATÁS

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

[Ábra 6 – A* ALGORITMUS]

Egy kis magyarázat a [6]-os ábrához: a sárga (h) szín jelöli a céltól való távolságot, a cián (g) pedig a kezdő ponttól mé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.

48/11.


IAR

IRODALOMKUTATÁS

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őző fejezetben említett grid itt is létezik, és itt is hasonló elven tudjuk eldönteni az akadályok helyzetét. Ráadásul az előző fejezetben tárgyalt Dijkstra algoritmusa is ránézésre egyféle hullámterjedést mutatott be, és az is rögtön ki fog derülni, hogy az övé gyorsabban szolgáltat eredményt, mivel ott nem szükséges az egész területet előre ismerni, így szükségtelen bejárni is. 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. Legrövidebb út Nézzük, hogy is működnek ezek az algoritmusok. A [7]-es ábrán fogunk vizsgálódni. 254 254

255

254 254 254 254 254

0 [Ábra 7 - 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).

48/12.


IAR

Először a hullámtová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]-as á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

[Ábra 8 – 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 2 pont között, nincs esély, hiszen biztos, hogy lesz legalább egy, egyel alacsonyabb pont minden mező szomszédságában. Miért is van szükség járulékos szabályokra? Előfordulhat, ráadásul elég sűrűn, hogy egy adott pontból több irányba is tudunk menni! Ahhoz, hogy egyértelmű utat tudjunk meghatározni, ilyenkor meg kell tanítani az algoritmust arra, hogy melyik utat válassza. Ezért egy prioritási sorrendet érdemes felállítani a nyolc lehetséges irány között. Erre egy lehetséges példa a [9]-es ábra. 4 3 2

5 1

6 7 8

[Ábra 9 – 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]-es táblázatnak a függvényében fog változni maga az út is, ezért nem garantálható, 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]-es ábrán a fenti prioritási sor, és a térképünk által meghatározott utat látjuk.

48/13.


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

IAR

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

IRODALOMKUTATÁS

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

[Ábra 10 – 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). [Ábra 11 – 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 10 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 9x történt ez meg. Úgy kezdtem 8 7 6 a hullámtovábbterjesztéses algoritmus 1 5 leírását, hogy „nem garantálja a 2 3 4 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 verziója 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

Hullámtová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 4 irányban terjed ([12]-es ábra).

48/14.


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

[Ábra 12 – NÉGY IRÁNYÚ HULLÁM]

Bár az rögtön szembetűnik, hogy több súlyra volt szükségünk, mint az előző esetben, de ez nem befolyásolja az algoritmus futási idejét, és a megoldás ([13]-as ábra) valamivel életszerűbb lesz (itt is a már sokszor használt nyolc irá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

[Ábra 13 – 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őző algoritmusokhoz), így egy közelítő értékkel célszerű számolni, mondjuk 7/5-el (1.4 az ~1.4142 helyett)([14]-es ábra), melyet aztán felszorozva 5-el ([15]-ös ábra) minden egyes mezőre egész számot kapunk, és a megoldás időigényében nem lesz különbség!

48/15.


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 [Ábra 14 – 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

[Ábra 15 - FELSZORZÁS]

A számolás ebben az esetben lényegesen több időt vett igénybe számomra is (az elszámolások lehetségesek). 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

[Ábra 16 – PONTOS MEGOLDÁS]

A megoldás ([16]-os ábra) megegyezik az előbb kapott eredménnyel, azonban sokkal általánosabb esetben ez még pontosabb megoldást szolgáltat. Ha összeadjuk az út során érintett súlyokat, és elosztjuk 5-el az eredményt, akkor kisebb számot kapunk, mint a négy irányú hullám esetében. Ez a kapott szám a súlyokra nézve pontosabb, bár az út fizikailag nem lesz rövidebb (ebben a példában). Az első pont amire „rálépünk” 12,40-es súlyú (62/5), míg az előző esetben ez 16 volt, ami nyilvánvalóan pontatlanabb távolság érték. Legbiztonságosabb út Nézzük most meg egy másik hullámtovábbterjesztéses algoritmust. Ennek tehát a lényege a legbiztonságosabb út megkeresése. Itt a fentiek alapján már nem fogok 48/16.


IAR

IRODALOMKUTATÁS

kételkedni abban, hogy ez e a lehető legbiztonságosabb út. A módszer itt is nagyon hasonló, csak itt 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]-es á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 [Ábra 17 – A „LEGBIZTONSÁGOSABB ÚT” HULLÁMA]

A prioritási mátrixunk legyen itt is a már megismert ([9]-es ábra). Mindezek után a lehető legbiztonságosabb utat a [18]-as á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 [Ábra 18 – A LEGBIZTONSÁGOSABB ÚT]

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

48/17.


IAR

IRODALOMKUTATÁS

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

[Ábra 20 – Á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]-es á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 [Ábra 21 – 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őből gráf él csak a kettes mezőhöz vezet, így onnan nem is mehetünk egyik egyesre sem a gráf bejárása során. A keletkezett gráfot a [22]-es ábra mutatja be.

48/18.


IAR

IRODALOMKUTATÁS

[Ábra 22 – 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 variáció 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). 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. Implementálás Kicsit rátérek arra, hogy ezen algoritmusok hogyan lesznek beépítve működő programokba. Felmerül a kérdés, hogy minden esetben szükségünk van-e arra, hogy a teljes térképet előre „kiszámoljuk”. Én úgy vélem nincs. Dijkstra algoritmusa alapján addig terjesztjük a hullámunkat, amíg a hullám egyik pontja el nem éri a kiindulási pontunkat (255). Ezek után az út keresése már egyértelmű. A hullám terjedését kell még 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ő legkisebb értékhez adunk hozzá 1-et, vagy a pontosabb eredmény érdekében az átlós értékekhez 1, 4-et, a többihez 1-et, és ezek után keressük meg a legkisebb új értéket, amit beírunk az aktuális helyre, majd felszorozzuk 5-el a kapott értékeket. 48/19.


IAR

IRODALOMKUTATÁS

GRÁFOK, MINIMÁLIS KÖLTSÉGTÉRÍTÉSŰ FESZÍTŐFA, ÉS A LEGRÖVIDEBB ÚT [4] 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. 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, tartalmaz 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. 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]-as á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

[Ábra 23 – KAPCSOLATMÁTRIXOS ÁBRÁZOLÁS]

48/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]-es ábra alapján lehet elképzelni.

[Ábra 24 – 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 2 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]-ös á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

[Ábra 25 – 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 csupán két gráf-ponttal jelölünk meg (ha mondjuk 2x4 sáv van, akkor azt négy gráf48/21.


IAR

IRODALOMKUTATÁS

ponttal 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. 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 Megjegyzések: NEMÉRINTETT az az érték, amely jelzi, hogy egy adott pontot a bejárás során már érintettünk, vagy sem. Kezdetben Érintett() vektor minden eleme ezt tartalmazza. 48/22.


IAR

IRODALOMKUTATÁS

Életbeilleszt (G,x,y) a G gráfba az x,y pontok közé élet illeszt be VanRövidebb (Sor,a,b,Volt) megvizsgálja, hogy szerepel-e az „a” pont a prioritási sorban, ha igen, akkor megvizsgálja, hogy a „b” súlynál nagyobb-e az ott szereplő pont súlya. Ha igen, akkor kicseréli ezt a pontot az „a” pontra, amelynek „b” a súlya. Ha a sor így módosul, akkor Volt=igaz lesz. Legrövidebb út A következő sorok Öveges Ferenc jegyzetéből vannak idézve. 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 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: 48/23.


48/24.

IAR

IRODALOMKUTATÁS


IAR

IRODALOMKUTATÁS

[Ábra 26 – 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őző pont helyére pedig az aktuális pontot. 4. A gráf összes ideiglenes címkéjét megvizsgálva kiválasztjuk azt a pontot, amely az ideiglenesek közül a legrövidebb úton érhető el a kezdőpontból, vagyis azt, amelyiknek a címkéjében a hosszúság értéke a legkisebb. E pont címkéjét véglegesre állítjuk, ezzel jelezve, hogy e ponthoz nem vezethet a már bejegyzettnél rövidebb út. 5. Legyen most az így kiválasztott pont az aktuális. 6. Ismételjük a 3. résztől a műveletet egészen addig, amíg az aktuális pont azonos nem lesz a végponttal. 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 48/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őző:=aktuális állapot[i].hossz:=aktuális[k].hossz+A[aktuális,i] Elágazás vége Elágazás vége Ciklus vége Eljárás vége A második szimulációs program: Graphs and spanning trees Nem véletlenül gyűjtöttem össze a fenti algoritmusokat. Tervezem egy szépen kivitelezett gráf kezelő program készítését, mely ábrázolja, bejárja, generálja, követi a gráfokat, és a gráfokon végezhető műveleteket, algoritmusokat. Ezen program megírt algoritmusait a későbbiekben hatékonyan lehet beültetni a térképprogramba. 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 2 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 1-es é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…).

48/26.


IAR

IRODALOMKUTATÁS

A POSEIDON NAVIGATION PROJECT ÉS A GPS Bevezetés Programunk a GPS segítségével képes tudatni a felhasználóval az aktuális helyzetét. Ehhez szükséges egy olyan készülék, amiről le lehet kérdezni a szükséges adatokat. Vámossy Zoltán tanár úrtól kaptuk kipróbálásra két készüléktípust, egy µBlox és egy Garmin gyártmányú vevőt.

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

[Ábra 27 - 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

48/27.


IAR

IRODALOMKUTATÁS

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 hitelessége A GPS hitelessége a GPS kialakításának egyik funkciója a szatellit elhelyezkedés és a kiválasztó lehetőség mellett.

[Ábra 28 - A GPS panel műszaki paraméterei I]

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

48/28.


IAR

IRODALOMKUTATÁS

Technikai áttekintés

[Ábra 29 – Abszolút maximum értékek]

FONTOS! A panel nincs túláram, feszültségtüskék és inverz áram ellen védve! Működési feltételek

[Ábra 30 – 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

[Ábra 31 – Kimeneti tüskék leírása I]

[Ábra 32 – Kimeneti tüskék leírása II]

48/29.


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.

[Ábra 33 - A soros port általános 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

[Ábra 34 –

48/30.

A GPS készülék csatlakozótüskéinek számozása]


IAR

IRODALOMKUTATÁS

Fizikai specifikáció

[Ábra 35 –

A GPS panel műszaki paraméterei II

[Ábra 36 – A GPS panel műszaki paraméterei III]

A feszültségszint-konvertáló áramkör Alapja egy MAX232 IC (vagy ezzel kompatibilis, pl. a 37. ábrá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:

48/31.


IAR

IRODALOMKUTATÁS

[Ábra 37 – ??????????????????? ]

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 Tű száma

Funkció

Leírás

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

[Ábra 38 – A soros port (RS232) tűkiosztása]

[Ábra 39 – A soros port]

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 mű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.

48/32.


IAR

IRODALOMKUTATÁS

A koordináták: • 19,035° •

47,553°

Tengerszint feletti magasság: 168,4m Megjegyzés Az áramkör megépítésére azért volt szükség, mert a kapott csatlakozóval nem mű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 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.

48/33.


IAR

IRODALOMKUTATÁS

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. 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ődő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ája:

[Ábra 40 - ?????????????????????]

– lsd. köv. táblázat b – ez a megvalósítás nem támogatja a geoid korrekciókat, az értékek WGS84 elliptikus magasság a

[Ábra 41 - ????????????????????]

48/34.


IAR

IRODALOMKUTATÁ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ája:

[Ábra 42 - ???????????????]

Az utóbbi NMEA mondatot jobban tudjuk hasznosítani, mert ebben minden elégséges információ megtalálható.

[Ábra 43 - ????????????????]

A checksum, azaz a hibaellenőrző kód segítségvel az esetleges hibás NMEA mondatokat ki lehet szűrni. A soros portról történő olvasás Az általam tesztelt GPS kommunikálni.

készülékekkel

soros

porton

keresztül

lehet

[Ábra 44 - ????????????????]

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 48/35.


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

48/36.


IAR

0. SZINTŰ RENDSZERTERV

A HARDWARE ÉS A SOFTWARE 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álták. 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!

[Ábra 45 – Pocket PC 2003 Emulator]

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. 48/37.


IAR


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.

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. [Ábra 46 – mitac Mio 339 DigiWalker]

48/38.


IAR


AZ ELSŐ FUTÓ PROGRAM Nagyon nehéz elkezdeni valamit tervezni, amennyiben nincs kézzelfogható „bizonyíték” arra, hogy reális időn belül meg is tudjuk azt valósítani. Ezért elkészítettem 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. [Ábra 47 – Első program][5 kép]

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 48-as képen látható GPS-el fogunk dolgozni (valamint az µBlox-al). [Ábra 48 - GPS]

48/39.


IAR


A SOFTWARE ALAPVETŐ MODULJAINAK LEÍRÁSA A Delphi-s 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 Delphi-s 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.

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

AZ EGYES MODULOK KAPCSOLATA

[Ábra 49 – 0. rendszerterv: PPC]

[Ábra 50 – 0. rendszerterv: System]

EGYES MODULOK LEÍRÁSA 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ó.

48/40.


IAR


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. 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. 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. Adatbázis Megpróbálunk 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. 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ó.

48/41.


IAR


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 program autós használatra van tervezve, 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. [Ábra 51 – Destination 3 - Német verzió](4 kép)

48/42.


IAR


TESZTELÉS 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. A legvalószínűbb az, hogy a Budapesti Műszaki Főiskolát, és környékét valósítjuk meg. A tesztelést megpróbáljuk mi magunk elvégezni, és az eredményeket összehasonlítani a piac többi résztvevőjével.

48/43.


IAR


SZEREPKIOSZTÁS BEDŐK DÁVID A nyár folyamán elkészítem a From Game to Map, és a Graphs and spanning trees programot. Ebből következik, hogy az alkalmazás útkeresése az én fő területem.

SZIRBIK FERENC A nyáron a GPS lehetőségeit fogom kutatni, és ehhez készítek szimulációs programot.

Tervünk között szerepel a C# és a MS eMbedded Visual C++ 4.0 fejlesztői környezetben való jártasság megszerzése is.

48/44.


IAR

IRODALOM JEGYZÉK

IRODALOM JEGYZÉK 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. Főoldal: http://www.aiguru.com Internetes oldal URL: http://theory.stanford.edu/~amitp/GameProgramming/ Szerző: AMIT J. PATEL Dátum: 2004. május 15. Fő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. – Internetes oldal 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. – Internetes oldal 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. – Internetes oldal 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. – Internetes oldal Címe: µ-Blox PS1E GPS Reciever Module Datasheet 48/45.


[6]

IAR

IRODALOM JEGYZÉK

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: Szerző: Dátum:

KÉPEK, GRAFIKÁK [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26]

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

48/46.


IAR

IRODALOM JEGYZÉK

[27] A SiRFStar architektúra elvi felépítése Forrás: Készítette: [28] A GPS panel műszaki paraméterei Forrás: Készítette: [29] Abszolút maximum értékek Forrás: Készítette: [30] Működési feltételek Forrás: Készítette: [31] Kimeneti tüskék leírása I Forrás: Készítette: [32] Kimeneti tüskék leírása II Forrás: Készítette: [33] A soros port általános beállítása Forrás: Készítette: [34] A GPS készülék csatlakozótüskéinek számozása Forrás: Készítette: [35] A GPS panel műszaki paraméterei II Forrás: Készítette: [36] A GPS panel műszaki paraméterei III Forrás: Készítette: [37] ????????????????? Forrás: Készítette: [38] A soros port (RS232) tűkiosztása Forrás: Készítette: [39] A soros port Forrás: Készítette: [40] ????????????????? Forrás: Készítette: [41] ????????????????? Forrás: Készítette: [42] ???????????????? 48/47.


[43]

[44]

[45] [46] [47]

[48] [49]

[50]

[51]

IAR

IRODALOM JEGYZÉK

Forrás: Készítette: ??????????????? Forrás: Készítette: ????????????????? Forrás: Készítette: 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 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

digitális

TOVÁBBI INFORMÁCIÓK A TÉMÁHOZ: http://www.policyalmanac.org/games/binaryHeaps.htm English: Describes using a binary heap to make A* more efficient. Magyar: Leírás a bináris verem eljárásról. http://www.policyalmanac.org/games/twoTiered.htm English: Describes using A* efficiently by using nodes of different densities. http://www.policyalmanac.org/games/aStarTutorial.htm English: Nice description of A* http://www.generation5.org/content/2000/astar.asp English: Another A* descripion - includes C++ source. http://www.geocities.com/SiliconValley/Lakes/4929/astar.html English: Another description of A* (you can never get too many points of view!) including source code. http://www.red3d.com/cwr/steer/gdc99/ English: Craig Reynolds' 1999 Game Developer's Conference presentation. Well worth reading.

48/48.

POSEIDON NAVIGATION PROJECT intelligent Map with Rules of Traffic

Recommend Documents