Racunanje distance (pathfinding problem)

[Nemesis]

Molio bih ljude koji imaju iskustva sa pathfindingom da mi pomognu (savetima)oko dobrog algoritma za odredjivanje putanje.

Problem:
Potrebno je za uneti broj tacaka k (k < 20) odrediti njihova medjusobna rastojanja (tj. broj turnova od jedne tacke do druge) ako su poznate koordinate svake tacke i ako je data matrica po kojoj se treba kretati.

Poznato:
- Svaka tacka (npr. A, B, C) je definisana koordinatama X i Y
- Data je matrica "sveta" dimenzija M X N na kojoj se nalaze tacke
* M <= 10000 i N <= 10000 (ove velike dimenzije su glavni problem)
* svako polje matrice je jedan integer i to:
0 - ako na polje nije moguce stati (zid)
1,2,3,4,5 - cena kretanja po datom polju (tj. koliko se poteza utrosi ako se krece preko tog polja; 1 najbrze, 5 najsporije)

Ogranicenja:
Postoji vremenski limit za nalazenje resenja koji iznosi 1 sec!!!



S obzirom da se ne zna putanja izmedju tacaka pretpostavljam da je prvo potrebno naci optimalnu (ili dovoljno dobru) putanju, a onda "izmeriti" njenu duzinu i to sacuvati kao minimalno rastojanje.
Ja sam se odlucio za A* u resavanju ovog problema i sa malim dimenzijama matrice radi savrseno. Ali problem se javlja kada M i N predju 1000, a sam svet je neki zaguljeni lavirint sa mnogo "slepih ulica". (pa A* trosi node u budzacima)

Da li neko ima ideju za eventualno poboljsanje A* ili bi mozda trebao da probam sa nekim drugim algoritmom?
Svaki savet ili link je dobrodosao.

Jos da dodam da resenje ne mora da bude 100% tacno. Manje greske su prihvatljive ako se dobija na brzini.

[void*]

Bilo bi zgodno kad bi mape bile dostupne pre samog startovanja programa, onda bi bilo moguće uraditi deo ispitivanja offline i zatim ga keširati. Koliko sam shvatio, to ovde nije slučaj.

Možda bi trebao da pokušaš sa nekim adaptivnim metodom. Recimo, podeliš mapu 10,000 x 10,000 na sektore veličine 100 x 100. Zatim za svaki sektor utvrdiš povezanost sa okolnim, ispitujući ivične nodove. To sve naravno keširaš. Za svaki par tačaka A i B, koristeći povezanost sektora, određuješ najkraći put. Zatim za svaki sektor u dobijenoj putanji povezuješ tačke U i I, gde je U ulazna tačka u dati sektor, a I tačka izlaza tj. ulaza u sledeći. Ideja je veoma slična, kao kad u velikom gradu pokušavaš da sa jednog kraja stigneš u drugi. Svakako nećeš odmah da zabiješ lice u kartu u pratiš svaku uličicu i prolaz, već ćeš prvo u globalu isplanirati put(ovde prelazim most, idem do onog bulevara, kod trga skrenem desno...). Ovo je samo ideja. Nisam nikad implementirao ništa slično tome i generalno nemam nekog posebnog iskustva sa pathfinding-om (stoga, ovo je možda savršeno nepotreban post, ali eto, možda bude od koristi :) )

Takođe, možda bi trebalo da ispitaš svoju implementaciju, ima li prostora za neke optimizacije, pamćenje delova mape koje si već obišao, gde su slepe ulice i tome slično.

neki linkovi o A* algoritmu:
http://theory.stanford.edu/~amitp/GameProgramming/
http://www.policyalmanac.org/games/aStarTutorial.htm

[Nemesis]

Hvala na savetima i linkovima. Prvi link je bio izuzetno koristan. Na osnovu njega sam promenio strukturu podataka i dobio malo ubrzanje algoritma. Jos uvek je daleko od zeljenog cilja, ali je ipak za nijansu brzi.

void* kaže:

Možda bi trebao da pokušaš sa nekim adaptivnim metodom. Recimo, podeliš mapu 10,000 x 10,000 na sektore veličine 100 x 100. Zatim za svaki sektor utvrdiš povezanost sa okolnim, ispitujući ivične nodove. To sve naravno keširaš. Za svaki par tačaka A i B, koristeći povezanost sektora, određuješ najkraći put. Zatim za svaki sektor u dobijenoj putanji povezuješ tačke U i I, gde je U ulazna tačka u dati sektor, a I tačka izlaza tj. ulaza u sledeći.

Upravo to i pokusavam. Mislim da su bas tom logikom radili pathfinding u Diablu (a verovatno i u drugim igrama). Resenje je super kada je mapa "otvorena" tj. traba naci put oko prepreka.
Ali ako je neki lavirint u pitanja sa veoma uzanim putanjama, tako da po nekoliko putanja moze stati u jedan sektor, a da pri tom vode ka razlicitim tackama onda zaista imam problem. Na primer podelio sam mapu 10000 x 10000 na 100 x 100. Ono sto u 100 x 100 izgleda kao najbolja putanja moze biti i veoma losa jer je unutar tih sektora putanja puna prepreka ili ne vode sve putanje u istom pravcu. Postaje problem kako sad naci U i I tacke jer ih ima vise?

A attachmentu saljem sliku u paint-u cisto ilustracije radi. Neka je mapa 100 x 100 izdeljena u sektore 10 x 10. Plave tacke oznacavaju pocetak i kraj zeljene putanje. Crveni pikseli su oni preko kojih je moguce kretanje (sada ne uzimam brzinu kao faktor) a crni su zidovi. Prvo trazim putanju preko sektora i ovde se algoritam zaleti i krene dole pa desno. (a trebao bi prvo levo pa dole, pa tek onda desno)Tek kada pocne povezivanje U i I tacaka i odredjivanje putanje unutar svakog sekotra zakljucuje da u poslednjem sektoru ima prepreku i da putanja nije dobra.
Ovo za sada ne znam kako da resim.

Inace, ako je mapa otvorena onda A* radi super kao i poboljsanje koje si predlozio!

[void*]

Nemesis kaže:

Tek kada pocne povezivanje U i I tacaka i odredjivanje putanje unutar svakog sekotra zakljucuje da u poslednjem sektoru ima prepreku i da putanja nije dobra.

Hmm... da, to jeste problem. Možda bi mogao da probaš da paralelno ispituješ i iz početne i iz ciljne tačke. Tada je najgori slučaj ako se prepreka nalazi na sredini puta. U najboljem slučaju prepreka se nalazi u početnom ili ciljnom sektoru.

Pala mi je na pamet još jedna ideja. Malo je heavy, ali mislim da vredi razmotriti :) Pretvoriš postojeću, matricu integera, u bit-mapu. Grupišeš polja u grupe od 8 (ili 16, 32) i ako je polje slobodno setuješ bit na 1, a ukoliko je to polje zid, na 0. Tada neki hodnik (#....##.) gde su tarabama označeni zidovi dobija oblik 10000110 ili 134 dekadno. Umesto da porediš 8 integera(odnosno 32 bajta), porediš 1 bajt. Poređenje bi se realizovalo primenom operatora AND:

10000110 - niz polja (1 bajt)
11111111 - 255 dekadno
-------------------------- AND
10000110 

11111111 - niz polja
11111111 - 255 dekadno
-------------------------- AND
11111111 = 255 dekadno

Jasno, ako su svi bitovi setovani na 1(tj sva polja su slobodna za prolaz) rezultat će biti 255, što nas dovodi do:

// ...
char test_niz;   
if ((test_niz & 255)==255)
{
	// sva polja su slobodna za prolaz
}
else
{
	// negde postoji prepreka
}
// ...

Na taj način možeš veoma efikasno da 'čistiš' hodnike. Mogu se koristiti i druge operacije(OR, XOR), sve zavisi šta ti konkretno treba u tom trenutku. Takođe, mislim da nema prepreke da kombinuješ glavnu mapu sa ovom bit-mapom. Ako bi se to dobro implementiralo, mislim da bi dobitak mogao da bude veoma značajan. Inače, na sličan način quake engine pakuje potencijalnu vidljivost(radi uštede memorije, pre svega), tako da ovo verovatno ima smisla :)

Interesuje me, da li se mapa generiše nekom funkcijom direktno u memoriju, ili se učitava iz fajla? Da li se vreme meri interno, pozivom funkcije, ili spolja, štopericom?

[Nemesis]

void* kaže:

Hmm... da, to jeste problem. Možda bi mogao da probaš da paralelno ispituješ i iz početne i iz ciljne tačke. Tada je najgori slučaj ako se prepreka nalazi na sredini puta. U najboljem slučaju prepreka se nalazi u početnom ili ciljnom sektoru.

Probao, ali su rezultati jos gori. Ostvaljam mogucnost i da sam nesto zabrljao u implementaciji, ali mislim da je glavni problem sto je kod paralelnog ispitivanja potrebno korigovati tezine za sve node. (jer kako se i cilj pomera treba i da se promeni tezina, tj. cena kretanja ka cilju) Od odvog koncepta odustajem.

void* kaže:

Pala mi je na pamet još jedna ideja. Malo je heavy, ali mislim da vredi razmotriti Pretvoriš postojeću, matricu integera, u bit-mapu. Grupišeš polja u grupe od 8 (ili 16, 32) i ako je polje slobodno setuješ bit na 1, a ukoliko je to polje zid, na 0. Tada neki ...

Sjajna ideja, s tim sto funkcionise samo u "Manhaten" slucaju. (kada je kretanje moguce samo gore, dole, levo i desno) Na srecu ovaj moj problem je tog tipa.
Inace, poznat mi je ovaj koncept jos od vremena igranja sa 2D grafikom u pascalu, kada je trebalo brzo flipovati sprajt (tj. boje) uzimajuci u obzir matricu transparentnosti.
Nije mi palo na pamet da isto probam ovde. Hvala!

Jedino sto ova varijanta ne uzima u obzir tezine, ali s obzirom na malu razliku, cena obilaska oko jedne celije je vece od proslaska kroz skuplju celiju tako da ce da prodje. Pitanje je da li ce to znacajno doprineti algoritmu koji se relativno dobro snalazi sa otvorenim mapama. Spirale i slicna "cudesa" su meni problem.

void* kaže:

Interesuje me, da li se mapa generiše nekom funkcijom direktno u memoriju, ili se učitava iz fajla? Da li se vreme meri interno, pozivom funkcije, ili spolja, štopericom?

Pa zar je to bitno? Osim ako nemas neku dobru ideju za kesiranje!?
Nisam hteo u opisu problema da pisem nebitne stvari, ali posto si pitao...
Ovaj algoritam je deo mnogo veceg AI algoritma koji sam koristio na takmicenju. Zamisli da imas neku RTS igru i da je potrebno napisati AI. Kad bi pisao sve detalje ovaj post bi bio predugacak. Poenta je da mi je jednina slaba tacka lose racunanje izmedju kljucnih tacaka zbog cega AI gresi.

Meni je dozvoljeno samo da napisem AI dll. Ostatak je kod sudije. Svi takmicari predaju dll-ove sudiji koji ih spaja i potom pokrece program. Sudija bira mapu koja se ucitava iz fajla.
Znaci mapa se ucitava ali sve sto ja imam je funkcija GetMap() koja vraca niz int-ova ili GetMap(int x, int y) koji vraca tezinu date celije.
Sto se tice merenja vremena to je opet na sudiji, ali sigurno ne radi stopericom. Nema ni potrebe. Verovatno je interno merenje vremena jer ako kod radi duze od 1 sec. po potezu onda igra penalizuje taj kod preskakanjem celog poteza. Ako se ponovi obicno kosta i cele partije.