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

[Mike]

The size of MAZE.PRG is 202 bytes, of which 2 are the loading address.

Regards shrinking your C version:

- Replace the peek(), and poke() functions with macros, like I did.
- Instead of using putchar(), and puts() for screen initialisation, poke text- and colour-RAM yourself.
- Replace rand(), with a table-lookup of (more or less) random values in ROM (also @nippur72), like I did.

In that way, you don't need to include stdio.h, and stdlib.h anymore, so (hopefully) only the absolutely necessary parts of the runtime library are included.

Maybe that gets the executable size below 1K.

Michael

[nippur72]

I also suggest declaring all variables outside the main function, making them "global" and not stack-allocated.

I don't know how cc65 works in detail, but I suspect it adds lots of overheading if a variable is in the stack. This because the 6502 doesn't have specific stack-dedicated istructions like in modern microprocessors, so they have to be emulated.

[GreyGhost]

I hope, its just an emulator thing, but every time i run the ML version I get the same maze. Also, is it possible to use the entire screen(22x23 with a border around the screen of course so, i guess 20x21)?

[Leeeeee]

There is no random number generator. The code uses the first 256 bytes of the BASIC ROM as a source of random bytes so you will always get the same maze.

Lee.

[Mike]

I hope, its just an emulator thing, but every time i run the ML version I get the same maze.

Emphasis by me.

Always when that kind of assumption crops up, I wonder why.

This is just plain machine code, no hardware hacks, and nowhere near to bring even a most basic implementation of VICE to its limits. It literally could not have any idea, that it is not running on a real VIC, but running in an emulator.

Lee is right, the first 256 bytes of BASIC are used as "random" number table, but that had already been pointed out by nippur72, a few postings above. I just initialise the seed index in $BD to 0, that's the reason you always get the same maze.

Also, is it possible to use the entire screen (22x23 with a border around the screen of course so, i guess 20x21)?

Of course it is possible to produce mazes of nearly arbitrary size. Only restriction is, the vertical and horizontal size must be odd, and at least 5.

The extra space around the maze simplifies the algorithm somewhat. If it isn't there, you'll need to add some code, so you don't peek from addresses outside the screen.

Michael

[GreyGhost]

My apologies, I didn't mean to offend anyone and never thought this little ML program pushed any limits of Vice. I did see the the part above about how it generates random numbers also. I guess I need to ask a different question.


I have a basic program that I am working on and would like to use this maze generator in the program. I have tried writing a simple loop around the SYS call in your program. What do I need to do to use this? How do i need to set up BASIC to use the program for myself.

thanks,

[Mike]

I have tried writing a simple loop around the SYS call in your program. What do I need to do to use this? How do I need to set up BASIC to use the program for myself.

As it is, the executable is currently assembled for an unexpanded VIC-20, and directly writes to screen memory at 7680.

However you can embed this in an own program as follows:

First the BASIC start needs to be lifted to 4352:

Code: Select all

1 PRINT"{CLR}POKE4352,0:POKE44,17:NEW"
2 PRINT"{2 DOWN}LOAD"CHR$(34)"MAIN"CHR$(34)","PEEK(186)
3 POKE631,19:POKE632,13:POKE633,131:POKE198,3

PEEK(186) must be located outside the quotes. Then, within MAIN you load, and execute MAZE.PRG:

Code: Select all

1 X=RND(-TI):CLR
2 DN=PEEK(186):SYS57809"MAZE.PRG",DN,1:POKE780,0:SYS65493
3 POKE4119,RND(1)*256:SYS4110
4 ...

where POKE4119,... will provide different seeds for the RNG.

If you need a relocated version, or want to use screen memory at another address, you'll need to re-assemble the source.

Greetings,

Michael

[carlsson]

I played some Fairchild Channel F games the other day, of which one is a maze game. It has some variations, of which one has a grid drawn onto the screen:

Code: Select all

*********************
* * * * * * * * * * *
*********************
* * * * * * * * * * *
*********************
* * * * * * * * * * *
*********************
* * * * * * * * * * *
*********************
* * * * * * * * * * *
*********************
* * * * * * * * * * *
*********************
* * * * * * * * * * *
*********************
* * * * * * * * * * *
*********************
* * * * * * * * * * *
*********************
* * * * * * * * * * *
*********************

As you move around in the maze, exits open up when you hit a wall. Eventually you find your way out of the maze. To implement this game, the maze generator could store its maze in second half of colour memory, given the screen dimensions 22*23. The routine could automatically determine which half is currently unused. Then you remove blocks accordingly to what is stored in the hidden part of colour memory.

Since colour memory can store 4 bit nybbles, the game could even get enhanced so some walls need to be hit several times before opening, using different colours or patterns. Does this kind of game already exist or do anyone think it sounds fun to implement, now when half the work is already done?

[GreyGhost]

Thanks, I speak as a child at times when it comes to the vic 20. Its harder these days to dive into the deeper mechanics of it all; I haven't the time I had when i was young.

I see, loc 4119 is the key. I also see that learning some hex numbers might be helpful also. So I can change the value in loc 4119 thru 4375( i'm guessing this is the first 256 bytes of basic) or just 4119 to randomize?

And carlsson, you have given me a great idea for a tidbit game. im gonna start on it tonight.

thanks again,

[Mike]

The location 4119 has no special meaning.

In that case, it happens to contain the immediate field of a LDA instruction, and the following STA stores this into the zeropage address $BD, which is designated by my program to contain an index into the first 256 bytes of the BASIC ROM, serving as "random" numbers.

If you POKE random values somewhere else into the program you'll most probably make it crash.

[GreyGhost]

I did a little modding of the original BASIC program and got it to use most of the Vic screen:

Code: Select all

10 d(0)=2:d(1)=-44:d(2)=-2:d(3)=44:w=160:h=32:s=7680:co=38400:a=s+23
20 fori=0to505:pokeco+i,0:pokes+i,160:next:fori=21to505step22:pokes+i,32:next
30 pokea,4
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 goto20

I also tried modding the ML version to do the same thing, but something is amiss. It still draws a maze, but something isn't working right.

Code: Select all

*=$100e        ;SYS 4110
   LDA #$18
   STA $900f
begin   
   LDA #$2D
   STA $FB
   LDA #$1E
   STA $FC
   LDA #$00
   STA $BD
   LDA #$15
   STA $00
   LDA #$1E
   STA $01
   LDX #$00
scrn_set
   LDA #$a0
   STA $1e00,x
   STA $1f00,x
   LDA #$00
   STA $9600,x
   STA $9700,x
   INX
   BNE scrn_set
   LDX #$17
stripe
   LDA #$20
   LDY #$00
   STA ($00),y
   CLC
   LDA $00
   ADC #$16
   STA $00
   BCC stripe1
   INC $01
stripe1
   DEX
   BNE stripe
   LDA #$04
   STA $1E1b
   LDY #$00
label2
   JSR $e094
   LDX $8d
   LDA $C000,X
   AND #$03
   STA $9B
   STA $9C
label3
   LDX $9B
   CLC
   LDA $FB
   ADC maze3,X
   STA $FD
   LDA $FC
   ADC maze2,X
   STA $FE
   LDA ($FD),Y
   CMP #$A0
   BNE label4
   LDA $9B
   STA ($FD),Y
   CLC
   LDA $FB
   ADC maze1,X
   STA $FB
   LDA $FC
   ADC maze2,X
   STA $FC
   LDA #$20
   STA ($FB),Y
   LDA $FD
   STA $FB
   LDA $FE
   STA $FC
   JMP label2
label4
   INX
   TXA
   AND #$03
   STA $9B
   CMP $9C
   BNE label3
   LDA ($FB),Y
   TAX
   LDA #$20
   STA ($FB),Y
   CPX #$04
   BCS label1
   SEC
   LDA $FB
   SBC maze3,X
   STA $FB
   LDA $FC
   SBC maze2,X
   STA $FC
   JMP label2
label1
   LDA $c5   
   CMP #$20
   BNE label1
stop
   JMP begin
maze1
   byte $01,$ea,$ff,$16
maze2
   byte $00,$ff,$ff,$00
maze3   
   byte $02,$d4,$fe,$2c,$ff

Sometimes it leaves the D marker on the screen. I also made it choose its own random numbers, so It gives a new maze each time.

[GreyGhost]

Also, the ML program above fills the screen with value 160 and then draws a stripe down the right side of the screen. I know there has to be a better, shorter way to draw that stripe. Any advise?

[wimoos]

I played with the Basic program and rewrote it in Wimbasic. The routine is 225 bytes in size and lists as follows:

Code: Select all

10 d(0)=2:d(1)=-44:d(2)=-2:d(3)=44:w=160:h=32:a=23
20 space0,0,21,22,w,1:space21,0,21,22:cokea,4
30 j=rnd(4)and3:c=j
40 b=a+d(j):ifb>0:ifb<505:ifceek(b,s)=w:cokeb,j:cokea+d(j)/2,h:a=b:goto30
50 j=(j+1)and3:ifj=c:j=ceek(a,s):cokea,h:ifj<4:a=a-d(j):goto30else20else40

Using Wimbasic makes it easily transportable to other memory configurations.

Regards,

Wim.

[nbla000]

I played...

OT ?: Welcome back Anders

[Jeff-20]

That was one year ago.