a pewno bawi│e╢ siΩ kiedy╢ znajdowaniem drogi przez labirynt. Tego typu │amig│≤wki do╢µ czΩsto sa umieszczane w pismach dla dzieci. Mnie jednak zawsze zastanawia│o co innego ni┐ tylko samo rozwi▒zanie tego bardzo trudnego zadania:) Pr≤bowa│em dociec, jak taki labirynt siΩ tworzy. To oczywi╢cie nic nadzwyczaj trudnego. Jest to jednak doskona│e zadanie, w sam raz do wykonania przez komputer. Konstruowanie algorytmu rozwi▒zuj▒cego ten problem jest do╢µ przyjemne, wiΩc na co czekaµ? Zakodujmy go, tym razem mo┐e w C++. Poni┐ej przedstawiane kody nadaj▒ siΩ do skompilowania w Borland C++ 3.1dla Dosa. Ich dostosowanie do innego kompilatora ogranicza siΩ do przerobienia mechanizmu wy╢wietlania labiryntu na ekranie komputera.
Najpierw trzeba sprecyzowaµ, co tak naprawdΩ chcemy napisaµ. Chodzi nam o program, kt≤ry wygeneruje losowy labirynt, o kt≤rym bΩdzie wiadomo, ┐e istnieje w nim przej╢cie miΩdzy dwoma wybranymi polami. Dodatkowo, niejako przy okazji sprawdzania przej╢cia miΩdzy dwoma polami, kt≤re bΩdzie czΩ╢ci▒ algorytmu, bardzo │atwo mo┐na zaimplementowaµ pokazywanie tej drogi na ekranie, ale o tym p≤╝niej.
Przed podej╢ciem do pisania programu skonkretyzujmy, jak nasz labirynt ma wygl▒daµ. W przypadku proponowanym przeze mnie, jest to plansza podzielona na kwadratowe pola, z kt≤rych ka┐de mo┐e byµ elementem ╢ciany (czyli tym, przez kt≤ry nie mo┐na przej╢µ) lub elementem drogi (czyli tym, kt≤rym mo┐na siΩ przemieszczaµ po labiryncie).
Poniewa┐ przedstawiany przeze mnie program bΩdzie napisany w C++, na pocz▒tek dobrze by│oby nasz labirynt jako╢ sensownie zaprojektowaµ, aby by│ dobrze reprezentowany w pamiΩci i aby mo┐na by│o na nim dokonywaµ pewnych operacji, takich jak generowanie i wy╢wietlanie. Jak │atwo siΩ domy╢liµ, stworzymy specjaln▒ klasΩ "labirynt" i obiekt tej klasy "lab".
Co musi posiadaµ nasza klasa, aby mog│a reprezentowaµ labirynt? Najwa┐niejszym elementem jest kwadratowa tablica, kt≤rej pola bΩd▒ odpowiada│y polom labiryntu - ╢cianie lub drodze. TablicΩ tΩ nazwijmy "tab" i nadajmy jej wymiary 50x50 p≤l. Wydaje siΩ, ┐e takie rozmiary s▒ do╢µ rozs▒dnym wyborem. Ka┐de pole tablicy bΩdzie musia│o zawieraµ dwie informacje: czy w danym miejscu jest ╢ciana (1) czy te┐ jej nie ma (0), oraz czy w pr≤bach przej╢cia odwiedzono ju┐ to pole (1 - tak, 0 - nie). Tak druga w│a╢ciwo╢µ na razie mo┐e byµ dla Ciebie trochΩ niejasna, ale w przysz│o╢ci bΩdzie potrzebna. W zwi▒zku z takimi potrzebami nasza tablica bΩdzie zawieraµ elementy typu strukturowego. Opr≤cz tego, klasa bΩdzie zawieraµ potrzebn▒ p≤╝niej informacjΩ o wsp≤│rzΩdnych pola, do kt≤rego chcemy zawΩdrowaµ od pola wej╢ciowego przez labirynt. Przy generowaniu labiryntu te informacje bΩd▒ niezbΩdne, aby by│o mo┐na sprawdziµ, czy istnieje przej╢cie przez labirynt. Wsp≤│rzΩdne te nazwijmy "xk" i "yk". BΩdziemy te┐ potrzebowaµ funkcji, kt≤ra powie nam, czy istnieje przej╢cie miΩdzy polem pocz▒tkowym a ko±cowym. Nazwiemy j▒ "int przechodni(int,int)". Funkcja zwraca 1, gdy przej╢cie istnieje lub 0, gdy jego brak. Jako argumenty bΩdziemy jej podawaµ wsp≤│rzΩdne pola pocz▒tkowego (wsp≤│rzΩdne pola ko±cowego bΩd▒ dostΩpne, gdy┐ s▒ zadeklarowane jako sk│adowe klasy). To, co om≤wili╢my dotychczas, deklarujemy jako sk│adowe prywatne klasy. Teraz czas na sk│adowe publiczne, dzieki kt≤rym bΩdziemy mogli w programie bezpo╢rednio wykorzystywaµ konkretny obiekt utworzonego typu. BΩd▒ to konstruktor, kt≤remu podaje siΩ jako argumenty wsp≤│rzΩdne pocz▒tkowego i ko±cowego pola, destruktor (raczej dla zasady - jest niepotrzebny tym razem) oraz funkcja "show()", rysuj▒ca wygenerowany labirynt na ekranie. Deklaracja naszej klasy bΩdzie wygl▒daµ tak:
class labirynt {
private:
struct tab{int mur,odw;};
tab tab[50][50];
int xk,yk;
int przechodni(int,int);
public:
labirynt(int,int,int,int);
~labirynt() {}
show();
};
Przejd╝my teraz do omawiania konkretnych metod. Zaczniemy od tej wywo│ywanej zwykle jako finalna czΩ╢µ algorytmu, mianowicie od funkcji "show()". Wygl▒da ona bardzo prosto. Wyja╢niΩ tylko, ┐e ka┐de pole labiryntu to na ekranie kwadracik o boku d│ugo╢ci 5 pikseli. ªciana ma u nas kolor bia│y, droga - czarny (domy╢lny po zainicjowaniu trybu graficznego). Ponadto pola nale┐▒ce do drogi miΩdzy polem pocz▒tkowym a ko±cowym bΩd▒ kolorowane nie na czarno, a na czerwono. DziΩki temu bΩdziemy mogli podziwiaµ bezpo╢rednie efekty dzia│ania funkcji sprawdzaj▒cej istnienie przej╢cia, to ona bowiem bΩdzie zaznaczaµ pola jako odwiedzone. Nasza funkcja rysuj▒ca wygl▒da tak:
labirynt::show(){
rectangle(0,0,5*50,5*50);
int x,y;
for (x=0;x<50;x++)
for (y=0;y<50;y++)
if (tab[x][y].mur){
setfillstyle(1,15);
bar(x*5,y*5,x*5+5,y*5+5);
} else if (tab[x][y].odw) {
setfillstyle(1,4);
bar(x*5,y*5,x*5+5,y*5+5);
}
}
My╢lΩ, ┐e powy┐szy kod jest zrozumia│y?
Teraz czas przej╢µ do zdefiniowania konstruktora. BΩdziemy w nim wykorzystywaµ funkcjΩ "int przechodni(int, int)". Za│≤┐my, ┐e jest ona ju┐ zdefiniowana. Faktycznie jej definicjΩ na razie zostawimy sobie na koniec. PrzypomnΩ, ┐e funkcja ta zwraca 1, gdy istnieje przej╢cie przez labirynt z pola wej╢ciowego, kt≤rego wsp≤│rzΩdne podajemy jej jako argumenty do pola ko±cowego, kt≤rego wsp≤│rzΩdne bΩdzie ona sprawdzaµ z prywatnych sk│adowych klasy "xk" oraz "yk".
Nasz konstruktor dostaje jako argumenty wsp≤│rzΩdne pola pocz▒tkowego i ko±cowego drogi. Najpierw ca│y labirynt jest "zamurowywany" w pΩtli. Jednocze╢nie wszystkie pola labiryntu trzeba oznaczyµ na pocz▒tku jako jeszcze nieodwiedzone. NastΩpnie "odmurowywujemy" pola pocz▒tkowe i ko±cowe. To logiczne, gdy┐ nie by│oby sensowne szukanie przej╢cia miΩdzy nimi, gdyby by│y murem. Kolejny krok to ustalenie warto╢ci sk│adowych "xk" i "yk". Jest to mo┐liwe dziΩki dw≤m ostatnim argumentom podanym konstruktorowi. Po tym fragmencie znajduje siΩ g│≤wny "trzon" algorytmu. Jest to pΩtla, tak d│ugo usuwaj▒ca mur przez jego usuwanie z losowo wybranych p≤l labiryntu, jak d│ugo nie istnieje przej╢cie miΩdzy polami pocz▒tkowym i ko±cowym. Jest to jednak tylko jeden z wielu mo┐liwych do zastosowania algorytm≤w generowania. W zasadzie jest to algorytm z natury z│y, gdy┐ jest bardzo wolny, a ponadto zawsze bΩdzie istnia│o tylko jedno przej╢cie, co wbrew pozorom wcale nie utrudnia osobie, kt≤rej poka┐emy nasz labirynt, znalezienia przej╢cia przez niego metod▒ kartki i o│≤wka. Wydaje siΩ, ┐e lepsze rezultaty czasowe dawa│by algorytm, w kt≤rym powoli zape│nialiby╢my puste pola "murem" a┐ do utracenia przej╢cia i usunΩli ustatnio postawion▒ czΩ╢µ muru, ale oznacza│oby to problemy z pamiΩci▒. Jak zaraz zobaczysz, funkcja "int przechodni(int,int)" jest funkcj▒ rekurencyjn▒ opart▒ na bardzo nieefektywnych algorytmach z nawrotani. W przypadku przez nas rozwa┐anym, gdy labirynt ma wymiary 50x50 p≤l, oznacza│oby to 2500 poziom≤w wywo│a± rekurencyjnych na pocz▒tku, czego nie wytrzyma│by program napisany za pomoca Borland C++, gdy┐ po prostu zabrak│oby mu pamiΩci. Z do╢wiadczenia wiem, ┐e to dla takiego programu by│oby kilka razy za du┐o do zrobienia, w zwi▒zku z powy┐szym u┐yty zosta│ algorytm, w kt≤rym mur siΩ burzy, a nie buduje, gdy┐ wtedy poziom zag│Ωbienia rekurencji jest znacznie ni┐szy (odpadaj▒ sytuacje rekurencyjnego wchodzenia w mur b▒d╝ przebijania siΩ przez niego).
labirynt::labirynt(int x1,int y1,int x2,int y2){
int x,y;
for (x=0;x<50;x++)
for (y=0;y<50;y++){
tab[x][y].mur=1;
tab[x][y].odw=0;
}
tab[x1][y1].mur=0;
tab[x2][y2].mur=0;
xk=x2;
yk=y2;
while (!przechodni(x1,y1)) tab[random(50)][random(50)].mur=0;
}
Pozosta│a nam do zrobienia jeszcze jedna funkcja, do╢µ niewdziΩczna, sprawdzaj▒ca istnienie przej╢cia miΩdzy polami. Wygl▒da ona do╢µ nieciekawie z powodu potrzeby sprawdzania wielu warunk≤w zwizanych z kontrol▒ zakresu tablicy, jednak sam algorytm u┐yty do jej stworzenia wbrew pozorom nie jest skomplikowany. Ca│a funkcja jest po prostu realizacj▒ klasycznego algorytmu z nawrotami, czyli wywo│uje siΩ rekurencyjnie, pr≤buj▒c "wΩdrowaµ" po ca│ym labiryncie, omijaj▒c oczywi╢cie murki. UWAGA: "x1" i "y1" to nie te same zmienne co w przypadku konstruktora!!! Zbie┐no╢µ nazw jest jedynie przypadkowa! Tutaj s▒ to zmienne aktualnie odwiedzanego pola. W wywo│aniu tej metody w konstruktorze, s▒ to jednocze╢nie wsp≤│rzΩdne pola pocz▒tkowego, czyli wnioskujemy, ┐e sprawdzanie przechodnio╢ci labiryntu zaczyna siΩ odwiedzeniem pola pocz▒tkowego. Tablica "ruchy" zawiera struktury ze wsp≤│rzΩdnymi umo┐liwiaj▒cymi │atwiejsze, automatyczne przemieszczanie siΩ do s▒siednich p≤l. Mo┐emy siΩ przemie╢ciµ jedno pole do g≤ry, na d≤│, w prawo lub w lewo. Jak widzisz, z ka┐dego pola s▒ mo┐liwe co najwy┐ej cztery ruchy, po skosie wiΩc nie da rady siΩ przemie╢ciµ. Funkcja "wchodz▒c" na pole oznacza je jako odwiedzone, gdy bΩdzie siΩ z niego wycofywaµ w przypadku niepowodzenia, odznaczy je. Potrzebna jest te┐ zmienna tymczasowa "temp". Pocz▒tkowo ma zawsze warto╢µ 1. Je╢li jednak funkcja nie zosta│a wywo│ana dla pola ko±cowego, jest to sygna│, ┐e jeszcze trzeba szukaµ drogi i byµ mo┐e ona nie istnieje (zostaje wysnute takie za│o┐enie). Wtedy zmienn▒ tΩ siΩ zeruje. NastΩpnie wykonuje siΩ pr≤by ruch≤w. Dokonuje siΩ tu kontroli zakresu tablic i kontroli, czy pole, na kt≤re chce siΩ wej╢µ, nie jest przypadkiem zamurowane lub odwiedzone (gdyby by│o odwiedzone, algorytm by siΩ zapΩtli│!!!). Sprawdza siΩ tak┐e zmienn▒ "temp" i przypisuje jej warto╢µ kolejno wykonywanej rekurencyjnie funkcji "int przechodni(int, int)" dla nowego pola. Chodzi o to, ┐e je╢li w jakim╢ podrzΩdnym poziomie rekurencji stwierdzi siΩ istnienie przej╢cia, to mo┐na zrezygnowaµ z dalszych poszukiwa± na wy┐szych poziomach. W ten spos≤b wynik jest rekurencyjnie podawany od ostatniego, najni┐szego poziomu, do najwy┐szego, a┐ w ko±cu jest zwracany konstruktorowi klasy, kt≤ry wywo│a│ funkcjΩ. Kolejne wywo│ania rekurencyjne moga zag│Ωbiaµ siΩ do stwierdzenia, ┐e jest przej╢cie miΩdzy polami pocz▒tkowym i ko±cowym, lub ┐e w danej ga│Ωzi wywo│a± rekurencyjnych nie ma ju┐ mo┐liwo╢ci "ruchu".
int labirynt::przechodni(int x1,int y1){
struct {int x,y;} ruchy[4]={{-1,0},{0,-1},{0,1},{1,0}};
tab[x1][y1].odw=1;
int temp=1;
int r;
if (!((x1==xk)&&(y1==yk))) temp=0;
for (r=0;r<4;r++)
if ((x1+ruchy[r].x>=0)&&(x1+ruchy[r].x<=49)&&
(y1+ruchy[r].y>=0)&&(y1+ruchy[r].y<=49)&&
((tab[x1+ruchy[r].x][y1+ruchy[r].y].mur)==0)&&
((tab[x1+ruchy[r].x][y1+ruchy[r].y].odw)==0)&&
(temp==0))
temp=przechodni(x1+ruchy[r].x,y1+ruchy[r].y);
if (temp==1) return 1; else {tab[x1][y1].odw=0; return 0;}
}
My╢lΩ, ┐e po moich wyja╢nieniach rozumiesz ju┐, jak mo┐na wygenerowaµ labirynt i znale╝µ w nim drogΩ. No to ┐eby nie by│o ci weso│o: podany algorytm jest STRASZNIE powolny. Wynika to z powstawania niekorzystnych uk│ad≤w dr≤g. S▒ one albo bardzo kr≤tkie, albo tworz▒ du┐e pola prostok▒tne (czΩsto ale oczywi╢cie nie zawsze). Zwykle punktem najbardziej blokuj▒cym wygenerowanie algorytmu jest brak przej╢cia od pola pocz▒tkowego/ko±cowego do sieci powsta│ych ju┐ korytarzy, spowodowany zwykle cienk▒ ╢ciank▒ wok≤│ tego pola. Warto wiΩc pokusiµ siΩ o modyfikacjΩ konstruktora i ju┐ na wej╢cie "wyburzyµ" wok≤│ tych dw≤ch p≤l wszystkie s▒siednie murki.
A oto, jak mo┐esz ju┐ w praktyce wykorzystaµ stworzon▒ klasΩ, wywo│uj▒c j▒ na przyk│ad z funkcji "main()":
main()
{
randomize();
int dr=DETECT,mo;
initgraph(&dr,&mo,"c:/prog/borlandc/bgi");
labirynt lab(0,0,49,49);
lab.show();
getch();
while (kbhit()) getch();
closegraph();
return 0;
}
Nie zapomnij o w│▒czeniu odpowiednich plik≤w nag│≤wkowych!!!
