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

Basic and Machine Language

Moderator: Moderators

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

Post by 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
de Lagash
Posts: 574
Joined: Thu Sep 07, 2006 8:35 am

Post by 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.
User avatar
GreyGhost
Vic 20 Nerd
Posts: 525
Joined: Wed Oct 05, 2005 11:10 pm

Post by 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)?
Rob
Leeeeee
soldering master
Posts: 396
Joined: Fri Apr 23, 2004 8:14 am

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

Post by Mike »

GreyGhost wrote: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
User avatar
GreyGhost
Vic 20 Nerd
Posts: 525
Joined: Wed Oct 05, 2005 11:10 pm

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

Post by Mike »

GreyGhost wrote: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
Class of '6502
Posts: 5516
Joined: Wed Mar 10, 2004 1:41 am

Post by 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?
Anders Carlsson

Image Image Image Image Image
User avatar
GreyGhost
Vic 20 Nerd
Posts: 525
Joined: Wed Oct 05, 2005 11:10 pm

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

Post by 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.
Post Reply