CATEGORII DOCUMENTE
Afaceri Calculatoare Casa masina Didactica pedagogie Diverse Educatie Finante Geografie Istorie & politica Legislatie Limba Management Sanatate Tehnologie

Access	Adobe photoshop	Algoritmi	Autocad	Baze de date	C	C sharp
Calculatoare	Corel draw	Dot net	Excel	Fox pro	Frontpage	Hardware
Html	Internet	Java	Linux	Matlab	Ms dos	Pascal
Php	Power point	Retele calculatoare	Sql	Tutorials	Webdesign	Windows
Word	Xml

Prezentarea aplicatiei Tom & Jerry

algoritmi

+ Font mai mare | - Font mai mic

DOCUMENTE SIMILARE

Constructia si simularea executiei unui program (in limbaj de asamblare)

Liste - Arbori

Structuri de date

Mod de abordare al algoritmilor euristici in Inteligenta Artificiala

Introducere in ModelSIM

Limbaje de programare: Cobol, Pascal

Sistem informational - Sistem informatic

METODE DE SORTARE

SCHEMELE LOGICE - Structuri fundamentale ale algoritmilor

ALGORITMUL HOOKE-JEEVES

Prezentarea aplicatiei

Tom & Jerry

Aceasta aplicatie implementeaza algoritmul de cautare A*. Jocul consta intr-o tabla de dimensiuni 15X15 (sau 6X6) pe care pisica Tom trebuie sa gaseasca drumul minim printre obstacole pentru a-l prinde pe soricelul Jerry.

Programul utilizeaza o structura Baza care contine punctul de start, punctul de oprire si un buton care este 1 daca s-a apasat start, 2 daca s-a apasat stop, 3 daca s-a apasat obstacol si 0 in rest.

public struct Baza

O alta structura folosita este Celula care detine coordonatele celulei, tipul celulei (este 1 daca este punct de start, 2 daca este punct de oprire, 3 daca este obstacol si 0 altfel), valorile g, h, f, folosite in calcularea costului minim al drumului in algoritmul A* descrise mai tarziu, si coordonatele celulei parinte.

public struct Celula

In continuare vom lucra cu matricea considerata harta jocului pe care o vom borda astfel incat prima si ultima linie, si prima si ultima coloana sa contina intotdeauna obstacole. In acest fel daca NrLiniiMax si NrColMax sunt egale cu 17 in joc vor fi puse doar 15.

public operareHarta(int dim)

else

nrCel=nrLiniiMax*nrColMax;

mat = new Celula[nrLiniiMax,nrColMax];

for(int i=0;i<nrLiniiMax;i++)

mat[i,j].c.X=i;

mat[i,j].c.Y=j;

}

Jocul va avea optiunea de a genera o harta aleatoare iar acest lucru este implementat prin urmatoarele functii :

public void InitRandStart() //genereaza un punct de start aleator

public void HartaRadom(int procent)//genereaza o harta aleatoare

//fixam startul

x=r.Next(nrLiniiMax-2)+1;

y=r.Next(nrColMax-2)+1;

mat[x,y].tip=1;

//fixam stopul

int ok=1;

while(ok!=0)

}

Dupa afisarea unui drum gasit de program, harta va trebui curatata, reinitializata, si acest lucru se face cu ajutorul functiei CurataHarta.

public void CurataHarta()

}

Prin functiile GasesteStart si GasesteStop se face localizarea pe harta a punctelor de plecare respectiv oprire pe harta.

public Point GasesteStart()

}

return pct;

}

public Point GasesteStop()

}

return pct;

}

In continuare vom implementa operatiile asupra listelor openl si closel adica listele folosite de algoritmul A pentru a pastra nodurile care mai pot fi luate in considerare si nodurile care nu mai pot fi explorate.

public void InitializareLista(Celula []lista)

}

public int AdaugaInLista(Celula pct,Celula []lista)

public void StergeDinLista(Celula pct, Celula []lista)

lista[i-1].c.X=0;

lista[i-1].c.Y=0;

}

public int GasesteInLista(Celula pct, Celula []lista)

return -1;

}

public int LengthList(Celula []lista)

}

return i-1; //prima pozitie libera

}

Stim ca algoritmul A de cautare a drumului minim va alege in drum nodul adiacent celulei curente care va avea cel mai mic cost F. Acest cost F se calculeaza prin formula: F=G+H.

G este costul mutarii de la start la celula curenta urmand drumul generat pana atunci. Pentru calculul lui G asignam costul 10 la mutarea pe vertical sau orizontal si 14 la mutarea pe diagonala.

H este costul estimat al mutarii de la celula curenta la punctul de stop. Pentru calculul lui H se calculeaza numarul total de celule pe oriyontala si pe verticala, ignorand diagonalele, de la celula curenta la punctul de oprire si apoi se inmulteste cu costul stabilit pentru parcurgerea pe orizontal sau vertical adica 10. Aceasta metoda este cunoscuta sub numele de metoda Manhattan.

public int CalculG(Celula curent,Celula nou)

else

return curent.g+14;

}

public int CalculH(Celula start, Celula stop)

public int CalculF(Celula pct)

public int minimF(Celula []lista,int lung)

}

return poz;

}

In continuare ne ocupam de interfata grafica a programului. Punctul de start va fi simbolizat de poya pisicii Tom, punctul de oprire de soricelul Jerry, iar obstacolele in drumul lui Tom vor fi sibolizate de un caine. Pe drumul gasit de algoritm va aparea poza lui Tom alergand iar atingerea punctului de oprire va fi simbolizata de poza in care Tom prinde soricelul. Pentru o harta cu dimensiuni 15 X 15 vom folosi pozele "tom1.png" , "jerry1.png" , "dog1.png" , "tomrun1.png" , "catch1.png" iar pe o harta cu dimensiuni 6 X 6 se vor folosi "tom2.png" , "jerry2.png" , "dog2.png" , "tomrun2.png" , "catch2.png".

private Bitmap bitwall = new Bitmap('dog1.png');

private Bitmap bitstart = new Bitmap('tom1.png');

private Bitmap bitstop = new Bitmap('jerry1.png');

private Bitmap path = new Bitmap('tomrun1.png');

private Bitmap end = new Bitmap('catch1.png');

private Bitmap bitwall1 = new Bitmap('dog2.png');

private Bitmap bitstart1 = new Bitmap('tom2.png');

private Bitmap bitstop1 = new Bitmap('jerry2.png');

private Bitmap path1 = new Bitmap('tomrun2.png');

private Bitmap end1 = new Bitmap('catch2.png');

private int dim;

private unu.Baza info;

private unu.operareHarta hartaMea;

private unu.Celula []drum;

private int gata;

Se stabilesc butoanele pentru optiuni de genul harta aleatoare sau harta creata de utilizator, butonul pentru crearea drmului dupa stabilirea punctului de start, stop, si a obstacolelor.

public MainForm()

private void StartButon_Click(object sender, System.EventArgs e)

private void StopButon_Click(object sender, System.EventArgs e)

private void ObstacleButon_Click(object sender, System.EventArgs e)

Se realizeaza desenarea hartii si asezarea imaginilor pe harta.

private void desenareHarta(Graphics g)/*aseaza imaginile pe harta*/

if(hartaMea.mat[i,j].tip==2)

if(hartaMea.mat[i,j].tip==1)

}

else

if(hartaMea.mat[i,j].tip==2)

if(hartaMea.mat[i,j].tip==1)

}

Trecem la algoritmul A* propriu zis. Pentru inceput initializam listele openl si closel si nodul de start o sa fie introdus in lista openl. In continuare pentru fiecare celula repetam urmatorii pasi:

pentru fiecare din cei 8 vecini ai celulei ( dreapta, dreapta sus, dreapta jos, stanga, stanga sus, stanga jos, sus si jos ) procedam in felul urmator: daca celula nu face parte din lista closel sau nu este impracticabila (adica nu exista obstacol in acea celula - tipul ei nu este 3) se adauga in openl si se calculeaza costul F=G+H. Daca exista deja in openl atunci se verifica daca nu cumva vom avea cost G mai bun pentru acesta celula pe noua cale. Se alege pentru a continua drumul nodul cu costul F cel mai mic, se scoate din openl si se trece in closel.

Cautarea se opreste atunci cand celula de sfarsit va fi adaugata la lista closel, caz in care drumul a fost gasit si se va desena, sau atunci cand lista openl e goala (nu mai exista noduri de explorat) si inca nu s-a gasit punctul de sfarsit, iar programul va semnala acest lucru prin mesajul: "drum imposibil".

private int Algoritm()/*algoritmul A* */

stop.c=hartaMea.GasesteStop();

if((stop.c.X==0)&&(stop.c.Y==0))

start.g=0;

start.h=0;

start.f=0;

hartaMea.InitializareLista(openl);

hartaMea.InitializareLista(closel);

hartaMea.AdaugaInLista(start,openl);

else

}

//pentru vecin dreapta sus

vf=hartaMea.mat[curent.c.X+1,curent.c.Y-1];