Princip rješavanja "labirinta"...

[mk]

Imam zadatak u kojem je u fajlu zadan labirint (1 - zid, 0- prolaz) i drugi file u kojem se nalaze koordinate nekog polja (to polje je uvijek 0 ili prolaz) i vrijednost tog polja u bodovima. Treba napisati program koji pronalazi put kroz labirint ali tako da se skupi najvise bodova.

E sad, ne zelim da mi neko uradi ovaj zadatak vec da mi objasni princip na kojem se radi. Princip na kojem se obicno rjesavaju zadaci sa labirintima. Mozete li objasniti i kako samo naci najkraci put, zanemarujuci ove bodove.

Tnx!

[junior]

Malo mi je smiješno to što treba naći najkraći put. Ne zvuči ni malo realno... Ako se nađeš u labirintu, znači da si totalno izgubljen u prostoru (prema tome ne možeš znati koji je pravi put, a kamoli koji je najkraći. Kad bih se ja našao u labirintu, stavio bih lijevu ruku na zid labirinta. Na svakom raskršću skretao bih lijevo (tako da lijeva ruka uvijek dodiruje zid labirinta).
Ovo dakako nije najkraći put, ali sam tako siguran da ću izaći. A sad, možeš ti zapisivati kuda si se kretao, pa ako se vratiš na istu točku na kojoj si već bio (raskršće) jednostavno ispustiš tu (slijepu) ulicu iz puta kojeg ćeš kasnije nazvati najkraći put. Jedino je zeznuto ako labirint ima više točnih puteva...

[e1]

mk: necu ti puno pomoc ako ti kazem da mislim da se radi o sustavu pronalazenja bilo kojeg tocnog puta i ako je vijednost svakog predjenog polja jedinica, najkraci ima najmanju zbirnu vrijednost.
No, sjecam se da sam vidio algoritam na www.gotoandplay.it a obzirom da se ljudi tamo vecinom takvim stvarima bave, mozda ti bude od vece pomoci.

junior: ako je labirint = pacman igra, onda je najbrzi put = AI neprijatelja koji trebaju unutar zidova naci najbrzi put do maloga pece... pa upit onda ima smisla.

[mk]

Nije ništa nemoguce, takvi su zadaci, od vise puteva treba naci onaj najkraci.

[junior]

Onda radiš kao što je e1 rekao, pronađeš sve puteve, lako je onda odredit koji je najkraći

[mk]

Onda radiš kao što je e1 rekao, pronađeš sve puteve, lako je onda odredit koji je najkraći
Gle, skontoa sam to i prije nego sam pokrenuo temu.

Mene zanima kako odrediti te puteve, koji algoritam, koja je logika, sta kako.....

[e1]

pa ako bi pogleda http://gotoandplay.it/_articles/index.php > pathfinding možda ti neki od ponuđenih primjera da odgovor.