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

Basic and Machine Language

Moderator: Moderators

Athlor
Vic 20 Drifter
Posts: 30
Joined: Mon Sep 01, 2008 11:58 pm

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

Post by Athlor »

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
Image
Last edited by Athlor on Tue Sep 16, 2008 2:13 am, edited 1 time in total.
JJ Abrams Star Trek: Boldly going where we've already been...
User avatar
Jeff-20
Denial Founder
Posts: 5759
Joined: Wed Dec 31, 1969 6:00 pm

Post by Jeff-20 »

I remember the original as being a much longer program... interesting.
High Scores, Links, and Jeff's Basic Games page.
User avatar
eslapion
ultimate expander
Posts: 5458
Joined: Fri Jun 23, 2006 7:50 pm
Location: Canada
Occupation: 8bit addict

Post by eslapion »

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.
Be normal.
Athlor
Vic 20 Drifter
Posts: 30
Joined: Mon Sep 01, 2008 11:58 pm

Post by Athlor »

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.
JJ Abrams Star Trek: Boldly going where we've already been...
User avatar
Mike
Herr VC
Posts: 4816
Joined: Wed Dec 01, 2004 1:57 pm
Location: Munich, Germany
Occupation: electrical engineer

Post by Mike »

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.
Last edited by Mike on Fri Sep 19, 2008 12:09 am, edited 2 times in total.
nippur72
de Lagash
Posts: 574
Joined: Thu Sep 07, 2006 8:35 am

Post by nippur72 »

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.
User avatar
Mike
Herr VC
Posts: 4816
Joined: Wed Dec 01, 2004 1:57 pm
Location: Munich, Germany
Occupation: electrical engineer

Post by Mike »

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
Vic 20 Drifter
Posts: 30
Joined: Mon Sep 01, 2008 11:58 pm

Post by Athlor »

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. :D
JJ Abrams Star Trek: Boldly going where we've already been...
nippur72
de Lagash
Posts: 574
Joined: Thu Sep 07, 2006 8:35 am

Post by nippur72 »

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
User avatar
Mike
Herr VC
Posts: 4816
Joined: Wed Dec 01, 2004 1:57 pm
Location: Munich, Germany
Occupation: electrical engineer

Post by Mike »

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.
User avatar
Mike
Herr VC
Posts: 4816
Joined: Wed Dec 01, 2004 1:57 pm
Location: Munich, Germany
Occupation: electrical engineer

Post by Mike »

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. :D
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
Vic 20 Drifter
Posts: 30
Joined: Mon Sep 01, 2008 11:58 pm

Post by Athlor »

Now that's what I'm talking about. You da man.
Very nice Mike, ah er assembly dude! :wink:
JJ Abrams Star Trek: Boldly going where we've already been...
nippur72
de Lagash
Posts: 574
Joined: Thu Sep 07, 2006 8:35 am

Post by nippur72 »

Well done Mike, I see you read in $C000, is that for getting pseudo-random values, right? (that would be a nice shortcut).
DanSolo
Vic 20 Dabbler
Posts: 88
Joined: Sat Apr 21, 2007 5:22 am

Post by DanSolo »

Save me fingers and put this on a .d64 please. :lol:
Athlor
Vic 20 Drifter
Posts: 30
Joined: Mon Sep 01, 2008 11:58 pm

Post by Athlor »

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.
JJ Abrams Star Trek: Boldly going where we've already been...
Post Reply