» »

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.

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.

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


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Baza v vektorskem prostoru

Oddelek: Šola
182646 (1144) BivšiUser2
»

Python

Oddelek: Programiranje
203063 (1749) d_DJ
»

Matematika-problem

Oddelek: Šola
81671 (1445) Math Freak
»

[C++/OpenGL] Collision detection

Oddelek: Programiranje
7911 (679) Senitel
»

Aproksimacija kroga

Oddelek: Šola
92249 (1868) whatever

Več podobnih tem