Učitavanje lavirinta i njegovo rešavanje

[dexa0704]

@StefanAndjelic Dejan Zarić, SW33-2014, Grupa 3

Problem predstavlja slika lavirinta koja se programski učitava. Vrši se izbor algoritma i lavirint rešen tom metodom se zapiše u drugu sliku, sa prikazanom putanjom kojom se došlo do rešenja. Nakon rešavanja prikazali bi se podaci o utrošenom vremenu za rešavanje kao i broj koraka potrebnih za dolazak do cilja.

Bila bi Desktop GUI aplikacija implementirana u python programskom jeziku. Za rad sa slikama bi se koristila python biblioteka PIL.

Algoritmi koji bi se koristili su oni koji su pominjani na nastavi u oblasti pretraga:

• A* algoritam #
• BFS algoritam
• DFS algoritam -Iterativni DFS algoritam

Napomena za A* algoritam: Biće ponudjen izbor heuristike. Planiram da stavim Manhattan rastojanje i verovatno Euklidsko rastojanje.

Podaci sa kojima se bude radilo će biti pripremljene slike lavirinta, ali isto tako se može dodati nova slika po izboru koja će biti rešena. Iz fajl sistema se bira slika, učita se u program i ispišu se svi detalji učitavanja (vreme potrebno za učitavanje slike i kreiranje grafa, kao i broj kreiranih čvorova). Takodje postojaće opcija generisanje lavirinta i izbor veličine tog lavirinta koji se generiše kroz program, i onda da tako generisan lavirint bude rešen.

Nakon rešavanja postojala bi opcija da se automatski otvori slika koja predstavlja rešenje. Na njoj bi se jasno prikazalo koji je put od starta do cilja i to bi predstavljalo jedinu i dovoljnu validaciju.

[StefanAndjelic]

Pozdrav,

Koje metode nameravaš da koristiš za prepoznavanje zidova u lavirintu? Da li su upitanju računarski izgenerisane slike ili kamerom snimljene slike na papiru? Za slučaj generisanih slika, ne vidi se nikakvo proširenje u odnosu na ono što je rađeno na vežbama i stoga to ne može biti validna tema za projekat.

[dexa0704]

Pozdrav,

planirao sam da proveravam boju za zidove. Lavirint bi bio crno beo verovatno, odnosno crna boja bi bili zidovi, a bela prazan prostor. Nisam nameravao da podržavam ručno slikane fotografije lavirinta na papiru. Tako da izgleda nije dovoljno za projekat. Nadao sam se da može i manje kompleksan projekat da se radi i da se osvoji manji broj poena, jer nemam ambicije za najviše ocene. Recimo da na projektu ja maksimalno mogu uzeti 25 poena ako odradim program koji sam opisao, a ne 35 kao ostali koji bi se ozbiljnije bavili računarskom inteligencijom, ili nešto slično kako se dogovorimo, jer je bilo reči i o tome na vežbama, ali očigledno ipak ne može :)

U svakom slučaju, hvala Vam na odgovoru, vidimo se na kolokvijumu :)