After a frustrating period playing LabPixies Flood-It! (see here) on PC and iPod, my software aspirations came out with the thought of "This should be easy to implement on the BBC Micro".

After a bit of fiddling around, I now have an Alpha version ready for people to laugh at.

In particular, the "search" algorithm is currently rather dumb (and hence slow), and the implementation is missing any sort of running success/failure rate score, but the basic game is playable.

A .zip of the SSD is attached, and I'd appreciate any constructive comments on this.

Thanks

Michael

Nice job Michael, I can see that it would become very addictive. My sort of game too, not needing handfuls of keys

I ran it on BeebEm as a 'B' and on the two occasions I was destined for success, it bombed with 'No Room' . After the first time I moved PAGE to &1100 and I got a lot further after that but just before I nearly cracked it a second time, 'No Room'

As a start on the speed front, change every variable you can to integer (trailing %) and it will instantly be a lot quicker. Definitely worth continuing with it though

Hey that's really nice. I've certainly played that game before and I wouldn't entirely rule out that it was on a Beeb - maybe some obscure PD or type-in perhaps? Or I may just be imagining things!

Played it on B-Em at 500% speed. It really crawls towards the end of the game otherwise. Was in Master 128 mode also (where PAGE=&E00) in a bid to get around the lack of memory.

Got to just 4 squares left on one game but ran out of turns. On another game I got down to the very last square before it crashed.

There's a lot of optimising can be done to this program though, memorywise. % variables are the way to go, as Martin says. You can strip down bulky variable and procedure names and remove all those unnecessary spaces and REMinders. Something else to do would be to rearrange the i and j arrays. Arrays start with the '0th' entry, so you only need to dimension up to (11,11).

If you can crack that - and the speed issue - then perhaps there's a place at Retro Software waiting for this!

It's great - a nice little diversion.

If you run it on a Master in MODE130 it doesn't run out of room.

However, I'm sure that the code can be improved a lot so that it will run on a BBC B.

Here's an updated version, which adds an optimisation to the search algorithm which makes it faster as you approach the end, and less demanding of memory.

It also selects "MODE 130" instead of "MODE 2", so will use Shadow RAM on a BBC B+ or M128, or a BBC B system that's compatible with that option.

I haven't been able to make it run on a standard BBC B with DFS active - even compressed the code is 2.75K, and there just isn't enough room left between TOP and HIMEM in MODE2.

It will run on a BBC B with PAGE at &E00, so I've added a "quick and dirty" relocator to the SSD. If you have a shadow RAM board on your BBC B, then just change the !BOOT file to not load the relocator.

To keep things simple, I haven't attempted to detect a BBC B+ in the !BOOT file, which could run it without the relocation because of the shadow RAM.

I've also added a "play again" prompt at the end, and a tally of wins and losses.

As its "pure BASIC", it also play on BBC Basic for Windows (where it really flies), and (I presume) would play on a RiscOS machine.

I'm not sure if the 8K limit of the demo version of BBC Basic for Windows would still be an issue - it was before the code optimisations.

Thanks for the positive comments so far!

Regards

Michael

I can confirm it runs on RISC OS (via Virtual RiscPC) and each key press is instant.
Also, version 09 is definately faster later towards the end than 07.
Cheers!

Nice job - great little thinker game!

You may want to change some of the integer variables, such as tl% and tw% to using uppercase integer variables (e.g. T%, S%) and minimise local variables. These are stored in page 4 so won't take up any space in the BASIC variable heap. (Obviously this won't work for d%)

Another way to shrink down memory use is instead of using an integer array to store the board, which will take 4 bytes 11 * 4 * 11 = 484 bytes; you could just use a contiguous block of memory and store the information in a byte: 11 * 11 = 121 bytes.

This would be quite trivial to put in place with the current code, so instead of:
Use:

You could actually half the amount of memory needed (61 bytes) as you only need a nibble for each block, though this would make the code more complex! (You can get it even shorter - as the numbers only go up to 6, you can use 3 bits for each square, which works out at 46 bytes; though this'll add a lot more complexity to the code!)

Also you can save some memory in the code, by, instead of:
Use:

This'll save you 4 bytes on the line number and length, and will save you one byte over doing NEXTJ%:NEXTI%.

You could save even more by putting some of it (e.g. the scanning for colour changes) in machine code.

You can make 12K available in the trial version (assuming you don't need to use the INSTALL statement) as follows:


Richard.

Thanks for the tip - is that on the website somewhere? The "headline" description of the demo mode just talks about the 8K restriction.

Major Cudos on BBC Basic for Windows BTW, it really helped me with debugging some of the issues I had.

Thanks

Michael

The issue with this is that for the main function that uses local variables (PROCs in the crunched version, PROCsearch in the expanded) uses recursion, which requires the LOCALs to work properly.
It could be done for PROCm (PROCmaxsquare in the expanded version), but I was beginning to lose track of which single letter variables I'd used and which I hadn't - hence only those two functions use non static integers.



I have managed to implement a version using the indirection approach - it wasn't as simple as you'd think because of the different way a BASIC array and the memory array had to be indexed. In the end I had to change S% so it was the "size", rather than the "max element", without that to get things to work correctly the DIM has to be DIM D% (S%+1)*(S%+1), and all the indirections get very messy (e.g. D%?((mx%+1)*(S%+1)+ml%) - yuck!), but the side effect was some of the other code became less elegant (e.g. all the FOR I%=0 TO S% loops had to become FOR I%=0 TO S%-1)

Unfortunately the program still won't work on a DFS BBC B with PAGE at &1900 - I suspect the recursion is what's really chewing up the memory, hence the only likely way to get the program to run on a standard DFS BBC B will be to further optimise the "flood search" algorithm.


Doh! This little project has been good at proving just how rusty my BBC BASIC is! Forgetting arrays start at zero (even the same as C, I should have expected that) and now forgetting you can do "double NEXTs"



I think that (unless it was precompiled machine code that was *LOADed, which would make development and testing more complex) any in-line assembler would be more memory hungry than the BASIC equivalent.
That might help significantly with some of the speed issues, but it would really mess up the portability which is quite a nice benefit - the program is currently multi-platform (BBC, RiscOS and BBC Basic for Windows), but adding 6502 machine code would limit it to the BBC only.

On a beeb with DFS you should be able to safely drop memory down to &1400 as long as you only open one file at a time (it uses a couple of pages for each file handle to buffer data).

The recursion will take up a bit of memory, so about the only way to change this is to tune the algorithm to make it iterative; I'll be honest I didn't look too much at the code and didn't notice this

Here's another version, with Tautology's improvements implemented, and run through the Beebug Toolkit+ "CRUNCH", which saves another 512 bytes (ish) off the code.

Runs for me in BeebEm with PAGE at &1900, but I'm not sure it will if the earlier optimisations are defeated (i.e. leave one miscoloured square near the top left)

I've also fixed the typo in the scoring that reported you'd taken one less move than you really had when you win.

Regards

Michael

The attached file is based on your initial posting (v0.7)
I have taken the flood fill algorithm from wikipedia http://en.wikipedia.org/wiki/Flood_fill
and have adapted it with some structured programming because Im a bit anal that way (I definately miss BBC Basic5 stuff, multi line IF, WHILE loops etc).

It seems about the same speed as the original, but it works on a standard beeb. The larger board sizes need PAGE=&1200 but thats for the board%(X,Y) array, not for the flood fill queue (the queue is suprisingly short, I have allocated 4*width entries but have never seen it go over 2.5*width entries. I dont know the theoretical maximum queue that can occur).

There is a text mode as well as a graphics one (I developed it on Brandy basic which runs in DOS/Linux but has no graphics) and some debug stuff if you switch it on.

Three things need changing for portability

• IF PAGE=&1900 THEN PAGE=&1200 :CHAIN "FLOODGR"
• PROCmakeError which mimicks Basic5's ERROR command with CALL
• Q%=&900 :REM DIM Q% maxQ%-1

The different board sizes need the number of moves tweaking for difficulty, and can be added to if you have more memory (I can run 20*30 with PAGE=&1200)

Sounds interesting - I should always look at Wikipedia before I try to do anything!

I'll try and compare your version to mine next time I get to look at this (probably Wednesday at least), and see if I can produce a "best of both" version.

Have you tried adding my main optimisation from V0.9 to your V0.71 code? The basic extra idea was to find the maximal square at the top left that's already contiguous, and just search for the flood fill out from there. Its the main reason the V0.9 is (a) much faster than V0.7 and (b) less memory hungry than V0.7. As I mentioned above this can be foiled by a "malicious" attempt of intentionally leaving one or more "wrong" coloured squares near the top left, but for standard playing seems to make a big difference.

One other discovery I've made today (which is probably obvious to everyone else) is that procedure / function calls on the BBC are slow - In one attempt to implement Tautology's ideas, I added a function to read the colour of a square and a procedure to set the colour. It made the code more readable before the S%=S%+1 modification, but slowed it down by at least a factor of 2.

Sad really that "neat" code on the BBC runs slow but "ugly" code is faster.

Michael

It's on the Wiki: http://bb4w.wikispaces.com/Fitting+programs+in+the+demo+version

Incidentally, you can make the static integer variables (A% - Z%) LOCAL, so even when recursion is involved you can save some space by using them.

I think you'll find that it's the passing of parameters that makes them slow; I would expect PROC (with no parameters) to be faster than GOSUB if the program is a reasonable size. GOSUB has to scan the program from the beginning every time, so the higher the line number the slower GOSUB gets. The speed of PROC (except for the first time) isn't so sensitive to the size of the program.

I have been doing some speed tests on my version 0.7.1 as follows:
1) fixed seed (RND(-123456) )
2) 12*12 board
3) auto input moves (DATA 3,2,5,4,5,2,1,3,5,6,1,4,2,1,3,5,3,6,4,1,3,5,2,6 )
Results (using BeebEm) are:
1) 106 seconds = Full game
2) 51 seconds = Without printing graphics (DEFPROCbox(X%,Y%):ENDPROC )
3) 54 seconds = 6502 2nd proc with graphics
(I dont know why but this locked up at the end of the game.
TRACEON showed the last line was "IF count =0 PROCwin ELSE PROClose" )

So roughly 51% of the time is spent painting the screen and 49% calculating the board.

I have run speed tests on the crunched V9 game and here are the resultsL
1) 120 seconds = Full game
(I notice the plot routine uses one more MOVE than absolutely necessary)
2) 51.5 seconds = Without printing graphics

I can take a couple of percent off the time for my V0.7.1 version by removing all the Debug stuff, text mode & queue checking but I dont think its worth it.
The board%(X,Y) array could be changed to a byte array (bigger board but slower access speed if using Basic).
Short of using machine code I dont think there is a lot left to optimise (we could also use machine code for the screen drawing).
Acorns Graphics Extension Rom has a Rectangel Fill which might be faster than PLOT85 but I cant find it to download and it allocates itself a page of workspace (which could make lowering PAGE tricky).

There may be a faster flood fill algorithm around but if code size or stack space go up were in trouble again!

Oh lol, I think I'd half-forgotten you even needed a variable in a BBC BASIC 'NEXT' loop.

I generally just use a simple 'NEXT', or for a double loop then 'NEXT,'.


It did occur to me that this is a game which could quite happily run in teletext MODE7 - that would speed up things (and also free up a crapload of memory).

Or what about poking the blocks of colour directly into the screen memory?


Great effort so far, anyways. And I expect to see a 3D version released by next week!
Idk, I just have a weird idea of something isometric, kinda like Q*bert.

D'oh! For my defence, it's been 15 years since I last programmed in BBC BASIC and that was on the Arc.



Good idea; but both of those may break compatibility with the other versions of BBC BASIC that the game currently has!

Found out why it locked up with 2nd processor. I used memory at &900 for the flood fill queue to give more space to BASIC for bigger boards (&900 is normally ENVELOPE storage or casette output buffer). With 2nd processor active PAGE is &800, so I was overwriting part of my own program!
Reverted back to "DIM Q% maxQ%-1" & 2nd processor now works OK.
On a standard BBC the program works with 12*12 board with PAGE=&1900.
20*20 board works with PAGE=&1200, 20*30 needs PAGE=&1100
Remember this is because of the DIM board%(X,Y) array, not the flood fill queue.
The program can be crunched quite a bit as it has comments and spacing lines not to mention debug code that could be stripped out.

You are so close! VDU24 is where you want to look.

Excuse me, I've butchered your wonderful game (only managed to defeat second level so far) and have a several things to say, but I'll focus on the long point you've made above.

Delete line 100, it's a nice touch for the way you drawn the screen but I had to
go dig out my BBC User guide to understand some of the PLOT modifiers you used, and it just suited me to get rid of it all. The penalty of negative numbers is one byte for the minus. Positive comes free!
Delete lines 1110 to 1150 - your plot routine.
Now, the equivalent of RECTANGLE FILL can be done with a quick graphics window, set the background colour and CLG that space...

1110my%=maxY%+1-Y%:GCOL0,128+board%(X%,Y%):VDU24,(X%-1)*dX%;40+(my%-1)*dY%+9;X%*dX%-9;40+my%*dY%;:CLG

You gain a fraction of speed redrawing, which in the larger playing areas is a large gain. Don't think there is any memory saving doing this though, have had to introduce a new variable and a bottom guard (8 pixels = 40 OS units)

Your debug selection method I thought was clever. But for instance when drawing the screen you branch to the procedure to plot a graphics square, then test whether to leave and display it textually. This will be part of the speed penalty you see when debugging, and is probably acceptable for a debug where you may want the program top run slowly to catch what is happening. Ideally you could have put in 'IF D% THEN PROCdebug_routine ELSE PROCgraphics_routine' where it's called first.
The test is outside of the procedure, still gets done so doesn't give any improvement there, but reduces the procedure call stack by one.

I have the Graphics ROM in my Beeb, was great to play with when I was a kid, almost completely pointless now I've grown up and can better drive the raw Beeb :o)

As for your relocating routine :o(
Adjust 60 ;
60IFPAGE>&E00GOTO32000
add;
32000PRINT"Relocating..."
32010S%=TOP-PAGE:FORI%=0TOS%:?(&E00+I%)=
?(PAGE+I%):NEXT
32020PAGE=&E00
32030*TAPE
32040RUN

But that's not all! This is incomplete, the rest I leave as an exercise. LOMEM
is going to remain too high, you have to bring it down to the new TOP... easier than it sounds? ;o)

There are other things I wanted to say, like what have you got against FNs!!! But I'll go away again, I'm trying a few optimisations in other places - PRINTTAB(0,Ll%-1)'"<space>Loser...." - you are really scaring me now!

Oh, yes! One dire warning, do not try to modify the program after PAGE has been reduced to &E00, you may be unhappy with the state of your Floppy afterwards. Load file, edit file, save changes, run to test. Forgot that myself last night hence the *TAPE :o( Still, we can't be expected to remember everything we ever learned 20+ years ago?

Yep, using the CLG method is a big time saver
New Results are:

• 84 seconds = Full game (from 106 secs)
• 41 seconds = 6502 2nd proc (from 54 secs)

Attached is updated program (plus timer variant)
P.S. I've got nothing agains FN's, I think there are one or two in there

Jeeeeeeez!

How happy am I to see this thread I own an Android phone (Samsung Galaxy Apollo), and Flood It was the 1st game/app that I got for it. I regarded it as being the Android version of "Hexaconnect". The only difference was that Hexaconnect was honeycomb-shaped blocks, where Flood It was square blocks. Soon afterwards, it transpired that there are numerous variations of this type of game, so not only I'm chuffed to see that Flood It itself got mentioned, but it is now available on the Beeb!