What implementations of BASIC had a robust flood fill operator?

Question

When I learned BASIC on Elektronika BK, I got fascinated with the flood fill (PAINT) operator: how does it know to get to all nooks and crannies of the shape to fill? I've devised an algorithm, tried to write my own implementation of it, and soon realized that it requires a substantial amount of scratch memory. A fine grid would be a good example of a tall order.

The next thing I did was to write a very short program like this:

10 CLS
20 COLOR 1
30 FOR I=10 TO 200 STEP 2
40 LINE (5,I)-(205,I)
50 LINE(I,5)-(I,205)
60 NEXT I
70 PAINT (5,10),2,0

The grid is drawn with color 1; the paint operation uses a point on the grid and directs to paint with color 2 using color 0 (background) as the boundary.

And indeed, it hung and required power-cycling of the computer (there was no hardware reset button).

My question is, how do other implementations of the flood fill operator in BASIC on retro-computers with limited memory behave.

The absolute best would be to paint the 2-pixel-wide grid covering the whole screen correctly; presumably, this requires the most stack space.

The second best would be to detect the stack/queue overflow and to stop with a runtime error.

Here's another complex shape, a herringbone pattern, that causes PAINT to hang:

10 CLS
20 COLOR 1
30 FOR I=2 TO 200
40 FOR J=2 TO 200
50 K=I MOD 4
60 L=J MOD 4
70 IF (K=L AND K<2) OR K*L=6 THEN PSET (I,J)
80 NEXT J
90 NEXT I
99 PAINT (0,0)

Here we draw the pattern then ask to paint the background.

---

Findings so far:

• Sinclair QL sidesteps the issue by implementing a simplified operation: the fill mode must be requested before drawing the outline, and If you have more than one pair of points in your shape's outline per horizontal scanline, divide the shape into less complex parts so that this condition is met.
• CBM BASIC 7.0 on C128 fails with an "?OUT OF MEMORY" error if the shape is too complex.

Answer 1

It's not clear to me what constitutes a correct answer here, but here's my take.

GW-BASIC 3.23 uses a queue-based algorithm which is pretty robust. It has no trouble with either of your test cases or the u's mentioned by scruss; however it's still possible to design a pattern specifically to make it use lots of memory and overflow, even though it has nearly 60K available:

10 DEFINT A-Z
20 SCREEN 1:WIDTH 40:KEY OFF:CLS
30 LINE (1,0)-(1,95)
40 LINE (1,97)-(1,191)
50 PSET (0,191)
60 LINE (3,49)-(3,143)
70 LINE (5,25)-(5,71)
80 LINE (5,121)-(5,167)
90 FOR I=0 TO 3:LINE (7,13+I*48)-(7,35+I*48):NEXT
100 FOR I=0 TO 7:LINE (9,7+I*24)-(9,17+I*24):NEXT
110 FOR I=0 TO 15:LINE (11,4+I*12)-(11,8+I*12):NEXT
120 FOR I=0 TO 31:LINE (13,2+I*6)-(13,4+I*6):NEXT
130 LINE (15,1)-(255,191),15,BF
140 FOR I=2 TO 190 STEP 2:LINE (15,I)-(255,I),0:NEXT
150 FOR I=16 TO 254 STEP 2:LINE (I,0)-(I,191),0:NEXT
1000 PAINT (0,0)
1010 PRINT INPUT$(1);

The trick to make it fail is that the left part makes it double the number of "threads" several times, and each "thread" then has to cope with the many rows of dots, which means lots of holes both up and down, each of which has to be enqueued, until it crashes.

(Note there's a GW-BASIC emulator called PC-BASIC; however, as of this writing, the flood fill algorithm it uses is not the same queue-based algorithm implemented in GW-BASIC 3.23, besides the fact that it "cheats" by having much more memory available).

But the most robust algorithm I've seen, is one for the ZX Spectrum. The system's BASIC doesn't have a FILL function, but there's a BASIC extension called Beta Basic that does. Versions up to 3.1 have the most robust fill algorithm I saw at the time in a retro computer. I couldn't make it fail no matter what I tried.

  10 FOR x=1 TO 255 STEP 2
  20 PLOT x,0
  30 DRAW 0,175
  40 NEXT x
  50 FOR x=1 TO 175 STEP 2
  60 PLOT INVERSE 1;0,x
  70 DRAW INVERSE 1;255,0
  80 NEXT x
  90 FILL 1,1

(Use graphics mode and F to enter the FILL keyword).

The price for that, however, is speed: the algorithm is somewhat slow. That's probably why it was replaced in version 4.0, even though the new one is very easy to crash with either of your test cases.

Answer 2

I didn't quite manage to replicate your test, but came up with something for the Amstrad CPC6128. A screen of 40×25 lower case ‘u’ is quite a difficult fill, but the FILL command manages it well:

Here's the code to do this:

10 MODE 1
20 PEN 1
30 FOR i%=1 TO 25
40 PRINT STRING$(40,"u");
50 NEXT i%
60 LOCATE 1,1
70 MOVE 10,14
80 FILL 1

The animation is a little faster than realtime, but it really does take a few seconds to fill the screen.

Answer 3

The classical flood fill algorithm is a recursive algorithm that, in its most simple form, can use an enormous amount of stack space

void fill (x, y, col) {
   plot (x, y, col)
   if (point (x + 1, y) != col then fill (x + 1, y, col);
   if (point (x, y + 1) != col then fill (x, y + 1, col);
   if (point (x - 1, y) != col then fill (x - 1, y, col);       
   if (point (x, y - 1) != col then fill (x, y - 1, col);
}

There are a number of strategies to limit the amount of space the fill algorithm will use, like having only working in a specific direction and limit the recursive part or using a list instead of the stack to avoid a stack overflow and be able to stop witth an "Out of memory error", and, there are alternative algorithms that aren't recursive at all.

The Sinclair QL, for example, uses such an alternative algorithm. This requires you to "bracket" shape drawing code to be filled with FILL 1 / FILL 0 pairs and fill the shape you have drawn in that bracket with the current ink color. BASIC will then set up a buffer of x-coordinate pairs per scanline in your shape and remember such pairs where you have drawn a "left" and "right" outer shape pixel. On the closing FILL 0bracket, the algorithm will run through the buffer and simply draw horizontal lines between the coordinates found in the buffer. This needs a fixed buffer space of

typedef struct fillBufferT {
   int x1, x2;
};

fillBufferT buffer [vertical_res];

with no chance of buffer overflow at all. The downside is, that this algorithm is only capable of storing one pair of horizontal coordinates per scanline - complex shapes that need more coordinate pairs need to be sub-divided by the programmer to be properly filled.

But the algorithm as such is entirely bullet-proof and cannot lead to a runtime error. It is also obviously much faster than the recursive flood-fill, but will always fill the entire shape, regardless of "what's been inside" before.

The limitation that the Sinclair QL FILL command was not able to fill arbitrary shapes was mentioned in the manual as follows:

The FILL algorithm stores a list of points to plot rather than actually plotting them. When the figure closes there are two points on the same horizontal line. These two points are connected by a line in the current INK colour and the process repeats. Fill must always be reselected before drawing a new figure to ensure that the buffer used to store the list of points is reset.

Warning

There is an implementation restriction on FILL. FILL must not be used for re-entrant shapes (i.e. a shape which is concave). Re-entrant shapes must be split into smaller shapes which are not re-entrant and each sub-shape filled independently.

Answer 4

In the original BBC BASIC versions for the BBC Micro, a large range of PLOT codes were reserved for the Graphics Extension ROM, which was an optional extra. The GXR included both a flood-fill function and a horizontal line-fill. The BBC Master included half of the GXR as standard, omitting the "sprite" routines, but still included flood-fill.

In BBC BASIC V, most of the commonly used PLOT codes gained convenience keywords, including quite a few associated with GXR functionality - and including flood-fills using the FILL statement. A version of BBC BASIC V was available for late-model BBC Micros, but it is most often associated with the Acorn Archimedes which ran RiscOS. On the Archimedes, GXR functionality was available as standard.

The easiest way to run BBC BASIC V or VI (the latter uses IEEE-standard floating-point but is otherwise identical) is on a Raspberry Pi running RiscOS. BeebEm in "BBC Master" mode gives access to flood-fill via GCOL 0,128+POINT(X,Y) : PLOT &85,X,Y.

The GXR manual indicates that the flood-fill routine accounts for 512 of the 768 bytes of RAM permanently claimed by GXR as workspace. A command is provided to disable the flood-fill routine to reclaim this extra RAM, reducing GXR's overhead to one page (256 bytes). The BBC Master's version of GXR used some of the shadow RAM for workspace (as well as the framebuffer), eliminating this overhead from user programs' perspective.

With 768 bytes of RAM, the flood-fill routine is able to maintain a list of 256 pixels to process, but it is still possible to overflow this list with a complex pattern such as a fine grid; the routine exits gracefully instead of crashing in this case (tested on a BBC Master emulation). Test case:

The RiscOS version, being less memory-constrained, should be much more robust, and my limited tests using RiscOS 3.5 (on an emulated ARM610 CPU with 32MB RAM) appear to confirm this; none of the three tests give it any trouble at 640x480 resolution (MODE 28). It must be conceded that a 32-bit environment is very different from an 8-bit one.

Answer 5

The Sharp MZ-800 is a little-known Z80-based micro which has to load its BASIC interpreter from disk or tape. What it does have is a bank of dedicated VRAM behind a custom video controller, which makes plotting and querying pixels significantly easier for the CPU.

I was able to put an emulated MZ-800 into "mode 4" graphics, which provide 4 colours at 640x200, and generate a similar fine grid which stumped all previous micros at this resolution. Issuing PAINT on this grid successfully changed it from white to blue, leaving the black holes intact.

The algorithm appeared to behave differently from usual, taking care of the whole scanlines first (outwards) and the vertical bars afterwards (inwards). This suggests it is a scanline-stack algorithm which sets pixels only upon retrieving stack entries, not upon placing them. This is very wasteful of memory and easily leads to unnecessary recursion steps.

When faced with the herringbone pattern, progress became very slow indeed. After several minutes, it had filled in only a few pixels, and it then gave a "Memory capacity error". So although it coped well with one "difficult" pattern, it was not robust enough to deal with another one.

Answer 6

As has been stated the problem with standard flood fill is that the buffer size can be enormous so it was somewhat rare for the 8 bit era computers to have a bundled fill routine that didn't impose limitations. I remember playing with a diamond fill variation in the 80s - the Wiki article refers to it as "4-way fill". https://en.wikipedia.org/wiki/Flood_fill

The disadvantage I found is that it executes somewhat slower than a flood fill. But the advantage is that the memory requirement is a lot less - the maximum number of buffer entries would be about 4 times the longest possible 45 degree diagonal line supported by the bitmap mode you're using. As a starting point I used the program provided as DATA within an article in Analog Computing #16 from Feb 1984 (an Atari centred magazine). https://web.archive.org/web/20060308092706fw_/http://www.cyberroach.com:80/analog/an16/default.htm

Full copy of the magazine here though it's ~ 130 Meg and very slow to download: http://www.atarimania.com/mags/pdf/analog_no_16.pdf

In most applications a constrained flood fill isn't greatly useful. It'd be OK for something like a drawing program but not so much for a realtime game e.g. Qix. For something like a graphical adventure that does procedurally generated pics, it'd be OK since you'd obviously test and correct any anomolies during development.

I downloaded the PDF I mentioned earlier - painfully slow and the text is hard to select and when you do grab some the OCR is full of errors. So, I typed in the 6502 assembly routine for the 4-way flood fill.

Someone started a thread over at AtariAge, so grab the routine from it here (hit Spoiler button in the linked thread to expand listing):
http://atariage.com/forums/topic/278446-flood-fill-test/#entry4021426

If I get time in the next few days I'll convert to "Psuedo-code" - to make sense of it you'd need to know 6502 assembly. There's Atari specific stuff in there like pulling A to get passed parameters off the stack, and CIO calls. The parameter stuff, easy to deal with. The CIO stuff - the GET call just expects the pixel value of a given location to be returned in A so could be replaced with a sub call that performs that function, same with the PUT call. Pixel values are just that - masked and shifted so that packed/chunky values equate to what a user would expect. The routine with modification can work on other resolutions so long as they're 0-255 range. Substantial modification to the program would be needed for larger values since 2 byte entries would be needed.

Answer 7

Atari BASIC had a fill operation, but for some reason this was not mapped to a command called FILL, but instead one called XIO.

The background here is that they couldn't fit the BASIC into an 8k ROM. The solution was to move some of the more generic operations out of BASIC into the OS ROM, which had some left-over room. So they moved the floating point routines and graphics over to the OS, and then wrote stubs in BASIC that accessed them.

Although they mapped most of these routines back into BASIC, like PLOT and LINETO, for whatever reason the didn't do a FILL. So in order to access it, you had to use the catch-all OS command, XIO (the IO is for input/output, which is what you would normally use it for). A little mystery to be solved there...

One upside to the code being relocated to the OS was that it was also available to other programming languages. One downside was that the floating point routines were very slow, so anyone that used them also got that slow performance.

Answer 8

The answers specific to each micro are interesting, but I thought it might be useful to compare the classical algorithms from the point of view of theoretical memory requirements. So I implemented a test harness in C and ran it on my MBP.

The test cases are:

• Field of U's, 8x8 chars on a 640x256 canvas, starting from the top and the bottom. This is very close to the animation in my BBC Micro answer.
• Fine grid, 320 columns and 128 rows on a 640x256 canvas. Filling begins either from the corner, from a row in the centre, or from a column in the centre. So far only the MZ-800 has passed this test convincingly, but it has a smaller screen resolution than the BBC Micro.
• Herringbone pattern on a 640x256 canvas, starting from either the first background pixel on the top row, or one in the centre. Nothing has passed this test in the 8-bit category, except for the BBC Micro with reduced screen resolution (320x256).
• Yin-Yang symbol rendered 768 pixels across on a 1024x1024 canvas. This provides several simple shapes which represent a plausible "intended use case" for a compact graphics library.

So far I've got six variants of classical flood-fill algorithms working correctly:

• Pixel Queue with painting before enqueue.
• Pixel Stack with painting before enqueue.
• Pixel Stack with painting after dequeue (this one has the simplest implementation).
• Scanline Queue with painting before enqueue.
• Scanline Stack with painting before enqueue.
• Scanline Stack with painting after dequeue.

Of these, there is a clear categorical difference between the Queue and Stack variants in terms of peak memory usage. For any of the test cases above, the Pixel Stack algorithms require such deep stacks that they would have severe difficulty fitting into an 8-bit micro. For the "grid" and "herringbone" tests, the paint-after-dequeue version additionally requires twice the stack size of the paint-before-enqueue version - as many as 81154 entries for one of the "fine grid" fills, requiring over 240KB RAM just for the stack.

Conversely, if we ignore the Yin-Yang test with its huge canvas, the Pixel Queue algorithm gets away with a 513-entry queue on the worst test case, which is starting the "fine grid" fill on a central row (starting on a column requires 512 entries). If each queue entry requires 3 bytes (one for the Y axis, two for the X), that's a hair over 1.5KB. One of the Yin-Yang fills requires 1160 entries.

The scanline variants show a similar pattern in general, but differ in detail. The Yin-Yang tests are really their forte, as even the most wasteful stack-based variant requires only 4 queue entries on those. They struggle a bit more with the more complex tests, with Scanline Queue requiring 959 entries to cope with starting the "fine grid" fill on a central column, and 381 to fill the herringbone from the centre. These queue entries would also be a bit bigger, requiring 4 bytes each if two X coordinates were packed into 3 bytes. Memory usage could thus go up to 4KB, though performance is generally improved by dealing with runs of pixels in one go.

The BBC Micro (especially the BBC Master, in which the GXR extensions came as standard) has plenty of RAM to make either of the queue-based algorithms work. However, the 6502 makes constructing queues more than 256 entries long a bit awkward, because it only has 8-bit index registers. (Multi-byte queue entries can be split across pages, so you can always have 256 of them.) To index into a longer queue, you need to explicitly construct a pointer in memory. I assume that GXR implemented a 256-entry queue for ease of implementation and for performance reasons, and because it's far more than adequate (with the Scanline Queue algorithm) for the simple, solid shapes that most people want to fill.

I also implemented the Floor Painter algorithm, which uses neither a queue nor a stack and is therefore not memory-constrained. On the Yin-Yang tests, it appears to be similar in performance to the Pixel Queue algorithm, but using less memory. On the synthetic patterns, it still uses no extra memory, but is very slow indeed. I might port this one to the RiscPC instead of the BBC Micro for that reason.

There might still be a bug in the Floor Painter; filling the herringbone from the centre appears to hang, while filling it from the corner didn't take long compared to the fine grid tests. I'll poke it some more with the debugger.

Answer 9

Locomotive BASIC 1.1 on the Amstrad CPC6128 had a fairly decent FILL command. It wasn't the fastest, but then what FILL routines in BASIC were back then? It would do a decent job of filling complex shapes though.

This was one of the differences between 1.1 and the BASIC 1.0 supplied with the CPC464.