[ BiF @ 08.05.2008. 19:26 ] @
dali je neko pokusao da napravi program za resavanje sokoban-a, makar neuspesno
[ Shadowed @ 08.05.2008. 19:36 ] @
Ne znam da li neko jeste, verovatno da, ali nacin za to je jednostavan. Imas moguce poteze, probas jedan, pa onda opet jedan od mogucih sa te pozicije i tako dok ne upadnes u poziciju iz koje nemas nikakav moguci potez. Onda se vratis jedan korak i probas nesto drugo. Kad je level resen, koraci koje si izveo su resenje istog.
E sad, to se da optimizovati tako sto postoje stituacije koje ne smes imati (pa je dalje ispitivanje u tom smeru bespotebno) kao sto je ubacivanje sanduka u ugao, spajanje 4 komada u kvadrat i sl. (to mozes proveriti pri svakom potezu i smatrati da je to potez nakon kojeg nemas gde pa se vracas za jedan.
[ BiF @ 08.05.2008. 19:54 ] @
Radio sam ja sve to i jos po nesto ali... brzina je jaaaaaako daleko od upotrebljivog, sad ne mogu da kazem tacno, ali mnogo mnogo godina
[ qdot @ 09.05.2008. 02:05 ] @
Ja sam se neshto malo interesovao za to, pre godinu-dve, i koliko sam shvatio, problem nije nimalo jednostavan. Naime, prostor pretrage je veoma veliki, stoga je i velika kompleksnost algoritma. Moj primarni resurs za to je bio http://www.cs.ualberta.ca/~games/Sokoban/.

Pozdrav, Mladen.
[ BiF @ 09.05.2008. 16:03 ] @
Da, nije problem napisati program koji radi, problem je sto niko od nas nece doziveti da se program zavrsi
[ vlaiv @ 10.05.2008. 00:17 ] @
Mislim da metod isprobavanja svakog poteza u datom slucaju stvarno nije efikasan, obzirom na shirinu prostora za pretragu.

Ako neko zeli da se bavi ovom problematikom, preporucio bih sledece ideje:

- napraviti putanje svake kuglice/sanduka/sta vec od pocetne pozicije do zavrsne pozicije/zavrsnih pozicija (objekat moze zavrsiti na vise razlicitih pozicija) (ovih putanja ima dosta, ali mnogo manje nego kombinacija poteza).
- problem prebaciti u 3D, gde ce koordinata u trecoj dimenziji predstavljati vreme, odnosno potez, pomeraj ili sta vec.
- ispitati koja kombinacija putanja je validna u 3d prostoru.
[ maricn @ 15.05.2008. 21:46 ] @
Umesto backtracka o kome pricate (pronalazenja resenja putem pokusaja i greske), mislim da bi bilo bolje koristiti A* algoritam, naravno, sve zavisi od velicine matrice i dostupne memorije...
Resenje ne bi bilo mnogo tesko, pravila su tacno odredjena...
[ qdot @ 16.05.2008. 12:06 ] @
Obichnim A* algoritmom ne mozesh da reshish nijedan (netrivijalan) sokoban nivo. Ova grupa (sa stranice koju sam naveo gore) je krenula sa modifikacijom A* koji se naziva IDA*, pa su dodavali poboljshanja i reshavali sve vishe i vishe nivoa. IDA* je reshila ukupno 0 problema :).
[ maricn @ 21.05.2008. 23:19 ] @
pa da, nisam ni mislio obicnim, ali nesto na tu foru bi mozda bilo dobro...