Games programming is very challenging because each new game demands innovation and features which are different from past games. This usually means that we have to come up with new routines that are written from scratch for each game. Business programmers have got it easy - they can draw on stock routines such as calculators, display routines etc. and just tailor the stock routines into a new package with a so called ‘new’ product at the end of the day.
The subject of this month's discussion is the ‘fill’ routine. It will always be associated with graphical programs by virtue of its task, but it is seldom seen in games because, quite frankly, a ‘fill’ usually runs at a snail's pace. However, a programmer would not usually come up with a new fill algorithm and I have used the same program for years now.
Figure 1 has the source code listing in machine code for the basic fill algorithm. It is quite short considering the job it has to do but then again it is fairly efficient in terms of speed. The program is quite complex in operation as it is recursive - i.e. it keeps calling itself until it has finished.
This term needs a little explanation. A common routine structure is a LOOP. Loops appear all over the place. FOR/NEXT instructions in BASIC are probably the type known to most people but the format is nearly always as shown here, using a counter:
Using a test to terminate the loop:
The first stage in a loop structure can involve setting a counter. This is followed by the program main body and finally there is some form of ‘decrement counter and jump back if not zero’ type of arrangement. The number of loops is determined by a counter or it could be a test - say reading a keyboard to see if a key is being pressed. A loop cannot loop forever or we would have a ‘lock-up’ situation and so there is always some conditional situation for a loop to work successfully. A RECURSIVE program is one whereby it CALLs itself from within itself:-
PROGRAM:
CALL PROGRAM
RET
Yes, it is daft! The code above would just make the machine crash. It is not the same as a lock-up condition that can happen in a bug-ridden loop, but it is making the stack grow to enormous proportions until something gives. Practical recursion is not as daft as this but is typically like this instead:
LD (MEM), SP
PROGRAM:
CALL COMPLICATED_TEST
CALL NZ, PROGRAM
LD SP, (MEM)
RET
This is only an illustration of what a recursive routine is all about. In the above instance, the sub-routine COMPLICATED_TEST has a conditional result - namely, zero or not zero. In the not-zero case the whole lot is called again (with the stack growing by two bytes per call). If we relate this to the fill routine, we can see that the complex task of determining which pixels need ‘filling’ can only be done on a pixel-by-pixel basis. Effectively we check one pixel to see if it is filled and we store the status of the four pixels adjacent to the one we are testing.
If any of the four adjacent pixels need filling then we will want to re-enter the program again but with a new central pixel forming the basis of the complicated test. This will happen until there are no more pixels to fill and all adjacent ones have been filled - hence the condition to loop back will fail when the program has done its job. The stack pointer can be restored as shown for simplicity. The fill routine in figure 1 does not actually CALL itself from within but jumps back at FI130.
Before you say ‘ah, but that's a conditional loop then’, just look at the couple of PUSH HL and PUSH AF instructions embedded in the main body of code. These pushes contain a screen co-ordinate and flags for the testing process to determine pixels which need filling. Initially BC is used to push FF00H on the stack as a stop code. As the various values get ‘popped’ off the stack we only return when this value of FF00H crops up. This is our condition that prevents the program going mad and never returning.
A recursive routine is a very difficult type of routine to design and unfortunately it seems to be cropping up in more and more kinds or programming areas. The printed circuit-board design packages which are being used in the CAD field are a good example of recursive design.
The routine wants typing into an assembler and basically you can assemble it anywhere convenient but do remember to provide adequate RAM for the stack to grow (downwards, remember!) I have omitted to put a stack check in this program as it only makes it longer and more complicated. In practice I just allow 600 bytes or so of stack space and this is usually enough. Only in this case it is not really a blank but part of the design of a tile pattern. Plotting tile patterns will only succeed in making the routine lock-up, as it would be going around in circles trying to do the job!
Sinclair User
|