20

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 is the shape is too complex.
  • 1
    Many Microsoft BASIC's supported the PAINT routine, including QBasic and Amiga Basic. – Brian H May 28 '17 at 4:00
  • @Brian Sure, that's where the Elektronika BASIC, mimicking MSX BASIC, got its PAINT from, but did PAINT in the original Microsoft BASICs work in a robust way for complex shapes? – Leo B. May 28 '17 at 5:09
  • The BASIC on the Commodore 16, Plus/4, and Commodore 128 all have a PAINT command. Also, the Super Expander (VIC-20) and Super Expander 64 (C64) and Simons BASIC (C64) each have a PAINT command. – Tim Locke May 28 '17 at 11:18
  • @TimLocke OK, and how well do they work on the example(s) in the question? – Leo B. May 28 '17 at 17:59
  • Look up the so called drunkard's walk algorithm.... – rackandboneman May 29 '17 at 9:15
11

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:

amstrad cpc fill

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.

  • I think that 40x25 is too coarse a grid to elicit a stack overflow on a 128 Kb computer. How many levels of GOSUB nesting does it allow (10 GOSUB 100; 100 PRINT I; 110 I=I+1; 120 GOSUB 100)? Elektronica displays an error at line 120 after printing 3459. – Leo B. May 29 '17 at 5:31
  • Locomotive BASIC gets to 83 before exiting with a Memory full error. The Amstrad CPCs were 8-bit Z80 machines. The extra memory was bank-switched in 16K pages, and most often used in CP/M+. I had difficulty getting your single-pixel grid to fill, that's why I came up with my own test. It's not 40×25, but 320×200 pixels – scruss May 29 '17 at 13:04
  • What kind of difficulty did you have with the single-pixel grid? Doesn't it prove that the algorithm is not robust? For the Scanline fill variation of the algorithm the resolution does not matter, it's the number of obstacles" per line and per column that affects the stack depth. – Leo B. May 29 '17 at 16:47
  • Note your example is not the worst case for a recursive flood fill: Filling a patterned area makes the recursion terminate early and saves stack space. Worst case for the algorithm is a large empty rectangle being filled from one corner. – tofro May 30 '17 at 8:13
  • @LeoB. it seems that the FILL command didn't like single-pixel widths. I'll try again alter, as I may have been doing it wrongly. To @tofro's comment, the CPC has no problem filling a blank 640×200 screen (MODE 2 : MOVE 0,0 : FILL 1) from the corner, so it might not be using a recursive algorithm – scruss May 30 '17 at 12:57
10

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.

  • That's cute, but was there a way to draw a filled non-simply connected shape, e. g. a thick ring? – Leo B. May 29 '17 at 16:50
  • Draw two half-rings (cut vertically) and fill them. – tofro May 29 '17 at 17:16
  • Actually, even a simply-connected shape can present problems for this algorithm. Consider a two-sided fine-toothed comb. It will need multiple starting coordinates per line to work properly. – Leo B. May 29 '17 at 18:07
  • 1
    Then it wasn't a flood fill operator. :) – Leo B. May 29 '17 at 18:22
  • 1
    Definitely disputable and depends on your definition. But I rather have something that works and is a bit inconvenient to use than something that crashes the computer in cases (which I wouldn't call a working FF command as well ;) ). – tofro May 29 '17 at 18:36
7

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.

BeebEm capture

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:

BeebEm screenshot

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.

  • 1
    Now that's a real flood fill; it even looks like a flood! :-) – wizzwizz4 Apr 26 '18 at 19:08
  • How about the herringbone pattern? – Leo B. May 2 '18 at 2:55
  • I was able to recreate the pattern on my emulated BBC Master, and in MODE 1 (320x256, 4c) with a centred start point, it completed the fill correctly. In MODE 0 (640x256, 2c) it halted after completing a large hexagon-shaped area. So it's not quite as tough a test as the fine grid. – Chromatix May 2 '18 at 3:39
  • @LeoB. I believe the GXR algorithm uses a 256-entry circular buffer, and when the head meets the tail it believes the queue is empty (when it's actually full). Therefore it halts and returns control instead of overwriting stuff it shouldn't. The herringbone is a tougher test than the field of U's, and nearly hits the queue capacity in Mode 1. – Chromatix May 2 '18 at 3:48
3

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.

2

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.

  • There's also a "floor painter" algorithm which operates in constant memory - about 16 bytes, or less if your screen is always smaller than 256 pixels in one or both dimensions. It's probably slower than a stack or queue algorithm when faced with a complex area to fill, but is guaranteed to complete without running out of RAM. – Chromatix May 5 '18 at 6:52
  • Your "4-way fill" seeems to be a breadth-first search of the fillable space. It performs better (with respect to memory) on large open areas than a recursive depth-first fill -- but one can construct intricate mazes where up to around every sixteenth pixel on the entire screen are in the last generation of the filling, and therefore need to be on the work list at the same time. – Henning Makholm May 5 '18 at 16:34
  • @HenningMakholm: I tried to construct particularly nasty patterns to test the fill routine and was never able to make anything particularly nasty. If I was missing something, that might be an interesting puzzle. – supercat May 5 '18 at 22:51
  • 2
    @supercat: I had in mind a fractal construction like i.stack.imgur.com/SLmZS.png -- the black pixels are walls. The ones marked in red will all be colored in generation 219 after flooding starts from the middle of the upper edge; they number more than one seventh of all the pixels. – Henning Makholm May 6 '18 at 1:45
  • @HenningMakholm Looks like a very interesting test pattern; I'll see if I can replicate it in my test suite. – Chromatix May 6 '18 at 21:37
1

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.

  • Yes, but how robust was it? – Wilson May 2 '18 at 16:01
  • Sounds like a similar situation to the BBC Micro. That had 16KB ROMs, one each for the MOS, BASIC, and DFS. Graphics were considered an MOS feature and accessed through the VDU driver's OSWRCH call, plus some OSBYTE calls for less-frequent queries. Floating-point calculations were considered a language feature and implemented in the BASIC ROM, so other languages had to duplicate them. – Chromatix May 2 '18 at 19:42
  • More to the point, which of the many Atari computers is this relevant to? If we know that, we can test the fill routine using an emulator and the test patterns used elsewhere in this thread. – Chromatix May 2 '18 at 19:46
  • 1
    I managed to dig out an Atari 800XL emulator and a copy of the Atari BASIC manual. The fill routine only works to fill colour 0 with something else, so I made a "field of dots" to simulate the "fine grid", and started the fill from the middle of the screen. This made the machine reset after incompletely processing half the screen, in a manner strongly suggestive of a stack-based algorithm. – Chromatix May 4 '18 at 23:56
  • 1
    Even worse results with the herringbone pattern; it only "filled" a diagonal line to the southeast corner before resetting. Moreover, the thing throws an error if you try to plot outside the screen, instead of simply discarding the nonexistent pixels as the BBC Micro does. Not very impressive, really. – Chromatix May 5 '18 at 0:10
1

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.

  • Incidentally, another algorithm which may be usable if there are at least four colors that would be recognized as "edges" is to use a backtracking algorithm, but initially fill each pixel with a color that indicates its direction from the previous one. When backtracking, observe the color of each pixel, paint it with the final color, and move in the direction the pixel's color had indicated. That approach will allow any size screen to be flood-filled with O(1) memory outside the screen pixel array. – supercat May 6 '18 at 23:44
  • @supercat That presupposes you conveniently have several colours in the palette exclusively for use by the fill routine. In effect, it's just another way of saying you need O(N) storage, where N is the number of pixels involved. – Chromatix May 7 '18 at 6:19
  • It's not necessary that the colors be reserved exclusively for the fill routine. All that is necessary is that they be recognizable as edge colors; as I think about it, even that might not be necessary if one is sufficiently clever. Divide colors into "fill", "edge", or "anything else". Use right-hand rule to follow the boundary of what one can fill, and paint places one goes straight with "edge" color and places where one turns right with "fill" color. When backtracking, the color of a square combined with the direction of backtracking will indicate the direction to backtrack next. – supercat May 7 '18 at 15:03
  • Operations whose job it is to change the contents of some storage in some way do not usually count that storage in the "space" requirement. Sorting algorithms, for example, are usually allowed to write and read back "array slots". While one could perform a selection sort that required O(1) space and could never read back anything it had written (e.g. producing a sorted printout from a list stored on CD-ROM) such things are very seldom required. – supercat May 7 '18 at 15:45
  • @supercat With sorting algorithms, the object is to rearrange the items, so rearranging them is allowed. With a fill routine, you either can't predict what the edge colours might be (you're given the background colour) or you can't predict the colours already present in the area to fill (you're given the edge colour). So unless there are colours specifically reserved, you can't rely on the framebuffer itself for storage. Either way, it counts as auxiliary memory because you're storing values not found in the input. – Chromatix May 7 '18 at 16:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.