A* Pathfinding za Početnike

od Patrick Lester (Update-ovano  18. Jula, 2005)

Preveo i adaptirao sa engleskog jezika: Aleksandar Božinović. Sva pitanja možete poslati na e-mail adresu alexbozinovic@yahoo.com 


Ovaj članak je preveden sa engleskog na albanski, kineski, nemački, portugalski, ruski i španski. Drugi prevodi su dobrodošli. Vidite email adresu na dnu ovog članka.

A* (čita se: A-zvezda) algoritam može biti komplikovan za početnike. Iako na netu ima mnogo članaka koji objašnjavaju A*,  uglavnom su napisani od strane ljudi koji već  razumeju osnovu toga.

Ovaj članak je za istinske početnike.

Ovaj članak ne pokušava da bude definitivan rad na subjekat (naslov) teme. Umesto toga, članak opisuje osnove i priprema vas za sledeći korak, da biste razumeli i drugu materiju, a koja je usko povezana sa ovom. Na dnu strane ovog članka postavljeni su linkovi ka nekim od tih već pomenutih „nastavaka“.

Ovaj članak nije predodređen samo za jedan programski jezik. Napravljen je tako da se adaptira bilo kom programskom jeziku. Kao što i očekujete, u ovom članku naći  ćete i link ka programu koji je primer, na kraju ovog članka. Primerak sadrži dve verzije: jedna je u C++-u, a jedna u Blitz Basic-u. Takođe sadrži i executable's (egzekutabilne) fajlove, za slučaj da želite da vidite A* u akciji. 

Malo smo se udaljili od suštine. Hajde da počnemo, naravno, otpočetka... 

Uvod:  Područje pretrage

Pretpostavimo da imamo nekoga ko želi da ide od tačke A do tačke B.

Pretpostavimo da se zid nalazi između ovih tačaka. Ovo je ilustrovano ispod, zelenom je obeležena početna tačka A, crvenom završna tačka B, a plavom su obojeni kvadrati koji predstavljaju zid između njih.

Bild 1
[
Figure 1]

Prva stvar koju treba primetiti je da smo podelili naše područje pretrage na kradratnu mrežu.

Pojednostavljenje područja pretrage je prvi korak u pronalaženju staze (pathfinding).  Ovaj metod smanjuje naše područje pretrage na jednostavne dve dvodimenzionalne matrice. Svaka stavka u matrici predstavlja jedan kvadrat u mreži i sadrži status, to jest obeležava kvadrat kao prohodan ili neprohodan. Staza se nalazi otkrivanjem kojim putem treba ići (preko kojih kvadrata treba preći) da bi se stiglo od tačke A do tačke B. Jednom kad se staza nađe, naša osoba (koju smo ranije zamislili) se pomera od centra jednog kvadrata do centra sledećeg i tako dalje, sve dok ne stigne do željenog mesta.   

Ovi centri (kvadrata) se nazivaju „čvorovi“. Kad čitate o pronalaženju staze (pathfinding) negde drugde, često ćete videti da ljudi raspravljaju o čvorovima. Zašto ih ne zvati samo kvadratima? Zato što je moguće da tu oblast, na kojoj tražite stazu, podelite i na druge oblike. Mogu biti podeljeni na pravougaonike, šestougaonike, trouglove, ili zaista, bilo koji oblik. Što se tiče  čvorova, oni mogu biti postavljeni bilo gde po tom obliku, može u centru, duž ivica, ili bilo gde drugde. Međutim, mi koristimo ovaj sistem jer je najjednostavniji.

Početak traženja

Kada smo pojednostavili područje pretrage na određeni broj čvorova, kao što smo uradili to iznad, sledeći korak je pokretanje pretrage da bismo našli najkraći put (stazu). Uradićemo ovo počevši od tačke A, proverimo susedne kvadrate i generalno tražimo sve dok ne nađemo metu.

Počinjemo pretragu tako što radimo sledeće:

  1. Počinjemo kod početne tačke A i dodajemo je na „otvorenu listu“ kvadrata koja će se posmatrati. Otvorena lista je ista kao i shopping lista (lista za kupovinu). Trenutno je jedna stavka na listi, ali ćemo imati još stavki kasnije. Otvorena lista sadrži kvadrate koji se mogu naći duž staze koju ćemo odabrati, ali možda i neće. U suštini, ovo je lista kvadrata koji treba da se provere.
  2. Usmerićemo pogled ka dostupnim, to jest, prohodnim susednim kvadratima početnog kvadrata, ignorišući kvadrate sa vodom, zidovima i drugim neprohodnim terenima. Dodaćemo ih na otvorenu listu (dodajemo samo prohodne kvadrate!). Za svaku od ovih kvadrata (na otvorenoj listi), sačuvaćemo tačku A kao njegov (kvadratni) roditelj. Ovaj izraz „kvadratni roditelj“ ili „roditelj kvadrata“ biće veoma važan kada budemo pratili našu stazu. Biće detaljnije objašnjen kasnije.
  3. Ispustićemo početni kvadrat A sa naše otvorene liste i dodati ga u „zatvorenu listu“ kvadrata za koje nema potrebe da ponovo pogledate za sada.

U ovom momentu objašnjavanja sledi ilustracija. Na njoj, zeleni kvadrat u sredini je početni kvadrat. On je uokviren plavom bojom koja označava da je kvadrat dodat na zatvorenu listu. Svi susedni kvadrati su sada na otvorenoj listi kvadrata koji treba da se provere i oni su uokvireni zelenom bojom. Svaki ima i zeleni pokazivač koji pokazuje nazad na svog roditelja, koji je, u ovom slučaju, početni kvadrat.

Bild 2
[
Figure 2]

Sada, odabiramo jedan od susednih kvadrata sa otvorene liste i, manje-više, ponavljamo prethodni proces, kao što je opisano ispod. Pitanje je sad: „Koji kvadrat da izaberem?“ Onaj sa najmanjim F utroškom. 

Utrošak staze

Ključ, koji određuje koji će kvadrat da se koristi da bi se otkrila staza, određen je sledećim računanjem:

F = G + H

Gde su:

Kao što je opisano iznad, G je utrošak pomeranja za kretanje od početne tačke do određenog kvadrata, idući po stazi koja je stvorena (generisana) da se dođe do tu. U ovom primeru, dodelićemo utrošak od 10 za svako horizontalno ili vertikalno kretanje kvadrata, a za dijagonalno kretanje utrošak  

će biti 14. Koristićemo ove brojeve jer je stvarna distanca dijagonalnog kretanja jednaka korenu iz 2 (), što je jednako negde oko 1.414, što predstavlja utrošak dijagonalnog kretanja. Da bi stvari bile jednostavnije, umesto 1 ćemo koristiti 10, a umesto 1.414 ćemo uzeti 14. Otprilike je srazmerno, a ujedno smo se oslobodili decimala, dakle pojednostavili smo stvari.

Pošto računamo G utrošak duž  staze do datog kvadrata, način za određivanje G utroška tog kvadrata je da se uzme G utrošak od njegovog roditelja, pa se onda doda 10 ili 14 u zavisnosti da li se pokrenuo dijagonalno ili ortogonalno (nedijagonalno) od tog kvadrata roditelja.Potreba za ovom metodom biće očigledna malo kasnije na ovom primeru.

H utrošak može biti procenjen na razne načine. Metod koji ovde koristimo se zove Menhetenov metod (Manhattan), gde računate totalni broj kvadrata kojim se pokreće horizontalno i vertikalno da bi se dostigla meta (željeni kvadrat) od kvadrata u kojem se trenutno nalazi, ignorišući dijagonalne pokrete, i ignorišući bilo koje prepreke koju mogu biti na putu. Onda pomnožite ovaj broj sa 10 (to jest, utroškom jednog horizontalnog ili vertikalnog kretanja), te tako dobijate H utrošak. Podsećam vas da se prilikom računanja ide samo horizontalno i vertikalno, to jest ortogonalno.

Čitajući ovaj opis, nagađate da je heuristički način gruba procena preostalog rastojanja između trenutnog kvadrata i mete. To realno nije tako. Ustvari, mi pokušavamo da procenimo preostalo rastojanje duž staze (koje je često duže).  Što je naša procena bliža stvarnoj razdaljini, to je i algoritam brži. Ako precenimo ovu razdaljinu, kako god, nije garantovano da ćemo dobiti najkraću stazu. U takvim slučajevima, imamo nešto što se zove „neprihvatljiva heuristika“.

Tehnički, u ovom primeru, Menhetenov metod je nedopustiv jer precenjuje preostalo rastojanje. Mi ćemo se ipak služiti ovom metodom jer je mnogo lakše da se razume i zadovoljava naš cilj, ali i zato jer je to samo blago (dakle, do određene mere) precenjivanje. U retkim slučajevima, kada rezultujuća staza nije nakraća moguća, biće blizu najkraće (malo duža od najkraće). Želite da znate više? Možete naći informacije i dodatne beleške o heuristici ovde.

Utrošak F se izračunava sabiranjem G i H utroška (F = G + H). Ovi rezultati prvog koraka naše pretrage mogu se videti na ilustraciji ispod. F, G i H utrošci su napisani u svakom kvadratu. Kao što je označeno na prvom desnom kvadratu (od početnog zelenog), F je otštampano u gornjem levom uglu, G je u donjem levom uglu, a H je otštampan u donjem desnom uglu.

Bild 3
[
Figure 3]

Bacite pogled na neke od ovih kvadrata. Na desnom kvadratu sa slovima unutar, G = 10. Ovo je zato što je samo jedan kvadrat od početnog u horizontalnom pravcu. Kvadrat iznad, zatim ispod, kao i onaj s leve strane početnog, svi oni imaju G koje je jednako 10. Dijagonalni kvadrati imaju G koji je jednak 14.

H utrošak jer izračunat procenom Menhetenove distance (rastojanja) do crvenog kvadrata, pomerajući se samo horizontalno i vertikalno, ignorišući zid koji je na putu. Koristeći ovu metodu, kvadrat s desne strane početnog kvadrata je udaljen 3 kvadrata od crvenog kvadrata, stoga mu je H utrošak jednak 30. Kvadrat iznad početnog kvadrata je 4 kvadrata udaljen od crvenog (zapamtite, samo se pomera horizontalno i vertikalno), te za H utrošak ima 40. Možete i sami da vidite kako su ostali H-ovi izračunati za druge kvadrate.

F utrošak, za svaki, da ponovimo, je ,jednostavno, jednak zbiru G i H. 

Nastavak traženja

Da bismo nastavili traženje, jednostavno ćemo izabrati kvadrat sa najnižim F-om od svih kvadrata sa otvorene liste.

Onda ćemo uraditi sledeće sa odabranim kvadratom:

Ok, pa, hajde da vidimo kako ovo radi. Od naših 9 inicijalnih (početnih) kvadrata, imamo 8 postavljenih na otvorenu listu, pošto je početni kvadrat prebačen na zatvorenu listu. Od ovih na otvorenoj listi, kvadrat sa najmanjim F-om je sa desne strane od početnog kvadrata sa F = 40, tako da ćemo ga odabrati da bude sledeći. Uokviren je plavom bojom na sledećoj ilustraciji.

Bild 4
[Figure 4]

Prvo ga spustimo sa otvorene liste i dodajemo ga na zatvorenu listu (zbog toga je uokviren plavom bojom). Onda proverimo susedne kvadrate. Ovi sa desne strane su kvadrati zidovi, pa ih ignorišemo. Onaj sa leve strane je početni kvadrat, a s obzirom da je na zatvorenoj listi, ignorisaćemo i njega takođe. Ostala četiri kvadrata su već na otvorenoj listi, te treba da proverimo da li je staza (počevši) od njih imalo bolja, koristeći G kao tačku reference. Pogledajmo kvadrat desno iznad našeg selektovanog kvadrata. Njegov G je 14. Ako smo umesto onog puta, prošli kroz ovaj kvadrat da bismo tamo stigli, G bi bio jednak 20 (10, što je G utrošak da se stigne do ovog kvadrata, plus još 10 da se pokrene vertikalno do onog iznad njega).  G utrošak 20 je veći od 14, tako da ovo nije bolja staza. To bi imalo smisla ako pogledate na dijagram. Usmerenije je otići do tog kvadrata od početnog kvadrata ako se jednostavno pomeri za jedan kvadrat dijagonalno da dođe tamo, nego da se pomeri horizontalno za jedan kvadrat, pa onda vertikalno za jedan kvadrat.

Kada ponovimo ovaj proces, za sva četiri susedna koja su već na otvorenoj listi, videćemo da nijedna od ovih staza nije poboljšana (to jest bolja od prethodne), tako da nećemo menjati išta. Sada, kad smo pregledali sve susedne kvadrate, završili smo sa ovim kvadratom i spremni smo da se pomerimo na sledeći kvadrat.

Kako idemo kroz otvorenu listu kvadrata, koja za sada ima sedam kvadrata, odabraćemo jedan sa najnižim F-om, odnosno u ovom slučaju, imamo 2 kvadrata sa F-om od 54. Koji ćemo onda da izaberemo? Zaista nije važno. Ako će nam kao razlog odabira biti brzina, onda bi najbrže bilo da se izabere onaj koji je poslednji dodat na otvorenu listu.

Hajde da izaberemo onaj ispod, a sa desne strane od početnog kvadrata, kao što je i prikazano na sledećoj ilustraciji.

Bild 5
[Figure 5]

Ovog puta, kadaproveravamo susedne kvadrate, nalazimo da li je onaj s desne strane kvadrat zid, pa ga ignorišemo. Isto ide za onaj koji je iznad tog. Takođe ignorišemo kvadrat koji je ispod zida. Zašto? Zato što se ne može doći do tog kvadrata direktno od trenutnog kvadrata (na kom smo sada), bez usecanja kroz ugao obližnjeg zida. Stvarno treba da idete pravo dole, a onda da pređete preko tog kvadrata, zaobilaženjem ugla u procesu. (Primedba: Ovo pravilo o zasecanju uglova je opcionalno (fakultativno, neobavezno. Njegova primena zavisi od toga kako su čvorovi postavljeni).

To ostavlja 5 drugih kvadrata. Druga dva kvadrata ispod trenutnog kvadrata nisu još uvek na otvorenoj listi, pa ćemo ih dodati, te će trenutni kvadrat postati njihov roditelj. Od tri drugih kvadrata, dva su već na zatvorenoj listi (početni kvadrat i onaj iznad trenutnog su uokvireni plavom bojom na dijagramu), pa ih ignorišemo. Poslednji kvadrat, s leve strane trenutnog kvadrata, proveravamo da bismo videli da li je njegov G manji ako idemo kroz trenutni kvadrat da stignemo tamo. Izgleda da nije. Gotovi smo i spremni da proverimo sledeći kvadrat na otvorenoj listi.

Ponovićemo ovaj proces sve dok ne dodamo završni kvadrat na zatvorenu listu, što je ilustrovano ispod.  

Bild 6
[Figure 6]

Opazite da se kvadrat roditelj kvadrata, koji je dva kvadrata ispod početnog kvadrata, promenio od prošle ilustracije. Ranije je imao G utrošak od 28 i pokazivao nazad na kvadrate iznad njega i s desne strane. Sada ima vrednost 20 i pokazuje ka kvadratu koji je iznad njega. Ovo se dešava negde duž puta na našoj pretrazi, gde se G proverava i promenjen je u nižu vrednost koristeći novu stazu – tako da je roditelj zamenjen, a G i F utrošci se ponovo izračunavaju. Iako ova promena ne izgleda kao tako značajna na ovom primeru, postoje brojne situacije gde će ovo konstantno proveravanje da napravi razliku u određivanju najbolje staze ka svom cilju.

Kako ćemo onda odrediti stazu? Jednostavno, samo treba da počnemo od crvenog kvadrata i da vršimo kretanje unazad od kvadrata ka njegovom roditelju, prateći strelicu (pokazivač). Ovo će vas na kraju dovesti nazad do početnog kvadrata, i to je vaša staza. Treba da liči na sledeću ilustraciju. Pomerajući se od početnog kvadrata A do destinacionog kvadrata B je, ustvari, kretanje od centra do centra svakog kvadrata (čvora) na stazi, dok se ne dostigne meta.

Bild 7
[Figure 7]

Rezime A* metode

Ok, sada kad ste prošli kroz objašnjenje, hajde da postavimo korap po korak ovu metodu sve na jedno mesto:

  1. Staviti početni kvadrat (ili čvor) na otvorenu listu.
  2. Ponoviti sledeće:
    1. Pronaći kvadrat sa najnižim F utroškom na otvorenoj listi. Odnositi se na taj kvadrat kao na trenutni kvadrat.
    2. Premestiti trenutni kvadrat na zatvorenu listu.
    3. Za svaki od 8 susednih kvadrata ovog kvadrata:
      • Ako nije prohodan ili ako je na zatvorenoj listi, ignorišemo ga. U suprotnom, učiniti sledeće:
      • Ako nije na otvorenoj listi, dodajte ga na listu. Načiniti trenutni kvadrat roditeljom ovog kvadrata. Sačuvajte F, G i H utroške kvadrata.
      • Ako je već na otvorenoj listi, proveriti da li je staza do ovog kvadrata bolja, koristeći G utrošak kao meru odlučivanja. Niži G utrošak znači da je staza bolja. Ako je tako, načiniti taj kvadrat roditeljom i ponovo mu izračunati G i F utroške. Ako na otvorenoj listi držite F utroške, onda je potrebno da resortirate listu.
    1. Zaustaviti se kada:
      • se doda završni kvadrat na zatvorenu listu, kada je staza pronađena, ili
      • ne pronađe zavrpni kvadrat i kada je otvorena lista prazna. U tom slučaju, nema staze.
  1. Sačuvati stazu. Treba ići unazad od završnog kvadrata, ići od svakog kvadrata do njegovog roditelja sve dok se ne dosegne početni kvadrat. To je vaša staza.