Labirintus algoritmus OFF

[Kis Norbert]

Sziasztok!


Koszi a segitseget labirintus ugyben. 
A kapott egyik linken szenzacios dolgokat lattam. Nagyon 
megnyero. Vegulis majd egy kiseloadast is kell rogtonoznom 
a dologbol, ugyhogy oda a PPT-hez tokeletesek lesznek a 
kepek, illetve az osszefoglalo.

Az algoritmusrol:
No, ejjel nekialltam, s csinaltam egy probaprogit. Mukodik 
is ugy-ahogy, de sajna nemi modositast kellett bevezetni a 
kapott algoritmusba. 

Endre irta:
>Kuldok egy forrast.

Koszi elore is. Szivesen megneznem, hogy en ertettem 
valamit felre a magyarazatbol, vagy az algoritmus 
sajatsaga, ahogy most muxik.

Daniel irta:
1. level.
>Veletlenszeruen, de felvaltva, vizszintesen es 
fuggolegesen huzol 
>"falakat" de mielott elersz egy keresztbe futo falat, 
kihagysz egy 
>rublikat atjaronak. n*m-es matrixban ez n/2+m/2 fal 
huzasat jelenti es
>jo ha paratlan a matrixod.

2. level.
>Az elvet mar elmondtam, az algoritmust neked kell irni ra.
>Szabalyok meg egyszer:
>Fuggolegesen majd vizszintesen huzzuk a csikokat veletlen 
kezdo
>poziciobol, de mindenkeppen faltol kezdve
>Ha a vonal falba utkozne (egybe mindenkeppen fog, a 
szemkoztibe) akkor
>mielott elerne a falat ki kell hagyni egy egyseg helyet.

No, ezek szerint eljarva eleg katasztrofalis lett az 
eredmeny.
A hiba azonban latszott a kepernyon, igy bevezettem 
szabalynak: Nemcsak akkor kell ajtot kihagyni, ha falhoz 
erek. A feltetel 3 eset vagy-kapcsolata: 
1., eppen vonalon allok (ugyanis moge atjaro kell majd)
2., eppen falnak mennek, ha egyet lepnek
3., eppen elertem a matrix szelet

Megcsinaltam igy. Javult, de akkor is eleg ortoped formaja 
lett. (Persze faltol falig ment, az utolso elemet kihagyva, 
illetve a keresztezesnel is egyet.) Rengeteg korbezart 
egyseg alakult ki. (Attol fuggoen, hogy a random generatort 
milyen kezdoertekkel inditom, most 2^16-fele labirintusom 
lehet, igy jol tesztelhetok, reprodukalhatok a problemas 
esetek.) Persze ehhez jon, hogy a matrixot at lehet 
meretezni... :)))
Vegigneztem parat, de 1..2 kivetellel hasznalhatatlanok 
voltak.
Az ok prozai: Egyik oldalrol televonallal indulok, hacsak 
nincs keresztezo sav. Igy eleg egyhangu lett a kep. Erre 
bevezettem, hogy egy adott forgasi irany menten haladva 
kezdem a random-vonalakat. Pl.: fugoleges baloldal egyik 
sora, majd vizszintes also oldal egyik oszlopa, fugguleges 
jobboldal egyik sora, vizszintes felso oldal egyik oszlopa, 
s igy tovabb ciklusban. Ez eppen az oramutato jarasaval 
ellentetes forgas, de lehet egyezo iranyban is, mind1. Igy 
lett a ketto helyett negy vonalhuzo ciklusom, amiket 
hivogatok. 
Ez mar egesz jo eredmenyt adott, de meg mindig bibis volt a 
dolog... Ugyanis ha szomszedos sort, vagy oszlopot huzok 
melle, akkor bezarja a "szobakba" onmagat, mondhatni: 
befalazom az ajtot. :))))
Persze erre bevezettem ujabb szabalyt: vonal melle nem 
huzunk kozvetlen parhuzamos vonalat. Igy a durva 
befalazasok megszuntek.
Masik bibi, hogy ahova huztam vonalat, nem huzhatok 
megegyszer, hiszen a keresztben azota nyilt atjarokat is 
behuztam ezzel. Ezert kell + ez a szabaly is... 
Mar kezdtem orulni, de az eredmeny megse lett egeszen 
tokeletes: nehany esetben (ha a kuldott peldaprogramnal 
765, 555, stb.. ertekekkel inditok) 
Nagymeretu, 'ajtajasincs' szobak alakulnak ki. Bar a 
legtobb esetben mostmar a teljes labirintus bejarhato 
maradt. (pl.: 0,1,2,3 ... tokeletes) Vegulis majdnem jo, de 
csak _majdnem_. Hajnali 1-ig eddig jutottam el. Fontos az 
is, hogy a labirintus akkor a legszebb, ha a matrix 
negyzetes.
Masik bibi, hogy a szeleknel eleg elvarazsolt a mintazat, 
illetve ott a bejarhatosaggal is bibi lesz. Megoldaskent 
erre azt talaltam ki, hogy a be es kijaratnal hagyok ki egy 
teljesen ures egysoros folyosot. (Bejarat: baloldal 
fuggoleges, kijarat: jobboldal, fuggoleges. Ezert a 
matrixot elol-hatul 1-el nagyobbra vettem.)

A probakeppen BASIC-ben irt tesztprogit mellekelem alant. 
(Nem eppen a koderek gyonyore, meg a vegen ctrl+break-el 
kell kilepni, de ez most mellekes, ugyiscsak tesztverzio. 
A lenyeg, hogy mutatja magat.) Ha mast nem, talan a 
tobbieknek is tanulsagos a dolog.
A "grafika" csak karakteres, de persze a vegleges verzioban 
grafikusra csinalom, s nyilvan C-- lesz a dologbol, vagy 
ASM. Ha tobb idom is lenne ra, akkor meg 3D.

Koszi mindenkinek meg1* a segitseget.

Udv.:
		Norbi.
A progi: (Csak gwbasic, qbasic, tbasic alatt tesztelve.)
10 KEY OFF:CLEAR:SCREEN 0,0,0:CLS:A=49:B=19:DIM T
(A+1,B+1):REM A*B meret+rnd-k
20 INPUT"Kerem a labirintus kodszamat:",VK:RANDOMIZE VK
80 FOR Q=1 TO 5:GOSUB 100:GOSUB 1000:GOSUB 250:GOSUB 
1000:REM forgo rajzciklus
85 GOSUB 150:GOSUB 1000:GOSUB 200:GOSUB 1000:NEXT
99 END
100 REM random vizszintes elore huzo...
110 GOSUB 400:FOR LX=1 TO A
120 IF T(LX,LY)=0 AND T(LX+1,LY)=0 AND LX<A THEN T(LX,LY)=1
130 NEXT:RETURN
150 REM random vizszintes hatra huzo...
160 GOSUB 400:FOR LX=A TO 1 STEP -1
170 IF T(LX,LY)=0 AND T(LX-1,LY)=0 AND LX>1 THEN T(LX,LY)=1
180 NEXT:RETURN
200 REM random fuggoleges elore huzo...
210 GOSUB 300:FOR LY=1 TO B
220 IF T(LX,LY)=0 AND T(LX,LY+1)=0 AND LY<B THEN T(LX,LY)=1
230 NEXT:RETURN
250 REM random fuggoleges hatra huzo...
260 GOSUB 300:FOR LY=B TO 1 STEP -1
270 IF T(LX,LY)=0 AND T(LX,LY-1)=0 AND LX>1 THEN T(LX,LY)=1
280 NEXT:RETURN
300 REM Sulyozott RND az x=koordinatara...
305 GOSUB 340:IF TESZT=1 THEN RETURN
310 LX=INT(RND*A)+1:IF T(LX-1,B+1)=1 OR T(LX+1,B+1)=1 OR T
(LX,B+1)=1 THEN 310
320 T(LX,B+1)=1
330 RETURN
340 REM teszteljuk, hogy van -e kitoltetlen sor. Ha nincs, 
akkor nincs dolgunk
350 TESZT=1:FOR VEGE=1 TO A:IF T(VEGE,B+1)=0 THEN TESZT=0
360 NEXT:RETURN
399 RETURN
400 REM Sulyozott RND az Y-koordinatara...
405 GOSUB 440:IF TESZT=1 THEN STOP:REM ez meg nem muxik, 
mert a szomszedelemekkel nem szamoltam...
410 LY=INT(RND*B)+1:IF T(A+1,LY-1)=1 OR T(A+1,LY+1)=1 OR T
(A+1,LY)=1 THEN 410
420 T(A+1,LY)=1:T(A+1,LY-1)=1:T(A+1,LY+1)=1:REM foglaltra 
allitjuk a 3-as csop.
430 RETURN
440 REM teszteljuk, hogy van -e kitoltetlen sor. Ha nincs, 
akkor nincs dolgunk
450 TESZT=1:FOR VEGE=1 TO B:IF T(A+1,VEGE)=0 THEN TESZT=0
460 NEXT:RETURN
499 RETURN
1000 REM labirintus megjelenito rutin...
1005 PX=20:PY=1:REM LOCATE PY,PX+1:PRINT STRING$(A,88):REM 
PX,PY kezdokoordinatak inicializalasa...
1006 REM LOCATE PY+B+1,PX+1:PRINT STRING$(A,88) ----> Ez 
itt a keret 3 sora, de most lekapcsoltam oket.
1007 REM FOR KY=0 TO B+1:LOCATE KY+PY,PX:PRINT"X";
1008 REM LOCATE KY+PY,PX+A+1:PRINT"X";:NEXT:LOCATE 
PY+1,PX:PRINT" ";:LOCATE PY+B,PX+A+1:PRINT" ";
1010 FOR KX=1 TO A:FOR KY=1 TO B:LOCATE KY+PY,KX+PX:P$="Ű"
1015 IF T(KX,KY)=0 THEN P$="."
1020 PRINT P$;:NEXT:NEXT:RETURN