Forum » Programiranje » Flooding alghorithm (Matlab)
Flooding alghorithm (Matlab)
WhiteSmith ::
Pozdravljeni!
Na faksu imam pri nekem projektu nalogo napisati t.i. Flooding alghorithm program v Matlabu. V splošnem to pomeni, če imamo nek labirint in v en vogal zlijemo vodo ter sledimo enemu toku vode, pridemo iz začetne v končno točko po najkrajši poti. Za učne potrebe sem labirint izrisal sam. Ta labirint je narejen z matriko, kjer so -1 robovi, ostalo pa prazni prostori, kjer lahko teče voda. Do sedaj mi je uspelo skoraj že končati program, vendar se mi zatakne na koncu. V sliki namreč ne znam izrisati poti od začetne do končne točke. Zatorej naprošam vse tiste, ki ste vešči programiranja v Matlabu, če mi lahko pomagate pri dokončanju programa oz. mi posredujete ideje kako lahko izvedem izris poti na sliki. Prilagam seveda tudi program.
Hvala že vnaprej za ideje in lep pozdrav!
Na faksu imam pri nekem projektu nalogo napisati t.i. Flooding alghorithm program v Matlabu. V splošnem to pomeni, če imamo nek labirint in v en vogal zlijemo vodo ter sledimo enemu toku vode, pridemo iz začetne v končno točko po najkrajši poti. Za učne potrebe sem labirint izrisal sam. Ta labirint je narejen z matriko, kjer so -1 robovi, ostalo pa prazni prostori, kjer lahko teče voda. Do sedaj mi je uspelo skoraj že končati program, vendar se mi zatakne na koncu. V sliki namreč ne znam izrisati poti od začetne do končne točke. Zatorej naprošam vse tiste, ki ste vešči programiranja v Matlabu, če mi lahko pomagate pri dokončanju programa oz. mi posredujete ideje kako lahko izvedem izris poti na sliki. Prilagam seveda tudi program.
axis ij grid A=[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1;-1,0,-1,0,0,0,-1,-1,-1,-1;... -1,0,-1,0,-1,0,0,0,0,-1;-1,0,-1,-1,-1,0,-1,-1,0,-1;... -1,0,0,-0,-1,0,-1,0,0,-1;-1,-1,-1,0,-1,-1,-1,0,-1,-1;... -1,0,-1,0,0,-1,0,0,0,-1;-1,0,-1,-1,0,-1,-1,0,-1,-1;... -1,0,0,0,0,0,0,0,0,-1;-1,-1,-1,-1,-1,-1,-1,-1,-1,-1] rectangle('position',[0 0 10 1],'facecolor','b','edgecolor','b') rectangle('position',[0 9 10 1],'facecolor','b','edgecolor','b') rectangle('position',[0 1 1 9],'facecolor','b','edgecolor','b') rectangle('position',[9 1 1 9],'facecolor','b','edgecolor','b') rectangle('position',[2 1 1 3],'facecolor','b','edgecolor','b') rectangle('position',[4 2 1 4],'facecolor','b','edgecolor','b') rectangle('position',[2 5 1 3],'facecolor','b','edgecolor','b') rectangle('position',[5 5 1 3],'facecolor','b','edgecolor','b') rectangle('position',[6 1 4 1],'facecolor','b','edgecolor','b') rectangle('position',[6 3 1 3],'facecolor','b','edgecolor','b') rectangle('position',[1 5 1 1],'facecolor','b','edgecolor','b') rectangle('position',[3 3 1 1],'facecolor','b','edgecolor','b') rectangle('position',[3 7 1 1],'facecolor','b','edgecolor','b') rectangle('position',[6 7 1 1],'facecolor','b','edgecolor','b') rectangle('position',[7 3 1 1],'facecolor','b','edgecolor','b') rectangle('position',[8 5 1 1],'facecolor','b','edgecolor','b') rectangle('position',[8 7 1 1],'facecolor','b','edgecolor','b') X_start=input('Vnesi zacetno x koordinato:'); Y_start=input('Vnesi zacetno y koordinato:'); round(X_start) round(Y_start) if A(X_start,Y_start)==(-1) fprintf('\nVnesli ste neveljavno koordinato začetka! Začetek ne sme biti na robu labirinta.\n') X_start=input('Vnesi zacetno x koordinato:'); Y_start=input('Vnesi zacetno y koordinato:'); end X_finish=input('Vnesi koncno x koordinato:'); Y_finish=input('Vnesi koncno y koordinato:'); round(X_finish) round(Y_finish) if A(X_finish,Y_finish)==(-1) fprintf('\nVnesli ste neveljavno koordinato cilja! Začetek ne sme biti na robu labirinta.\n') X_finish=input('Vnesi zacetno x koordinato:'); Y_finish=input('Vnesi zacetno y koordinato:'); end if ((X_start<1)||(X_start>10))||((Y_start<1)||(Y_start>10))||((X_finish<1)||(X_finish>10))||((Y_finish<1)||(Y_finish>10)) fprintf('\nVnesli ste neveljavno koordinato začetka oz. cilja! Koordinata mora biti celo število med 1 in 10.\n') X_start=input('Vnesi zacetno x koordinato:'); Y_start=input('Vnesi zacetno y koordinato:'); X_finish=input('Vnesi zacetno x koordinato:'); Y_finish=input('Vnesi zacetno y koordinato:'); end if ((X_start==X_finish)&&(Y_start==Y_finish)) fprintf('Koordinati cilja ne smeta biti enaki koordinati začetka!') X_start=input('Vnesi zacetno x koordinato:'); Y_start=input('Vnesi zacetno y koordinato:'); X_finish=input('Vnesi zacetno x koordinato:'); Y_finish=input('Vnesi zacetno y koordinato:'); end rectangle('position',[Y_start-1 X_start-1 1 1],'curvature',[1,1],'facecolor','r','edgecolor','r') rectangle('position',[Y_finish-1 X_finish-1 1 1],'curvature',[1,1],'facecolor','black','edgecolor','black') if((A(X_start,Y_start-1))==0) A(X_start,(Y_start-1))=A(X_start,(Y_start-1))+1; end if((A(X_start,Y_start+1))==0) A(X_start,(Y_start+1))=A(X_start,(Y_start+1))+1; end if((A(X_start-1,Y_start))==0) A((X_start-1),Y_start)=A((X_start-1),Y_start)+1; end if((A(X_start+1,Y_start))==0) A((X_start+1),Y_start)=A((X_start+1),Y_start)+1; end A(X_start,Y_start)=1000; A(X_finish,Y_finish)=2000; for cifra=1:40; [i,j]=find(A==cifra); Z=numel(i); for ind = 1 : Z; X=i(ind); Y=j(ind); if((A(X,Y-1))==0) A(X,(Y-1))=A(X,(Y-1))+cifra+1; end if((A(X,Y+1))==0) A(X,(Y+1))=A(X,(Y+1))+cifra+1; end if((A(X-1,Y))==0) A((X-1),Y)=A((X-1),Y)+cifra+1; end if((A(X+1,Y))==0) A((X+1),Y)=A((X+1),Y)+cifra+1; end end if (A(X,Y)==2000); break; end end display('Konec poti')
Hvala že vnaprej za ideje in lep pozdrav!
ragezor ::
flooding ti zalije vse prostore do katerih lahko pride
je breadth first search
izvedes ga tako, da zacnes na eni tocki, recimo 4,3. potem gres gledat okrog te tocke(predpostavimo, da se voda lahko razliva samo gor, dol, levo desno in ne po diagonali)
najprej zalijes 4,3 (zapises 1 na to mesto v matriki)
preveris torej (5,3), (3,3), (4,4),(4,2), ce je kateri od teh prostorckov 0 ga dodas v seznam polj, ki jih moras obiskati.
ok, to smo zakljucili. vzames prvega iz seznama (najbolj levega), ga zalijes in spet gres okrog njega iskat polja, ki imajo zapisano 0. najdena polja dodas na konec seznama (na desno stran). potem spet vzames najbolj evega iz seznama in ponavljas zadevo, dokler tvoj seznam ni prazen.
ce hoces dobiti pot vensi moras shranjevati se dodatne informacije. namrec shraniti moras podatek da prides iz (4,3) v (5,3), (3,3), (4,4),(4,2). Torej za vsako izmed teh stirih, ce si kje odkril 0 in si jo dodal v seznam, si moras shraniti, da si do tega poja prisel iz polja (4,3). Potem ko prides do cilja, gres gedat iz katerega polja si prisel v cilj. Potem gres gledat iz katerega poja si prisel v to polje in vse za nazaj do zacetnega polja.
je breadth first search
izvedes ga tako, da zacnes na eni tocki, recimo 4,3. potem gres gledat okrog te tocke(predpostavimo, da se voda lahko razliva samo gor, dol, levo desno in ne po diagonali)
najprej zalijes 4,3 (zapises 1 na to mesto v matriki)
preveris torej (5,3), (3,3), (4,4),(4,2), ce je kateri od teh prostorckov 0 ga dodas v seznam polj, ki jih moras obiskati.
ok, to smo zakljucili. vzames prvega iz seznama (najbolj levega), ga zalijes in spet gres okrog njega iskat polja, ki imajo zapisano 0. najdena polja dodas na konec seznama (na desno stran). potem spet vzames najbolj evega iz seznama in ponavljas zadevo, dokler tvoj seznam ni prazen.
ce hoces dobiti pot vensi moras shranjevati se dodatne informacije. namrec shraniti moras podatek da prides iz (4,3) v (5,3), (3,3), (4,4),(4,2). Torej za vsako izmed teh stirih, ce si kje odkril 0 in si jo dodal v seznam, si moras shraniti, da si do tega poja prisel iz polja (4,3). Potem ko prides do cilja, gres gedat iz katerega polja si prisel v cilj. Potem gres gledat iz katerega poja si prisel v to polje in vse za nazaj do zacetnega polja.
WhiteSmith ::
Ok. Hvala za odgovor. Bom preštudiral tolo idejo. Upam, da mi jo uspe realizirat. Če pa ima še kdo kakšen nasvet pa naj ga posta.
LP
LP
Vredno ogleda ...
Tema | Ogledi | Zadnje sporočilo | |
---|---|---|---|
Tema | Ogledi | Zadnje sporočilo | |
» | Baza v vektorskem prostoruOddelek: Šola | 2646 (1144) | BivšiUser2 |
» | PythonOddelek: Programiranje | 3063 (1749) | d_DJ |
» | Matematika-problemOddelek: Šola | 1671 (1445) | Math Freak |
» | [C++/OpenGL] Collision detectionOddelek: Programiranje | 911 (679) | Senitel |
» | Aproksimacija krogaOddelek: Šola | 2249 (1868) | whatever |