Following on from the previous post where I took a VIC20 BASIC game and rewrote it in 6502 assembler, I have a few issues to address.
- Fix bugs that I introduced
- A look at maze generation
- Fix bugs in the original version
- Tidy up the code
- Optimise the code for speed and size
- Improve readability and portability by using names constants
- Test this by writing a PET version
Fix bugs that I introduced
First up, I need to fix some bugs which I introduced in the rewrite.
The first is an odd one, that is no immediately obvious reason how and why it happens.
Normally, the player starts in the middle of the screen, which is actually the bottom of the maze. There is a maze below, but they have to move upwards as there is a solid row of walls two lines below them.
Sometimes (a wonderfully vague and unhelpful term in troubleshooting), sometimes, that solid wall that demarcates the bottom of the maze is broken.
I have highlighted the line in black and you can see gaps.
If you move below that line, it confuses things and it all goes wrong.
I initially "fixed" this by fixing the symptom, that bottom line being broken, rather than the cause.
I added some code to check to see if the maze generation was trying to place a path on that line and blocked it and sent it scurrying back up into the safe bits of the maze.
Later on, I worked out what was happening, and why it was happening, but to understand that, I need to look at how the maze is generated.
It is a random maze, freshly generated every time you start a new game, or the old one gets blown up because you didn't find the bomb in time.
A look at maze generation
To generate the maze, it first fills the maze with walls.
In the starts in the middle and creates paths.
(this is a modified debug build which draws the maze generation progress, see the github link at the end)
It picks a random direction, and sees what is two squares away in that direction. If it is a wall, it moves to that square and creates a path on the way.
It keeps moving in that direction until it hits something which isn't a wall, a previous path, or the edge or the maze.
At that point, it turns 90 degrees counter clockwise and tried to continue in that direction.
That repeats until it has turned a full 360 degrees, at which point, it backtracks to a previous square and tries again.
This continues until it gets back to the start.
That all works well, but I skipped over one detail - how does it know when it hits the edge of the maze?
It is 66 rows of 22 characters
It might look 2D.
It might even look 3D with the red and blue fringing.
But it is in fact 1D.
This is all dealt with linearly, a single run of 1452 squares (66 * 22). To move up or down, it jumps 22 squares in either direction, the width of the maze.
If it were generated using XY co-ordinates, it would be much easier to limit things, but I expect some of the other calculations would be more difficult. I don't know, maybe I will try to rewrite it like that, but not today. (please not today, this is already going to be a very long post)
To mark out the top of the maze, it adds a row of spaces. You can see this at the top where you also get to see what is in RAM before the start of the maze (I could fix that, but I have decided to leave it - for now).
You can see from that the right hand side also is a row of spaces.
This continues along the side of the whole maze.
I did think about trying to disguise that by shrinking the screen, or setting the spaces to be solid blue, but it didn't look right, so I left it alone.
In the generation algorithm, when it finds something which is not a wall, it stops and goes off in a different direction, creating a boundary.
That is the top and the side, what about the bottom?
Well, immediately following the maze in RAM is the top of video RAM, so on the original version, when it was generating the maze, the video RAM was full of spaces, other than the "MAKING MAZE" message on the second line.
A whole row of spaces, creating the 4th boundary of the maze.
How Did I Break It?
When I rewrote the maze generation in 6502 assembler, it was so lightening fast that I didn't actually need the "MAKING MAZE" screen, so I simply removed it.
The first time the game runs, the video RAM is probably going to be the BASIC screen.
That's fine, it is unlikely any of the characters will be walls, so that will work as the bottom boundary of the maze.
When you lose the game and it needs to generate a new maze. At that point, the screen contains the remains of the old maze, INCLUDING SOME WALLS.
Depending on where you finished, that might include places where there were runs of walls.
If it just happens that there is an old wall at the point the maze generator was poking it's nose into the video RAM, it will make a path there.
That won't happen very often, which is why this only happened "sometimes", and I now know never on the first run, which is why I didn't see it very often.
It is nice to get to the point where you understand why something happens, and more importantly, why it only happens sometimes.
To fix that, I moved the maze up in memory and added a row of spaces between the bottom of the maze and the top of video RAM.
A Random Bug
One random bug I caught was in the code which places the timebomb.
Part of that process needs a randomly generated horizontal location.
The maze is 22 characters wide. There are walls left and right, and is a space on the far right, making 19 possible locations.
The original code used int(rnd(0)*20) which will generate a random number from 0-19. (I think that might be a an error in the original, it only needs an offset of 0-18 to make that?)
I got the random number for 0-19 wrong in the first version. My plan was to take a number from 0-3 (4 options) and another from 0-15 (16 options) to get a number from 0-19 (20 options), but it doesn't work like that. There were two ways to generate 0, and no way to get 19, the maximum was going to be 3+15 = 18.
The RAND16 function generates a 16 bit number. The MSB is returned in the accumulator (and also SEED_MSB), and the LSB is in SEED_LSB.
Here I take the MSB in the accumulator and AND with $03 to get a number from 0-3.
I next take the LSB and AND that with $0F to get a number from 0-15, and add those together.
jsr RAND16
and #$03
sta TEMP
lda SEED_LSB
and #$0F
clc
adc TEMP
The fix was fairly simple, rather than the CLC to clear the carry, I used ROR to rotate one bit of the LSB into the carry.
jsr RAND16
and #$03
sta TEMP
lda SEED_LSB
ror
and #$0F
adc TEMP
The final ADC operation is now adding 0-3 to 0-15 and 0-1, giving a number from 0-19. (AND will never generate a carry, so does not touch the flag set in the previous instruction)
Testing that in practice, I did indeed see locations far left and far right. Sorted.
Fix bugs in the original version
There were a few issues I found that were present in the original.
One was the starting square was usually a wall, so when the player moved away, the wall the close up behind them.
Sort of a "reverse Homer".
That could lead to getting stuck in inescapable sections or blocking off a better route, so I hard wired it to mark that square as a path.
Another issue is also shown in those two pictures above.
The maze is composed of 66 lines of 22 characters.
This sits in memory directly below the screen RAM, 23 lines of 22 characters.
During the game, the screen is a view of 23 lines within the 66 lines maze.
The player is always on the middle row, and there are 11 lines of maze above, and 11 lines below.
That is fine when you are in the middle, but when you start, you are on the 64th line.
11 lines above that is line 53, so the screen will show lines 53-66, but what about the remaining 9 lines?
If you look at the starting screen.
This is composed of three parts, I have highlighted those below.
The maze is stored in RAM between the end of the program and the start of the screen RAM.
The red section at the top is a copy of last 14 lines of the maze.
The last line is highlighted in black. This is always a solid line across the maze to stop the player moving below (at least it is with the maze generation fixed).
Beneath that, highlighted in blue, is a copy of the next 9 x 22 characters in RAM following the maze.
This is actually the top of the screen RAM, so it copies that instead.
You get the maze lines 54-64, and then top of the screen, which is the maze lines 54-62
I have copied the blue squares up to the top so you can see.
That helps make the maze look larger, but the solid line stops the player moving into the "shadow maze".
When the player moves up, the maze moves down, and the pattern beneath the solid line changes to a copy of what is at the top of the screen now.
Previously what you saw was maze lines 54-64, followed by lines 54-62.
But now you get lines 53-64, followed by lines 53-61, so the pattern below the line changes.
That can be a little confusing or distracting if it catches your eye, and it continues until the solid line is off the bottom of the screen and the whole view is of valid maze.
I have highlighted the end of the maze in black, and as an example what is initially a 2 square section below that line.
When the maze moves up, the top of the screen changes, and so does the copy, so it looks like the layout is changing.
I fixed that when I added the row of spaces to fix the "hole in the wall" issue.
I rewrote that section so that rather than relying on the screen data being directly below the maze, there was now a lines space, so the original didn't work.
I changed it so that when it detected it had reached the end of the maze, it reset to a specific location, always line 54, matching what would have been shown on the start screen.
That means the maze under the line, will now remain consistent. It is a repeat of part of the maze you can already see, so it is not giving anything away as it would if I had duplicated a different portion of the maze. I did consider using the top of the maze, but that might give you hints if you knew it was that.
I picked an example with a similar two square wall on the left.
You can now see it stays intact when the maze moves.
The final one in this area was another of those "sometimes" issues.
I would occasionally see one of the squares around the middle row disappear at the start, and then reappear when the maze scrolled.
I thought I had got some screenshots, but I can't find them (they have also disappeared). So these are cheated (by modifying video RAM).
It was usually one on the left, just above the middle.
Did you see it (or rather not see it?)
This was another one that didn't make any sense until I worked it out.
When the player moves, it clears the old square and then redraws the player in the new square. (the process was slower in BASIC, so you can see the player character flickering between clear and redraw - that is something else I optimised out, don't redraw the maze if the player hasn't moved)
When the game first starts, the old square is initialised to $0000, so it writes the space character to that address (good job this is not a Commodore 64).
When you fail to find the bomb in time, it explodes, destroying the maze, so a new one has to be built.
The original, used RUN to restart the program (and then spent a minute creating a new maze). As part of that, the old square would have been initialised to $0000 again.
What I (finally) realised, is when you complete a round successfully, and restart the game, it does not reset the old position, so when you first move, it overwrites the old position and draws the new position.
But the old position was from the end of the last round, and if it turns out to be a wall now the maze has scrolled back to the start, it clears the wall until the maze scrolls, when it reappears.
Again, it makes sense once you work it out, but until then I just had a random square that sometimes flickered when a new round started.
That was an easy fix, I just set the old position to $0000, why not, that is just to STY commands. (Y is always 0 in my world, see the previous post)
Tidy up the code
Whilst I have been going through fixing things like that, to make things clearer, I have been expanding the comments where appropriate, and looking around for unnecessary code etc.
I found a few more variables that were set to a constant value, and then not changed, so I just changed those to be load the constant value when required. (those are a hangover from the BASIC version)
I found quite a few bits of similar or repeated code that I could combine, and things that could be rearranged to make more sense.
This was particularly true in the joystick section, where I was able to change a large block of code which set direction and player character if a direction was detected, part of which is shown on the left.
The new version (on the right above) load an index in the X register and later in a single block of code, uses an existing array, and a new 4 byte array to set the direction and player character once.
There were several places where multiple things were being set to the same thing, so shuffling code around could save the duplication.
There were also a few times variables were used for temporary storage that I was able to optimise out by using the X register as a temporary store.
Optimise the code for speed and size
Time for some more top tips?
Top Tip - Optimise Loops # 1
There is often quite a few things that can be done to tighten code loops. This can reduce size and increase speed, both quite useful things.
This loop writes wall characters to an area of memory. It keep going until the MSB reaches an address after the end.
lda #CHAR_WALL
-
sta (DST),y
inc DST_LSB
bne -
inc DST_MSB
lda DST_MSB
cmp #>MAZE_END+1
bne -This increments the MSB, then loads it, then compares it, and tests the result.
With something like that, one trick I like to use is to preset X to the compare value.
You can then skip loading the value and compare X to the store value and save some instructions.
lda #CHAR_WALL
ldx #>MAZE_END+1
-
sta (DST),y
inc DST_LSB
bne -
inc DST_MSB
cpx DST_MSB
bne -
Top Tip - Optimise Loops # 2
Another thing when you have a more complicated compare to do it to simply avoid doing it.
There is one bit of code that writes spaces all down the right hand side.
But after the adding, it needs to check if it has reached the end each time
- lda #CHAR_PATH
sta (DST),y
lda DST_LSB
clc
adc #22
sta DST_LSB
bcc +
inc DST_MSB
+
lda DST_MSB
cmp #$1E
bne -That is a simple example, sometimes it would be a 16-bit comparison.
Here, the start point and end point are fixed, so it is always going to run the same number of cycles, the 66 lines between them. So why not just turn it into a 66 cycle loop?
ldx #MAZE_HEIGHT
- lda #CHAR_PATH
sta (DST),y
lda DST_LSB
clc
adc #22
sta DST_LSB
bcc +
inc DST_MSB
+
dex
bne -
Top Tip - Optimise Loops # 3
You can do similar things with other loops, avoid the comparison by counting down to zero.
ldy #0
- lda (MAP),y
sta (SCREEN),y
iny
cpy #22
bne -
Can become
#MAZE_WIDTH-1
- lda (MAP),y
sta (SCREEN),y
dey
bpl -
In this case, Y need to got from 21 to 0, so the comparison is BPL which will stop when it hits -1
(as long as it does not matter that it is copying the last character first. The end result is the same, nothing is reversed, only the order that things happen in.)
Top Tip - Optimise Loops # 4
One rule to consider with loops is to move anything you can out side of the loop to speed it up.
And example is toggling the clock pin on an IO port 8 times as fast as possible
One version could look like:
lda #0
sta COUNTER
- lda DATA
ora #CLOCK_PIN
sta VIA_PORTA
lda DATA
sta VIA_PORTA
inc COUNTER
lda COUNTER
cmp #8
bne -A more optimised version could be
ldy #8
lda DATA
tax
ora #CLOCK_PIN
- sta VIA_PORTA
stx VIA_PORTA
dey
bne -
Here the value to be written (the contents of the DATA byte with and without the clock bit set) are pre-loaded into A and X and can then be written out to the port without reloading or recalculating.
Top Tip - Optimise Loops # 5
Continuing with that example, if you really want to go as fast as possible, but are less concerned about space, you can unroll the loop.
lda DATA
tax
ora #CLOCK_PIN
sta VIA_PORTA
stx VIA_PORTA
sta VIA_PORTA
stx VIA_PORTA
sta VIA_PORTA
stx VIA_PORTA
sta VIA_PORTA
stx VIA_PORTA
sta VIA_PORTA
stx VIA_PORTA
sta VIA_PORTA
stx VIA_PORTA
sta VIA_PORTA
stx VIA_PORTA
sta VIA_PORTA
stx VIA_PORTA
That will toggle the clock pin 8 times without any delays between instructions.
The only way you could speed that up further is to arrange for the IO port to be mapped into zero page (which I have done before).
Fitting It All In Under 1K
Although I mentioned in the previous post that the code was a little over 1K in size and it would be nice to get it below 1K, for no real reason, I wasn't actively trying to achieve that.
However, as I was optimising things to make it better or faster or clearer, I did end up shedding quite a few bytes, so I had another pass through the code to see if there was anywhere I could make savings without affecting performance or readability of the code.
I had made sure that Y was always going to be left as zero, so I removed a couple of places where it was reset to 0.
I changed a few JMP label instructions to BNE label, in cases where label was within 127 bytes, and the zero flag was going to be clear, often the previous instruction was lda #constant and constant was not zero.
There were a few places I could reorder things to the code dropped through to the right place and didn't need any jumps or branches.
There were also a few hangover variables stored in the $03xx region. I moved those into zero page, which saved 1 byte per access.
Almost there. There was one variable which indicated if the bomb has been found. It only ever contained 0 or 1. This is where it was set to 1.
lda #1
sta f
I changed that to
inc FOUND
That saved the final two bytes.
After all that, the current version is now down to 977 bytes.
I am happy with that, I would take the rest of the day off, but it's past midnight already.
Improve readability and portability by using named constants
I have used code examples from various version, in the more recent ones, I have tried to get rid of all the literals like 22 and $1E00 etc. and replace those with named constants.
That should make it easier to follow, and often it makes the comments redundant.
; start in the middle
lda #<MAZE_MIDDLE
sta CURRENT_SQUARE_LSB
lda #>MAZE_MIDDLE
sta CURRENT_SQUARE_MSB
I have also gone for calculating all the positions and offsets in the constants. Avoids the need for code which loads the address of the start of the maze and then adds and offset.
If both of those values are constants, why not calculate them in advance and then just load the pre-calculated value in.
MAZE_WIDTH = 22
MAZE_HEIGHT = 66
MAZE_TOP = MAZE_END -(MAZE_HEIGHT * MAZE_WIDTH) + 1
MAZE_END_OF_TOP_LINE = MAZE_TOP + MAZE_WIDTH - 1
Test this by writing a PET version
One advantage of not having any screen size or address information in the code, and having it all in one location in the defines file means it is easier to change.
To test this, I wanted to write a PET version. This is similar to the VIC20 version, much of the code remains the same, only reading the joystick, making the sounds and the size and location of the screen change.
I did look at making the screen wider, but that made the maze too complicated. Maybe I could offer the user a choice of difficulty at the start, but the one on the VIC just seems about right, and so I have a 22 character maze in the middle of the screen.
I still need to write a new sound routine to make the ticks and explosion, but other than that it is working and looks rather good in green and black.
The updated VIC20 code is on github, I will upload the PET version once I have added the missing bits.
I now need to read my own blog post on PET Sounds.
All items are still available, and I can ship worldwide.
International shipping is a bit complicated at the moment, so if you want to order from outside the UK, please see this page for more information:
Sorry to have to do this, and I know this is going to affect sales, but please understand it is the only option I have right now.
Patreon
If you enjoy posts like this, you can support me via Patreon, and get access to advance previews of blog posts, and exclusive posts.
You also get progress updates on new projects and other behind the scenes updates, as well as access to my Patreon only Discord server for even more regular updates, and to discuss your own projects.
I currently have 50% off your fist month if you want to try it out.
