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.