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

Athlor · Post by **Athlor** » Wed Sep 10, 2008 12:30 am

I was toying around with Ye Olde Compute! maze generator and got a version running under Cc65 for the Vic. Since there aren't very many examples of programs for it I thought I might as well post this.

Code: Select all

// Compute! maze generator for unexpanded Vic-20
// Chrs: home = 19  clr = 147  rvs = 18  lwr = 14  screen = 7680
#include <stdio.h>
#include <stdlib.h>

signed char peek(unsigned int z) {
  return (*(signed char*)(z));
}

void poke(unsigned int q, signed char v) {
  (*(signed char*)(q) = (v));
}

void main (void) {
  signed char j, c, w = 160, h = 32;
  signed char d[] = {2, -44, -2, 44};
  unsigned int s = 7680, a = s+45, b;

  putchar(147); putchar('\n');     // Clear screen
  for (c=1; c<22; c++) {
    putchar(18);
    puts("                     "); // 21 spaces
  }
  putchar(19);  // Home cursor
  poke(a, 4);
  do{
    j = rand()&3;
    c = j;
l2:
    b = a + d[j];
    if(peek(b) == w) {
      poke(b, j);
      poke(a + (d[j]>>1), h);
      a = b;
      continue;
    }
    j=(j+1)*(j<3);
    if(j != c)  goto l2; // Yuk!
    j = peek(a);
    poke(a, h);
    a -= d[j];
  } while(j < 4);
}

The original Basic version was:

Code: Select all

10 d(0)=2:d(1)=-44:d(2)=-2:d(3)=44
20 w=160:h=32:s=7680:a=s+45
30 print"{clear}":fori=1to21
40 print"{rvson}                     ":next:pokea,4:print"{home}"
50 j=int(rnd(1)*4):c=j
60 b=a+d(j):ifpeek(b)=wthenpokeb,j:pokea+d(j)/2,h:a=b:goto50
70 j=(j+1)*-(j<3):ifj<>cthen60
80 j=peek(a):pokea,h:ifj<4thena=a-d(j):goto50
90 geta$:ifa$=""then90

Post by **Jeff-20** » Wed Sep 10, 2008 1:09 am

I remember the original as being a much longer program... interesting.

eslapion · Post by **eslapion** » Wed Sep 10, 2008 3:33 am

Just for the fun of it, I modded this program to generate mazes on the Protecto 80 column display adapter.

Code: Select all

10 d(0)=2:d(1)=-160:d(2)=-2:d(3)=160 
20 w=160:h=32:s=47104:a=s+81 
30 print"{clear}";:fori=1to23 
40 print"{rvson}";:forsp=1to79:print" ";:next;print:next:pokea,4:print"{home}" 
50 j=int(rnd(1)*4):c=j 
60 b=a+d(j):ifpeek(b)=wthenpokeb,j:pokea+d(j)/2,h:a=b:goto50 
70 j=(j+1)*-(j<3):ifj<>cthen60 
80 j=peek(a):pokea,h:ifj<4thena=a-d(j):goto50 
90 geta$:ifa$=""then90

Very nice results.

Athlor · Post by **Athlor** » Thu Sep 11, 2008 12:31 am

I made an Windows console 80 column version awhile back so I know what you mean. It does indeed look even better. That was the thing I always liked about this routine. You'll find many a long-winded programs that don't look quite as good.

Mike · Post by **Mike** » Thu Sep 11, 2008 2:56 am

This implementation in C avoids the 'goto' statement. The maze is stored in an array.

Code: Select all

/*
 *  maze.c
 *
 *  written 2008-09-11 by Michael Kircher
 */

#include <stdio.h>
#include <stdlib.h>

/* X_SIZE and Y_SIZE should be odd, and greater than 5 */
#define X_SIZE 23
#define Y_SIZE 23

#define BLANK ' '
#define WALL '*'

signed char dx[4]={1,0,-1,0};
signed char dy[4]={0,-1,0,1};

char maze[Y_SIZE][X_SIZE+1];

double rnd(void)
{
  return(rand()/(RAND_MAX+1.0));
}

int drill(int *ay, int *ax, int j)
{
  int by,bx,c=j;
  do
  {
    bx=*ax+2*dx[j];
    by=*ay+2*dy[j];
    if(WALL == maze[by][bx])
    {
      maze[by][bx]=j;
      maze[*ay+dy[j]][*ax+dx[j]]=BLANK;
      *ax=bx;
      *ay=by;
      /* drill successful, ask for a new random direction */
      return(1); 
    }
    j=(j+1)*(j<3);
  } while(j!=c);
  /* ended up in a blind lane */
  return(0);
}

int main(int argc, char *argv[])
{
  int ay,ax,j;
  
  for(ay=0; ay<Y_SIZE; ay++)
  {
    for(ax=0; ax<X_SIZE; ax++)
      if(ax>0 && ay>0 && ax<X_SIZE-1 && ay<Y_SIZE-1)
        maze[ay][ax]=WALL;
      else
        maze[ay][ax]=BLANK;
    maze[ay][ax]='\0';
  }

  if(argc > 1) srand(atoi(argv[1]));
  ay=2;
  ax=2;
  maze[ay][ax]=4;

  do
  {
    while(drill(&ay,&ax,(int)(rnd()*4))) {}
    j=maze[ay][ax];
    maze[ay][ax]=BLANK;
    if(j<4)
    { 
      /* back-track */
      ax=ax-2*dx[j];
      ay=ay-2*dy[j];
    }
  } while(j<4);

  for(ay=0; ay<Y_SIZE; ay++) printf("%s\n",maze[ay]+1);

  exit(EXIT_SUCCESS);
}

Edit: replaced the reference '*j' in foo() by its value. Also c only is used, and thus initialised within foo().

Edit 2: renamed foo() to drill(). Replaced the do-while loop calling drill() by a shorter (empty) while loop. Added some comments.

nippur72 · Post by **nippur72** » Thu Sep 11, 2008 4:08 am

I'm aMAZED by the simplicity of the original basic source code, it's very compact.

I have written a random maze generator too, check this past thread.

Mike · Post by **Mike** » Thu Sep 11, 2008 5:49 am

nippur72 wrote:I'm aMAZED by the simplicity of the original basic source code, ...

I wouldn't call this simplicity, since it only happens by chance, that the real program structure in the longer C source I gave above can be folded into two intermixed loops, inside a third loop, and done by GOTO in BASIC.

... it's very compact.

And of course the original BASIC source can be translated into C that's barely more in length, mainly for boilerplate code, POKE, and PEEK defines:

Code: Select all

#include <stdio.h>
#include <stdlib.h>

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

int main(void)
{
  signed char d[4]={2,-44,-2,44};
  int b,c,i,j,w=160,h=32,s=7680,a=s+45;
  putchar(147); putchar(13);
  for(i=1; i<=21; i++) printf("%c                    \n",18);
  poke(a,4); putchar(19);
l50:c=j=rand()&3;
l60:b=a+d[j]; if(peek(b)==w) {poke(b,j); poke(a+d[j]/2,h); a=b; goto l50;}
    j=(j+1)*(j<3); if(j!=c) goto l60;
    j=peek(a); poke(a,h); if(j<4) {a=a-d[j]; goto l50;}
/* geta$:ifa$=""then90 */
  return(0);
}

But this version will only run on a VIC, as it relies on fixed addresses, and direct access to screen memory.

Greetings,

Michael

Athlor · Post by **Athlor** » Sun Sep 14, 2008 2:49 am

It's always interesting to see another's interpretation. Size was my priority and have since thought of a couple things I would have changed on mine. But what would be really cool now is to get an assembly dude to do a version.

nippur72 · Post by **nippur72** » Mon Sep 15, 2008 4:11 am

looking at line 70

Code: Select all

j=(j+1)*-(j<3)

is it a MOD 4, right? Would it be simpler if written as

Code: Select all

j=(j+1) AND 3

Mike · Post by **Mike** » Mon Sep 15, 2008 5:37 am

Not quite. The expression 'J=(J+1)*-(J<3)' increments the value by one, or resets it to zero, if the value was greater than, or equal to 3 before. It is only for the values -1, 0, 1, 2, or 3, that this expression, and 'J=(J+1) AND 3' lead to the same result:

Code: Select all

(-2+1)*-(-2<3) = -1, (-2+1) AND 3 = 3
 (4+1)*-(4<3)  =  0,  (4+1) AND 3 = 1

As it happens, only the values 0 to 3 are used in the program, so you should be okay with that. Just to note the point.

P.S.: true logical expressions evaluate to -1 in BASIC, to 1 in C. In case someone wondered about the different sign used in both languages.

Mike · Post by **Mike** » Tue Sep 16, 2008 1:06 am

I knew I were right:

Athlor wrote:It's always interesting to see another's interpretation. Size was my priority and have since thought of a couple things I would have changed on mine. But what would be really cool now is to get an assembly dude to do a version.

https://dateipfa.de/.Public/denial/imag ... lyDude.jpg

This data loader writes the executable to disc:

Code: Select all

10 REM ** MAZE
11 OPEN2,8,2,"MAZE.PRG,P,W":FORT=1TO202:READA:PRINT#2,CHR$(A);:NEXT:CLOSE2:END
12 DATA1,16,12,16,216,7,158,32,52,49,49,48,0,0,0,169,45,133,251,169,30,133,252
13 DATA169,0,133,189,169,147,32,210,255,169,13,32,210,255,160,21,169,18,32,210
14 DATA255,169,32,162,21,32,210,255,202,208,250,169,13,32,210,255,136,208,233
15 DATA169,4,141,45,30,169,19,32,210,255,160,0,166,189,232,134,189,189,0,192,41
16 DATA3,133,155,133,156,166,155,24,165,251,125,197,16,133,253,165,252,125,193
17 DATA16,133,254,177,253,201,160,208,34,165,155,145,253,24,165,251,125,189,16
18 DATA133,251,165,252,125,193,16,133,252,169,32,145,251,165,253,133,251,165
19 DATA254,133,252,76,73,16,232,138,41,3,133,155,197,156,208,189,177,251,170
20 DATA169,32,145,251,224,4,176,18,56,165,251,253,197,16,133,251,165,252,253
21 DATA193,16,133,252,76,73,16,32,228,255,240,251,96,1,234,255,22,0,255,255,0,2
22 DATA212,254,44

And here's the source code in the HI BASIC inline assembler. Hex values are prefaced with '&'.

Greetings,

Michael

Code: Select all

REM>Maze
DIM code 1023
FOR pass=4 TO 7 STEP 3
P%=&1001 - 2:O%=code
[OPT pass
 EQUW &1001

.Basic
 EQUW Basic_00
 EQUW 2008
 EQUB &9E
 EQUB &20
 EQUS STR$(Maze)
 EQUB 0
.Basic_00
 EQUB 0
 EQUB 0

.Maze
 LDA #&2D
 STA &FB
 LDA #&1E
 STA &FC

 LDA #0
 STA &BD
  
 LDA #147
 JSR &FFD2
 LDA #13
 JSR &FFD2
 LDY #21
.Maze_00
 LDA #18
 JSR &FFD2
 LDA #32
 LDX #21
.Maze_01
 JSR &FFD2
 DEX
 BNE Maze_01
 LDA #13
 JSR &FFD2
 DEY
 BNE Maze_00
 LDA #4
 STA &1E2D
 LDA #19
 JSR &FFD2
 LDY #0
.Maze_02
 LDX &BD
 INX
 STX &BD
 LDA &C000,X
 AND #3
 STA &9B
 STA &9C
.Maze_03
 LDX &9B
 CLC
 LDA &FB
 ADC Maze_08,X
 STA &FD
 LDA &FC
 ADC Maze_07,X
 STA &FE
 LDA (&FD),Y
 CMP #160
 BNE Maze_04
 LDA &9B
 STA (&FD),Y
 CLC
 LDA &FB
 ADC Maze_06,X
 STA &FB
 LDA &FC
 ADC Maze_07,X
 STA &FC
 LDA #32
 STA (&FB),Y
 LDA &FD
 STA &FB
 LDA &FE
 STA &FC
 JMP Maze_02
.Maze_04
 INX
 TXA
 AND #3
 STA &9B
 CMP &9C
 BNE Maze_03
 LDA (&FB),Y
 TAX
 LDA #32
 STA (&FB),Y
 CPX #4
 BCS Maze_05
 SEC
 LDA &FB
 SBC Maze_08,X
 STA &FB
 LDA &FC
 SBC Maze_07,X
 STA &FC
 JMP Maze_02
.Maze_05
 JSR &FFE4
 BEQ Maze_05
 RTS
.Maze_06
 EQUB &01
 EQUB &EA
 EQUB &FF
 EQUB &16
.Maze_07
 EQUB &00
 EQUB &FF
 EQUB &FF
 EQUB &00
.Maze_08
 EQUB &02
 EQUB &D4
 EQUB &FE
 EQUB &2C
]
NEXT

Athlor · Post by **Athlor** » Tue Sep 16, 2008 2:34 am

Now that's what I'm talking about. You da man.
Very nice Mike, ah er assembly dude!

nippur72 · Post by **nippur72** » Wed Sep 17, 2008 8:07 am

Well done Mike, I see you read in $C000, is that for getting pseudo-random values, right? (that would be a nice shortcut).

DanSolo · Post by **DanSolo** » Thu Sep 18, 2008 2:15 pm

Save me fingers and put this on a .d64 please.

Athlor · Post by **Athlor** » Thu Sep 25, 2008 11:29 pm

Orginal Basic: 274 bytes
Assembly: 244 bytes
C (cc65): 1767 bytes
I wish I could have shaved of some the size of the C version.
Anybody else know how to?
I know not using printf saved 256 bytes.