játékfejlesztés.hu
FórumGarázsprojectekCikkekSegédletekJf.hu versenyekKapcsolatokEgyebek
Legaktívabb fórumozók:
Asylum:    5471
FZoli:    4892
Kuz:    4455
gaborlabor:    4449
kicsy:    4304
TPG:    3402
monostoria:    3284
DMG:    3172
HomeGnome:    2919
Matzi:    2525

Pretender:    2498
szeki:    2440
Seeting:    2306
Geri:    2194
Orphy:    1893
Joga:    1791
Bacce:    1783
MaNiAc:    1735
ddbwo:    1654
syam:    1491
Útkereső algoritmus kezdőknek 2006.04.15 14:44


Egy útkereső algoritmus írása nehézkes lehet egy kezdő számára, főleg talán azért, mert hiába van róla rengeteg cikk az interneten, legtöbbjük angol nyelvű, még több közülük pedig feltételez némi alapismeretet. Nos ez a cikk igazán a kezdőknek szól.

Bár ezzel az írással csupán körvonalakban magyarázom el az útkeresés, illetve az A* algoritmus lényegét, a cikk végén találsz néhány hasznos linket a témával kapcsolatban, amin tovább indulhatsz, sőt komplett forrásokat (C++ és BlitzBASIC nyelveken) illetve példaprogramokat is mellékeltem (érdemes ezeket elindítani és próbálgatni, sokat segíthetnek az útkeresés megértésében).

Akkor talán kezdjük is el...

Bevezetés: Végy egy Területet
Tegyük fel, hogy van egy pályánk, amin van egy A és B pontunk. Mi el szeretnénk jutni A-ból B-be. Tegyük fel továbbá, hogy a két pont között van egy fal, amin ugye keresztül nem mehetünk, ergo meg kell kerülnünk.

A képen a zöld négyzet jelöli az A, a piros a B pontokat. A kékkel satírozott négyzetek adják a falat.



Ami elsőként látszik a képen, hogy a területünk szabályos négyzetekre van felosztva. A keresendő terület leegyszerűsítése az útkeresés első lépése. Azzal, hogy négyzetrácsosan felosztjuk a pályánkat, egy egyszerű kétdimenziós tömbbel le tudjuk írni azt. A tömb minden eleme egy négyzet a rácsunkon és megjelölhetjük a tömbben, hogy az adott négyzet járható-e számunkra, vagy sem. Az útvonalat úgy kapjuk meg, hogy megnézzük melyik négyzetekre kell rálépnünk ahhoz, hogy A-ból B-be jussunk. Ha pedig meg van az útvonalunk, nem marad más hátra, minthogy a négyzetek középpontjától középpontjáig haladva végigsétáljunk azon. Persze használhatnánk más alakzatokat is négyzetek helyett (pl. hatszög, téglalap, vagy szabálytalan alakzatokat is), de tekintve, hogy ez a legegyszerűbb módszer, ebben az írásban ezeket fogom használni.

Kezdjük el a keresést
A következő lépésként kereséséseket fogunk indítani, hogy megtaláljuk a lehető legrövidebb útvonalat. Ezt az A pontból fogjuk kezdeni, megvizsgálva a szomszédos négyzeteket, majd innen lépésenként haladva a célterület felé, míg el nem érjük azt.

A keresés megkezdéséhez a következőket kell tennünk:

1. Az A pontunkat felvesszük egy listára. Nevezzük várólistának, amin tulajdonképpen azok a négyzetek fognak szerepelni, amiken talán végig kell haladnunk, de lehet hogy mégsem, tehát idővel lehet, hogy meg kell őket vizsgálnunk.

2. Keressünk meg minden szomszédos, járható négyzetet a kiindulóponthoz képest, és vegyük fel őket is a várólistánkra. Jegyezzük fel a négyzetek szülőnégyzetét, jelen esetben az A pontot. Ez a művelet, (a szülőnégyzet ismerete) nagyon fontos, enélkül nem fogjuk tudni merre van az arra, de később még úgyis elmagyarázom ezt..:)

3. A kiindulópontunkat a várólistánkból beletehetjük egy másik listába, amiben a már megvizsgáltak kapnak helyet, amiket többször már nem szükséges leellenőriznünk.

A fentieket a következő ábra illusztrlája. A képen a zöld négyzet a kiindulópontunk, jelenleg világoskék körvonallal, ami azt jelöli, hogy a négyzetünk a megvizsgáltak listájában van. A szomszédos négyzetek pedig a várólistán, ezért is vannak világoszölddel körberajzolva. A négyzetekben lévő szürke nyíl pedig a szülőnégyzetüket mutatja, jelenleg mindegyik nyilacska az A pont felé néz.



Ezután a várólistából kiválasztunk egy négyzetet, és azzal is elvégezzük a fenti lépéseket. De melyik négyzetet válasszuk? Minden négyzethez tartozik egy érték (továbbiakban: F), amelyiknek a legkisebb az F értéke, az lesz a jó választás.

Az F kiszámításának módja:

F = G + H

ahol
G = a lépések "költsége" a négyzetrácson a kiindulóponttól a jelenleg vizsgált pontig.
H = Heuristics (meg sem kísérlem egyetlen ide illő szóban lefordítani a jelentését...:)), tulajdonképpen a becsült távolság a jelenleg vizsgált ponttól a célnégyzetig.

Az útvonalat létrehozása pedig úgy történik, hogy ciklkikusan kiválasztunk a legkisebb F értékű elemet a várólistából, majd megvizsgáljuk. Ezt a műveletet még a továbbiakban részletesen elmagyarázom.
Elsőként azonban vegyük át részletesebben , hogyan is számoljuk ki az F-et.

Tehát G az eddig megtett lépések költsége. Tehát a költség annál nagyobb, minél messzebb vagyunk most a kiindulóponttól. Hogy egy lépésnek mekkora költséget szabunk, az tetszés szerinti, én a vízszintes és függőleges mozgásokért négyzetenként 10-et, az átlósakért 14-et számolok fel. (csak zárójelben: Azért ennyi, mert az egy átlós lépés megtett távolsága a 2 négyzetgyöke egy vízszintes vagy függőleges mozgáshoz képest (már ha az ilyenkor megtett távolságot 1-nek vesszük). Tehát egy átlós lépés 1.414-szer hosszabb táv egy vízszinteshez vagy függőlegeshez képest. Viszont az útvonalkeresés elég melós a gépnek így is, ne nehezítsük meg a dolgát hogy lebegőpontos számokkal dolgoztatjuk, ezért hát a 10 és a 14, mert ők barátságos, egész számok.) Így hát minden megtett újabb lépésnél a szülőnégyzet G-jéhez hozzáadunk 10-et vagy 14-et.

A H sokféleképpen megadható, az itt épp használt a eljárás a Manhattan módszer, amikor is azt számoljuk, hogy mennyi vízszintes és függőleges lépés a jelenlegi ponttól eljutni a célterületre. Ezután ezt az értéket megszorozzuk 10-el (mivel a G-nél is tízzel szoroztunk). Átlós lépést ekkor nem számolunk és nem vesszük figyelembe azt sem, hogy van e fal vagy egyéb, amúgy járhatatlan négyzet. A módszer neve onnan ered, hogy négyzetenként mozgunk, mintha csak háztömbök vonalán mozognánk és nem vághatunk át egyik háztömbön sem. A H-ról bővebben itt olvashatsz (angolul).
Tehát hogy megkapjuk az F-et, összeadjuk a G-t és a H-t. A keresés első eredménye a következő képen látható.Az F, G és H értékek minden négyzetbe bele vannak írva.



Elemezzük kicsit a fenti képet. A négyzetnél, ahol a betük is be vannak jelölve, G=10. Ez ugye azért van, mert ez a négyzet egy vízszintes lépésre van a kezdőponttól. Ugyanennek a négyzetnek a H-ja 30, mivel 3 lépésnyire van a célnégyzettől. Az ez alatt lévő négyzetnek már 40, mert egyet még felfelé is kell lépnünk hogy elérjük a célt.

A keresés folytatása
Hogy tovább haladjunk a kereséssel, válasszuk ki a legkisebb F-el rendelkező, várólistás négyzetünket. Ezután tegyük át a vizsgáltak listájára, majd:
5. Vegyük szemügyre a környező négyzeteket. azokat a négyzeteket, amik még nincsenek megvizsgálva és járhatóak is, tegyük várólistára. Az újonan listára tett négyzetek szülőjévé a jelenlegi négyzetet tegyük.
6. Ha az egyik szomszédos négyzet már korábbról várólistán volt, nézzük meg, nem-e lenne jobb a jelenlegi négyzetünkről odamennünk, mint a régi útvonalát meghagyni. Ha nem jobb, ne csináljunk semmit. Ha jobb, akkor a az adott négyzet szülőjének adjuk meg azt, ahol most állunk és számoljuk újra a négyzet G és F értékeit.

Rendben, lássuk hogy működik ez a gyakorlatban. 9 várólistás elemünk van. Ebből a kezdőpont rögtön át is kerül a vizsgáltak listájára. Marad 8 négyzet. Mind járható, tehát közülük válasszuk ki a legkisebb F értékűt. Ez lesz a következő négyzetünk. A következő képen világos kékkel van körberajzolva.



Tegyük át a vizsgáltak listájába őt is. Most vizsgáljuk meg a szomszédjait. A három jobboldali négyzet fal, tehát őket nem vizsgáljuk, valamint szomszédunk még a kezdőpont, de mivel ő már vizsgált elem, őt is figyelmen kívül hagyjuk. A megmaradt 4 négyzet viszont már korábbról várólistára került. Nézzük meg, azokhoz a négyzetekhez melyik út a rövidebb: A jelenlegi útvonaluk, vagy az az útvonal ami a jelenlegi négyzetünkön keresztül vezet. Nézzük meg például a jelenlegink alatt lévő négyzetet. A G értéke 14. Ha a négyzetünktől most odalépnénk, akkor a képzelt G 20 lenne (a jelenegi négyzetünk G-je 10 és a másik négyzethez is el kell jutnunk, innen a +10). A 20 nagyobb a 14-nél, tehát az új útvonal hosszabb lenne, így nem kell változtatnunk. Ez az ábrán is jól látszik: hogy a jelenlegi alatt lévő pontba eljussunk, az csupán egy átlós lépés a kezdőponttól, de a jelenlegi négyzetünkön keresztül már 2 lépés lenne. Miután leellenőriztük mind a 4 nágyzetet, arra jutunk, hogy egyik útvonalán sem kell változtatnunk. Vegyük hát a várólistánkat, mostanra már 7 elemet tartalmaz. Ismét kiválasszuk közülük a legkisebb F értékűt. Viszont, most két elemünk is legkisebb lesz. Melyiket válasszuk? Igazából teljesen mindegy, de hogy a gépnek is egyszerűbb legyen, érdemes mindig az utoljára várólistára tettet kiválasztani. Tehát válasszuk ki egyikőjüket, ami most - mint a mellékelt ábrán is jól látszik - a kezdőponttól jobbra-lent lévő négyzet lesz.

Most, miközben az új négyzetünk szomszédait vizsgáljuk, láthatjuk, hogy a jobboldali szomszéd fal, tehát nem kerülhet várólistára, viszont nem kerül listára a közvetlen alatta lévő négyzet sem (annak ellenére, hogy az játható lenne). Hogy miért? Ahhoz a négyzethez közvetlenül csak átlósan juthatunk el, de átlósan nem mehetünk, mert beleütköznénk a jobboldali fal sarkába. Tehát ahhoz a négyzethet jelenleg egy lépésben nem juthatunk el, tehát nem is kerül (még) várólistára.
A másik két alsó négyzet viszont még nem volt várólistás, hát odakerülnek, szülőnégyzetük pedig a jelenlegi négyzetünk lesz. A baloldalit megvizsgáljuk még, ahogy ezt a már korábban várólistára került négyzetekkel tenni kell, majd, mivel nem kell rajta változtatni, mehetünk tovább(legkisebb F értékű elem várólistáról kiválasztása, szomszédai vizsgálata és így tovább és így tovább...)



Ezt az keresést egészen addig kell folytatnunk, míg a vizsgáltak listájára nem kerül a célnégyzet. Hogy ekkor hogy áll a keresés, azt a következő ábra mutatja.



A kezdőpont körülötti négyzetek, mint látható, időközben felkerültek a vizsgáltak listájára (kékkel vannak körberajzolva), mivel volt olyan állapota a keresésnek, mikor az F értékük ezeknek volt a legkisebb.

Ezenkívül láthatjuk, hogy a kezdőponttól kettővel lentebbi négyzet szülője is megváltozott. Ez azért történt, mert korábban 28 volt a G-je, de a keresés közben 20 G érték is kijött neki, ezért szülőt váltott. Így újra számolódott a G és F értéke is, ezúttal a jobbra. Bár ez a kis változtatás nem tűnik lényegesnek, sokszor ennek is fontos szerepe van abban, hogy a legrövidebb útvonalhoz jussunk.

De hogyan kapjuk meg végre azt a legrövidebb útvonalat? Egyszerűen csak haladjunk a B ponttól visszafelé, mindig a négyzetek szülei felé haladva (az ábrán a nyilakat követve). Így közvetlenül visszajutunk a kezdőpontunkra, tehát ez lesz az áhított útvonalunk. A-ból B-be tehát csak a már megállapított út négyzeteinek kzéppontjáról középpontjára haladva juthatunk el.



Összefoglalva tehát az A* algoritmusos útkeresés menete:
1. Kezdőpont hozzáadása a várólistára
2. a következő ismétlése:
a. a legkisebb F értékű, várólistán lévő négyzet megkeresése
b. a négyzet átpakolása a vizsgáltak listájára.
c. ennek mind a 8 szomszédos négyzetével:
* ha nem járható, vagy zárt listán van, nem törődünk vele. Egyébként:
- ha nincs még a várólistán, tegyük hát hozzá. Szülője a jelenegi négyzetünk lesz. Állapítsuk meg G, H és F értékeit.
- ha már várólistás, nézzük meg melyik a rövidebb útvonal hozzá. Ha az új útvonal rövidebb lenne, cseréljük hát le a szülőt és kalkuláljuk újra a G és F értékeket. Ha a várólistát az F értékek alapján rendezve tartod, ne felejsd el ekkor újra rendezni a listát.
d. Állj meg, ha:
- a célterületet hozzáadtad a megvizsgáltak listájához. Ez azt jelenti, hogy meg van az útvonal
- meg kell állnod, ha nincs meg a célterület, de kifogytál a várólistás elemből. Ez azt jelenti, hogy nincs létező útvonal.
3. Mentsd el az útvonalat. A célterülettől a kezdőpontig visszafelé haladva leled meg a pontos útirányt.

Dióhéjban ennyi lenne az útkeresés, de a későbbiekben igyekszem minél több, témába vágó cikket lefordítani, mert bizony még sok mindenről nem esett szó. Addig is:


A cikkhez tartozó forráskódok és példaprogramok:
http://ilab.hu/jf/datas/users/9-astar.zip

Az eredeti, teljes cikk itt olvasható:
http://www.policyalmanac.org/games/aStarTutorial.htm

Útkereséssel kapcsolatos cikkek (angolul):
http://www-cs-students.stanford.edu/~amitp/gameprog.html#Paths
http://www.gamasutra.com/features/19970801/pathfinding.htm
http://www.gamasutra.com/features/gdcarchive/2000/pottinger.doc
http://www.gameai.com/pathfinding.html

Írta: Patrick Lester
Fordította: FZoli.

Értékelés: 9.44

Új hozzászólás
idioty          2007.11.26 06:47
Én már kb fél éve fejlesztem a táblás társasjátékon alapuló játékomat. Hozzá kell tenni, hogy semmilyen programozói tanfolyamot/iskolát nem végeztem, csak saját önszorgalom útján tanultam a programozást, és így olvastam el ezt a cikket most, hogy eljutottam a játékomban arra a szintre, hogy már lehetne gépi játékost is csinálni. Nah az útkereséssel nekem is sok bajom volt. De ez a cikk rövid, lényegretörő, és fantasztikus . Szerintem mindenféle útkeresést meg lehet vele oldani. Bár néha biztos ki kell egészíteni egy kicsit (gondolok itt olyanra, hogy ha az útvonal néha hegyes dombos vidéken át megy, akkor csak hozzá kell adni a mező költségéhez bizonyos nehézségi pontokat...).
Szóval összességében nagyon nagyon király!
Ati500          2007.02.21 13:33
Na megcsináltam c# alatt.. Marha jó!
peti634          2006.05.31 12:41
Hi all
nincs valakinek egy foráskodja hozá, plzzzz
FZoli          2006.04.19 02:55
Ez a magyar verzió 4 napja létezik, nem is csodálom, hogy nem ezt olvastad, hanem az angolt
És egyetértek, tényleg ez a legjobb, ha valaki most kezdi. Érthetően elmagyarázza és sok linket ad továbbjutásra.

FZoli.
Yokubo          2006.04.19 01:43
Én is ezt az algoritmust használom, és egész jól működik. A magyarázat is a legjobb amit sikerült fellelnem amikor kerestem, bár én az angol verzióját olvastam nem ezt.
Hacker          2006.04.17 23:46
Ok bocs látom már, hogy fordítás
Hacker          2006.04.17 23:45
Hmm ismerős ez a cikk. Ezt te írtad vagy csak fordítás?
FZoli          2006.04.17 15:28
Köszi!

Amúgy Google

FZoli.
robar          2006.04.17 11:40
Nagyon jó kis cikk! Honnan találsz ilyen jókat?