The algorithm is quite simple: it does have a "drilling head" that is moved randomly as long as it can without going into an already existing tunnel. When the head can no longer be moved, it steps back finding another drilling point. When there are no more drilling points the maze is completed.
It is a slight different version from the classical algorithm because it doesn't use any stack; the maze itself serves as memory.
It's quite slow so VICE's Warp function is suggested.
Code: Select all
basic start compact
100 rem === inits ===
105 dim d(4,5)
110 for t=0 to 3
120 for i=0 to 4
130 read d(t,i)
140 next
150 next
155 dim m(4):for t=0 to 3:m(t)=t:next
160 rem === fill empty maze ===
170 for t=0 to 512
171 poke 7680+t,160
172 poke 38400+t,3
173 next
188 rem nv=0:s=7680:goto270
189 rem === starting point ===
200 v = 7680+10*22+10
205 s = 7680
210 nv = 0
220 rem === main loop ===
225 poke v,22
230 nv = nv + 1
240 x = m(0):gosub 500:if n=0 then goto 300
250 x = m(1):gosub 500:if n=0 then goto 300
252 x = m(2):gosub 500:if n=0 then goto 300
255 x = m(3):gosub 500:if n=0 then goto 300
260 rem === find another drilling point ===
260 poke v,32
265 nv=nv-1
266 if nv=0 then goto 295
270 if peek(s)=22 then v=s:goto 240
280 s = s + 1
285 if s = 8192 then s = 7680
290 goto 270
295 get a$:if a$="" then 295
296 run
300 rem === drills ===
310 v = z
319 rem if rnd(1)< 0.20 then goto 280
320 if rnd(1)< 0.5 then goto 220
321 t=int(rnd(1)*4)
322 i=int(rnd(1)*4)
323 z=m(t):m(t)=m(i):m(i)=z
330 goto 220
500 rem === check drilling direction ====
520 if x=0 then z = v - 22:goto 560
530 if x=1 then z = v + 1 :goto 560
540 if x=2 then z = v + 22:goto 560
550 if x=3 then z = v - 1
560 if z<7680 or z>8208 or peek(z)<>160 then n=5:return
561 if int((z-7680)/22)=(z-7680)/22 then n=5:return
565 n = 0
570 for t=0 to 4
580 if peek(z+d(x,t))<>160 then n=n+1
590 next
595 return
1000 rem === drilling head directions ===
1005 data +1,-1,-23,-22,-21
1010 data +22,-22,-21,+1,+23
1020 data +1,-1,+21,+22,+23
1030 data +22,-22,-23,-1,+21
basic end