Compute! Maze Generator in Basic, C and now Assembly!!!

[wimoos]

This is a conversion into WimBasic that shows a maze with a four times higher resolution.
For the "breadcrumbs" I used the spare color memory at $9600 (line 9).

Regards,

Wim.

Code: Select all

1 gosub7
2 print"{clr}":£k=1:£l=1:i=rnd(-ti):set£k,£l:pokefnl(0),4
3 £j=int(rnd(1)*4):£c=£j
4 £m=£k+x(£j):if£m<.or£m>£pthen6:else£n=£l+y(£j):if£n<.or£n>£qthen6
5 ifpoint£m,£n:elseset£k+x(£j)/2,£l+y(£j)/2:£k=£m:£l=£n:set£k,£l:pokefnl(0),£j:goto3
6 £j=(£j+1)and3:if£j=£c:£j=fnp(0):if£j<4:£k=£k-x(£j):£l=£l-y(£j):goto3:else2:else4
7 deffnl(i)=£b+£k/2+int(£l/2)*22:deffnp(i)=peek(fnl(0))and15:data0,2,0,-2,2,0,-2,0
8 £p=43:£q=45:dimx(3),y(3):fori=0to3:readx(i),y(i):next
9 £b=(xor(peek($0288),2)and3or$94)*256:return

[Mike]

I'd like to follow-up with yet another one, which this time utilises the 160x192 bitmap mode of MINIGRAFIK:

Code: Select all

10 T=RND(-TI):DIMBI(7),D(4),S%(9,95):BI(0)=1:FORT=1TO7:BI(T)=4*BI(T-1):NEXT
11 D(1)=2:D(3)=-2:DEFFNS(X)=X+65536*(X>32767):DEFFNU(X)=X-65536*(X<0)
12 @ON:@CLR:AX=2:AY=2:FORT=1TO157:@1,T,1TOT,189:NEXT
13 J=INT(RND(1)*4):C=J
14 BX=AX+D(J+1):BY=AY+D(J):IF@(BX,BY)=0THEN17
15 T=BX/2AND7:S%(BX/16,BY/2)=S%(BX/16,BY/2)ANDNOTFNS(3*BI(T))ORFNS(J*BI(T))
16 @0,AX,AYTOBX,BY:AX=BX:AY=BY:GOTO13
17 J=J+1AND3:IFJ<>CTHEN14
18 T=AX/2AND7:J=FNU(S%(AX/16,AY/2)ANDFNS(3*BI(T)))/BI(T)
19 IFAX<>2ORAY<>2THENAX=AX-D(J+1):AY=AY-D(J):GOTO13
20 GETA$:ON-(A$="")GOTO20:@RETURN

The backtracking information (the "breadcrumbs") is stored in the array S%(), yet the program still only requires a +8K RAM expansion, which is necessary for running MINIGRAFIK anyway. Here's a screenshot:



This takes quite a long time though... unless you run it in VICE with 'Maximum Speed > No limit'.

Cheers,

Michael

[tokra]

You know what's coming now, don't you?

Code: Select all

10 t=rnd(-ti):dimbi(7),d(4),s%(12,127):bi(0)=1:fort=1to7:bi(t)=4*bi(t-1):next
11 d(1)=1:d(3)=-1:deffns(x)=x+65536*(x>32767):deffnu(x)=x-65536*(x<0)
12 clear:ax=2:ay=2:fort=1to205:draw1,t,1tot,253:next:draw0,2,2
13 j=int(rnd(1)*4):c=j
14 bx=ax+2*d(j+1):by=ay+2*d(j):ifpoint(bx,by)=0then17
15 t=bx/2and7:s%(bx/16,by/2)=s%(bx/16,by/2)andnotfns(3*bi(t))orfns(j*bi(t))
16 draw0,ax+d(j+1),ay+d(j)tobx,by:ax=bx:ay=by:goto13
17 j=j+1and3:ifj<>cthen14
18 t=ax/2and7:j=fnu(s%(ax/16,ay/2)andfns(3*bi(t)))/bi(t)
19 ifax<>2oray<>2thenax=ax-2*d(j+1):ay=ay-2*d(j):goto13
20 show

That's right, the MAXIGRAFIK-version

[Mike]

You know what's coming now, don't you? [...] That's right, the MAXIGRAFIK-version

Wow! I did some small improvements though, while you were posting your adaptation.

How about a C128 version?

Code: Select all

10 T=RND(-TI):DIMBI(7),D(4),S%(19,99):BI(0)=1:FORT=1TO7:BI(T)=4*BI(T-1):NEXT
11 GRAPHIC1,1:BOX1,1,1,317,197,,1:D(1)=2:D(3)=-2:AX=2:AY=2
12 DEFFNS(X)=X+65536*(X>32767):DEFFNU(X)=X-65536*(X<0)
13 J=INT(RND(1)*4):C=J
14 BX=AX+D(J+1):BY=AY+D(J):LOCATEBX,BY:IFRDOT(2)=0THEN17
15 T=BX/2AND7:S%(BX/16,BY/2)=S%(BX/16,BY/2)ANDNOTFNS(3*BI(T))ORFNS(J*BI(T))
16 DRAW0,AX,AYTOBX,BY:AX=BX:AY=BY:GOTO13
17 J=J+1AND3:IFJ<>CTHEN14
18 T=AX/2AND7:J=FNU(S%(AX/16,AY/2)ANDFNS(3*BI(T)))/BI(T)
19 IFAX<>2ORAY<>2THENAX=AX-D(J+1):AY=AY-D(J):GOTO13
20 GETKEYA$:GRAPHIC0

Suspiciously similar, isn't it?



I had to exchange lines 11 and 12, because C128 BASIC doesn't handle the pointers to DEFined functions correctly when a graphics area first needs to be created (which also moves the function definitions in memory). The BOX command is used to draw the initial filled rectangle.

And, as I've found out, even though only BASIC 3.5 commands are used, this one does not run on C16/C116/+4, because their integer routines are slightly bugged: Integer variables accept everything and reduce to signed MOD 65536 (instead of throwing an error if outside the range -32768 .. 32767, as in V2 and V7) - not that much of a problem, but then the logical operators AND, OR, NOT also do *not* accept the value -32768, flagging an incorrect ?ILLEGAL QUANTITY error. Huh?

[GreyGhost]

wow, these are very cool. I thought about doing that before, but had no idea how to implement it. Good work guys.

[Mike]

I [...] had no idea how to implement it.

It's really quite simple. The original implementation used the screen to store information how to backtrack from a blind lane. This is a nice method for a text screen buffer, since it can easily hold the information (0 .. 3: directions, 4: start of maze, 32: empty, 160: filled), but it can't be applied directly to the screen bitmap, as every position now only stores 1 bit, on or off.

The screen bitmap is still used to display the maze, but the backtracking information is now stored in the array S%(). Only every fourth position (both X and Y at even coordinates) needs to hold data, so this already reduces the size of the array. Still, we'd end up at 80x96=7680 entries, stored as integers (2 bytes per number) these require 15360 bytes. Ouch!

If you look closer, each position only holds 4 different numbers, 0 .. 3 - you don't need to store the value 4 at X=2, Y=2 at the maze start, instead you simply check for that position (done in line 19). So, all that's needed is to access the integer array as an array holding packed 2-bit numbers. This is done in the lines 15 and 18, cutting down the size of the array to 1920 bytes.

[wimoos]

Aaargh ! I couldn't stand having to set up two four-element arrays to convert some predefined numbers. Also I wanted to do something with USR(), so I composed the following.

In (the WimBasic implementation of) MAZE, the arrays are filled with these values:
X(0)=Y(2)=0
X(1)=Y(3)=0
X(2)=Y(0)=2
X(3)=Y(1)=-2

First improvement: X(0..3) and Y(0..3) only differ in the order of their element values, so Y(P) is the same as X(XOR(P,2)).

Next, when a USR routine is invoked, FAC1 (Zp $61-$66) is filled with the float representation of the parameter. When the routine is finished (RTS), the contents of FAC1 is presented as function value.
With the given values, Zp $63, $64 and $65 will contain zero and need not be touched.
For the other locations:

• Input | Output
  fl.p 61 62 66 | fl.p 61 62 66
  --------------------------
  0.0 00 xx 00 | 0.0 00 xx 00
  1.0 81 xx 00 | 0.0 00 xx 00
  2.0 82 80 00 | 2.0 82 80 00
  3.0 82 C0 00 | -2.0 82 80 80

Now, I set the USR vector to the 20-bytes ML-routine below:

Code: Select all

  lda $61
  beq 1$ ; check 0, do nothing
  eor #$81 ; check 1
  beq 2$ ; convert to zero
  bit $62 
  bvc 3$ ; check 2, do nothing
  asl $62 ; change 3 to 2, set the carry
  ror $66 ; shift carry as sign bit, return -2
3$  rts
2$  sta $61
1$  rts

Now, when you need X(P), just call USR(P). When you need Y(P), call USR(XOR(P,2)).

This was a finger exercise to manipulate simple floats in a USR() routine, without converting to and from integer.

Regards,

Wim

[Kweepa]

The OP maze generator is awesome!
For a different machine code implementation, see the October 1983 Compute!:
http://archive.org/stream/1983-10-compu ... 3/mode/2up
There's a VIC-20 implementation

And here it is:

Code: Select all

10 rem maze (vic)
20 rem maze generator in machine language
50 rem for the vic-20 (any memory size)
100 y=peek(55)+256*peek(56)-202: x=int(y/256): y=y-256*x
110 poke 55,y: poke 56,x: poke 51,y: poke 52,x
120 clr: poke 36879,27: print chr$(142);: x=rnd(-ti)
130 s=peek(55)+256*peek(56): a=s
140 print "{clr}{2 down}loading..."
150 read x$: if x$="xxx" then 200
160 r=asc(x$): q=val(mid$(x$,1-(r<48)))
170 if r<>43 then x=q: goto 190
180 y=s+q: x=int(y/256): y=y-256*x: poke a,y: a=a+1
190 poke a,x: a=a+1: goto 150
200 print "{home}": if peek(210)<>16 then 220
210 poke s+17,16: poke s+45,148: poke s+48,149
220 print "{down}activate with"
230 print "  {rvon}sys"; s+8
240 print "{2 down}press any key for"
250 print "demonstration mazes."
260 print "{2 down}press 'q' when you"
270 print "want to quit.": goto 290
280 sys s+8: print "{home}press key..."
290 get x$: if x$="" then 290
300 if x$<>"q" then 280
310 print "{clr}": poke 36879,27
320 data 1, 0, 234, 255, 255, 255, 22, 0, 169, 45
330 data 133, 87, 169, 22, 133, 89, 169, 30, 133, 88
340 data 133, 90, 169, 25, 141, 15, 144, 32, 95, 229
350 data 32, 148, 224, 165, 143, 41, 7, 201, 2, 48
360 data 245, 160, 0, 153, 0, 150, 153, 0, 151, 200
370 data 208, 247, 162, 0, 160, 0, 169, 160, 145, 89
380 data 200, 192, 21, 208, 249, 24, 165, 89, 105, 22
390 data 133, 89, 144, 2, 230, 90, 232, 224, 21, 208
400 data 229, 160, 0, 169, 4, 145, 87, 32, 148, 224
410 data 165, 143, 41, 3, 133, 1, 170, 10, 168, 24
420 data 185, +0, 101, 87, 133, 91, 185, +1, 101, 88
430 data 133, 92, 24, 185, +0, 101, 91, 133, 89, 185
440 data +1, 101, 92, 133, 90, 160, 0, 177, 89, 201
450 data 160, 208, 18, 138, 145, 89, 169, 32, 145, 91
460 data 165, 89, 133, 87, 165, 90, 133, 88, 76, +87
470 data 232, 138, 41, 3, 197, 1, 208, 189, 177, 87
480 data 170, 169, 32, 145, 87, 224, 4, 240, 26, 138
490 data 10, 168, 162, 2, 56, 165, 87, 249, +0, 133
500 data 87, 165, 88, 249, +1, 133, 88, 202, 208, 238
510 data 76, +87, 96, xxx

http://www.kweepa.com/step/vic20/mazer.prg

It's a weak bit of code, since it relocates it from basic rather than just using relative jumps, but it's fast enough

I updated it to not have to be relocated (so it installs faster), and put it in the cassette buffer (by moving the random maze color from asm to basic):

Code: Select all

10 p=828:fori=0to182:reada:pokep+i,a:next
20 data 169, 45, 133, 87, 169, 22, 133, 89, 169, 30
30 data 133, 88, 133, 90, 169, 5, 160, 0, 153, 0
40 data 150, 153, 0, 151, 200, 208, 247, 162, 0, 160
50 data 0, 169, 160, 145, 89, 200, 192, 21, 208, 249
60 data 24, 165, 89, 105, 22, 133, 89, 144, 2, 230
70 data 90, 232, 224, 21, 208, 229, 160, 0, 169, 4
80 data 145, 87, 32, 148, 224, 165, 143, 41, 3, 133
90 data 1, 170, 10, 168, 24, 185, 235, 3, 101, 87
100 data 133, 91, 185, 236, 3, 101, 88, 133, 92, 24
110 data 185, 235, 3, 101, 91, 133, 89, 185, 236, 3
120 data 101, 92, 133, 90, 160, 0, 177, 89, 201, 160
130 data 208, 18, 138, 145, 89, 169, 32, 145, 91, 165
140 data 89, 133, 87, 165, 90, 133, 88, 24, 144, 188
150 data 232, 138, 41, 3, 197, 1, 208, 189, 177, 87
160 data 170, 169, 32, 145, 87, 224, 4, 240, 25, 138
170 data 10, 168, 162, 2, 56, 165, 87, 249, 235, 3
180 data 133, 87, 165, 88, 249, 236, 3, 133, 88, 202
190 data 208, 238, 240, 144, 96, 1, 0, 234, 255, 255
200 data 255, 22, 0
210 print"{clr}":pokep+15,2+6*rnd(1):sysp:print"{home}press key..."
220 k=peek(197):ifk<>48thenon1-(k=64)goto210,220
230 poke198,0

http://www.kweepa.com/step/vic20/mazer2.prg

[wimoos]

The MAZE kept intruiging me, and especially the spaghetti way of programming it.

Now, WimBasic offers WHILE, WEND and QUIT and I took this as an opportunity to review the algorithm.

Code: Select all

1 deffnl(i)=£b+£k/2+int(£l/2)*22:£p=44:£q=46:£r=-1:£k=1:i=rnd(-ti)
2 deffnr(i)=usr(xor(i,2)):£b=(peek($0288)+2)and3or$94)*256:£l=1:defusrdeek(45)-20
3 while1:print"{clr}":set£k,£l:while1:£j=int(rnd(1)*4):£c=£j:£f=1
4 while£f:£m=£k+usr(£j):if£m>£rif£m<£p£n=£l+fnr(£j):if£n>£rif£n<£qifpoint£m,£nelsequit
5 £j=(£j+1)and3:£f=£j-£c:wend
6 if£fset£k+sgn(usr(£j)),£l+sgn(fnr(£j)):£k=£m:£l=£n:set£k,£l:pokefnl(.),£j
7 if£felse£j=peek(fnl(.))and15:£k=£k-usr(£j):£l=£l-fnr(£j):if£k=1if£l=1quit
8 wend:wend

The USR routine is the ML program from my previous post here.



Regards,

Wim.

[unebonnevie]

>#define poke(q,v) do *(char *)(q) = (v); while(0)

Why the "while(0)" is in the define? I know it's necessary but forgot the reason.

[RJBowman]

I think that this was the same maze generator that was used an Anthony Godshall's "Superchase" game published in a later issue of Compute. He lived in the same town as me and I'd see him sometimes at the local user's group meetings.

[pixel]

>#define poke(q,v) do *(char *)(q) = (v); while(0)

Why the "while(0)" is in the define? I know it's necessary but forgot the reason.

Just to put it into a block, so it won't mess up the code around it. Like brackets around calculations to avoid precedence issues.