ALGORITMI DE GENERARE ȘI REZOLVARE AUTOMATĂ A LABIRINTURILOR Coordonator : Conf.dr. NĂDĂBAN SORIN Absolvent: BUCUR EDUARD ARA D, 2013 REFERAT privind… [601671]

UNIVERSITATEA “AUREL VLAICU” ARAD
FACULTATEA DE Ș TIIN ȚE EXACTE
SPECIALIZAREA INFORMATICĂ

LUCRARE DE LICENȚĂ

Coordonator :
Conf.dr. NĂDĂBAN SORIN

Absolvent: [anonimizat], 2013

UNIVERSITATEA “AUREL VLAICU” ARAD
FACULTATEA DE ȘTIINȚE EXACT E
SPECIALIZAREA INFORMATICĂ

LUCRARE DE LICENȚĂ

ALGORITMI DE GENERARE ȘI REZOLVARE
AUTOMATĂ A LABIRINTURILOR

Coordonator :
Conf.dr. NĂDĂBAN SORIN

Absolvent: [anonimizat], 2013

REFERAT
privind lucrarea de licență cu titlul
„ALGORITMI DE GENERARE ȘI REZOLVARE
AUTOMATĂ A LABIRINTURILOR ”
întocmită de absolvent: [anonimizat], prin prezentul referat recomand Lucrarea
de Licență a absolvent: [anonimizat] 2013 .
Lucrarea de Licență cu titlul „ ALGORITMI DE GENERARE ȘI REZOLVARE
AUTOMATĂ A LABIRINTURILOR ” se referă la o problema întotdeauna de actualitate, și
de utilitate practică. Conținutul lucrării dovedește că absolvent: [anonimizat], îl
abordează cu pro fesionalism și stăpânește cunoștințele necesare legate de subiectul tratat,
implementarea algoritmilor și realizarea interfețelor grafice în Java.
Lucrarea este organizată în 3 capitole, însoțite de introducere și bibliografie:
Capitolul I – Noțiuni teore tice legate de labirinturi
Capitolul II – Proiectarea aplicației
Capitolul III – Utilizarea aplicației
Din punct de vedere al conținutului și prezentării, lucrarea întrunește toate condițiile
cerute de o lucrare de licență la specialitatea Informatică în c adrul Facultății de Științe Exacte.
Având în vedere cele de mai sus, recomand susținerea publica a Lucrării de Licență cu
titlul „ ALGORITMI DE GENERARE ȘI REZOLVARE AUTOMATĂ A
LABIRINTURILOR ” întocmită de absolvent: [anonimizat] 2013
și propun acordarea notei …..

Conf.dr. SORIN NĂDĂBAN

Arad 10.06.20 13

CUPRINS
Introducere ………………………….. ………………………….. ………………………….. ………………………….. .. 6
Capitolul 1. Noțiuni teoretice legat e de labirinturi ………………………….. ………………………….. ….. 7
1.1 Clasificarea labirinturilor ………………………….. ………………………….. ………………………….. .. 7
1.2 Principii generale cu privire la generarea labirinturilor ………………………….. ……………… 15
1.3 Algoritmi de generare a labirinturilor perfecte ………………………….. …………………………. 17
1.3.2 Algoritmul de generare prin căutare în adâncime (DFS) ………………………….. …….. 17
1.3.3 Algoritm de generare folosind Revenirea recursivă (Recursive backtracker) ……… 18
1.3.4 Algoritmul randomizat a lui Kruskal ………………………….. ………………………….. ……. 18
1.3.5 Algoritmul randomizat al lui Prim ………………………….. ………………………….. ………. 19
1.3.6 Versiunea modificata a algoritmului lui Prim ………………………….. ……………………. 19
1.3.7 Metoda de divizare recursiv ă ………………………….. ………………………….. ………………. 20
1.3.8 Algoritmul lui Wilson ………………………….. ………………………….. ………………………… 20
1.3.9 Algoritmul “Vânează și omoară” ………………………….. ………………………….. ………… 21
1.3.10 Algoritmul lui Eller ………………………….. ………………………….. …………………………. 21
1.3.11 Algoritm care nu se bazează pe celule ………………………….. ………………………….. … 21
1.4 Algoritmi de rezolvare a labirint urilor ………………………….. ………………………….. ………… 23
1.4.1 Algoritmul aleator al șoarecelui ………………………….. ………………………….. ………….. 23
1.4.2 Urmărirea pereților ………………………….. ………………………….. ………………………….. .. 23
1.4.2 Algoritmul lui Pledge ………………………….. ………………………….. ………………………… 24
1.4.3 Algoritmul lui Tremaux ………………………….. ………………………….. ……………………… 24
1.4.4 Umplerea capetelor de drum ………………………….. ………………………….. ……………….. 25

1.4.5 Algoritmul “Cel mai scurt drum” ………………………….. ………………………….. ………… 25
1.5 Al te operații asupra labirinturilor ………………………….. ………………………….. ………………. 27
Capitolul 2. Proiectarea aplicației ………………………….. ………………………….. ……………………….. 29
2.1 Alegerea limbajului de programare – Java ………………………….. ………………………….. …… 29
2.2 Interfața grafică cu utilizatorul ………………………….. ………………………….. ………………….. 34
2.3 Applet -uri ………………………….. ………………………….. ………………………….. ………………….. 45
2.4 Clase le folosite în aplicație ………………………….. ………………………….. ……………………….. 49
Capitolul 3. Utilizarea aplicației ………………………….. ………………………….. …………………………. 60
Bibliografie ………………………….. ………………………….. ………………………….. …………………………. 65

6
Introducere

Labirintul a fascinat dintotdeauna, fie că a fost perceput ca un element decorativ, ca
mit al căutării, ca simbol al perfecțiunii sau dimpotrivă al rătăcirii. Hocke spunea că labirintul
este “o metaforă unificatoare pentru c eea ce este calculabil și incal culabil în lume. Drumul
ocolit duce spre centru. Numai drumul ocolit duce spre perfecțiune”.
Intrat în conștiința lumii moderne îndeosebi prin mitul Minotaurului, al eroului Tezeu
și al firului Ariadnei, labirintul este un arhetip prezent în vechi civiliza ții răspândite pe
aproape întreg globul. În Vechiul Egipt se întâlnesc mărturii despre simbolul labirintului încă
din scrierile istoricilor antici, unul dintre cele mai vechi și cele mai cunoscute fiind labirintul
construit de faraonul Amenhotep III despre a cărui grandoare Herodot scria că eclipsa
piramidele de la Giza ; alte mărturii despre labirint uri, în alte zone geografice, sunt cele grafice
de la Val Camonica, Old Bewyck, Brindisi, Wisby, Pena de Mayor, Cremona, Nazca, Wier.
Labirinturile există în re alitate , dar și în alte forme, cum ar fi desenate sau reprezentate
cu ajutorul calculatorului. La fel, rolurile labirinturilor pot fi multiple : pot fi simple elemente
decorative, pot fi utilizate în diverse moduri pentru divertisment, pot avea conotații fi losofice,
cât și utilități practice cum ar fi diverse experimente care să evidențieze capacitatea de
memorare și de învățare a unui subiect.
Formele labirinturilor sunt foarte diverse, putând fi clasificate după o multitudine de
criterii, după cum se va ve dea și în prezenta lucrare în prima secțiune a capitolului 1.
După cum era de așteptat, știința s -a implicat și ea de -a lungul timpului rezultând
diverși algoritmi pentru generarea și soluționarea labirinturilor, parte din ei fiind descriși în
prezenta luc rare, începând cu secțiunea a doua a capitolului 1.
În capitolul al doilea se prezintă instrumentele și modul în care am proiectat o aplicație
de generare (folosind diverși algoritmi) și soluționare a labirinturilor perfecte, în plan.
Cel de -a treilea cap itol prezintă modul de utilizare a aplicației.

7
Capitolul 1. Noțiuni teoretice legate de labirinturi

1.1 Clasificarea labirinturilor

Labirinturile în general ( și algoritmii folosi ți în crearea acestora) pot fi organizate în
cel puțin sapte clasific ări diferite. Acestea sunt: dimensiunea, hiperdimensiunea, topologia,
modelul, rutarea , textura și focus ul. Un labirint poate lua câte un element din fiecare dintre
clasele enumerate, în orice combinație.

 Dimensiunea : clasa dimensiune înseamnă în principiu cât e dimensiuni ocupă un labirint.
Tipurile posibile sunt:
2D: Cele mai multe labirinturi, fie desenate pe diverse suporturi sau în mărime
naturală , sunt de această dimensiune.
3D: Un labirint în trei dimensiuni este unul cu mai multe nivel e, în care (în cazul
ortogonal cel puțin) pasajele pot merge în sus și în jos corespunzător punctelor
cardinale. Un labirint 3D este adesea afișat ca o serie de nivele 2D, unite prin
indicatori de tip “sus” și “jos”.
Dimensiuni superioare : Este posibil să existe și labirinturi 4D sau de dimensiuni
superioare. Acestea sunt cel mai adesea reprezent ate ca 3D labirinturi, cu “portaluri”
speciale pentru a putea călători prin a patra dimensiune, de exemplu portaluri “trecut”
și “viitor”.
Val: un labirint val (weave) este un labirint 2D (sau mai exact 2.5D), dar unde
pasajele se pot întretăia. În afișare este evident care este un capăt de drum și care este
un pasaj care merge sub un alt pasaj. Labirinturile reale care au poduri de legătură
dintr -o parte a labirintului de alta sunt parțial labirinturi val.

8
 Hiperdimensiunea : clasa hiperdimensiune se referă la dimensiunea obiectului ce se va
deplasa prin labirint, spre deosebire de dimensiunea labirintului în sine.
Tipurile posibile sunt:
Non-hyper labirinturi : Cam toate labirinturile, chiar și cele de dimensiuni superioare
sau cu reguli speciale sunt non-hyperlabirinturi. În ele se lucrează cu un punct sau un
obiect mic care se mută dintr -un punct în altul al labirintului formând în urma sa o
linie.
Hyper labirint : Un hyperlabirint este cazul în care obiectul cu care se rezolvă
labirintul este mai mult decât doar un punct. Un hyperlabirint standard (numit și
hyperlabirint de ordinul intâi) constă într-o linie care pe cum este mutată, în spatele ei
se formează o suprafață. Un hyperlabirint poate exista doar într -o dimensiune 3D sau
mai mare, unde intrarea în hyperlabirint este, de asemenea, o linie în loc de un punct.

Hyperhy per labirinturi: Hyperlabirinturile pot avea o dimensiune arbitrară mare. Un
hyperhyper labirint (numit și hyperlabirint de ordinul doi) crește dimensiunea
obiectului folosit la rezolvarea labirintului. Aici obiectul este un plan, care după ce
este mutat formeaza în spatele său o urmă solidă. Un hyperhyper labirint poate exista
doar într-o dimensiune 4D sau mai mare.

 Topologia: clasa topologie descrie geometria spațiului în care există labirintul.
Tipurile posibile sunt:
Normal : Acesta este un labirint standard în spațiul euclidian.
Planair : Termenul “plana ir” se referă la orice labirint cu o topologie anormală . Acest
lucru înseam nă, de obicei, conectarea muchiilor labirint în moduri

9
interesante. Exemple sunt: labirinturi pe suprafața unui cub, labirinturi pe suprafața
unei benzi Moebius, etc.

 Modelul: clasa model (tessellation) reprezintă geometria celulelor individuale care
compun labirintul.
Tipurile posibile sunt:
Ortogonală : Aceasta reprezintă o grilă standard dreptunghiulară în care celulele s-au
pasajele se intersectează în unghi drept.
Delta : Un Delta labirint este compus din triunghiuri conectate între ele și unde fiecare
celula poate avea până la trei pasaje conectate la ea.

Labirint de tip Delta Labirint de tip Sigma

10

Sigma : Un Sigma labirint este compus din hexagoane conectate între ele și unde
fiecare celulă poate avea până la șase pasaje conectate la ea.
Theta : Theta labirinturile sunt compuse din cercuri concentrice de pasaje și unde
începutul sau sfârșit ul este în centru, iar celălalt pe marginea exterioară. Celulele au
deobicei patru pasaje conectate la ele, dar pot avea și mai multe datorită numărului
mai mare de celule din inelele exterioare.
Labirint de tip Theta

Upsilon : Upsilon labirinturiturile sunt compuse din octagoane și patrate conectate
între ele și unde fieca re celul ă poate avea până la opt sau patru pasaje conectate la ea.
Zeta : Un Zeta labirint este pe o grilă dreptunghiulară, care conține în plus pasaje la
un unghi de de 45 de grade intre celule, pe lângă cele orizontale și verticale.
Labirint de tip Zeta

11

Omega : Termenul “Omega” se referă la cele mai multe orice labirint cu un model
non-ortogonal. Astfel, labirinturile de tip Delta, Sigma și Theta sunt toate de acest tip,
plus multe alte aranjamente la care ne putem gândi.
Crack : un labirint de tip crack este un labirint cu o formă amorfă, cu pereți sau pasaje
la unghiuri aleatoare.
Labirint de tip Crack

Fractal : un labirint de tip fractal este un labirint format din labirinturi mai mici. Un
labirint fractal recursiv infinit este un fractal adevărat, caz în care labirintul conține
copii ale lui însuși.
 Rutare a: clasa rutare este probabil cel mai interesant ă cu privire la generarea
labirinturilor. Aceasta se referă la tipurile de pasaje din orice geometrie definită în
categoriile de mai sus.
Perfect : Un labirint “perfect” înseamnă un labirint fără bucle sau circuite închise, și
fără nici o zona inaccesibil ă. Acest tip de labirint se mai numește și simplu conex. Din
orice punct, există exact un singur drum până la orice alt punct. Deasemenea,
labirintul are exact o soluție.
Panglică : Un labirint “panglic ă” înseamnă un labirint fără nici un punct mort. Un
astfel de labirint foloseste pasaje se înfășoară unul în jurul altuia și apoi se reîntâlnesc.
Un labirint panglic ă bine facut poate fi mult mai dificil decât un labirint perfect de
aceeași dimensiune.
Unicursal : un labirint unicursal înseamnă un labirint fără joncțiuni (intersecții). Un
labirint unicursal are doar un pasaj asemănător unui șarpe care se înfășoară de -a lungul
labirintului. Acest tip de labirint nu este foarte dificil, atât că la o întoarcere greșită se
poate ajung e înapoi la început, în loc de a merge spre sfârșit.

12
Labirint unicursal

Risipit (sparse) : acest tip de labirint nu își i construie ște drum prin fiecare celulă,
unele fiind lăsate necreate. Acest lucru duce la existența unor locații inaccesibile, ceea
ce face acest tip de labirint oarecum inversul labirintului de tip panglica.
Panglic ă parțială: Un labirint de tip panglic ă parțială este un labirint care conține atât
bucle cât și puncte moart e. Cuvântul “panglică ” pot fi utilizat cantitativ, astfel că un
”labirint puternic panglic ă“ înseamnă un labirint cu multe bucle sau pereți detașați, În
contrast cu un ”labirint slab panglic ă“.

 Textura: clasa textur ă este una subtilă și descrie stilul pasajelor în orice tip de rutare și în
orice geometrie. Ei nu caracterizează foarte precis un tip de labirint ci sunt mai mult un fel
de teme generale.
Iată niște exemple:
Predilecție : un labirint predilect este unul cu linii drepte care tind să meargă într-o
direcție mai mult decât altele. De exemplu, un labirint cu o predilecție orizontală vor
avea pasaje stânga -dreapta lungi și pasaje scurte sus-jos care sa le conecteze.
Cursa (Run): Efectul “cursă” al unui labirint înseamnă cât de lungi sunt liniile drepte
până când apar cotituri. Un labirint cu o cursă scăzuta nu va avea pasaje drepte decât
pentru trei sau patru celule, și va avea un aspect foarte aleator. Un labirint cu cursă
ridicată va avea pasaje lungi o mare parte din labirint.

13
Labirint de tip ”run”

Elita : Acesta este un factor care indică lungimea soluției comparativ cu dimensiunea
labirintului. Un labirint “elitist” are î n general o soluție scurt ă, cât mai directă, în timp
ce un labirint “non -elitist” are o soluție care se întinde pe o bună parte a labirintului.
Totuși, u n labirint “elitist” bine conceput poate fi mult mai greu decât unul “non –
elitist”.
Simetric : un labirint simetric are pasaje simetrice, de exemplu, în sens simetric în
jurul mijlocul ui, sau relativ la axa verticală sau orizontal ă. Un labirint poate fi parțial
sau total simetric și poate repet a un model de un număr de ori.
 Focus: clasa “focus” este puțin obscură, dar arată că, crearea labirinturilor poate fi
împărțită în două tipuri generale: adăugări de pereți și creare de pasaje. Adesea, același
labirint poate fi generat în ambele moduri:
Adăugări de pereți : Acest tip de a lgoritmi care se concentrează pe pereți încep cu o
zonă goală (sau o margine exterioară) și adaugă pereți. În cazul unui labirint real,
compus din garduri vii sau pereți din lemn, acesta este considerat a fi creat prin acest
tip de algoritmi.
Crearea de pasaje : algoritmii care se concentrează pe pasajele încep cu un bloc solid
și începe să creeze pasaje. În viața reală, un labirint compus din tuneluri sau conducte
este considerat a fi creat prin acest tip de algoritmi.
Șablon : Un șablon de labirint se referă la un grafic general care nu este un labirint,
care este apoi modificat pentru a deveni un labirint valabil din cât mai puțini pași
posibil, dar încă mai are textura șablonului graficului inițial. Labirinturile mai
complexe cum ar fi cele în spirala sunt mai ușor de creat pe calculator cu sabloane.

14
Labirint creat după șabloane

Alte clase și tipuri de labirinturi:
Direcț ia : Aceasta este în cazul labirinturilor în care anumite pasaje pot fi parcurse
într-o singură direcție.
Labirinturi de lungime infinită : Este posibil pe ntru a crea labirint infinit de lung (de
exemplu un număr finit de coloane, dar oricâte rânduri), prin menținerea doar a unei
părți din labirint în memorie la un moment dat. Algoritmi de generare a labirinturilor
infinite este cel al lui Hunt și Kill sau cel al lui Eller.

15
1.2 Principii generale cu privire la generarea labirinturilor
Noțiuni din teoria grafurilor
Un labirint poate să fie generat pornind cu o aranjare predeterminată de celule (cel mai
obișnuit grilă dreptunghiulară, dar și alte aranjări sunt posibile) cu pereți între celule. Această
aranjare predeterminată poate să fi considerată ca fiind un graf conex cu muchiile
reprezentând posibilii pereți și nodurile reprezentând celulele. Scopul algoritmului de
generare a labirintului din acest punc t de vedere poate fi considerat ca fiind generarea unui
subgraf în care se dorește găsirea unui drum între două noduri date.
Dacă subgraful nu este conex, atunci există regiuni ale grafului care sunt irosite din
cauză că acele regiuni nu contribuie la spa țiul de căutare. În cazul în care graful conține
cicluri, atunci pot exista mai multe drumuri între nodurile alese. Din acest motiv, generarea de
labirinturi este adesea abordată ca fiind generarea unui arbore parțial. Cicluri care pot să
deruteze „solvere ” naive a labirinturilor pot fi introduse prin adăugarea de muchii aleatoare la
rezultat pe parcursul derulării algoritmului.

Cerințe pentru generarea diverselor tipuri de labirinturi
Perfect : Crearea unei labirint perfect standard implică “creșterea” labirintului ,
asigurând u-se că sunt îndeplinite restricțiile de a nu exista bucle și zone izolate. Se începe cu
un perete exterior și se adaugă aleator un perete. Se continuă adăuga re de pereți aleatori în
labirin t, dar se asigură că fiecare nou perete atinge la un capăt un perete deja existent, iar
celălalt capăt este într -o zonă încă negenerată a labirintului . Dacă s-ar adăuga un perete care
are ambele capete erau separate de restul labi rintului, acesta ar fi un perete izolat cu o buclă în
jurul lui și dacă s-ar adăuga un perete care atinge labirintul pe la ambele capete atunci s-ar
obține o zonă inaccesibilă. Aceasta este metoda de adăugarea a unui perete, un mod aproape
identic care fac e acest lucru este pasajul sculptat, în cazul în care trece rea noii secțiuni este
sculptată astfel încât cap ătul terminal atinge exact un pasaj existent. În mod similar se poate
crea un labirint perfect prin crearea de pasaje, având grijă ca un pasaj nou s ă atingă la un capăt
un pasaj deja existent.
Panglic ă : Pentru a crea un labirint de tip panglică fără puncte moarte, în principal se
adaugă aleator segmente de perete în labirint, dar asigură că fiecare segment nou adăugat nu
va provoca un punct mort .

16

Unicursal : O modalitate de a crea un labirint unicursal aleatoar este de a lua un
labirint perfect, se elimină ieșirea astfel încât să rămână doar intrarea liber ă, apoi se adaugă
pereți divizând în două fiecare pasaj. Aceasta va transforma fiecare punct mort într -un pasaj în
formă de U, iar la final va exista un pasaj unicursal care începe și se termină în punctul
deintrare în labirint și va descrie același drum ca și algoritmul de urmărir e a pereților .
Labirint ul unicursal va avea de două ori dimensiunea labirintului perfect original.
Risipit : Labirinturile “risipite” se generează respectând regula de a lăsa spații goale în
unele locații ale labirintului . Un mod de a face asta este ca atu nci când se ajunge la o nouă
celulă, să se verifice celulele aflate într -un semicerc de rază stabilită în fața direcției actuale .
Dacă vreuna din celulele din acea zonă este deja parte a labirintului, celula curentă nu va fi
generată, urmănd ca ea să facă parte din zona neocupată a labirintului.
3D: Labirinturile 3D sau de dimensiuni mai mari pot fi create la fel ca un labirint 2D
perfect standard, cu excepția ca de la fiecare celulă se poate trece la întâmplare la șase în loc
de patru alte celule or togonale. Aceste labirinturi sunt în general create cu algoritmi de tip
creare de pasaje .
Val: Generarea l abirinturil or de tip “val” se aseamănă cu labirinturil e perfecte
generate prin creare de pasaje , cu diferența că atunci câ nd un nou pasaj întâlnește un pasaj
deja existent poate să treacă pe sub el , astfel că nu se intersectează.
Crack : Labirinturile de tip “c rack” seamănă cu modul de generare a labirint urilor
perfec te prin adăugare de pereți , cu diferența că de data aceasta nu există modele prestabilite
ale celulelor decât locații aleatoare de pixeli . Un nou perete se crează prin alegerea unui pixel
care face parte de ja dintr -un perete și a unui al doilea pixel aleator dintr -o zonă încă
neocupată, după care se încearcă trasarea unui perete între cele două puncte, avănd grijă însă
ca noul perete să nu intersecteze un perete deja existent, deoarece aceasta ar putea duce la
apariția unei zone izolate.
Planair : Labirinturile de tip „p lanair ” care au o topologie neobișnuit ă, sunt în general
create dintr -o serie de mai multe labirint uri mai mici sau secți uni de labirint , fiind definit
modul în care se conecte ază muchiile între ele . De exemplu u n labirint de pe suprafața unui
cub are șase secțiuni pătrate de labirint , astfel că atunci când partea care se crează ajunge la o
margine a cubului va trece apoi î ntr-o altă secțiune .

17
1.3 Algoritmi de generare a labirinturilor perfecte

1.3.2 Algoritmul de generare prin căutare în adâncime (DFS)
Acest al goritm este o versiune randomizată a algoritmului de căutare în adâncime
(DFS) . Frecvent implementat cu ajutoru l unei stive, această abordare este una dintre cele mai
simple moda lități de generare a unui labirint cu ajutorul calculator ului.
Considerând s pațiu l pentru un labirint ca fiind o grilă de celule (cum ar fi o tabl ă mare
de șah ), fiecare celul ă încep ând cu patru pereți. Pornind de la o celulă oarecare , computerul
selectează apoi o celulă vecină aleatore care încă nu a fost vizitat ă. Calculatorul elimină
“peretele ” dintre cele două celule și adaug ă o nouă celul ă la stiv ă (aceasta este similar cu
trasarea un ei linii pe p lanșă). Procesul continu ă până când se ajunge la o celul ă care nu are
vecini nevizita ți, iar acest lucru este considerat punct mort . Într-o astfel de situație , algoritmul
se întoarce pe drumul parcurs până găsește o celul ă cu vecini nevizita ți, continu ând cu vecinii
nevizitați ai celulei respective ( creând un nou pasaj ). Acest proces continu ă până când toate
celulele au fost vizitate, făcând algoritmul să se î ntoarc ă până la celula inițială . Această
abordare garanteaz ă că labirintul este în î ntregime parcurs . Acest algoritm este foarte simplu
și nu generează labirinturi foarte complexe. Mai multe criterii adăugate acestui algoritm pot
contribui însă la generarea unor labirinturi care sunt mai greu de rezlovat.
Pașii algoritmului:
1. Se pornește de la o celulă aleatore care va fi numită „ ieșire”.
2. Se marchează celula ca vizitată și se obține lista vecinilor săi. Pentru fiecare vecin,
începâ nd cu un vecin ales aleator :
– Dacă acel vecin nu a fost vizitat, se elimină peretele dintre celulă și veci n și
se continuă algoritmul setând vecinul ca fiind celula curentă.
– Dacă celula nu mai are vecini nevizitați, se va merge înapoi până la o celulă
care mai are vecini nevizitați.
Algoritmul prezentat mai sus implic ă recursivitate a și poate cauza probleme de
suprasolicitate a stivei pe anumite arhitecturi de calculatoare. Algoritmul poate fi rearanjat
într-un ciclu stocâ nd informa ția de revenire direct î n labirint ; acest mod de lucru fiind și o
modalitate de generare a soluțiilor, se poate începe de la oric are celulă, iar apoi se merge din
celulă în celulă până la ieșire.

18
Labirinturile generate cu ajutorul algoritmul ui de căutare în adân cime au un număr
scăzut de coridoare și foarte lungi, dar care face din acesta un foarte bun algoritm de generare
a labirin turilor î n jocurile video. Eliminarea î n mod aleator a unui număr de pereți, după
crearea un ui labirint de tip DFS poate face coridoarele sale mai puțin înguste, lucru ce poate fi
potrivit în situațiile în care dificultatea de a rezolva labirintul nu este importantă. Acestă
caracteristică poate fi favorabilă î n jocurile video.
În labirinturi generate de acest tip de algoritm, va fi relativ ușor să se găsească drumul
spre celula care a fost aleasă la începutul algoritmului, deoarece multe drumuri conduc de l a
sau la ac ea celulă lucru, dar este foarte greu de găsit calea spre ieșire.

1.3.3 Algoritm de generare folosind Revenirea recursivă (Recursive backtracker)
Algoritmul de generare a unui labirint prin căutare în adâncime (DFS) este adesea
implementat folo sind metoda Backtracking urmând pașii:
1. Marcheaz ă o celul ă ca fiind “Vizitată”
2. Dacă curenta celula are vecini care nu au fost vizitati
 Alege aleator unul din vecini nevizita ți
 Adaug ă celula curentă la stivă
 Șterge peretele dintre celula curentă și celula vecină aleas ă
 Seteaz ă celula aleas ă ca fiind celula curent ă
3. Altfel
 Șterge ultima celul ă din stiv ă
 Întoarce re la execu ția anterioară a funcției

1.3.4 Algoritmul randomizat a lui Kruskal
Algoritmul prezentat este o varianta simpl ă randomizată a algoritmului lui Kruskal ,
utilizând următorii pași:
1. Creaz ă o list ă a tuturor pereților și crează o mulțime pentru fiecare celul ă, inițial
fiecare mulțime continând doar acea celulă
2. Pentru fiecare perete , în mod aleator :
Dacă celulele separate de respectivul perete aparț in la mulțimi diferite:
 Se înlătură peretele curent
 Se reunesc mulțimile corespunzătoare celor două celule alăturate

19
Există mai multe structuri de date care poate fi folosit e pentru a modela mulțimile de
celule. O implementare eficientă folos ește o structu ră de date de tip mulțimi disjuncte care
oferă posibilitatea efectu ării reuniuni i într-un timp foarte scurt , timpul de derulalare al acestui
algoritm fiind în esență propor țional cu numă rul de pereți disponibil p entru labirint.
Are mai pu țină importan ță dacă lista ini țiala a zidurilor este inițial randomizată sau
dacă un zid este aleator ales dintr -o list ă nealeatoare.
Pentru că efectul acestui algoritm este de a produce un arbore parțial minim d intr-un
graf cu muchii cu aceeași pondere, labirinturile obțin ute tind să urmeze un tipar asemănător,
făcându -le astfel destul de ușor de rezolvat.

1.3.5 Algoritmul randomizat al lui Prim
Acest algoritm este o variantă randomizată a algoritmului lui Prim și folosește pașii:
1. Începe cu o gril ă plină de pereț i
2. Se a lege aleator o celulă care este marca tă ca parte din labirint. Pereții celulei se
adaugă la lista de pere ți.
3. Atâta timp c ât există pereți în list ă:
 Se alege un perete aleatoar din list ă. Dacă celula pe partea opusă nu este în
labirint încă:
Peretele devine cor idor. iar celula din partea opusă este marcată ca făcând
parte din labirint.
Se adaugă pereții vecin i celul ei în lista de pere ți.

Similar cu algoritmul DFS, folosind acest algoritm va fi relativ ușor de găsit drumul
spre celula de început, dar greu de găs it drumul spre orice altă celulă .
Ca și observație, dacă s -ar rula algoritmul clasic al lui Prim pe un graf cu ponderi
aleatoare s -ar obține un labirint foarte similar ca aspect ca și cel obținut aplicând algoritmul
lui Kruskal, însă varianta randomizată i ntroduce o variație în aspect deoarece muchiile mai
apropiate de punctul de pornire se consideră a avea o pondere mai mică.

1.3.6 Versiunea modificata a algoritmului lui Prim
Deși algoritmul c lasic a lui Prim p ăstrează o listă a muchii lor, pentru generare a
labirinturilor s-ar putea păstra în schimb o list ă a celulelor adiacente. Astfel, dacă o celulă
aleasă aleator are mai multe muchii care o pot conecta la labirintul existent, se va selecta una

20
din aceste muchii aleator . Aceasta va duce la crearea mai mul tor ramur i decât în varianta
bazată pe muchii descrisă mai sus.
1.3.7 Metoda de divizare recursiv ă
Labirinturile pot fi create prin metoda divizării recursivă, algoritm care func ționează
după cum urmează:
1. Se pornește de la un labirint fără pereți numit și cameră
2. Se împarte camera folosind un perete plasat aleator (sau mai mulți pereți), iar
fiecare perete con ține pe el un pasaj poziționat aleator
3. Se repet ă recursiv procesul de divizare până când subcamerele ating o m ărime
minimă stabilită
Aces t algoritm ge nerează labirinturi cu ziduri lungi și drepte , ceea ce face labirintul
mai uș or de rezolvat.
De exemplu , într-un labirint dreptunghiular (cu o dimensiune a celulelor prestabilită)
se construiesc în puncte alese aleator 2 ziduri care sunt perpendiculare între ele. Aceste dou ă
ziduri î mpart camera mare în 4 camere mai mici separate de ziduri. Se aleg la întamplare trei
din cele 4 ziduri și deschide pe fiecare un pasaj de dimensiunea unei celule într -o poziție
aleator aleasă . Se continu ă recursiv în acest mod , până când fiecare camer ă are dimensiunea
unei celule .
Ilustrarea metodei de divizare recursivă
Camera inițială Divizare prin
2 ziduri Găuri în ziduri Continuarea
subdivizării… Final

1.3.8 Algoritmul lui Wilson
Algoritmul pornește de la alegerea unei celule aleatoare ca fiind punctul de start. Se
continuă prin a alege aleator o celulă care nu face încă parte din labirint, după care se
deplasează aleator până când se ajunge de la acea celulă până la una care face deja parte din

21
labirint. Toate celulele de pe acel drum vor fi adăugate la labirint. Algoritmul se încheie când
s-a trecut prin toate celulele labirintului.

1.3.9 Algoritmul “Vânează și omoară”
Acest algoritm este recomandat a fi folosit deoarece nu nec esită spațiu suplimentar de
memorie sau o stivă, astfel că este potrivit pentru a genera fără probleme labirinturi oricât de
mari. Algoritmul se aseamămă cu cel de Revenire recursivă însă este mai flexibil, astfel că
atunci când se ajunge la o celulă care nu are vecini nevizitați, se intră în modul “vânătoare” ,
căutând în labirint o celulă nevizitată care este vecină cu o celulă vizitată și se continuă
algoritmul de la acea celulă. Algoritmul se încheie când au fost verificate toate celulele în
modul “vânăt oare”. Acest algoritm are tendința de a genera labirinturi cu factor “râu” mare.

1.3.10 Algoritmul lui Eller
Acesta este cel mai rapid algoritm dintre toți cei prezentati și este cel mai eficient din
punct de vedere al memoriei necesare pentru a rula. El nu necesită ca întreg labirintul să se
afle în memorie la un momentdat, ci doar o singură linie. Odată o linie generată, algoritmul nu
va mai reveni la ea. Fiecare celulă dintr -o linie aparține unei mulțimi, astfel că dacă două
celule aparțin aceleiași mu lțimi, înseamnă că există un drum între ele în bucata de labirint
generată până atunci. Această informație permite crearea de pasaje în linia curentă, fără a
genera bucle sau zone izolate.
Crearea unei linii constă din două părți: (1) conectarea aleatoar e a celulelor adiacente
din linie (pasaje orizontale) și (2) conectarea aleatoare a celulelor din linia curentă și linia
următoare (pasaje verticale). În cazul pasajelor orizontale nu se vor conecta celulele care fac
deja parte din aceeași mulțime pentru a evita buclele.

1.3.11 Algoritm care nu se bazează pe celule
Un labirint poate fi generat fără a folosi celule. În anul 2000 a ap ărut un program
sharewave denumit AmorphousMaze care creaz ă labirinturi cu ziduri plasate în unghiuri
complet aleatoare. Algor itmul pornește de la un perete exterior și se bazează pe extinderea
pereților cu mici segmente cu restricția ca un perete să nu treacă peste altul deja existent.
Pereții generați sunt memorați într -un container. Când operația de extindere ajunge într -un
punct mort, se alege aleator un segment din container pentru a fi extins. Dezavantajul acestui

22
algoritm este faptul ca timp necesar testelor de intersectare a segmentelor este de tip O(E2),
unde E este num ărul de segmente desenate.

Exemplu:

Alți algor itmi
Exist ă alți algoritmi care necesit ă doar atâta memorie suficientă pentru a stoca o linie a
unui labirint 2D sa u unui plan de labirint 3D. Aceș tia evit ă ciclurile stoc ând care celule din
linia curentă sunt conectate prin celule din liniile anterioare și niciodat ă nu ș terg zidurile
dintre două astfel de celule deja conectate.
Majoritatea algoritmilor de generare a unui labirint cer p ăstrarea legă turilor dintre
celulele din el, pentru a se asigura ca rezultatul final poate fi rezolvabil. Totuși, labirint uri
valabile pot fi generate și doar concentr ându-ne asupra fiecarei celule independent.

23
1.4 Algoritm i de rezolvare a labirinturilor

Exist ă un num ăr de diferi ți algoritmi de rezolvar e a labirinturilor sau cu alte cuvinte,
metode automate de rezolvare a labirinturilor. Câțiva din algoritmii de rezolvare a
labirinturilor sunt explica ți mai jos . Algoritmii: Șoarece aleator , Urmărirea pereților , Pledge și
Tremaux sunt destinați pentru a fi folositi în labirinturi de către cineva care nu cun oaste în
prealabil labirintul , în timp ce algoritmi cum ar fi Umplerea punctelor moarte și cei de găsire a
celui mai scurt drum sunt destinați pentru a fi folosi ți de către o persoană sau de un program
pe calculator care pot vedea tot labirintul la un moment dat.
Labirintur ile care nu conț in bucle sunt cunoscute a fi “standard ” sau “perfecte ” și sunt
echivalente cu un arbore în teoria grafurilor. Astfel , mulți algoritmi de rezo lvare a
labirinturilor sunt strâns legaț i de teoria grafurilor. În mod intuitiv , dacă s-ar putea mu ta și
redimensiona în mod convenabil pasajele dintr -un labirint, ele ar putea să semene cu un
arbore .

1.4.1 Algoritmul aleator al șoarecelui
Acest a este o metod ă trivială care poate fi implementat ă de către un robot neinteligent
sau poate chiar un șoarece . Este vorba pur și simplu de a urma o linie dreaptă până când se
ajunge la o răscruce și apoi sa ia o decizie aleatoare despr e urm ătoarea direc ție care va fi
urmată. .

1.4.2 Urmărirea pereților
Urmărir ea pereților este cea mai cunoscută regul ă de a parcu rge un labirint , numită
deasemenea și regula de stânga sau de dreapta . Dacă labirintul este simplu cone x, adică toți
pereții săi sunt conectat i între ei sau de marginea exterioară a labirintului (bordura) , mergând
tot timpul pe lângă pereți se va ajunge la o altă ieșire , dacă exist ă vreuna , sau se va ajunge
înapoi de unde s-a pornit. Aceast ă strategie func ționeaz ă cel mai bine când este pus ă în
aplicare imediat după intrarea în labirint.
Dacă labirint ul nu este simplu conex (punctul de pornire sau cel de ieșire sunt în
mijlocul labirintului sau c ărările trec una peste sau dedesubtul alteia ), aceasta metod ă nu mai
garant ează atingerea scopului.

24

Urmărir ea pereților poate utilizată și în 3D sau în labirinturi de dimensiuni mai mar i
dacă pasaj ele de dimensi uni superioare pot fi proiectat e în planul 2D într-o manieră
deterministă. De exemplu , dacă intr-un labirint 3D pasajele în “sus” se presupune că duc
înspre nord-vest, iar pasajele în “jos” se pr esupune că duc înspre sud-est, atunci regulile
algoritmului de urmărire a pereților por fi aplicate . Cu toate acestea, spre deosebire de 2D,
este necesar ca orientare a actuală să fie cunoscută , pentru a se stabili care direc ție este spre
stânga sau dreapta .

1.4.2 Algoritmul lui Pledge
Labirinturile despartite pot fi rezolvate cu algoritmul urmăririi pereților dacă intrarea
și ieșire a din labirirint sunt pe marginile exterioare ale labirintului. Dacă cumva cel ce rezolva
labirintul incepe din int eriorul lab irintului, s-ar putea afla într -o sectiune disjunctă de cea cu
ieșire a, iar algoritmul urmăririi pereților se va invarti în jurul unui inel. Algoritmul Pledge
(numit după Jon Pledge de Exeter) poate rezolva aceasta problema.
Algoritmul Pledge, proiectat pe ntru a ocoli obstacole, necesita o directie arbitrar aleasa
pe care să o urmeze . Atunci când un obstacol este intalnit o mână (sa spun em mana dreapta)
este pastrata de-a lungul obstacolul ui în timp ce este calculat a suma unghiuril or cotiturilor
luate . Când cel care rezolva labirintul se află din nou pe direcția inițială , atunci suma
unghi rilor devine 0, iar cel care rezolva labirintul părăsește obstaculul și își continua miscare a
spre directia originală .
Acest algoritm permite unei persoa ne care are la în demână un compas să gaseasca
drumul de la orice punct din interior spre ieșirea din orice labirint bidimensional finit
indiferent de pozitia initiala din care se pleacă . Cu toate acestea, acest al goritm nu va
functiona în sens invers , adică să gasească dru mul de la o intrare dinafara labirintului la un
punct din interiorul lui .

1.4.3 Algoritmul lui Tremaux
Algoritmul lui Tremaux reprezintă o metodă eficientă pentru a găsi calea de ieșire
dintr -un labirint care necesită desenarea de linii pe jos pentru a ma rca un traseu și

25
funcționează garantat pentru toate labirinturile care au pasaje bine definite. Un traseu este fie :
nevizitat, marcat odata sau marcat de 2 ori. De fiecare data când este aleasa o directie , ea este
marcat a prin trasarea unei linii pe jos (de la o joncțiune la alta ). La inceput este aleasă o
directie aleatoare (dacă există mai mult decât una). Când ajungem la o joncțiune care nu a
mai fost vizitat a (nu este marcată) se alege o directie alea toare și se marchează traseul . Când
se ajung e la o juncțiune marcat a, și dacă traseul curent este marcat doar o data, ne întoarcem ,
și traseul este marcat a doua oară . Dacă joncțiune a la care se ajunge nu este marcată, se alege
direcția cu cele mai pu ține marcari (și se marchează traseul) . Dacă nu este ni ci o ieșire atunci
aceasta metoda ne va intoarce în punctul unde toate traseele sunt marcate de doua ori. În acest
caz, fiecare traseu este parcurs exact de două ori, câte o dată în fiecare directie.
O joncțiune este ca și o răscruce sau intersecție unde se întâlnesc trei sau mai multe
pasaje.

1.4.4 Umplerea capetelor de drum
Umplerea capetelor de drum (numite și puncte moarte) este un algoritm rapid pentru
rezolvarea labirinturilor , atunci când este posibilă vizualiz area în întregime a lor . El poate fi
folosit p entru rezolvarea labirinturilor pe hartie sau cu ajutorul unui program de calculator,
dar nu este folositor unei persoane care este în interiorul labirintului și nu îl cunoaste.
Pașii algoritmului sunt:
1. Găsește toate capetele de drum din labirint și apoi
2. “Umple ” traseul de la fiecare capăt de drum până la prima joncțiune intalni ta.
Umplerea capetelor de drum nu poate sa separe accidental intrarea în labirint de ieșire
deoarece fiecare pas al procesului pastreaza topologia labirintului. În plus nu va opri procesul
mai devreme decât este cazul doarece rezultatul final nu poate contine nici un capăt de drum .
Astfel dacă umplerea capetelor de drum se face pe un labirint perfect (labirint fără bucle)
atunci va ramane în labirint doar soluti a. Dacă se aplică pentru un labirint “panglică ” (cu
bucle) atunci vor rămâne în labirint toate soluțiile posibile, însă nimic în plus.

1.4.5 Algoritmul “Cel mai scurt drum ”
Când un labirint are solutii multiple , cel care îl rezolva poate dor i sa gasesca ce l mai
scurt drum de la start până la sfârșit . Acest algoritm găsește cel mai scurt drum prin
implementarea algoritmului de căutare în lățime (Breadth -first search) . Algoritmul foloseste o
structură de date de tip coadă pentru a vizita celulele în ordinea cr escatoare a distantei dintre

26
ele, de la punctul de start până la sfârșit . Fiecare celula vizita ta trebuie să cunoască distan ța de
la ea până punctul de start sau ca re celul ă adiacenta mai apropi ata de start a făcut ca ea să fie
adaugata la coada. Când se ajunge la sfârșit , se urme ază drumul format din celulele din coadă
până la start, iar aceasta este cel mai scurt drum.

1.4.6 Algoritmul de rezolvare în stil ”lanț”
Acest algoritm privește labirintul ca pe o înlănțuire de mai multe labirinturi mai mici,
pe care le rezolvă pe rând. Ceea ce este neapărat este să se specifice care sunt punctele de start
și de sfârșit. Algoritmul generează soluții de lungimi aproape de minim.

27
1.5 Alte operații asupra labirinturilor
Există mai multe operații care pot fi aplica te asupra labirinturi , înafară de crearea și
rezolvarea acestora, cum ar fi cele descris e mai jos:
“Inu ndar ea” labirintului : aceasta este o metodă care poate fi aplicată în mai multe moduri ,
”inundând” pasaje sau pereți, în operații de generare sau rezol vare a labirintului, dar și în alte
posibile scopuri.

Eliminarea zonelor izolat e: Un zonă izolată din labirint este una în care nu se poate ajunge
prin pasaje. Eliminarea lor se face prin ștergerea unor pereți dintre ele și restul . Găsirea
zonelor izol ate poate fi făcută folosind metoda inundării labirintului.

Eliminarea bucle lor: Acest procedeu se aseamănă cu eliminarea zonelor izolate , însă acum
este vorba despre pasaje și nu despre pereți. Găsirea zonelor izolate poate fi făcută folosind tot
metod a inundării labirintului. Se analizează apoi labirintul pentru detecta pereți neumpluți
care sunt adiacen ți la pere ți umpluți . Se adaugă apoi un perete în acea locație și se inunda
labirintul la acest nou punct . Algoritmul se oprește când fiecare secțiune a labirintului este

28
umpluta. Acest procedeu este folosit în crearea de labirinturi după șabloane sau pentru a
transforma un labirint panglica în unul labirint perfect.

29
Capitolul 2. Proiectarea aplicației

2.1 Alegerea limbajului de progra mare – Java
2.1.1 Limbajul de programare Java
Java este o tehnologie inovatoare lansată de compania Sun Microsystems în 1995, care
a avut un impact remarcabil asupra întregii comunități a dezvoltatorilor de software,
impunându -se prin calități deosebite c um ar fi simplitate, robustețe și nu în ultimul rând
portabilitate. Denumită inițial OAK, tehnologia Java este formată dintr -un limbaj de
programare de nivel înalt pe baza căruia sunt construite o serie de platforme destinate
implementării de aplicații pen tru toate segmentele industriei software.
Amintim caracteristicile sale principale, care l -au transformat într -un interval de timp
scurt în una din cele mai populare opțiuni pentru dezvoltarea de aplicații, indiferent de
domeniu sau de complexitatea lor: simplitate a; ușurința în crearea de aplicații complexe ce
folosesc programarea în rețea, fire de execuție, interfața grafică, baze de date, etc. ; complet
orientat pe obiecte ; securitate ; neutralitate arhitecturală ; portabililtate ; performanța.

Platforme de lucru Java
Limbajul de programare Java a fost folosit la dezvoltarea unor tehnologii dedicate
rezolvării unor probleme din cele mai diverse domenii. Aceste tehnologii au fost grupate în
așa numitele platforme de lucru, ce reprezintă seturi de librarii scr ise în limbajul Java, precum
și diverse programe utilitare, folosite pentru dezvoltarea de aplicații sau componente destinate
unei anume categorii de utilizatori.
• J2SE (Standard Edition): Este platforma standard de lucru ce oferă suport pentru crearea de
aplicații independente și appleturi. De asemenea, aici este inclusă și tehnologia JavaWeb Start
ce furnizează o modalitate extrem de facilă pentru lansarea și instalarea locala a programelor
scrise în Java direct de pe Web, oferind cea mai comodă soluție pentru distribuția și
actualizarea aplicațiilor Java.
• J2ME (Micro Edition): Folosind Java, programarea dispozitivelor mobile este extrem de
simplă, platforma de lucru J2ME oferind suportul necesar scrierii de programe dedicate
acestui scop.

30
• J2EE (Enterp rise Edition): Aceasta platform ă oferă API -ul necesar dezvolt ării de aplicații
complexe, formate din componente ce trebuie sa ruleze în sisteme eterogene, cu informațiile
memorate în baze de date distribuite, etc. Tot aici găsim și suportul necesar pentru crearea de
aplicații și servicii Web, bazate pe componente cum ar fi servleturi, pagini JSP, etc.
Toate distribuțiile Java sunt oferite gratuit și pot fi descarcate de pe Internet de la
adresa ”http://java.sun.com”.

2.1.2 Clase și obiecte
Clasa este un c oncept de bază al programării orientate obiect, domeniu în care
reprezintă structura care definește caracteristicile abstracte ale unui lucru (obiect), printre care
caracteristicile acestuia (atributele sale, câmpuri sau proprietăți), precum și comportamen tele
acestui lucru (lucrurile pe care le poate face, sau metode, operații sau proprietăți).
Se poate spune că o clasă este schița care descrie natura unui lucru.
Clasele asigură modularitatea și structura într -un program de calculator orientat pe
obiecte. O clasă ar trebui să poată fi înțeleasă de către o persoană care nu știe programare dar
cunoscătoare a domeniului problemei, caracteristicile clasei ar trebui să aibă sens în
respectivul context. De asemenea, codul clasei ar trebui să fie auto -suficient ( folosind în
general încapsularea ).
În ansamblul lor, proprietățile și metodele definite intr -o clasă sunt numite membri .
Pentru a da consistență atributelor este nevoie de cearea unui obiect într -o clasă.
Astfel, un obiect se mai numește și instanță a une i clase.
Încapsularea este termenul care definește accesul la membrii unei clase. Un atribut
sau o metodă a unui obiect pot sau nu să fie accesate de către un obiect exterior clasei. Se
poate întâmpla ca o parte din membrii unei clase să poată fi utilizaț i doar în interiorul clasei și
să nu se permită accesul la ei dinafară. Ca urmare, se spune că aceștia vor fi încapsulați în
interiorul clasei, fără a fi vizibili sau accesabili din exterior. Definirea accesului la un membru
al unei clase se face prin inte rmediul specificatorilor de acces.

Crearea claselor
Clasele reprezintă o modalitate de a introduce noi tipuri de date într -o aplicație Java,
cealaltă modalitate fiind prin intermediul interfețelor. Declararea unei clase respectă
următorul format general:
[modificatori clasa] class NumeClasa
[extends NumeSuperclasa]

31
[implements Interfata1 [, Interfata2 … ]]
{
// Corpul clasei
}
Așadar, prima parte a declarației o ocupă modificatorii clasei. Aceștia sunt: public,
abstract, final.
După numele clasei putem sp ecifica, dacă este cazul, faptul că respectiva clasă este
subclasă a unei alte clase cu numele NumeSuperclasa sau/și că implementează una sau mai
multe interfețe, ale căror nume trebuie separate prin virgulă.

Extinderea claselor
Spre deosebire de alte lim baje de programare orientate -obiect, Java permite doar
moștenirea simplă, ceea ce înseamnă că o clasă poate avea un singur părinte (superclasă).
Evident, o clasă poate avea oricâti moștenitori (subclase), de unde rezultă că mulțimea tuturor
claselor defini te în Java poate fi vazută ca un arbore, rădăcina acestuia fiind clasa Object.
Așadar, Object este singura clasă care nu are părinte, fiind foarte importantă în modul de lucru
cu obiecte și structuri de date în Java.
Extinderea unei clase se realizează fol osind cuvântul cheie extends .
O subclasă moștenește de la părintele său toate variabilele și metodele care nu sunt
private.

Corpul unei clase
Corpul unei clase urmează imediat după declararea clasei și este cuprins între acolade.
Conținutul acestuia este format din:
• Declararea și, eventual, inițializarea variabilelor de instanță și de clasă (cunoscute împreună
ca variabile membre).
• Declararea și implementarea constructorilor.
• Declararea și implementarea metodelor de instanța și de clasă (cunoscute îm preună ca
metode membre).
• Declararea unor clase imbricate (interne).

Constructorii unei clase

32
Constructorii unei clase sunt metode speciale care au același nume cu cel al clasei, nu
returnează nici o valoare și sunt folosiți pentru inițializarea obiecte lor acelei clase în
momentul instanțierii lor. Constructorii nu sunt considerați ca fiind membrii ai clasei.
Constructorii sunt apelați automat la instanțierea unui obiect. În cazul în care dorim să apelăm
explicit constructorul unei clase folosim expresia this(argumente), care apelează constructorul
corespunzător (ca argumente) al clasei respective.

Clase și metode abstracte
Uneori în proiectarea unei aplicații este necesar să reprezentăm cu ajutorul claselor
concepte abstracte care să nu poată fi instanț iate și care să folosească doar la dezvoltarea
ulterioară a unor clase ce descriu obiecte concrete.
Spre deosebire de clasele obișnuite care trebuie să furnizeze implementări pentru toate
metodele declarate, o clasă abstractă poate conține metode fără ni ci o implementare. Metodele
fara nici o implementare se numesc metode abstracte și pot apărea doar în clase abstracte. În
fața unei metode abstracte trebuie să apară obligatoriu cuvântul cheie abstract, altfel va fi
furnizată o eroare de compilare.
În felu l acesta, o clasă abstractă poate pune la dispoziția subclaselor sale un model
complet pe care trebuie să -l implementeze, furnizând chiar implementarea unor metode
comune tuturor claselor și lăsând explicitarea altora fiecărei subclase în parte.
O subclas ă a unei clase abstracte, care nu este abstractă trebuie să furnizeze
obligatoriu implementări ale metodelor abstracte definite în superclasă.

Supraîncărcarea și supradefinirea metodelor
Supraîncărcarea și supradefinirea metodelor sunt două concepte extre m de utile ale
programării orientate obiect, cunoscute și sub denumirea de polimorfism, și se referă la:
• supraîncarcarea ( overloading ) : în cadrul unei clase pot exista metode cu același nume cu
condiția ca signaturile lor să fie diferite (lista de argum ente primite să difere fie prin numărul
argumentelor, fie prin tipul lor) astfel încât la apelul funcției cu acel nume să se poată stabili
în mod unic care dintre ele se execută.
• supradefinirea ( overriding ): o subclasă poate rescrie o metodă a clasei păr inte prin
implementarea unei metode cu același nume și aceeași signatură ca ale superclasei.

Crearea obiectelor

33
În Java, ca în orice limbaj de programare orientat -obiect, crearea obiectelor se
realizează prin instanțierea unei clase și implică următoarele lucruri:
• Declararea : Presupune specificarea tipului acelui obiect, cu alte cuvinte specificarea clasei
acestuia (vom vedea că tipul unui obiect poate fi și o interfață).
NumeClasa numeObiect;
• Instanțierea : Se realizează prin intermediul operatorului new și are ca efect crearea efectivă
a obiectului cu alocarea spațiului de memorie corespunzător.
numeObiect = new NumeClasa();
• Inițializarea : Se realizează prin intermediul constructorilor clasei respective. Inițializarea
este de fapt parte integrantă a procesului de instanțiere, în sensul că imediat după alocarea
memoriei ca efect al operatorului new este apelat constructorul specificat.
Mai general, instanțierea și inițializarea apar sub forma:
numeObiect = new NumeClasa([argumente constructor]);
Odată un obiect creat, el poate fi folosit în următoarele sensuri: aflarea unor informații
despre obiect, schimbarea stării sale sau executarea unor acțiuni. Aceste lucruri se realizeaza
prin aflarea sau schimbarea valorilor variabilelor sale, respectiv pr in apelarea metodelor sale.
Referirea valorii unei variabile se face prin obiect.variabila.

Obiecte anonime
Este posibilă și crearea unor obiecte anonime care servesc doar pentru inițializarea
altor obiecte, caz în care etapa de declarare a referinței obi ectului nu mai este prezentă:
Ex: Rectangle patrat = new Rectangle(new Point(0,0), new Dimension(100, 100));
Spațiul de memorie nu este pre -alocat. Declararea unui obiect nu implică sub nici o
formă alocarea de spațiu de memorie pentru acel obiect. Alocare a memoriei se face doar la
apelul operatorului new.

34
2.2 Interfața grafică cu utilizatorul

2.2.1 Introducere
Interfața grafică cu utilizatorul (GUI), este un termen cu înțeles larg care se referă la
toate tipurile de comunicare vizuală între un program și utilizatorii săi. Aceasta este o
particularizare a interfeței cu utilizatorul (UI), prin care vom întelege conceptul generic de
interacțiune dintre program și utilizatori.
Limbajul Java pune la dispoziție numeroase clase pentru implementarea diverselor
funcționalitati UI, însă ne vom ocupa în continuare de cele care permit realizarea intefeței
grafice cu utilizatorul (GUI).
De la apariția limbajului Java, bibliotecile de clase care oferă servicii grafice au suferit
probabil cele mai mari schimbări în tre cerea de la o versiune la alta. Acest lucru se datorează,
pe de o parte dificultății legate de implementarea noțiunii de portabilitate, pe de altă parte
nevoii de a integra mecanismele GUI cu tehnologii apărute și dezvoltate ulterior, cum ar fi
Java Beans. În momentul actual, există două modalități de a crea o aplicație cu interfață
grafică și anume:
• AWT (Abstract Windowing Toolkit) – este API -ul inițial pus la dispoziție începând cu
primele versiuni de Java;
• Swing – parte dintr -un proiect mai amplu numi t JFC (Java Foundation Classes) creat în urma
colaborării dintre Sun, Netscape și IBM, Swing se bazează pe modelul AWT, extinzând
funcționalitatea lui și adăugând sau înlocuind componente pentru dezvoltarea aplicațiilor GUI.
În principiu, crearea unei apli cații grafice presupune următoarele lucruri:
• Design :
– Crearea unei suprafețe de afișare (cum ar fi o fereastră) pe care vor fi așezate obiectele
grafice (componente) care servesc la comunicarea cu utilizatorul (butoane, controale pentru
editarea text elor, liste, etc);
– Crearea și așezarea componentelor pe suprafața de afișare la pozițiile corespunzătoare;
• Funcționalitate :
– Definirea unor acțiuni care trebuie să se execute în momentul când utilizatorul
interacționează cu obiectele grafice ale aplicației;
– ”Ascultarea” evenimentelor generate de obiecte în momentul interacțiunii cu utilizatorul și
executarea acțiunilor corespunzătoare, așa cum au fost ele definite.

35
2.2.2 Modelul AWT
Obiectele grafice sunt derivate din clasa Component , cu exc epția meniurilor care
descind din clasa MenuComponent . Așadar, prin noțiunea de componentă vom întelege în
continuare orice obiect care poate avea o reprezentare grafică și care poate interac ționa cu
utilizatorul. Exemple de componente sunt ferestrele, but oanele, listele, bare de defilare, etc.
Toate componentele AWT sunt definte de clase proprii ce se gasesc în pachetul
java.awt , clasa Component fiind superclasa abstractă a tuturor acestor clase.
Interfața grafică servește interacțiunii cu utilizatorul. D e cele mai multe ori programul
trebuie să facă o anumită prelucrare în momentul în care utilizatorul a efectuat o acțiune și,
prin urmare, componentele trebuie să genereze evenimente în funcție de acțiunea pe care au
suferit -o (acțiune transmisă de la tast atură, mouse, etc.).
Începând cu versiunea 1.1 a limbajului Java, evenimentele sunt instanțe ale claselor
derivate din AWTEvent . Așadar, un eveniment este produs de o acțiune a utilizatorului asupra
unui obiect grafic, deci evenimentele nu trebuie generat e de programator.

2.2.3 Suprafețe de afișare (Clasa Container)
Crearea obiectelor grafice nu realizează automat și afișarea lor pe ecran. Mai întâi ele
trebuie așezate pe o suprafață, care poate fi o fereastră sau suprafața unui applet, și vor deveni
vizibile în momentul în care suprafața respectivă va fi vizibilă. O astfel de suprafața pe care
sunt plasate componentele se numește suprafață de afișare sau container și reprezintă o
instanța a unei clase derivată din Container. Clasa Container este o subcl asă aparte a lui
Component, fiind la rândul ei superclasa tuturor suprafetelor de afișare Java.
O parte din clasele a căror părinte este Container este prezentată mai jos:
• Window – este superclasa tututor ferestrelor. Din această clasă sunt derivate:
– Frame – ferestre standard;
– Dialog – ferestre de dialog modale sau nemodale;
• Panel – o suprafață fără reprezentare grafică folosită pentru gruparea altor componente. Din
această clasă derivă Applet, folosită pentru crearea appleturilor.
• ScrollPane – container folosit pentru implementarea automată a derulării pe orizontală sau
verticală a unei componente.
Așadar, un container este folosit pentru a adăuga componente pe suprafața lui.
Componentele adăugate sunt memorate într -o listă iar pozițiile lor din această listă vor defini

36
ordinea de traversare ”front -to-back” a acestora în cadrul containerului. Dacă nu este
specificat nici un index la adăugarea unei componente, atunci ea va fi adaugată pe ultima
poziție a listei.
Clasa Container conține metodele com une tututor suprafețelor de afișare. Dintre cele
mai folosite, amintim:
• add – permite adăugarea unei componente pe suprafața de afișare.
• remove – elimină o componentă de pe container; O componentă nu poate aparține decât unui
singur container, ceea ce înseamnă că pentru a muta un obiect dintr -un container în altul
trebuie sa -l eliminam mai întâi de pe containerul initial.
• setLayout – stabilește gestionarul de poziționare al containerului

2.2.4 Gestionarea poziționării
Un gestionar de poziționare (lay out manager) este un obiect care controlează
dimensiunea și aranjarea (poziția) componentelor unui container.
Așadar, modul de aranjare a componentelor pe o suprafața de afișare nu este o
caracteristică a containerului. Fiecare obiect de tip Container (Ap plet, Frame, Panel, etc.) are
asociat un obiect care se ocupă cu dispunerea componentelor pe suprafața sa și anume
gestionarul său de poziționare.
Sunt însă situații când dorim să plasăm componentele la anumite poziții fixe iar
acestea să ramâna acolo chia r dacă redimensionăm containerul. Folosind un gestionar această
poziționare absolută a componentelor nu este posibilă și deci trebuie cumva să renunțăm la
gestionarea automată a containerul. Acest lucru se realizează prin trimitera argumentului null
metode i setLayout.
La instanțierea unui container se creează implicit un gestionar de poziționare asociat
acestuia. De exemplu, pentru o fereastră gestionarul implict este de tip BorderLayout, în timp
ce pentru un panel este de tip FlowLayout.
Cei mai utilizați gestionari din pachetul java.awt sunt:
• FlowLayout : așează componentele pe suprafața de afișareîn flux liniar, mai precis,
componentele sunt adăugate una după alta pe linii, în limita spațiului disponibil.
• BorderLayout : împarte suprafața de afișare în cinci regiuni, corespunzătoare celor patru
puncte cardinale și centrului. O componentă poate fi plasată în oricare din aceste regiuni,
dimeniunea componentei fiind calculata astfel încât să ocupe întreg spațiul de afișare oferit de
regiunea respectivă. Pen tru a adăuga mai multe obiecte grafice într -una din cele cinci zone,

37
ele trebuie grupate în prealabil într -un panel, care va fi amplasat apoi în regiunea dorită. La
adăugarea unei componente pe o suprafață gestionată de BorderLayout, metoda add va mai
prim i pe lânga referința componentei și zona în care aceasta va fi amplasată, care va fi
specificată prin una din constantele clasei: NORTH, SOUTH, EAST, WEST, CENTER.
BorderLayout este gestionarul implicit pentru toate containerele care descind din clasa
Window, deci al tuturor tipurilor de ferestre.
• GridLayout : organizează containerul ca un tabel cu rânduri și coloane, componentele fiind
plasate în celulele tabelului de la stânga la dreapta, începând cu primul rând. Celulele
tabelului au dimensiuni egale iar o componentă poate ocupa doar o singură celulă. Numărul
de linii și coloane vor fi specificate în constructorul gestionarului, dar pot fi modificate și
ulterior prin metodele setRows (), respectiv setCols ().
• CardLayout : tratează componentele adăugate pe suprafața sa într -o manieră similară cu cea
a dispunerii cărților de joc într -un pachet. Suprafața de afișare poate fi asemănată cu pachetul
de cărți iar fiecare component ă este o carte din pachet. La un moment dat, numai o singură
componentă este vi zibilă (”cea de deasupra”).
• GridBagLayout : Este cel mai complex și flexibil gestionar de poziționare din Java. La fel ca
în cazul gestionarului GridLayout, suprafața de afișare este considerată ca fiind un tabel însă,
spre deosebire de acesta, numărul de linii și de coloane sunt determinate automat, în funcție
de componentele amplasate pe suprafața de afișare. De asemenea, în funcție de componentele
gestionate, dimensiunile celulelor pot fi diferite cu singurele restricții ca pe aceeași linie să
aibă acee ași înălțime, iar pe coloană aibă aceeași lățime. Spre deosebire de GridLayout, o
componentă poate ocupa mai multe celule adiacente, chiar de dimensiuni diferite, zona
ocupată fiind referită prin ”regiunea de afișare” a componentei respective.

38
2.2.5 Comp onentele AWT
După cum am spus deja, toate componentele AWT sunt definte de clase proprii ce se
gasesc în pachetul java.awt, clasa Component fiind superclasa abstractă a tuturor acestor
clase.
• Button – butoane cu eticheta formată dintr -un text pe o singur ă linie;
• Canvas – suprafață pentru desenare;
• Checkbox – componentă ce poate avea două stări; mai multe obiecte de acest tip pot fi
grupate folosind clasa CheckBoxGroup;
• Choice – liste în care doar elementul selectat este vizibil și care se deschid la apăsarea lor;
• Container – superclasa tuturor suprafețelor de afișare;
• Label – etichete simple ce pot conține o singură linie de text needitabil;
• List – liste cu selecție simplă sau multiplă;
• Scrollbar – bare de defilare orizontale sau verticale;
• TextComponent – superclasa componentelor pentru editarea textului: TextField (pe o singură
linie) și TextArea (pe mai multe linii).
Componentele AWT au peste 100 de metode comune, moștenite din clasa Component.
Acestea servesc uzual pentru aflarea sau set area atributelor obiectelor, cum ar fi: dimensiune,
poziție, culoare, font, etc. și au formatul general getProprietate, respectiv setProprietate.

2.2.6 Tratarea evenimentelor
Un eveniment este produs de o acțiune a utilizatorului asupra unei componente gr afice
și reprezintă mecanismul prin care utilizatorul comunică efectiv cu programul. Exemple de
evenimente sunt: apăsarea unui buton, modificarea textului într -un control de editare,
închiderea sau redimensionarea unei ferestre, etc. Componentele care gene rează anumite
evenimente se mai numesc și surse de evenimente.
Interceptarea evenimentelor generate de componentele unui program se realizează prin
intermediul unor clase de tip listener (ascultător, consumator de evenimente). În Java, orice
obiect poate ” consuma” evenimentele generate de o anumită componentă grafică.
Așadar, pentru a scrie cod care să se execute în momentul în care utilizatorul
interactionează cu o componentă grafică trebuie să facem următoarele lucruri:
• să scriem o clasă de tip listener care să ”asculte” evenimentele produse de acea componentă
și în cadrul acestei clase să implementăm metode specifice pentru tratarea lor;
• să comunicăm componentei sursă că respectiva clasa îi ”ascultă” evenimentele pe care le
generează, cu alte cuvinte să înregistrăm acea clasă drept ”consumator” al evenimentelor
produse de componenta respectivă.

39
Pentru ca evenimentele unei componente să fie interceptate de către o instanță a unei
clase ascultător, această clasă trebuie înregistrata în lista ascultătoril or componentei
respective. Inregistrarea unei clase în lista ascultătorilor unei componente se face cu metode
din clasa Component de tipul add TipEveniment Listener, iar eliminarea ei din această listă cu
remove TipEveniment Listener.

Tipuri de evenimente
Evenimentele se împart în două categorii: de nivel jos și semantice.
Evenimentele de nivel jos reprezintă o interacțiune de nivel jos cum ar fi o apăsare de
tastă, mișcarea mouse -ului, sau o operație asupra unei ferestre.
O anumită acțiune a utilizatorului p oate genera mai multe evenimente. De exemplu,
tastarea unei litere va genera trei evenimente: unul pentru apăsare, unul pentru eliberare și
unul pentru tastare. În funcție de necesitățile aplicație putem scrie cod pentru tratarea fiecărui
eveniment în part e.
Evenimentele semantice reprezintă interacțiunea cu o componentă GUI: apăsarea unui
buton, selectarea unui articol dintr -o listă, etc.
Următorul tabel prezintă componentele AWT și tipurile de evenimente generate,
prezentate sub forma interfețelor coresp unzătoare.
Component ComponentListener
FocusListener
KeyListener
MouseListener
MouseMotionListener
Container ContainerListener
Window WindowListener
Button
ActionListener List
MenuItem
TextField
Choice
ItemListener Checkbox
List
CheckboxMenuItem
Scrollbar AdjustmentListener
TextField TextListener TextArea

40
Se observă că deși există o singură clasă MouseEvent, există două interfețe asociate
MouseListener și MouseMotionListener. Acest lucru a fost făcut deoarece evenimentele
legat e de deplasarea mouse -ului sunt generate foarte frecvent și adesea tratarea acestora nu ne
interesează și dorim să tratăm doar evenimente de tip click, de exemplu.
Fiecare din interfețele Listener au metode care trebuiesc implementate de către clasa
ascult ător.

Folosirea adaptorilor și a claselor anonime
O clasă care tratează evenimente de un anumit tip trebuie să implementeze interfața
corespunzătoare acelui tip. Aceasta înseamnă că trebuie să implementeze obligatoriu toate
metodele definite de acea inter față, chiar dacă nu specifică nici un cod pentru unele dintre ele.
Sunt însă situații când acest lucru poate deveni supărator, mai ales atunci când nu ne
interesează decât o singura metodă a interfeței.
Un adaptor este o clasă abstractă care implementează o anumită interfață fără a
specifica cod nici unei metode a interfeței.
Scopul unei astfel de clase este ca la crearea unui ”ascultător” de evenimente, în loc să
implementăm o anumită interfață și implicit toate metodele sale, să extindem adaptorul
corespu nzător interfeței respective (dacă are) și să supradefinim doar metodele care ne
interesează (cele în care vrem să scriem o anumită secvență de cod).
Avantajul clar al acestei modalități de tratare a evenimentelor este reducerea codului
programului, acesta devenind mult mai lizibil.
Însă există și două dezavantaje majore. De exemplu, dacă o clasă extinde deja o altă
clasă, ea nu va mai putea extinde și clasa adaptor. Acest dezavantaj poate fi eliminat însă prin
folosirea unei clase anonime. Un alt dezavant aj este că orice greșeală de sintaxă în declararea
unei metode a interfeței nu va produce o eroare de compilare dar nici nu va supradefini
metoda interfeței ci, pur și simplu, va crea o metodă a clasei respective.

2.2.7 Desenarea
Conceptul de desenare
Un program Java care are interfață grafică cu utilizatorul trebuie să deseneze pe ecran
toate componentele sale care au o reprezentare vizuală. Această desenare include
componentele standard folosite în aplicație precum și cele definite de către programator.

41
Desenarea componentelor se face automat și este un proces care se execută în următoarele
situații:
• la afișarea pentru prima dată a unei componente;
• la operații de minimizare, maximizare, redimensionare a suprafeței de afișare;
• ca răspuns al unei soli citări explicite a programului.
Metodele care controlează procesul de desenare se găsesc în clasa Component și sunt
următoarele:
• void paint(Graphics g) – Desenează o componentă. Este o metodă supradefinită de fiecare
componentă în parte pentru a furniza reprezentarea sa grafică specifică. Metoda este apelată
de fiecare dată când conținutul componentei trebuie desenat sau redesenat.
• void update(Graphics g) – Actualizează starea grafică a unei componente.
Acțiunea acestei metode se realizează în trei pași :
1. șterge componenta prin supradesenarea ei cu culoarea fundalului;
2. stabilește culoarea (foreground) a componentei;
3. apelează metoda paint pentru a redesena componenta.
• void repaint() – Execută explicit un apel al metodei update pentru a actualiza reprezentarea
grafică a unei componente.
După cum se observă, singurul argument al metodelor paint () și update () este un
obiect de tip Graphics. Acesta reprezintă contextul grafic în care se execută desenarea
componentelor .

Suprafețe de desenare – clasa Canvas
În afara posibilității de a utiliza componente grafice standard, Java oferă și
posibilitatea controlului la nivel de punct (pixel) pe dispozitivul grafic, respectiv desenarea a
diferite forme grafice direct pe suprafața unei componente.
Deși este po sibil, în general nu se desenează la nivel de pixel direct pe suprafața
ferestrelor sau a altor containere, ci vor fi folosite clase dedicate acestui scop.
În AWT a fost definit un tip special de componentă numită Canvas (pânză), al cărei
scop este de a fi extinsă pentru a implementa obiecte grafice cu o anumită înfățișare. Așadar,
Canvas este o clasă generică din care se derivează subclase pentru crearea suprafețelor de
desenare (planșe).
Planșele nu pot conține alte componente grafice, ele fiind utilizate doar ca suprafețe de
desenat sau ca fundal pentru animație. Desenarea pe o planșa se face prin supradefinirea
metodei paint a acesteia.

42
O planșă este o suprafață dreptunghiulară de culoare albă, pe care se poate desena.
Dimensiunile sale implicite sunt 0 și, din acest motiv, este recomandat ca o planșa să
redefinească metoda getPreferredSize, eventual și getMinimumSize, getMaximumSize,
deoarece acestea vor fi apelate de către gestionarii de poziționare.

Contextul grafic de desenare
Înainte ca utilizatoru l să poată desena, el trebuie să obțină un context grafic de
desenare pentru suprafața căreia îi aparține regiunea pe care se va desena.
Un context grafic este, de fapt, un obiect prin intermediul căruia putem controla
procesul de desenare a unui obiect. Î n general, desenarea se poate face:
• pe o porțiune de ecran,
• la imprimantă sau
• într -o zonă virtuală de memorie.
Un context grafic este specificat prin intermediul unui obiect de tip Graphics primit ca
parametru în metodele paint și update. În funcție de dispozitivul fizic pe care se face afișarea
(ecran, imprimantă, plotter, etc) metodele de desenare au implementări interne diferite,
transparente utilizatorului.
Clasa Graphics pune la dispoziție metode pentru:
• primitive grafice: desenarea de figuri g eometrice, texte și imagini
• stabilirea proprietăților contextului grafic, adică stabilirea:
– culorii și fontului curente cu care se face desenarea,
– originii coordonatelor suprafeței de desenare,
– suprafeței în care sunt vizibile componentelor desenat e,
– modului de desenare.

Proprietățile contextului grafic
La orice tip de desenare parametrii legați de culoare, font, etc. vor fi specificați pentru
contextul grafic în care se face desenarea și nu vor fi trimiși ca argumente metodelor
respective de des enare. În continuare, enumerăm aceste proprietăți și metodele asociate lor
din clasa Graphics:

43
Proprietate Metode
Culoarea de desenare Color getColor()
void setColor(Color c)
Fontul de scriere a textelor Font getFont()
void setFont(Font f)
Originea c oordonatelor translate(int x, int y)
Zona de decupare
(zona în care sunt vizibile desenele) Shape getClip()
void setClip(Shape s)
Modul de desenare void setXorMode(Color c)
void setPaintMode(Color c)

Primitive grafice
Prin primitive grafice ne vom refe ri în continuare la metodele clasei Graphics, care
permit desenarea de figuri geometrice și texte.
Desenarea textelor se face cu uzual cu metoda drawString care primește ca argumente
un șir și colțul din stânga -jos al textului. Textul va fi desenat cu fon tul și culoarea curente ale
contextului grafic.
Desenarea figurilor geometrice se realizează cu următoarele metode:
Figură geometrică Metode
Linie drawLine
drawPolyline
Dreptunghi simplu drawRect
fillRect
clearRect
Dreptunghi cu chenar
“ridicat” sau “a dâncit” draw3Drect
fill3DRect
Dreptunghi cu colțuri
rotunjite drawRoundRect
fillRoundRect
Poligon drawPolygon
fillPolygon
Oval (Elipsă) drawOval
fillOval
Arc circular sau eliptic drawArc
fillArc

Metodele care încep cu ”fill” vor desena figuri geomet rice care au interiorul colorat,
adică ”umplut” cu culoarea curentă a contextului de desenare, în timp ce metodele care încep
cu ”draw” vor desena doar conturul figurii respective.

44
Folosirea culorilor
Orice culoare este formată prin combinația culorilor standard roșu (red), verde (green)
și albastru (blue), la care se adaugă un anumit grad de transparență (alpha). Fiecare din acești
patru parametri poate varia într -un interval cuprins fie între 0 și 255 (dacă dorim să specificăm
valorile prin numere între gi), fie între 0.0 și 1.0 (dacă dorim să specificăm valorile prin
numere reale). Valoarea 255 (sau 1.0) pentru transparență specifică faptul că respectiva
culoare este complet opacă, iar valoarea 0 (sau 0.0) specifică transparență totală. Implicit,
culoril e sunt complet opace.
Pentru a crea o culoare avem două posibilități: să folosim una din constantele definite
în cele două clase; sau să folosim unul din constructorii clasei Color.
Putem crea noi culori prin intermediul constructorilor clasei Color:
– Color (float red, flot green, float blue)
– Color(flot red, float green, float blue, float alpha)
– Color(int red, int green, int blue)
– Color(int red, int green, int blue, int alpha)
– Color(int rgb)
Parametrul ”rgb” de la ultimul constructor reprezintă un întreg form at din biții: 16 -23
pentru roșu, 8 -15 pentru verde, 0 -7 pentru albastru.

45
2.3 A pplet -uri
Un applet reprezintă un program Java de dimensiuni reduse ce gestionează o suprafață
de afișare (container) care poate fi inclusă într -o pagină Web. Un astfel de progr am se mai
numește și miniaplicatie . Ca orice altă aplicație Java, codul unui applet poate fi format din
una sau mai multe clase. Una dintre acestea este principală și extinde clasa Applet, aceasta
fiind clasa ce trebuie specificată în documentul HTML ce de scrie pagina Web în care dorim
să includem appletul.
Diferența fundamentală dintre un applet și o aplicație constă în faptul că un applet nu
poate fi executat independent, ci va fi executat de browserul în care este încărcată pagina Web
ce conține appletul respectiv. O aplicație independentă este executată prin apelul
interpretorului Java, av ând ca argument numele clasei principale a aplicației, clasa principală
fiind cea care conține metoda main . Ciclul de viaț ă al unui applet este complet diferit, fiind
dictat de evenimentele generate de către browser la vizualizarea documentului HTML ce
conține appletul.
Pachetul care oferă suport pentru crearea de appleturi este java.applet , cea mai
importantă clasă fiind Applet. În pachetul javax.swing există și clasa J Applet, care extinde
Applet, oferind suport pentru crearea de appleturi pe arhitectura de componente JFC/Swing.
Fiind derivată din clasa Container, clasa Applet descrie de fapt suprafețe de afișare,
asemenea claselor Frame sau Panel.

2.3.1 Crearea unui ap plet simplu
Crearea structurii de fișiere și compilarea applet -urilor sunt identice ca în cazul
aplicațiilor. Diferă în schimb structura programului și modul de rulare a acestuia.
Pași:
1. Scrierea codului sursă
Pentru a putea fi executată de browser, cla sa principală a appletului trebuie să fie
publică.
2. Salvarea fi șierelor sursă
Ca orice clasă publică, clasa principala a appletului va fi salvată într -un fișier cu
același nume și extensia .java. Să considerăm de exemplu un fișier FirstApplet.java.
3. Co mpilarea

46
Compilarea se face la fel ca și la aplicațiile independente, folosind compilatorul javac
apelat pentru fișierul ce conține appletul.
javac FirstApplet.java
În cazul în care compilarea a reușit va fi generat fisierul FirstApplet.class.
4. Rularea a ppletului
Applet -urile nu ruleaza independent. Ele pot fi rulate doar prin intermediul unui
browser: Internet Explorer, Netscape, Mozilla, Opera, etc. sau printr -un program special cum
ar fi appletviewer din kitul de dezvoltare J2SDK. Pentru a executa un a pplet trebuie să facem
două operații:
• Crearea unui fișier HTML în care vom include applet -ul. Să considerăm fișierul
simplu.html, av ând conținutul de mai jos:
<html>
<head>
<title>Primul applet Java</title>
</head>
<body>
<applet code=FirstApplet.class w idth=400 height=400>
</applet>
</body>
</html>
• Vizualizarea appletului: se deschide fisierul simplu.html folosind unul din browser -ele
amintite sau efectu ând apelul:
appletviewer simplu.html

2.3.2 Ciclul de viață al unui applet
Execuția unui applet înce pe în momentul în care un browser afișează o pagină Web în
care este inclus appletul respectiv și poate trece prin mai multe etape. Fiecare etapă este str âns
legată de un eveniment generat de către browser și determină apelarea unei metode specifice
din cl asa ce implementează appletul.
Metodele specifice applet -urilor
Există o serie de metode specifice appleturilor ce sunt apelate automat la diverse
evenimente generate de către browser. Acestea sunt definite în clasa Applet și sunt enumerate
în tabelul de m ai jos:

47

Metoda Situația în care este apelată
init La inițializarea appletului. Teoretic, această metodă ar trebui să se apeleze
O singură dată, la prima afișare a appletului în pagină, însă, la unele browsere
Este posibil ca ea să se apeleze de mai multe ori.
start Imediat după inițializare și de fiecare dată când appletul redevine activ, după
o oprire temporară.
stop De fiecare dată când appletul nu mai este vizibil (pagina Web nu mai este
vizibilă, fereastra browserului este minimizată, etc) și îna inte de destroy .
destroy La închiderea ultimei instanțe a browserului care a încărcat în memorie clasa
principală a appletului.

2.3.3 Interfața grafică cu utilizatorul
După cum am văzut, clasa Applet este o extensie a superclasei Container, ceea ce
înseamnă că appleturile sunt, înainte de toate, suprafețe de afișare.
Plasarea componentelor, gestionarea poziționării lor și tratarea evenimentelor generate
se realizează la fel ca și în cazul aplicațiilor care folosesc interfețe grafice . Uzual, adăugarea
componentelor pe suprafața appletului precum și stabilirea obiectelor responsabile cu tratarea
evenimentelor generate sunt operațiuni ce vor fi realizate în metoda init.
Gestionarul de poziționare implicit este FlowLayout, însă acesta poate fi schimbat prin
metoda setLayout.
Desenarea pe suprafața unui applet
Există o categorie întreagă de appleturi ce nu comunică cu utilizatorul prin intermediul
componentelor ci, execuția lor se rezumă la diverse operațiuni de desenare realizate în metoda
paint . Reamintim că metoda paint () este responsabilă cu definirea aspectului grafic al oricărei
componente. Implicit, metoda paint din clasa Applet nu realizează nimic, deci, în cazul în care
dorim să desenăm direct pe suprafața unui applet va fi nevoie să supradefinim aceas tă metodă.
În cazul în care este aleasă această soluție, evenimentele tratate uzual vor fi cele
generate de mouse sau tastatură.

2.3.4 Tag-ul APPLET
Sintaxa completă a tagului APPLET, cu ajutorul căruia pot fi incluse appleturi în
cadrul paginilor Web est e:

48

<APPLET
CODE = clasaApplet
WIDTH = latimeInPixeli
HEIGHT = inaltimeInPixeli
[ARCHIVE = arhiva.jar]
[CODEBASE = URLApplet]
[ALT = textAlternativ]
[NAME = numeInstantaApplet]
[ALIGN = aliniere]
[VSPACE = spatiuVertical]
[HSPACE = spatiuOrizontal] >
[< PARAM NAME = parametru1 VALUE = valoare1 >]
[< PARAM NAME = parametru2 VALUE = valoare2 >]
…
[text HTML alternativ]
</APPLET>
Atributele puse între paranteze pătrate sunt opționale.

2.3.5 Folosirea firelor de execuție în appleturi
La încărcarea unei pagi ni Web, fiecărui applet îi este creat automat un fir de execuție
responsabil cu apelarea metodelor acestuia. Acestea vor rula concurent după regulile de
planificare implementate de mașina virtuală Java a platformei folosite.
Din punctul de vedere al interf eței grafice însă, fiecare applet aflat pe o pagină Web
are acces la un același fir de execuție, creat de asemenea automat de către browser, și care este
responsabil cu desenarea appletului (apelul metodelor update și paint ) precum și cu
transmiterea mesaj elor generate de către componente. Intruc ât toate appleturile de pe pagină
”împart” acest fir de execuție, nici unul nu trebuie să îl solicite în mod excesiv, deoarece va
provoca funcționarea anormală sau chiar blocarea celorlalte.
În cazul în care dorim s ă efectuăm operațiuni consumatoare de timp este recomandat
să le realizăm într -un alt fir de execuție, pentru a nu bloca interacțiunea utilizatorului cu
appletul, redesenarea acestuia sau activitatea celorlalte appleturi de pe pagină.

49
2.4 Clasele folosite în aplicație
2.4.1 Clasa Maze: abstract class Maze
Această clasă abstractă se ocupă de:
 crearea labirintului ca matrice în cadrul constructorului (și desenarea lui apelând
metoda drawGrid() din clasa MazeCanvas). Valorile matricii se vor obține folosind
operații pe biți, împreună cu constantele definite pentru toate situațiile care se pot
întâlni în labirint (direcții, pereți, borduri, drum). Se va folosi și o stivă care
memorează celulele care fac parte din soluție.
 stabilirea aleatoare punctelor de star t și de final în două din cele patru colțuri ale
labirintuluia în cadrul metodei setStartEnd()
 găsirea unei soluții a labirintului în cadrul metodei solveMaze() prin metoda urmăririi
pereților .
Exemplu cod:
static final int
NORTH=0, N_WALL=0x01, N_BORDER=0x10, N_PATH=0x100, CN_PATH=0x1100,
EAST =1, E_WALL=0x02, E_BORDER=0x20, E_PATH=0x200, CE_PATH=0x1200,
SOUTH=2, S_WALL=0x04, S_BORDER=0x40, S_PATH=0x400, CS_PATH=0x1400,
WEST =3, W_WALL=0x08, W_BORDER=0x80, W_PATH=0x800, CW_PA TH=0x1800,
ALL_WALLS=0x0F, C_PATH=0x1000,
N_BACK=0x10000, CN_BACK=0x110000,
E_BACK=0x20000, CE_BACK=0x120000,
S_BACK=0x40000, CS_BACK=0x140000,
W_BACK=0x80000, CW_BACK=0x180000,
C_BACK=0x100000 ;

protected Point startPt, endPt ;
protected int m[][], stack[], stackPtr, cols, rows, totalCells ;
MazeCanvas mc ;
ControlPanel cp ;
MazeGen mg ;
// constructor
Maze(Dimension d,MazeCanvas mc,ControlPanel cp,MazeGen mg) {
this.mc = mc ; t his.cp = cp ; this.mg = mg ;
cols = d.width ; rows = d.height ;
totalCells = cols * rows ;
// initializare stivă, care va conține celulele din soluție
stack = new int[totalCells] ;
// se inițializează matricea cu toți pereții, se setează bordurile
m = new int[cols][rows] ;
for (int i=0; i<cols; i++) {

50
for (int j=0; j<rows; j++) {
m[i][j] |= ALL_WALLS ;
if (j==0) m[i][0] |= N_BORDER ;
if (i==(cols -1)) m[i][j] |= E_BORDER ;
if (j==(rows -1)) m[i][j] |= S_BORDER ;
if (i==0) m[0][j] |= W_BORDER ;
}
}
// desenare grila
if (cp.isShowGen()) {
mc.drawGrid(this) ;
mg.sleep(500) ;
}
}

void setStartEn d() {
//setarea aleatoare a punctelor de start și de final în colțuri opuse
switch (randomInt(4)) {
case 0: startPt = new Point(0,0) ;
endPt = new Point(cols -1,rows-1) ;
break ;
case 1: startPt = new Point(cols -1,0) ;
endPt = new Point(0,rows -1) ;
break ;
case 2: startPt = new Point(cols -1,rows-1) ;
endPt = new Point(0,0) ;
break ;
case 3: startPt = new Point(0,rows -1) ;
endPt = new Point(cols -1,0) ;
break ;
}
}

// metoda de rezolvare a labrintului
void solveMaze() {
int direction[]=new int[4], candidates=0, choice=0 ;
int x=startPt.x, y=startPt.y ;

stackPtr = 0 ;
m[x][y] |= C_PATH ;
while ((x!=endPt.x)||(y!=endPt.y)) {
candidates = 0 ;
// prima dată se verifică pereții vecini, apoi se verifică dacă
// s-a mai trecut prin acea locație
if ( ((m[x][y]&N_WALL)==0)&&((m[x][y -1]&C_PATH)==0)&&
((m[x][y -1]&C_BACK)==0) ) direction[candidates++] = NORTH ;
if ( ((m[x][y]&E_WALL)==0)&&((m[x+1][y]&C_PATH)==0)&&

51
((m[x+1][y]&C_BACK)==0) ) direction[candidates++] = EAST ;
if ( ((m[x][y]&S_WALL)==0)&&((m[x][y+1]&C_PATH)==0)&&
((m[x][y+1]&C_BACK)==0) ) direction[candidates++] = SOUTH ;
if ( ((m[x][y]&W_WALL)==0)&&((m[x -1][y]&C_PATH)==0)&&
((m[x-1][y]&C_BACK)==0) ) direction[can didates++] = WEST ;

// dacă există cel puțin o directie în care se poate merge
if (candidates != 0) {
// se alege aleator o direcție
choice = direction[randomInt(candidates)] ;
stack[stackPtr++] = choi ce ;
switch (choice) {
// se setează drumul, se schimbă celula curentă
case NORTH: m[x][y –] |= N_PATH ;
m[x][y] |= CS_PATH ;
break ;
case EAST: m[x++][y] |= E_PATH ;
m[x][y] |= CW_PATH ;
break ;
case SOUTH: m[x][y++] |= S_PATH ;
m[x][y] |= CN_PATH ;
break ;
case WEST: m[x –][y] |= W_PATH ;
m[x][y] |= CE_PATH ;
break ;
}
// se desenează drumul până la noua celulă
if (cp.isShowSolve()) {
mc.drawSolve( x,y,choice,mg.pathColor,this) ;
mg.sleep(cp.getSolveDelay()) ;
}
}
else {
// nu se mai poate continua, ne întoarcem
// și se desenează urma de venire înapoi
choice = stack[–stackPtr] ;
if (cp.isShowSolve()) {
mc.drawSolve(x,y,choice,
cp.isShowBack()?mg.backColor:mg.bkgrndColor,this) ;
mg.sleep(cp.getSolveDelay()) ;
}
switch ( choice) {
// se renunță la drum, se setează drumul de revenire
// se revine la celula anterioara
case NORTH: m[x][y] &= ~CS_PATH ;
m[x][y] |= CS_BACK ;
m[x][++y] &= ~N_PATH ;

52
m[x][y] |= N_BACK ;
break ;
case EAST: m[x][y] &= ~CW_PATH ;
m[x][y] |= CW_BACK ;
m[–x][y] &= ~E_PATH ;
m[x][y] |= E_BACK ;
break ;
case SOUTH: m[x][y] &= ~CN_PATH ;
m[x][y] |= CN_BACK ;
m[x][–y] &= ~S_PATH ;
m[x][y] |= S_BACK ;
break ;
case WEST: m[x][y] &= ~CE_PATH ;
m[x][y] |= CE_BACK ;
m[++x][y] &= ~W_PATH ;
m[x][y] |= W_BACK ;
break ;
}
}
if ((stackPtr==1)&&cp.isShowSolve())
mc.drawStartEnd(startPt,endPt) ;
}
if (cp.isShowSolve())
mc.drawStartEnd(startPt,endPt) ;
else mc.drawPath(cp.isShowBack(),this) ;
}

2.4.2 Clasa MazeDFS : final class MazeDFS extends Maze
Această clasă extinde clasa Maze și implementează algoritmul de generare a
labirintului folosind Căutarea în adâncime .
Exemplu de cod:
void setWalls() {
int direction[]=new int[4], visited=0, candidates= 0, choice=0 ;
// se alege un punct aleator de pornire
int x=randomInt(cols), y=randomInt(rows) ;
stackPtr = 0 ;
visited = 1 ;
while(visited < totalCells) {
candidates = 0;
// se caută toate direcțiile în care se poate merge din celula
curenta
// prima dată se cauta bordurile, apoi se verifică dacă toti
pereții sunt intacti
if (((m[x][y]&N_BORDER)==0)&&((m[x][y -1]&ALL_WALLS)==ALL_WALLS))

53
direction[candidates++] = NORTH ;
if (((m[x][y]&E_BORDER)==0)&&((m[x+1][y]&ALL_WALLS)==ALL_WALLS))
direction[candidates++] = EAST ;
if (((m[x][y]&S_BORDER)==0)&&((m[x][y+1]&ALL_WALLS)==ALL_WALLS))
direction[candidates++] = SOUTH ;
if (((m[x][y]&W_BO RDER)==0)&&((m[x -1][y]&ALL_WALLS)==ALL_WALLS))
direction[candidates++] = WEST ;

if (candidates != 0) {
// se salveaza celula curentă și se alege aleator o direcție
choice = direction[randomInt(candidates) ] ;
stack[stackPtr++] = choice ;
// se șterge din labirint peretele din direcția selectată
if (cp.isShowGen()) {
mc.drawGen(x,y,choice,this) ;
mg.sleep(cp.getGenDelay()) ;
}
switch (choice) {
// se desfiinteaza peretele și se seteaza noua celula
case NORTH: m[x][y] &= ~N_WALL ;
m[x][–y] &= ~S_WALL ;
break ;
case EAST: m[x][y] &= ~E_WALL ;
m[++x][y] &= ~W_WALL ;
break ;
case SOUTH: m[x][y] &= ~S_WALL ;
m[x][++y] &= ~N_WALL ;
break ;
case WEST: m[x][y] &= ~W_WALL ;
m[–x][y] &= ~E_WALL ;
break ;
}
visited++ ;
}
else {
// punct mort, revenire la celula anterioară
switch (stack[ –stackPtr]) {
// modificarea celulei curente
case NORTH: y++ ; break ;
case EAST: x – ; break ;
case SOUTH: y – ; break ;
case WEST: x++ ; break ;
}
}
}
}
2.4.3 Clasa MazeKruskal : final class MazeKruskal extends Maze

54
Această clasă extinde clasa Maze și implementează algoritmul de generare a
labirintului folosind algoritmul lui Kruskal .
Exemplu de cod:
void setWalls() {
// matricea care memoreaza peretii
// primele doua coloane reprezinta coordonatele peretelui
// a treia coordonata reprezinta directia
int walls[][]=new int[(totalCells*2) -cols-rows][3], wallsPtr=0 ;
int index=0, visited =1, direction=0, root1=0, root2=0 ;
int x1=0, y1=0, x2=0, y2=0 ;

for (int i=0; i<cols; i++) {
for (int j=0; j<rows; j++) {
// fiecare celula se plaseaza în clasa sa de echivalenta
uf[(j*cols)+i] = -1 ;
// se adau ga toti peretii interiori (doar N și W)
if (i!=0) {
walls[wallsPtr][0] = i ;
walls[wallsPtr][1] = j ;
walls[wallsPtr++][2] = WEST ;
}
if (j!=0) {
walls[wallsPtr ][0] = i ;
walls[wallsPtr][1] = j ;
walls[wallsPtr++][2] = NORTH ;
}
}
}
while (visited < totalCells) {
// se alege aleator o celula perete
index = randomInt(wallsPtr –) ;
x1 = walls[index][0] ;
y1 = walls[index][1] ;
direction = walls[index][2] ;
// se inlatura peretele din tablou
if (index!=wallsPtr)
for (int i=0; i<3; i++) walls[index][i] = walls[wallsPtr][i] ;
// se cauta o celula în cealalta parte a peretelui
if (direction==NORTH) { x2 = x1 ; y2 = y1 – 1 ; }
else { x2 = x1 – 1 ; y2 = y1 ; }
// se cauta radacinile
root1 = find(x1+(y1*cols)) ;
root2 = find(x2+(y2*cols)) ;
// celule le sunt din aceeasi clasa?
if (root1 != root2) {
// dacă nu, se conecteaza cei doi arbori

55
union(root1,root2) ;
visited++ ;
// și se desfiinteaza peretele
if (direction == NORTH) {
m[x1][y1] &= ~N_WALL ;
m[x2][y2] &= ~S_WALL ;
}
else {
m[x1][y1] &= ~W_WALL ;
m[x2][y2] &= ~E_WALL ;
}
// se sterge peretele de pe suprafata de desenare
if (cp.isShowGen()) {
mc.drawGen(x1,y1,direction,this) ;
mg.sleep(cp.getGenDelay()) ;
}
}
}
}

int find(int n) {
if (uf[n]<0) return n ;
return uf[n]=find(uf[n]) ;
}

void union(int r1, int r2) {
if (uf[r1]<=uf[r2]) {
uf[r1] += uf[r2] ; //se adauda dimensiunea lui r2 la r1
uf[r2] = r1 ; //r2 indica spre r1
}
else {
uf[r2] += uf[r1] ;
uf[r1] = r2 ;
}
}

2.4.4 Clasa Ma zePrim : final class MazePrim extends Maze
Această clasă extinde clasa Maze și implementează algoritmul de generare a
labirintului folosind algoritmul lui Prim .
Exemplu de cod:

void setWalls() {
Vector out=new Vector(totalCells) ;
Vector fro ntier=new Vector(totalCells) ;

56
Vector in=new Vector(totalCells) ;
Point cell=null, nCell=new Point(0,0), eCell=new Point(0,0),
sCell=new Point(0,0), wCell=new Point(0,0) ;
int[] direction=new int[4] ;
int index=0, candidates=0, choice=0 ;
// initializare – toate celulele sunt în Out
for (int i=0; i<cols; i++)
for (int j=0; j<rows; j++)
out.addElement(new Point(i,j)) ;
// se alege aleator o celula care se muta în In
index = randomInt(tot alCells) ;
cell = (Point)out.elementAt(index) ;
moveCell(out, in,index) ;
// celulele vecine celei de start se muta în Frontier
if (cell.x>0)
moveCell(out,frontier,out.indexOf(new Point(cell.x -1,cell.y))) ;
if (cell.y>0)
moveCell(out,frontier,out.indexOf(new Point(cell.x,cell.y -1))) ;
if (cell.x<(cols -1))
moveCell(out,frontier,out.indexOf(new Point(cell.x+1,cell.y))) ;
if (cell.y<(rows -1))
moveCell(out,frontier,out.indexOf(new Point(c ell.x,cell.y+1))) ;

while (!frontier.isEmpty()) {
// se muta o celula aleatoare din Frontier în In
index = randomInt(frontier.size()) ;
cell = (Point)frontier.elementAt(index) ;
moveCell(frontier, in,index) ;
// se muta vecinii celulei alese din Out în Frontier
if (cell.x>0) {
wCell.x = cell.x – 1 ; wCell.y = cell.y ;
moveCell(out,frontier,out.indexOf(wCell)) ;
}
if (cell.y>0) {
nCell.x = cell.x ; nCell.y = cell.y – 1 ;
moveCell(out,frontier,out.indexOf(nCell)) ;
}
if (cell.x<(cols -1)) {
eCell.x = cell.x + 1 ; eCell.y = cell.y ;
moveCell(out,frontier,out.indexOf(eCell)) ;
}
if (cell.y<(rows -1)) {
sCell.x = cell.x ; sCell.y = cell.y + 1 ;
moveCell(out,frontier,out.indexOf(sCell)) ;
}
// se cauta vecinii celulei care sunt în In
candidates = 0 ;

57
if (cell.x>0)
if (in.indexOf(wCell)>=0) direction[candidates++] = WEST ;
if (cell.y>0)
if (in.indexOf(nCell)>=0) direction[candidates++] = NORTH ;
if (cell.x<(cols -1))
if (in.indexOf(eCell)>=0) direction[candidates++] = EAST ;
if (cell.y<(rows -1))
if (in.indexOf(sCell)>=0) direction[candidates++] = SOUTH ;
// se alege aleator un vecin
choice = direction[randomInt(candidates)] ;
// se sterge peretele dintre celule de pe suprafata de afisare
if (cp.isShowGen()) {
mc.drawGen(cell.x,cell.y,choice,this) ;
mg.sleep(cp.getGenDelay()) ;
}
switch (choice) { // se sterge peretele
case NORTH: m[cell.x][cell.y] &= ~N_WALL ;
m[cell.x][cell.y -1] &= ~S_WALL ;
break ;
case EAST: m[cell.x][cell.y] &= ~E_WALL ;
m[cell.x+1][cell.y] &= ~W_WALL ;
break ;
case SOUTH : m[cell.x][cell.y] &= ~S_WALL ;
m[cell.x][cell.y+1] &= ~N_WALL ;
break ;
case WEST: m[cell.x][cell.y] &= ~W_WALL ;
m[cell.x -1][cell.y] &= ~E_WALL ;
break ;
}
}
}
void moveCell(Vector from, Vector to, int index) {
if (index!= -1) {
to.addElement((Point)from.elementAt(index)) ;
from.removeElementAt(index) ;
}
}

2.4.5 Clasa MazeCanvas : final class MazeCanvas extends Canvas
Această clasă extinde clasa Canvas și reprezintă suprafața pe care se desenează
labirintul pe tot parcursul execuției aplicației (pe parcursul generării și rezolvării labirintului).
Pentru a nu obține efecte vizuale neplă cute la desenarea labirintului, se folosește un buffer de
imagine dublu.
Exemplu de cod:

58
Image bufferImage ;
Graphics buffer ;
MazeGen mg ;

MazeCanvas(int mcw,int mch) {
width = mcw ; height = mch ;
}
private void drawInit(Maze mz) {
cols = mz.getCols() ; rows = mz.getRows() ;
cellSize = (int)Math.min(MAX_CELL_SIZE,
Math.min((width -BORDER)/cols,(height -BORDER)/rows)) ;
mzWidth = cellSize * cols ;
mzHeight = cellSize * rows ;
wOffset = (int)((width -mzWidth)/2) ;
hOffset = (int)((height -mzHeight)/2) ;
pathSize = (int)(cellSize/2) -1 ;
nwPathOffset = (int)((cellSize -pathSize)/2) ;
sePathOffset = cellSize – pathSize – nwPathOffset ;
if (buffer==null) {
bufferImage = createImage(width,height) ;
buffer = bufferImage.getGraphics() ;
}
// se deseneaza fundalul
buffer.setColor(mg.appletColor);
buffer.fillRect(0,0,width,height) ;
buffer.setColor(mg.bkgrndColor);
buffer.fillRect(wOffset,hOffset,mzWidth,mzHeight) ;
// draw outer maze frame
buffer.setColor(mg.frameColor);
buffer.draw3DRect(wOffset -2,hOffset -2,mzWidth+4,mzHeight+4,true) ;
buffer.drawRect(wOffset -1, hOffset -1, mzWidth+2, mzHeight+2) ;
}

2.4.6 Clasa ControlPanel : final class ControlPanel extends Panel
Această clasă se ocupă de realizarea interfeței grafice. Aceasta va conține în partea
stângă un obiect de tip MazeCanvas, iar în dreapta va fi un Panel care reunește toate celelalte
componente grafice.
Atribute:
static final int MIN_CELLS=3, MAX_W_CELLS=50, MAX_H_CELLS=50,
MAX_DELAY=500, MIN_DELAY=5 ;
private int rows=20, cols=20, genDelay=50, solveDelay=50 ;
private Button bGen, bSolve, bCycle ;
private Button bRowsPlus, bRowsMinus, bColsPlus, bColsMinus ;
private TextField tfRows, tfCols ;

59
private Checkbox cbShowGen, cbShowSolve, cbShowBack ;
private Choice cAlgorithm ;
private Scrollbar sbGenSpeed, sbSolveSpeed ;
private Font monoFont = new Font("Courier", Font.BOLD, 12) ;
private Font textFont = new Font("Helvetica", Font.PLAIN, 12) ;
private Font boldFont = new Font("Helvetica", Font.BOLD, 12) ;
private Panel rowsPanel, colsPanel, rowsBtnPanel, colsBtnPanel ;
private Maze Gen mg ;
private MazeCanvas mc ;
private Panel p = new Panel() ;

2.4.7 Clasa MazeGen : public class MazeGen extends Applet implements Runnable
Aceasta este clasa principală care extinde clasa Applet și implementează interfața
Runnable. În cadrul ei se stabilesc culorile componentelor grafice, se desenează suprafața
grafică și se tratează evenimentele apărute în urma intervenției utilizatorului (apăsare butoane,
bifare/debifare, alegere element din listă). Interfața Runnable este implementată pentru a crea
un thread, pentru care se folosește metoda sleep() .

60
Capitolul 3. Utilizarea aplicației

Aplicația are două funcții principale: cea de generare a unui labirint prin aplicarea a
diverși algoritmi și cea de rezolvare a labirintului generat.

Generarea unui labirint:
Implicit, la pornirea aplicației se va genera un labirint de 20 linii/20 coloane.
Utilizatorul poate alege pentru labirintul care se dorește a fi generat, numărul de linii și
numărul de coloane, care sunt restricționate din program la un interval de valori cuprins între
3 și 50.
Labirintul de 20 linii/20 coloane are cea mai mare dimensiune, astfel că pentru valori
mai mari ale numărului de linii sau de coloane, labirintul nu va ocupa o suprafață mai mare, ci
va avea celule mai mic i. Labirinturile care au mai puțin de 20 linii sau 20 de coloane vor
ocupa o suprafață mai mică.
Pentru a evita posibilele valori nevalide pentru numărul de linii sau de coloane,
casetele de text corespunzătoare lor nu pot fi editate de către utilizator, valorile putând fi
modificate doar cu ajutorul butoanelor – și + din dreptul lor.
Aplicația are implementați algoritmii de generare a unui labirint perfect: DFS, Kruskal
și Prim. Utilizatorul poate alege din listă unul din aceștia (implicit este DFS).
După ce utilizatorul stabilește dimensiunea labirintului și algoritmul de generare dorit,
se apasă butonul GENERARE .
Generarea labirintului se poate face în două moduri: cu vizualizarea pas cu pas a
generării sau doar a rezultatului final. Pentru aceasta, se va bifa sau nu checkbox -ul Afișare
gen. Deasemenea, se poate stabili viteza cu care se generează labirintul, utilizatorul putând
controla acest lucru prin scrollbar -ul Viteza generare (din program, viteza de generare va fi
determinată de diverse valori de milisecunde date metodei sleep() ).
Intrarea și ieșirea din labirint se stabilesc aleator din program, fiind întotdeauna în
colțuri opuse ale labirintului. Intrarea este semnalizată printr -un pătrat verde, iar ieșirea printr –
un pătrat roșu.

61
Procesul de generare a unui labirint 20×20 folosind DFS

Labirint de 30×30 generat complet folosind DFS

62
Labirint de 30×30 generat complet folosind Kruskal

Labirint de 30×30 generat complet folosind Kruskal

63
Rezolvarea labirintului:
După ce avem generat un labirint, putem vizualiza soluția acestuia. Pentu aceasta
trebuie acționat butonul REZOLVARE .
Vizualizarea rezolvării labirintului se poate face în mai multe moduri:
– cu afișarea revenirilor din drumurile care nu conduc spre soluție (ele vor fi desenate cu gri)
– fără afișarea revenirilor din drumurile care nu conduc spre soluție
Pentru aceasta se va bifa sau nu checkbox -ul Afisare Backtrack .
Pe lângă aceasta se poate alege, ca și la generarea labirintului, să se vizualizeze pas cu
pas generarea soluție i sau să se afișeze doar soluția finală. Pentru aceasta se va bifa sau nu
checkbox -ul Afisare Rez .
Ca și la generarea labirintului, se poate stabili viteza cu care se rezolvă labirintul,
utilizatorul putând controla acest lucru prin scrollbar -ul Viteza re zolvare (din program, viteza
de rezolvare va fi determinată de diverse valori de milisecunde date metodei sleep() ).
Ultimul buton, a cărui denumire alternează când este apăsat între CICLARE și STOP
CICLARE are semnificația de a genera și rezolva o singură dată labirintul sau de a -l genera și
rezolva în mod repetitiv.

Procesul de rezolvare a unui labirint, cu afișare reveniri

64
Soluția completă a labirintului, cu afișare reveniri

Soluția completă a unui labirint 25×15, fără afișare reveniri

65
Bibliogra fie

1. *** http://www.astrolog.org/labyrnth/algrithm.htm
2. *** http://www.ccs.neu.edu/home/snuffy/maze/
3. *** http://en.wikipedia.org/wiki/Maze_generation_algorithm
4. *** http://en.wikipedia.org/wiki/Maze_solving_algorithm
5. *** http://www.unmuseum.org/maze.htm
6. Thinking în Java , Bruce Eckel, Prentice Hall, 2002
7. Algoritmi fundamentali în Java. Aplicații , Doina Logofătu, Editura Polirom, 2007
8. Curs practic de Java , de Cristian Frăsinaru
9. Java in a Nutshell , David Flanag an, O'Reilly Media, 2005
10. *** http://java.sun.com