dev.gamez.lv

bubu · Posted: Mon Nov 26, 2007 11:02 pm Post subject: Vienkāršs A*

Izdomāju, ka nepiemēslošu Storm'a topiku par A*, tāpēc uztaisīšu savu topiku.
Beigu beigās tur man sanāca arī diezgan gatava A* implementācija. Lai arī vakar vēl bija bugi (tāpēc dažās kartēs tas staigāja diezgan dīvaini vai pat randomiski), taču tagad liekas esmu tos izlabojis, tāpēc piedāvāju C++ sourci kam nu vajag - lietojiet kā vien tik tīk. Iespējams nāksies nedaudz pielāgot to savām vajadzībām (kartes formāts/veids/ielasīšana un tml..) Veidoju tikai rūtiņu veida apstaigšanu, bet nu to ir iespējams modificēt, ja savā grafā ir iespējams viennozīmīgi sanumurēt nodes, tb piešķirt tiem numurus - 0, 1, 2,.. un ātri atrast pēc numura nodi, un jebkurai nodei tās numuru (relatīvi viegli izdarāms).

Galvenie divi faili:
grid_map.h - http://paste.php.lv/6493?lang=cpp
grid_map.cpp - http://paste.php.lv/6494?lang=cpp

Izsaukšanas piemērs:
main.cpp - http://paste.php.lv/6492?lang=cpp

Karte tiek ielādēta no faila, kurā pirmie divi unsigned shorti norāda attiecīgi kartes platumu un augstumu. Pēc tam seko kartes rūtiņas pa vienam baitam uz katru - 0=siena, jebkas cits=brīvs laukums. Programma pieņem, ka grūtība kāda ir pārvietojoties no vienas rūtiņas uz citu ir vienmēr konstanta = 1. Ja vajag dažādu grūtību, tad to viegli var pamodificēt grid_map.cpp failā 378 rindā pamainot to vieninieku (tur jāieliek atkarība no current_pos un new_pos - var, piemēram, ņemt kartes rūtiņu vērtību absolūto starpību šajās pozīcijās + 1).

Apstaigāšana notiek tikai vertikāli un horizontāli. Ja nepieciešams staigāt arī pa diagonāli, tad jāmaina direction un inverse_direction masīvi ~329 rindā. Vēlams tādā gadījumā arī pamainīt heiristikas funkciju 61 rindā. Ja grid_map.h faila sākumā tiks noņemts nost komentārs no tā #define REPORT_PERFORMANCE 1, tad programmas darbības gaitā tiks izvadīts uz ekrāna ceļa meklēšanas ilgums, patērētā atmiņa un citi dati.

GridMap klases konstruktora pirmajā parametrā ir jāpadod maģiskā H konstante, kura diezgan būtiski ietekmē algoritma performanci, taču nav viennozīmīgi nosakāmā - tā ir atkarīga no kartes un meklējamā ceļa sarežģītības. Lielām kartēm der likt lielas H vērtības, bet mazām - mazas. Jo lielāks skaitlis - jo vairāk "nederīgo" rūtiņu algoritms apstaigās, taču pie mazām vērtībām tas var atrast ne optimālāko ceļu (t.i. ne pašu īsāko). Iesaku vienkārši pamēģināt uz savas vajadzīgās karte dažādus ceļus ar dažādām H vērībā, un labāko pēc skata/laika paņemt par konstanti šai kartei.

Dažas piemēra kartes - tiny.raw, small.raw un large.raw (sazagos no Storm :) Large.raw ir ļoti ļauna karte, ar vienu vienīgu ceļu, no viena kartes gala līdz otram kartes galamm, kas nav īsti piemērota A* algoritmam, tāpēc par tās rezultātiem nevajadzētu brīnīties. Kā izsaukt ceļa meklēšanu šajās kartēs var apskatīt main.cpp failā, kurā atliek atkomentēt vajadzīgo koda daļu. Tur tiek arī saglabāts atrastais ceļš bmp failā kā bilde. Protams, tas nav obligāti, jo ceļu var izmantot arī savādāk. GridMap::save_bmp metodi vispār var mest ārā.

Daži piemēri. Sarkanais ir atrastais ceļš. Zaļais ir apmeklētās rūtiņas (jo mazāk, jo labāk).

tiny.raw (bilde palielināta 10 reizes)

snake5 · Indago dalībnieks Joined: 27 Jun 2007 Posts: 2590

paldies par sourci, ņemu ciet, autortiesību nav, būs man jaunā a* implementācija Mr. Green

joks!

pēc sources sapratu, ka pats A* atrod ceļu ar "brute-force" metodi, neņemot daudz ko vērā...
nu tā nu man rodas ideja par tādu astaru, kurš maina blakus esošo bloku pārbaudes secību atkarībā no virziena līdz galapunktam!
teorētiski spēlē tas varētu būt noderīgi, jo parasti AI jāapiet tikai daži šķēršļi, nevis jāskraida pa labirintu kā laboratorijas žurkai Wink

bet praktiski.. nu tas būtu vēl jāpārbauda..
_________________
"There are two choices here: "looks good" and "realism"." -- Paul Nettle

bubu · Posted: Mon Nov 26, 2007 11:44 pm Post subject:

snake5 · Indago dalībnieks Joined: 27 Jun 2007 Posts: 2590

kam citam tad tie "direction" mainīgie?
es domāju, ka viss tomēr notiek zināmā secībā, vai arī astar uz 4 thread'iem strādā?

EDIT: viss notiek šādā secībā:
Position( 1, 0),
Position( 0, 1),
Position(-1, 0),
Position( 0, -1),
kuru noderētu pamainīt attiecībā uz... nu kā es iepriekš teicu, apnika rakstīt Mr. Green

_________________
"There are two choices here: "looks good" and "realism"." -- Paul Nettle

bubu · Posted: Mon Nov 26, 2007 11:56 pm Post subject:

To vērtību secībai direction masīvā nav nekādas nozīmes. Maini kautvai visas otrādi (no apakšas uz augšu) vai arī izvēlies pilnīgā random kārtībā - algoritms izdos precīzi vienu un to pašu ceļu. Izskatās, ka tev nav izpratnes par to, kas A* algoritmā notiek manā kodā #359 un #410 rindiņās. Ja tu vēlies diskutēt par A* (pret ko man nekas pretī nav), tad ej vispirms izlasi, kā (un galvenais tieši kāpēc tā) A* darbojas un tikai tad sāc savas kārtējās idejas klāstīt.

Storm · Joined: 11 Apr 2006 Posts: 742

Kaadi izpildes laiki ir push un pop listam? (peec big O)

bubu · Posted: Tue Nov 27, 2007 8:45 am Post subject:

Ja tu domā ielikšanu/mazākā izņemšanu tajā NodePtrQueue, kas tiek izmantots, lai atrastu elementu ar mazāko svaru Open listā, tad abiem diviem ir O(log N), jo tajā izmantoju STL heap'u (kaudzi). Pielikšana/noņemšana no Closed lista ir O(1).

snake5 · Indago dalībnieks Joined: 27 Jun 2007 Posts: 2590

nu man neinteresē, vai atgriež tādu pašu vai citu pathu, galvenais, ka mana ideja astaru padara ātrāku!!!
ja vajag uzskatāmu piemēru, tad pasaki!

btw, 410. rindā ir "{"
_________________
"There are two choices here: "looks good" and "realism"." -- Paul Nettle

bubu · Posted: Tue Nov 27, 2007 1:27 pm Post subject:

Bah tu tiešām tici tam, ko pats saki!!? Nekas tur ātrāks nepaliks, jo kārtība kādā elementi nāks ārā no open lista nemainīsies. Un apskatāmo kaimiņu skaits arī nemainīsies. To nākamo elementu kārtību ietekmē tikai heiristikas funkcijas izvēle. Tā kārtība kādā apskata kaimiņu elementus nemaina to svaru (ja vien speciāli to neieliek heirisitkas funkcijā, taču par to tu ne vārda neesi minējis).

Gribēju teikt 411, ne 410 rindu.

snake5 · Indago dalībnieks Joined: 27 Jun 2007 Posts: 2590

hmm.. vēlreiz pētu kodu...
skatos, ka tas "direction loops" ir tā ierakts, ka kods paliks ļoti garš, ja tur ko mēģinās mainīt...

tātad.. pagaidām ideju nav.. bet drīz būs Wink

_________________
"There are two choices here: "looks good" and "realism"." -- Paul Nettle

bubu · Posted: Tue Nov 27, 2007 6:51 pm Post subject:

doh.. maini indeksus nevis lūpa ķermeni:

snake5 · Indago dalībnieks Joined: 27 Jun 2007 Posts: 2590

nu ir tā, ka man vajag to direction pārkārtot attiecīgi pēc tā, kurš virziena vektors tuvāks virziena vektoram no šīs nodes uz galapunktu*, jeb kura no "direction" masīva paņemtā vektora skalārais reizinājums ar to(*) virziena vektoru vislielākais...
tas varētu dot iespēju mazāk meklēt liekus ceļus..

bet tava ideja varētu palīdzēt šito īstenot... tik jāpamēģina...

es tā nedaudz pamēģināju un redzēju, ka secība virzienu masīvā ir diezgan svarīga.. tagad tikai jāizdomā, kā ātri sašķirot tos ciparus pēc iespējamā lietderīguma...
_________________
"There are two choices here: "looks good" and "realism"." -- Paul Nettle

bubu · Posted: Thu Jan 03, 2008 11:17 pm Post subject:

Izskatās, ka šņake noziedējis ar visām savām gudrajām "optimiziācijām" virzienu secībai masīvā...

Bet anyway, tā kā Storma fīča nedzēst no Open lista atkārtojošās nodes izrādījās diezgan noderīga, tad ieviesu šo fīču arī savā implementācijā. Rezultātā ieguvu lielāku ātrumu uz patukšākām kartēm. Kā arī source palika vienkāršāka.

Pie reizes pieķēros nožu glabāšanas sistēmas optimizēšanai - tagad algoritms runtaimā patērē aptuveni divreiz mazāk atmiņas. Attiecīgi piemēra kartēm:
tiny: 2 KiB
small: 624 KiB
large: 130035 KiB
Meklēšanas laiki kā arī atrastie ceļi šīm kartēm palikuši tādi paši kā iepriekš.

Pie reizes uzrakstīju arī staigāšanu pa diagonāli (ja nu kādam vajag). Atliek tikai atkomentēt rindiņas nr 297-300 un 309-312 un viss notiksies. Kustēšanās pa diagonāli ir par kvadrātsakni no 2 dārgāka nekā kustēšanās pa horizontāli vai vertikāli.

Mainītā source ir tikai grid.cpp fails: http://paste.php.lv/6686?lang=cpp

Kā redzams tā mana "vislēnākā" NodePtrQueue::remove() metode aizgājusi prom. Palikušas tikai "ātrās" :)