| helpline |
Andrew Hewson fills in the gaps
TACKLING a problem I have not attempted previously, I aim to describe how to "paint in" an area on the screen.
Consider the rather crude picture of the dog called Spike illustrated in figure one. Spike consists of 45 numbered points and we can imagine that each point is a pixel on the Spectrum screen. Spike's outline is determined by the asterisk characters. Suppose we have a program which will PLOT Spike's shape, i.e., one which will PLOT a pixel at points equivalent to the positions of the asterisks. Our problem is to write a program which will fill in all the internal points by PLOTting a pixel at each of the 4 5 internal points.
The solution must be general enough to work for any shape, no matter how convoluted, and for any starting-point in the shape. In practice, that means the painting program must keep track of the status of the pixels adjacent to the one which it is painting.
Suppose, for example, the program starts on Spike at position 0 and moves to the right, painting as it goes. It must look and remember that position 5 to the left of position 0 also needs to be painted in when it has completed the current line. The program listed in table one will paint Spike in the order of the numbers on the diagram using the look-and-remember principle.
The program is written so that its subroutines can be MERGEd into the user's program and the region-fill can thus be invoked with a GOSUB. It must be borne in mind that the inherent slowness of Basic is very apparent in this application, so it will normally be necessary to use a machine code routine.
The program remembers unpainted pixels by storing their location and other pertinent information on a pseudo-stack held in the two-dimensional character array S$. A stack is a very useful device for storing information in many circumstances, as it works on a last in, first out principle. The Z-80 makes use of a stack to keep track of the return addresses of its current routines and Sinclair has copied the principle in the Spectrum for holding the line numbers to which RETURNS are made.
Thus whenever the program completes the task of painting a line of pixels it looks to the stack for a new location at which to start painting again. The act of storing information is called, in Z-80 jargon, PUSHing, and retrieving information is called POPping.
The program also uses a recursive technique of which readers may not have heard previously. A recursive routine is one which is able to call itself and returns to itself when it has finished. At first sight that may seem to be impossible but with careful programming and the use of a stack it is a compact and efficient technique.
The easiest way to understand recursion is to follow the logic of a program which uses it, as explained, but the reader who has never encountered it might like to bear in mind the old joke about the entry in a dictionary of computing under the word recursion which read: Recursion - see recursion.
The program in table one consists of a test routine of a circle in a square and a call to the subroutine at line 1000 which executes the task. In the following explanation, however, the reader should refer to Spike the dog in figure one. The E11 routine is invoked by a GOSUB 1000, with x and y containing the x and y ordinates of any point inside the region to be filled.
At line 1000, a check is made to ensure that (x,y) is within the Spectrum screen and at 1010 a check is made to see if the point is PAPER or INK. If (x, y) is OUT OF SCREEN or is INK i.e., on the border of the region - an immediate RETURN is made. Otherwise the local variables - that is to say the ones used in this module only and not needed elsewhere are cleared to zero.
Line 1200 is where the work starts. The two formal parameters, x and y, are saved on stack along with the local variables left, right and here. Note that since screen co-ordinates lie in the range 0 to 255, the values can be saved as a single byte in a byte array as opposed to five bytes as in a floating point array, thus saving 20 bytes per level of the stack.
At lines 1245-1250,asecond check is made for (x, y) being out of screen or ink. Those checks are required a second time because the subroutine re-enters itself recursively at line 1200, thus missing the checks at line 1000. If the conditions are met, GOTO 1340 causes the removal of the most recently saved set of local variables from the stack prior to RETURNING, so that the number of PUSHes and POPs balance.
Next, the positions of the right-most and left-most PAPER pixels which occur before any kind of obstruction are found. Those SCANs are made INK, and right and left are given the values of their respective x-ordinates. In the case of Spike the dog, starting at point 0 - 1, 2, 3 and 4 are filled; right becomes 4; then 5, 6, 7 are filled and left becomes 7. A11 those operations are carried out by calling the subroutine at 1500.
The region-fill routine contains several subroutines. The Basic subroutine called SCAN is listed in lines 15001550. It starts at the point (x, y), and scans rightwards along a row of pixels, making each one INK until an INK pixel is reached. The x-ordinate of the of the right-most PAPER pixel is put into right. It then scans leftwards from (x, y), INKing as before, putting the left-most PAPER pixel's x-ordinate into left.
The plotting is performed by the subroutine at line 2000 which is called twice, once for moves to the right and once for moves to the left. It knows in which direction to scan from the value of dir because dir is added to the x-ordinate of the next pixel to be INKed, and so a value of +1 will cause a move right and -1 will cause a move left.
SCAN is called from line 1270. On return, here takes on the value of left, the left-most pixel in the current (y) line. Line 1300 causes the search for left and right ends to restart from the line above.
Lines 1290-1325 are the most difficult part of the routine to understand. What they say, for Spike, is 'Move up to point 8 (y=CODE s$(sp,z)+1). Then call myself, recursively, from line 1300 to scan points 9-16 then 17 and 18 in the same way as I did 1-4 and 5-7. At line 1300 again, point 18, move up one line and scan right then left. As there is only one point, left and right both become 19. Do the same again, producing point 20. Then, on the next GOSUB 1200 from line 1300, line 1250 will sense that point 20 is already INK, so an immediate POP/RETURN takes place. I execute line 1310 to scan one line downwards and again, at 1250, an INK pixel is found - so I POP/ RETURN. I am now at line 1320, with here being point 18. I increment here and loop back to line 1300 where the procedure recurses for point 17.
As the pixels above and below point 17 are both INK, I loop back to line 1300 and try again for point 8. That goes on until I reach point 15, where I find that the pixel above is still PAPER. I fill this, scan right and left recursively, but I have INK on all four sides. Here is thus incremented to point to point 16 and I try up and down again. That fails, so here is incremented to point to the right of point 16, so here ceases to be less than or equal to right and I go onto POP/RETURN at line 1340.
Having returned from my original GO SUB 1200 at line 1300, I can execute line 1310. That causes me to scan down one line and begin the right-left movement from point 22. I scan right, left, up, down repeatedly until all PAPER pixels become INK. Eventually I am back at point 4 and line 1320. I increment here, the test at line 1325 fails, and I POP. Then the RETURN picks up the return address from the main body of the program where I GO SUB 1000 '0, and I have finished.
It can be seen that once scanning is started on the line below point 7, all the upward scans are redundant, since the higher points are all INK. There is a similar redundancy when points 8, 9, 10 .. are being scanned to 'find' point 21. Those redundant statements must still be performed for recursion to work properly, as they will cease eventually to be redundant - e.g., at point 15. The routine appears to stop for a time on its way downwards while the redundant cads are being performed and then the return addresses are being pulled off the stack. That is a feature of recursion.
To show the extent of stack usage, the demonstration program fills the area of a square with an inner circle, avoiding the inside of the circle. Lines 1205 and 2025 are test lines to display the stack pointer and x and y parameters on each successive call. They show how stack space is gobbled up.
| ||||||||||
