Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Resavanje sokoban nivoa

[es] :: Veštačka inteligencija :: Resavanje sokoban nivoa

[ Pregleda: 664 | Odgovora: 8 ]

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

BiF

Član broj: 39763
Poruke: 43
89.216.46.*



Profil

icon Resavanje sokoban nivoa08.05.2008. u 19:26

dali je neko pokusao da napravi program za resavanje sokoban-a, makar neuspesno
08.05.2008. u 19:26 

Shadowed
.NET developer

SuperModerator
Član broj: 649
Poruke: 8676
*.dynamic.sbb.rs.

Sajt: www.diskusije.net


Profil

icon Re: Resavanje sokoban nivoa08.05.2008. u 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.
08.05.2008. u 19:36 

BiF

Član broj: 39763
Poruke: 43
89.216.46.*



Profil

icon Re: Resavanje sokoban nivoa08.05.2008. u 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
08.05.2008. u 19:54 

qdot
Mladen Srdic
Nova Pazova

Član broj: 51019
Poruke: 25
217.169.219.*



Profil

icon Re: Resavanje sokoban nivoa09.05.2008. u 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.
09.05.2008. u 02:05 

BiF

Član broj: 39763
Poruke: 43
89.216.46.*



Profil

icon Re: Resavanje sokoban nivoa09.05.2008. u 16:03
Da, nije problem napisati program koji radi, problem je sto niko od nas nece doziveti da se program zavrsi
09.05.2008. u 16:03 

vlaiv
Vladimir Vlaisavljevic
Novi Sad

Moderator
Član broj: 15993
Poruke: 281
79.101.168.*



Profil

icon Re: Resavanje sokoban nivoa10.05.2008. u 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.
10.05.2008. u 00:17 

maricn
za tastaturom

Član broj: 42409
Poruke: 76
*.static.va.sbb.co.yu.



Profil

icon Re: Resavanje sokoban nivoa15.05.2008. u 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...
15.05.2008. u 21:46 

qdot
Mladen Srdic
Nova Pazova

Član broj: 51019
Poruke: 25
217.169.219.*



Profil

icon Re: Resavanje sokoban nivoa16.05.2008. u 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 :).
16.05.2008. u 12:06 

maricn
za tastaturom

Član broj: 42409
Poruke: 76
*.static.va.sbb.co.yu.



Profil

icon Re: Resavanje sokoban nivoa21.05.2008. u 23:19
pa da, nisam ni mislio obicnim, ali nesto na tu foru bi mozda bilo dobro...
21.05.2008. u 23:19 

[es] :: Veštačka inteligencija :: Resavanje sokoban nivoa

[ Pregleda: 664 | Odgovora: 8 ]

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.