Interlude: Flood

The November 1991 "Programmer's Page" focused on an issue with reader's Geza Lucz's minigame Flood (the issue pointed to a difference between C=64 ROMS - on old systems, the default color for text is set to the screen's background color) but the place where the listing would be on the page is blank! The next month mentions the printer's error and prints the game in its entirety:


Believe it or not, that small bit of coding makes up a very playable little game...

Flood - Geza Lucz

The game is essentially "fun with real-time floodfill". Once the playfield is made two dots of water are place and immediately start to spread. The player has to maneuver the little check guy and press return to put down wall and minimize the spread of water, and then your final score is based on how many spaces you keep dry. Rating:4/5 in part because of the cleverness involved, and because I may want to borrow the basic idea.

I typed in and saved the game, you can get a D64 Image Here.

Just for geeky fun, I'm going to try to understand how it does its magic. Its been a long time since I've delved into C=64/Microsoft BASIC, so wish me luck...
This is what the November article focuses on, setting the background color to the desired foreground color, clearing the screen, and then setting the background back, as a hack for old ROMs.

The next part I'm not sure about:
The first line DIMs 2 arrays. A() is big enough for screen memory twice over (40x25 characters). The next lines set some magic numbers in B(). Hmm. The numbers (-1,1,-40, and 40) might well be offsets in screen memory... for example if you wanted to set or read the character one line down, you might add 40 to the current character memory location and that would be the memory mapped to the screen one character below... I'm not sure about the magic numbers 29,157,145,17 though, there in line 130.

The next block is so cute:

This is using a single FOR loop to set all 4 borders. According to the Commodore-64 Memory Map, 1024 is the default start of screen memory, and according to the C64 screen codes 42 is the code for "*". So line 150 POKEs in a * for the top row, and then the bottom row (1984 = 1024 memory start + (40 characters across * 24 rows down)).

Lines 160 and 170 are the really amusing bits (er, for people who are amused by this kind of thing) - instead of going from 0 to 39, the vertical sides are 0 to 23, so Lucz uses some division and rounding... that means some characters are being set twice, but that doesn't hurt anything, and is more efficient than conditionals to see if the setting is necessary.

Next is some more initialization, this time of the two starting water drops:
190 does a simple loop for 1 to 2. Line 200 is setting A(1) and then A(2) to the value of a random screen memory location, line 210 says if the location line 200 selected does not have a space character (32) then goto 200. (Confusingly {SPACE} is just Gazette's way of saying type a space here, and then for brevity they leave out the "GOTO") 220 then pokes a star into screen memory at the location A(1) or A(2) points to.

So this is an important hint at how A() will be used- it's not a simple memory map, it's a set of offsets INTO the screen memory, I'm assuming the use will be a flattened X,Y coordinate, one for each water drop.

Still initializing, we get
Confusingly, B and A are distinct from the arrays B() and A(). We'll have to figure out what they're doing later on.

Line 250 pokes a checkerboard (102) into the current player position, again according the the C64 screen codes.

Ok, time for our main game loop:


270-330 is the main loop for updating water. Inside this loop, there's that GOSUB 370 which as we'll see is the keyboard reading/player moving. It's important to see that that call is nested in the outer FOR loop, rather than just once per "infinite" GOTO loop... otherwise the game would be feel very unresponsive, and the player could only move once per global update.

So, I'm conjecturing "A" is the first water drop to inspect, and "B" is the final one. A(), remember, is the array of offsets to screenlocations (one for each drop) and B(1-4) is a series of offsets to look up, down, left, and right. So "I" is the offset of the drop we're inspecting. 290 says "if the location of the current drop adjusted for the up/down/left/right offset is NOT a space, then goto 310" (i.e. skip line 300).

So line 300 represents the addition of the drop. I'm thinking "L" represents how many drops we've added to this "GOTO loop". Into A(B+L) (i.e. the next available space in A() for a drop to sit) we push the screen memory location of this drop - A(I) - plus the up/down/left/right screen memory offset from B(). And to end the line we poke a 42 "*" character into that new screen location. (And because we started with those solid borders, we don't have to worry about poke'ing off of the screen.)

310 finishes looping for looking up/down/left/right, 320 reads and reacts to the player input, line 330 finishes looping through all the droplets that were known to be needed to be checked.

340 then sets up the variables for the next run of the GOTO loop, A, the start of the search, is set to B, where we ended the search this time. B, the end of the search for next time, is then increased by how many drops we added in.

In other words, each turn, the up/down/left/right neighbors of all the drops we added last time are inspected, and any blanks there are made new drops, and then next GOTO loop those new drops will be inspected in turn, and so on. Thus, the floodfill happens.

350 looks for the win condition. If L is zero, that mean we added in zero drops... i.e. there are no drops with empty neighbors, and the game is done. And B is the offset of the last drop, so we get a score by subtracting that from the total number of drops possible, if the player did nothing but stand there.

All we have left is the keyboard and player movement subroutine:
Once again, we see variables with the same name treated differently: R vs R$. We'll see that R$ is used to read in the keyboard, and I think R is what is "replacing" the character at the old position.

370 reads in the keyboard. Not sure about reasoning of appending a space, probably to prevent errors if no key is pressed?

380 says if the key pressed was the return key, than R will be 91 - this corresponds with the wall marking character, a big cross shape.

With line 390, the use of the second set of values for B() (as set in line 130) becomes clear: those magic numbers are character codes corresponding to the cursor movement keys. So we look at the screen map of the current player location H, treating the ASCII code of the pressed key as an offset into the up/down/left/right offset in B(), and if it's not a space there, we return; the player can't move there, whether its wall or water blocking them. (So in short, B() has 8 values, 2 sets that point to up/down/left/right offsets, the first set is index making it easy to loop through when looking for drop neighbors, and the second set has indexes lining up with keyboard codes. We never initialize B(), I guess other pressed keycodes could create odd movement jumps if they had old data.)

400 pokes the players current location with R - this looks to be a wall piece if they've hit return since we last tried to move.

410 uses the same B() offset trick to change the player's known location.

420 says R gets to be what is in the space the player is about to be moved to... i.e. I'm pretty sure that will always be a space. And having read what was there, we go ahead and put a 102 checkerboard in that new location.

Wow! That is a neat bit of coding.

You can make a harder variation by increasing the number of starting droplets, you just have to change what W loops up to in 190 and then the initial value of B in 240. And of course, being able to make that kind of change is part of the charm of this era of BASIC programming!

11 comments:

  1. It turns out that with a few modifications, this will work on an unexpanded Vic-20.

    First of all, change the A(2000) array to A%(420); now it uses 840 bytes instead of 10000, to cover a 20x21 playfield. Change B(299) to B(4), and find some other way to parse keystrokes. What I did was probably overkill, replacing line 130 with this:

    130 DEF FNB(C)=(((C AND 93)=17)*21 + ((C AND 16)>0)) * SGN(C-30)

    there's a bunch of other changes owing to the Vic's memory map, and some optimizations I did that probably weren't necessary. I'll post the URL if I can be sure it won't be filtered.

    ReplyDelete
  2. Turns out it will work on a TRS-80 Micro Color Computer too. Here's a vid: https://youtu.be/PrQT7vBYH90
    Thanks for sharing a nifty retro type-in programming project!

    ReplyDelete
    Replies
    1. Awesome! Glad you ran with it.

      Delete
    2. Also I forgot that I got a ".ca" version of my blog "for free" :-) Hope that doesn't mess up my google juice too badly ;-)

      Delete
  3. This type of deconstruction of a tiny BASIC program should have been a regular feature in some magazine. Nice explanation.

    ReplyDelete
  4. Hey you found one of my games ... I had a lot like this. I published them weekly here and there for years. This was before the internet, so space was limited.. this is why it's full of space saving tricks.

    ReplyDelete
    Replies
    1. Oh wow you're the author? It is some cool code!

      Delete
    2. Yes. I'm the author. I just have not figured out yet how I can get my google profile to show my name here. This optimized coding was kind of a challenge on how to create usable games when they only gave you 1 column: 1/3rd of a page and sometimes half of that. I will try to dig up the others if I can find the magazines. I think I stored them somewhere .... Compute run only the last few pieces. I think they were one of the last to accept small basic programs and the others don't have online archives from the 80's.

      Delete
  5. I must admit, line 100 confuses me as well, and your explanation confused me even more. If the goal is to set the foreground text colour, then why use some obscure hack that involves changing the background colour? Why not set the text colour directly with POKE646,14?

    Later on in the listing I see that the characters aren't being output to the screen via PRINT statements but rather by POKEing to screen memory, so maybe that has something to do with it. I guess that PRINT CHR$(147) not only clears the screen memory at $0400, but also fills colour memory at $D800 with the current background colour.

    ReplyDelete
  6. The padding of R$ in line 370 is because if you try to evaluate ASC() on an empty string, you'll get an illegal quantity error.

    ASC() only evaluates the ASCII value (well, PETSCII value) of the first character in a string, so the extra space is harmless when R$ is not empty, and prevents a halting error when it is empty.

    ReplyDelete
    Replies
    1. aha so my guess wasn't too far off. Thanks!

      Delete