|
dev.gamez.lv Latvian Game Developers Community
|
View previous topic :: View next topic |
Author |
Message |
bubu Indago Uzvarētājs
Joined: 23 Mar 2004 Posts: 3223 Location: Riga
|
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)
Code: | Time = 0.0561524
Path length = 72
Visited cells = 219/328 (66.7683%)
Used memory = 4 KiB |
small.raw
Code: | Time = 1.85079 msec
Path length = 1557
Visited cells = 7170/79999 (8.96261%)
Used memory = 1246 KiB |
small.raw ar citu ceļu
Code: | Time = 4.47096 msec
Path length = 2123
Visited cells = 23321/79999 (29.1516%)
Used memory = 1246 KiB |
large.raw (bilde samazināta 10 reizes)
Code: | Time = 2849.47 msec
Path length = 235947
Visited cells = 11473802/16634913 (68.9742%)
Used memory = 260040 KiB |
Viena lieta, kas tur palikusi diezgan neoptimāla ir NodePtrQueue::remove() metode, bet man slikums to optimizēt, jo tā strādāt tāpat diezgan (relatīvi) ātri.
Kods pārbaudīts, ka kompilējas uz MS VC++ 2008 Express Edition un zem GCC 4.2.0 (MinGW variantā). Gan jau uz citiem kompilēsies ar.
Bugus un nepilnības negarantēju - ja kāds tiek pamanīts, dodiet ziņu :) Nepretendēju arī uz vis-vis-optimālāko A* implementāciju. Galvenais uzsvars bija, lai kods sanāk īss - tādējādi būtu vieglāk maināms un pielāgojams pēc savas vajadzības. Netiek pārbaudīti arī visādi sliktumi - vai fails eksistē, vai sākuma/beigu pozīcija atrodas brīvā vietā, nevis sienā - tā ka uzmanīgi! ;)
Enjoy!
Last edited by bubu on Tue Nov 27, 2007 8:42 am; edited 1 time in total |
|
Back to top |
|
|
snake5 Indago dalībnieks
Joined: 27 Jun 2007 Posts: 2590
|
Posted: Mon Nov 26, 2007 11:40 pm Post subject: |
|
paldies par sourci, ņemu ciet, autortiesību nav, būs man jaunā a* implementācija
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
bet praktiski.. nu tas būtu vēl jāpārbauda.. _________________ "There are two choices here: "looks good" and "realism"." -- Paul Nettle |
|
Back to top |
|
|
bubu Indago Uzvarētājs
Joined: 23 Mar 2004 Posts: 3223 Location: Riga
|
Posted: Mon Nov 26, 2007 11:44 pm Post subject: |
|
snake5 wrote: | maina blakus esošo bloku pārbaudes secību atkarībā no |
Tu kautko murgo - A* algoritmā nekāda "blakus esošo bloku pārbaudes secība" neeksistē. |
|
Back to top |
|
|
snake5 Indago dalībnieks
Joined: 27 Jun 2007 Posts: 2590
|
Posted: Mon Nov 26, 2007 11:46 pm Post subject: |
|
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 _________________ "There are two choices here: "looks good" and "realism"." -- Paul Nettle |
|
Back to top |
|
|
bubu Indago Uzvarētājs
Joined: 23 Mar 2004 Posts: 3223 Location: Riga
|
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. |
|
Back to top |
|
|
Storm
Joined: 11 Apr 2006 Posts: 742
|
Posted: Tue Nov 27, 2007 1:52 am Post subject: |
|
Kaadi izpildes laiki ir push un pop listam? (peec big O) |
|
Back to top |
|
|
bubu Indago Uzvarētājs
Joined: 23 Mar 2004 Posts: 3223 Location: Riga
|
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). |
|
Back to top |
|
|
snake5 Indago dalībnieks
Joined: 27 Jun 2007 Posts: 2590
|
Posted: Tue Nov 27, 2007 12:29 pm Post subject: |
|
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 |
|
Back to top |
|
|
bubu Indago Uzvarētājs
Joined: 23 Mar 2004 Posts: 3223 Location: Riga
|
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. |
|
Back to top |
|
|
snake5 Indago dalībnieks
Joined: 27 Jun 2007 Posts: 2590
|
Posted: Tue Nov 27, 2007 5:32 pm Post subject: |
|
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 _________________ "There are two choices here: "looks good" and "realism"." -- Paul Nettle |
|
Back to top |
|
|
bubu Indago Uzvarētājs
Joined: 23 Mar 2004 Posts: 3223 Location: Riga
|
Posted: Tue Nov 27, 2007 6:51 pm Post subject: |
|
doh.. maini indeksus nevis lūpa ķermeni:
Code: | int x[4] = {0,1,2,3};
std::random_shuffle(x, x+4);
for (int i=0; i<4; i++)
{
Position new_pos = current_pos + direction[x[i]];
... |
|
|
Back to top |
|
|
snake5 Indago dalībnieks
Joined: 27 Jun 2007 Posts: 2590
|
Posted: Tue Nov 27, 2007 7:00 pm Post subject: |
|
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 |
|
Back to top |
|
|
bubu Indago Uzvarētājs
Joined: 23 Mar 2004 Posts: 3223 Location: Riga
|
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" :) |
|
Back to top |
|
|
|
|
You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
|