Home » Archimedes archive » Acorn User » AU 1994-09.adf » !StarInfo_Star » Morris/!Dizzy/!Help
Morris/!Dizzy/!Help
This website contains an archive of files for the Acorn Electron, BBC Micro, Acorn Archimedes, Commodore 16 and Commodore 64 computers, which Dominic Ford has rescued from his private collection of floppy disks and cassettes.
Some of these files were originally commercial releases in the 1980s and 1990s, but they are now widely available online. I assume that copyright over them is no longer being asserted. If you own the copyright and would like files to be removed, please contact me.
| Tape/disk: | Home » Archimedes archive » Acorn User » AU 1994-09.adf » !StarInfo_Star |
| Filename: | Morris/!Dizzy/!Help |
| Read OK: | ✔ |
| File size: | 1AE8 bytes |
| Load address: | 0000 |
| Exec address: | 0000 |
File contents
!Dizzy
------
By Henley
---------
Heres a little graphical demonstration that really shows that the Arc is no
slowcoach - even without any graphics hardware. Not many computers can
rotate, transform, sort, mask and plot around 285-300 16x16 sprites in under
0.02 seconds!
Although A5000 users will definately recieve 50 frames per second, some of
the more complicated shapes will slow down to 25 fps on slower processors.
Regular BAU readers may notice a distinct similarity between !Dizzy and
Tim Jones' "Dots" from April 1993, from where the initial inspiration was
derived. The first 9 shapes are mostly Tims' work.
Hold down SPACE for a new shape, RETURN to pause, and ESCAPE to quit.
How it works
------------
Each 'ball' is initially given four pieces of information, a colour and
three co-ordinates - X, Y, and Z (depth). The colour is from 1-6 and then
multiplied by &600 to assist the plotting routine, as this is the offset for
each different coloured ball. The colours are as follows;
Red Yellow Green Blue Cyan Magenta
1 2 3 4 5 6
There are eight versions of every ball, each one is offset by one pixel so
that we can address the screen in words rather than bytes, allowing a great
speed increase. Each ball is 16x16 pixels, and in Mode 9 one word (four
bytes) contains 8 pixels. The actual plotting width for the sprite routine
is 24 pixels (3 words) to allow for overflow with each x offset.
Immediately following all this information is the same data, only this time,
it is a masked version of each ball.
(1 word) x (width) x (height) x (offsets)
4 * 3 * 16 * 8 = &600
For each screen update (1/50th second hopefully), we must perform the
following tasks;
a) Clear the screen
b) Rotate each ball about two axis
c) Add perspective and transform to a 2D plane
d) Sort all the balls by depth
e) Plot all the balls in order, from back to front.
Rotation
--------
There are many ways of applying rotation to 3D co-ordinates. !Dizzy makes
use of two relatively simple formulae, that provide combined rotation about
the X and Z axis. These were chosen somewhat arbitrarily, and in fact could
be any other combination of X, Y or Z, but for reference they are provided
here in mathematical form.
Where x, y, and z are input co-ordinates, and angle is a degree value
s = SIN angle c = COS angle
X Axis Y Axis Z Axis
------ ------ ------
X = x X = x*c+z*s X = x*c-y*s
Y = y*c-z*s Y = y Y = x*s+y*c
Z = y*s+z*c Z = z*c-x*s Z = z
Once we have derived our new rotated set of co-ordinates, we must then apply
a further transformation for display within a two dimensional plane - our
computer screen. Remember that we have 3 co-ordinates for each ball, and
only two axis (X and Y) on which to plot them.
This is where perspective is applied which gives an illusion of depth, and
is really not so complicated as it sounds.
X2D = (X*scale) / (Z+rho)
Y2D = (Y*scale) / (Z+rho)
Where X, Y, and Z are 3D input co-ordinates
scale is an overall size factor (or viewing distance)
and rho is the perspective constant
Optimum values for 'scale' and 'rho' are hard to define, although lower
values of rho (toward zero) usually result in very exaggerated perspective.
As a general rule, reasonable results are usually achieved if rho is set to
scale/2.
!Dizzy uses a lot of 'tricks' to gain speed. One such trick removes the need
for any division (a sadly absent ARM instruction) with the above
transformation and is based on the theory that all division can be replaced
by multiplication if you've got the spare RAM! Let's elaborate.
e.g. 100/9 = 100 * (1/ 9) = 11.11111
1234/81 = 1234 * (1/81) = 15.234593
And there it is. We simply multiply our number by the fraction of the
divisor, and as long as we create a lookup table of 1/x functions for every
'x' we are likely to use, this method is perfectly acceptable, and requires
just one MUL instruction. One drawback of this scheme is that any remainder
is disregarded.
In the case of !Dizzy where we are dividing by the Z co-ord, the range is
from appox. -200 to +200, which requires a 400*4 = 1600 byte table.
Sorting (that old chestnut!)
----------------------------
Rotation and perspective are all very well for realism, however there is a
final hurdle before any real impression of 3D space can be attained, and
that is depth sorting.
Sorting has long been the bane of any programmers life and there are many
different ways of sorting data. The bubble sort is the simplest, and
unfortunately one of the slowest.
!Dizzy makes use of a 'bin' sort, which like everything is very simple in
theory. It works by creating a set of 'pidgeon holes' for every possible
value that may exist within the data to be sorted. In the case of !Dizzy, we
are only concerned with sorting each balls Z co-ordinate, and as these have
an imposed limit of -160 to 159, we reserve 320 spaces.
The sort routine then scans through the co-ordinates and slots each Z into
it's respective address, for instance, a Z co-ord of 5 goes into address 5
and so on until all the co-ords have been allotted.
Having done this, it is a simple matter of scanning through the list from
-160 to 159 and plotting the relevant ball from each address, which is
already depth sorted.
Simple huh? Well no, because we have overlooked one important fact. What if
there is more than one ball with the same Z co-ord? We have only reserved
one address for each balls Z, and so if there are two or more balls with the
same Z, there will be balls missing when we come to plot them.
Solution: Reserve another set of pidgeon holes in the guise of a stack, to
contain any overflow.
So now what happens is, when we come to place a Z co-ord into its allotted
address, we must first check that there isn't already something in there. If
not, everything is fine - we store it and carry on.
If however, the address is already full, we *stack* the new z in the reserve
address, and add a pointer to our origional (full) address telling us
whereabouts on the stack the second co-ord is. If any more duplicate Z
co-ords come along, we do the same, but adding the last pointer to this new
Z before we stack it.
In this way, the first (full) address we come across, ALWAYS points to the
most recent duplicate that has been stacked, and when we retrive that
duplicate, it points to the one before, and so on until there are no more
pointers meaning that we have reached the very first duplicate that was
stacked.
Examples.BinSort shows this algorithm working from BASIC.
00000000 21 44 69 7a 7a 79 0a 2d 2d 2d 2d 2d 2d 0a 42 79 |!Dizzy.------.By| 00000010 20 48 65 6e 6c 65 79 0a 2d 2d 2d 2d 2d 2d 2d 2d | Henley.--------| 00000020 2d 0a 0a 48 65 72 65 73 20 61 20 6c 69 74 74 6c |-..Heres a littl| 00000030 65 20 67 72 61 70 68 69 63 61 6c 20 64 65 6d 6f |e graphical demo| 00000040 6e 73 74 72 61 74 69 6f 6e 20 74 68 61 74 20 72 |nstration that r| 00000050 65 61 6c 6c 79 20 73 68 6f 77 73 20 74 68 61 74 |eally shows that| 00000060 20 74 68 65 20 41 72 63 20 69 73 20 6e 6f 0a 73 | the Arc is no.s| 00000070 6c 6f 77 63 6f 61 63 68 20 2d 20 65 76 65 6e 20 |lowcoach - even | 00000080 77 69 74 68 6f 75 74 20 61 6e 79 20 67 72 61 70 |without any grap| 00000090 68 69 63 73 20 68 61 72 64 77 61 72 65 2e 20 4e |hics hardware. N| 000000a0 6f 74 20 6d 61 6e 79 20 63 6f 6d 70 75 74 65 72 |ot many computer| 000000b0 73 20 63 61 6e 0a 72 6f 74 61 74 65 2c 20 74 72 |s can.rotate, tr| 000000c0 61 6e 73 66 6f 72 6d 2c 20 73 6f 72 74 2c 20 6d |ansform, sort, m| 000000d0 61 73 6b 20 61 6e 64 20 70 6c 6f 74 20 61 72 6f |ask and plot aro| 000000e0 75 6e 64 20 32 38 35 2d 33 30 30 20 31 36 78 31 |und 285-300 16x1| 000000f0 36 20 73 70 72 69 74 65 73 20 69 6e 20 75 6e 64 |6 sprites in und| 00000100 65 72 0a 30 2e 30 32 20 73 65 63 6f 6e 64 73 21 |er.0.02 seconds!| 00000110 0a 0a 41 6c 74 68 6f 75 67 68 20 41 35 30 30 30 |..Although A5000| 00000120 20 75 73 65 72 73 20 77 69 6c 6c 20 64 65 66 69 | users will defi| 00000130 6e 61 74 65 6c 79 20 72 65 63 69 65 76 65 20 35 |nately recieve 5| 00000140 30 20 66 72 61 6d 65 73 20 70 65 72 20 73 65 63 |0 frames per sec| 00000150 6f 6e 64 2c 20 73 6f 6d 65 20 6f 66 0a 74 68 65 |ond, some of.the| 00000160 20 6d 6f 72 65 20 63 6f 6d 70 6c 69 63 61 74 65 | more complicate| 00000170 64 20 73 68 61 70 65 73 20 77 69 6c 6c 20 73 6c |d shapes will sl| 00000180 6f 77 20 64 6f 77 6e 20 74 6f 20 32 35 20 66 70 |ow down to 25 fp| 00000190 73 20 6f 6e 20 73 6c 6f 77 65 72 20 70 72 6f 63 |s on slower proc| 000001a0 65 73 73 6f 72 73 2e 0a 0a 52 65 67 75 6c 61 72 |essors...Regular| 000001b0 20 42 41 55 20 72 65 61 64 65 72 73 20 6d 61 79 | BAU readers may| 000001c0 20 6e 6f 74 69 63 65 20 61 20 64 69 73 74 69 6e | notice a distin| 000001d0 63 74 20 73 69 6d 69 6c 61 72 69 74 79 20 62 65 |ct similarity be| 000001e0 74 77 65 65 6e 20 21 44 69 7a 7a 79 20 61 6e 64 |tween !Dizzy and| 000001f0 0a 54 69 6d 20 4a 6f 6e 65 73 27 20 22 44 6f 74 |.Tim Jones' "Dot| 00000200 73 22 20 66 72 6f 6d 20 41 70 72 69 6c 20 31 39 |s" from April 19| 00000210 39 33 2c 20 66 72 6f 6d 20 77 68 65 72 65 20 74 |93, from where t| 00000220 68 65 20 69 6e 69 74 69 61 6c 20 69 6e 73 70 69 |he initial inspi| 00000230 72 61 74 69 6f 6e 20 77 61 73 0a 64 65 72 69 76 |ration was.deriv| 00000240 65 64 2e 20 54 68 65 20 66 69 72 73 74 20 39 20 |ed. The first 9 | 00000250 73 68 61 70 65 73 20 61 72 65 20 6d 6f 73 74 6c |shapes are mostl| 00000260 79 20 54 69 6d 73 27 20 77 6f 72 6b 2e 0a 0a 48 |y Tims' work...H| 00000270 6f 6c 64 20 64 6f 77 6e 20 53 50 41 43 45 20 66 |old down SPACE f| 00000280 6f 72 20 61 20 6e 65 77 20 73 68 61 70 65 2c 20 |or a new shape, | 00000290 52 45 54 55 52 4e 20 74 6f 20 70 61 75 73 65 2c |RETURN to pause,| 000002a0 20 61 6e 64 20 45 53 43 41 50 45 20 74 6f 20 71 | and ESCAPE to q| 000002b0 75 69 74 2e 0a 0a 0a 48 6f 77 20 69 74 20 77 6f |uit....How it wo| 000002c0 72 6b 73 0a 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d |rks.------------| 000002d0 0a 0a 45 61 63 68 20 27 62 61 6c 6c 27 20 69 73 |..Each 'ball' is| 000002e0 20 69 6e 69 74 69 61 6c 6c 79 20 67 69 76 65 6e | initially given| 000002f0 20 66 6f 75 72 20 70 69 65 63 65 73 20 6f 66 20 | four pieces of | 00000300 69 6e 66 6f 72 6d 61 74 69 6f 6e 2c 20 61 20 63 |information, a c| 00000310 6f 6c 6f 75 72 20 61 6e 64 0a 74 68 72 65 65 20 |olour and.three | 00000320 63 6f 2d 6f 72 64 69 6e 61 74 65 73 20 2d 20 58 |co-ordinates - X| 00000330 2c 20 59 2c 20 61 6e 64 20 5a 20 28 64 65 70 74 |, Y, and Z (dept| 00000340 68 29 2e 20 54 68 65 20 63 6f 6c 6f 75 72 20 69 |h). The colour i| 00000350 73 20 66 72 6f 6d 20 31 2d 36 20 61 6e 64 20 74 |s from 1-6 and t| 00000360 68 65 6e 0a 6d 75 6c 74 69 70 6c 69 65 64 20 62 |hen.multiplied b| 00000370 79 20 26 36 30 30 20 74 6f 20 61 73 73 69 73 74 |y &600 to assist| 00000380 20 74 68 65 20 70 6c 6f 74 74 69 6e 67 20 72 6f | the plotting ro| 00000390 75 74 69 6e 65 2c 20 61 73 20 74 68 69 73 20 69 |utine, as this i| 000003a0 73 20 74 68 65 20 6f 66 66 73 65 74 20 66 6f 72 |s the offset for| 000003b0 0a 65 61 63 68 20 64 69 66 66 65 72 65 6e 74 20 |.each different | 000003c0 63 6f 6c 6f 75 72 65 64 20 62 61 6c 6c 2e 20 54 |coloured ball. T| 000003d0 68 65 20 63 6f 6c 6f 75 72 73 20 61 72 65 20 61 |he colours are a| 000003e0 73 20 66 6f 6c 6c 6f 77 73 3b 0a 0a 20 20 20 20 |s follows;.. | 000003f0 20 20 20 20 20 52 65 64 20 20 20 59 65 6c 6c 6f | Red Yello| 00000400 77 20 20 20 47 72 65 65 6e 20 20 20 42 6c 75 65 |w Green Blue| 00000410 20 20 20 43 79 61 6e 20 20 20 4d 61 67 65 6e 74 | Cyan Magent| 00000420 61 0a 20 20 20 20 20 20 20 20 20 20 31 20 20 20 |a. 1 | 00000430 20 20 20 20 32 20 20 20 20 20 20 20 33 20 20 20 | 2 3 | 00000440 20 20 20 20 34 20 20 20 20 20 20 35 20 20 20 20 | 4 5 | 00000450 20 20 20 36 0a 0a 54 68 65 72 65 20 61 72 65 20 | 6..There are | 00000460 65 69 67 68 74 20 76 65 72 73 69 6f 6e 73 20 6f |eight versions o| 00000470 66 20 65 76 65 72 79 20 62 61 6c 6c 2c 20 65 61 |f every ball, ea| 00000480 63 68 20 6f 6e 65 20 69 73 20 6f 66 66 73 65 74 |ch one is offset| 00000490 20 62 79 20 6f 6e 65 20 70 69 78 65 6c 20 73 6f | by one pixel so| 000004a0 0a 74 68 61 74 20 77 65 20 63 61 6e 20 61 64 64 |.that we can add| 000004b0 72 65 73 73 20 74 68 65 20 73 63 72 65 65 6e 20 |ress the screen | 000004c0 69 6e 20 77 6f 72 64 73 20 72 61 74 68 65 72 20 |in words rather | 000004d0 74 68 61 6e 20 62 79 74 65 73 2c 20 61 6c 6c 6f |than bytes, allo| 000004e0 77 69 6e 67 20 61 20 67 72 65 61 74 0a 73 70 65 |wing a great.spe| 000004f0 65 64 20 69 6e 63 72 65 61 73 65 2e 20 45 61 63 |ed increase. Eac| 00000500 68 20 62 61 6c 6c 20 69 73 20 31 36 78 31 36 20 |h ball is 16x16 | 00000510 70 69 78 65 6c 73 2c 20 61 6e 64 20 69 6e 20 4d |pixels, and in M| 00000520 6f 64 65 20 39 20 6f 6e 65 20 77 6f 72 64 20 28 |ode 9 one word (| 00000530 66 6f 75 72 0a 62 79 74 65 73 29 20 63 6f 6e 74 |four.bytes) cont| 00000540 61 69 6e 73 20 38 20 70 69 78 65 6c 73 2e 20 54 |ains 8 pixels. T| 00000550 68 65 20 61 63 74 75 61 6c 20 70 6c 6f 74 74 69 |he actual plotti| 00000560 6e 67 20 77 69 64 74 68 20 66 6f 72 20 74 68 65 |ng width for the| 00000570 20 73 70 72 69 74 65 20 72 6f 75 74 69 6e 65 0a | sprite routine.| 00000580 69 73 20 32 34 20 70 69 78 65 6c 73 20 28 33 20 |is 24 pixels (3 | 00000590 77 6f 72 64 73 29 20 74 6f 20 61 6c 6c 6f 77 20 |words) to allow | 000005a0 66 6f 72 20 6f 76 65 72 66 6c 6f 77 20 77 69 74 |for overflow wit| 000005b0 68 20 65 61 63 68 20 78 20 6f 66 66 73 65 74 2e |h each x offset.| 000005c0 0a 0a 49 6d 6d 65 64 69 61 74 65 6c 79 20 66 6f |..Immediately fo| 000005d0 6c 6c 6f 77 69 6e 67 20 61 6c 6c 20 74 68 69 73 |llowing all this| 000005e0 20 69 6e 66 6f 72 6d 61 74 69 6f 6e 20 69 73 20 | information is | 000005f0 74 68 65 20 73 61 6d 65 20 64 61 74 61 2c 20 6f |the same data, o| 00000600 6e 6c 79 20 74 68 69 73 20 74 69 6d 65 2c 0a 69 |nly this time,.i| 00000610 74 20 69 73 20 61 20 6d 61 73 6b 65 64 20 76 65 |t is a masked ve| 00000620 72 73 69 6f 6e 20 6f 66 20 65 61 63 68 20 62 61 |rsion of each ba| 00000630 6c 6c 2e 0a 0a 20 20 20 20 20 20 20 20 28 31 20 |ll... (1 | 00000640 77 6f 72 64 29 20 78 20 28 77 69 64 74 68 29 20 |word) x (width) | 00000650 78 20 28 68 65 69 67 68 74 29 20 78 20 28 6f 66 |x (height) x (of| 00000660 66 73 65 74 73 29 0a 20 20 20 20 20 20 20 20 20 |fsets). | 00000670 20 34 20 20 20 20 20 20 2a 20 20 20 20 33 20 20 | 4 * 3 | 00000680 20 20 2a 20 20 20 20 31 36 20 20 20 20 2a 20 20 | * 16 * | 00000690 20 20 38 20 20 20 20 20 20 20 3d 20 20 26 36 30 | 8 = &60| 000006a0 30 0a 0a 0a 46 6f 72 20 65 61 63 68 20 73 63 72 |0...For each scr| 000006b0 65 65 6e 20 75 70 64 61 74 65 20 28 31 2f 35 30 |een update (1/50| 000006c0 74 68 20 73 65 63 6f 6e 64 20 68 6f 70 65 66 75 |th second hopefu| 000006d0 6c 6c 79 29 2c 20 77 65 20 6d 75 73 74 20 70 65 |lly), we must pe| 000006e0 72 66 6f 72 6d 20 74 68 65 0a 66 6f 6c 6c 6f 77 |rform the.follow| 000006f0 69 6e 67 20 74 61 73 6b 73 3b 0a 0a 20 20 20 20 |ing tasks;.. | 00000700 20 20 20 61 29 20 43 6c 65 61 72 20 74 68 65 20 | a) Clear the | 00000710 73 63 72 65 65 6e 0a 20 20 20 20 20 20 20 62 29 |screen. b)| 00000720 20 52 6f 74 61 74 65 20 65 61 63 68 20 62 61 6c | Rotate each bal| 00000730 6c 20 61 62 6f 75 74 20 74 77 6f 20 61 78 69 73 |l about two axis| 00000740 0a 20 20 20 20 20 20 20 63 29 20 41 64 64 20 70 |. c) Add p| 00000750 65 72 73 70 65 63 74 69 76 65 20 61 6e 64 20 74 |erspective and t| 00000760 72 61 6e 73 66 6f 72 6d 20 74 6f 20 61 20 32 44 |ransform to a 2D| 00000770 20 70 6c 61 6e 65 0a 20 20 20 20 20 20 20 64 29 | plane. d)| 00000780 20 53 6f 72 74 20 61 6c 6c 20 74 68 65 20 62 61 | Sort all the ba| 00000790 6c 6c 73 20 62 79 20 64 65 70 74 68 0a 20 20 20 |lls by depth. | 000007a0 20 20 20 20 65 29 20 50 6c 6f 74 20 61 6c 6c 20 | e) Plot all | 000007b0 74 68 65 20 62 61 6c 6c 73 20 69 6e 20 6f 72 64 |the balls in ord| 000007c0 65 72 2c 20 66 72 6f 6d 20 62 61 63 6b 20 74 6f |er, from back to| 000007d0 20 66 72 6f 6e 74 2e 0a 0a 0a 52 6f 74 61 74 69 | front....Rotati| 000007e0 6f 6e 0a 2d 2d 2d 2d 2d 2d 2d 2d 0a 0a 54 68 65 |on.--------..The| 000007f0 72 65 20 61 72 65 20 6d 61 6e 79 20 77 61 79 73 |re are many ways| 00000800 20 6f 66 20 61 70 70 6c 79 69 6e 67 20 72 6f 74 | of applying rot| 00000810 61 74 69 6f 6e 20 74 6f 20 33 44 20 63 6f 2d 6f |ation to 3D co-o| 00000820 72 64 69 6e 61 74 65 73 2e 20 21 44 69 7a 7a 79 |rdinates. !Dizzy| 00000830 20 6d 61 6b 65 73 0a 75 73 65 20 6f 66 20 74 77 | makes.use of tw| 00000840 6f 20 72 65 6c 61 74 69 76 65 6c 79 20 73 69 6d |o relatively sim| 00000850 70 6c 65 20 66 6f 72 6d 75 6c 61 65 2c 20 74 68 |ple formulae, th| 00000860 61 74 20 70 72 6f 76 69 64 65 20 63 6f 6d 62 69 |at provide combi| 00000870 6e 65 64 20 72 6f 74 61 74 69 6f 6e 20 61 62 6f |ned rotation abo| 00000880 75 74 0a 74 68 65 20 58 20 61 6e 64 20 5a 20 61 |ut.the X and Z a| 00000890 78 69 73 2e 20 54 68 65 73 65 20 77 65 72 65 20 |xis. These were | 000008a0 63 68 6f 73 65 6e 20 73 6f 6d 65 77 68 61 74 20 |chosen somewhat | 000008b0 61 72 62 69 74 72 61 72 69 6c 79 2c 20 61 6e 64 |arbitrarily, and| 000008c0 20 69 6e 20 66 61 63 74 20 63 6f 75 6c 64 0a 62 | in fact could.b| 000008d0 65 20 61 6e 79 20 6f 74 68 65 72 20 63 6f 6d 62 |e any other comb| 000008e0 69 6e 61 74 69 6f 6e 20 6f 66 20 58 2c 20 59 20 |ination of X, Y | 000008f0 6f 72 20 5a 2c 20 62 75 74 20 66 6f 72 20 72 65 |or Z, but for re| 00000900 66 65 72 65 6e 63 65 20 74 68 65 79 20 61 72 65 |ference they are| 00000910 20 70 72 6f 76 69 64 65 64 0a 68 65 72 65 20 69 | provided.here i| 00000920 6e 20 6d 61 74 68 65 6d 61 74 69 63 61 6c 20 66 |n mathematical f| 00000930 6f 72 6d 2e 0a 0a 20 20 57 68 65 72 65 20 78 2c |orm... Where x,| 00000940 20 79 2c 20 61 6e 64 20 7a 20 61 72 65 20 69 6e | y, and z are in| 00000950 70 75 74 20 63 6f 2d 6f 72 64 69 6e 61 74 65 73 |put co-ordinates| 00000960 2c 20 61 6e 64 20 61 6e 67 6c 65 20 69 73 20 61 |, and angle is a| 00000970 20 64 65 67 72 65 65 20 76 61 6c 75 65 0a 20 20 | degree value. | 00000980 20 20 20 20 20 20 20 73 20 3d 20 53 49 4e 20 61 | s = SIN a| 00000990 6e 67 6c 65 20 20 20 63 20 3d 20 43 4f 53 20 61 |ngle c = COS a| 000009a0 6e 67 6c 65 20 20 20 20 0a 0a 20 20 20 20 20 20 |ngle .. | 000009b0 20 20 20 20 20 58 20 41 78 69 73 20 20 20 20 20 | X Axis | 000009c0 20 20 20 20 20 20 20 20 20 59 20 41 78 69 73 20 | Y Axis | 000009d0 20 20 20 20 20 20 20 20 20 20 20 20 20 5a 20 41 | Z A| 000009e0 78 69 73 0a 20 20 20 20 20 20 20 20 20 20 20 2d |xis. -| 000009f0 2d 2d 2d 2d 2d 20 20 20 20 20 20 20 20 20 20 20 |----- | 00000a00 20 20 20 2d 2d 2d 2d 2d 2d 20 20 20 20 20 20 20 | ------ | 00000a10 20 20 20 20 20 20 20 2d 2d 2d 2d 2d 2d 0a 20 20 | ------. | 00000a20 20 20 20 20 20 20 20 20 20 58 20 3d 20 78 20 20 | X = x | 00000a30 20 20 20 20 20 20 20 20 20 20 20 20 20 58 20 3d | X =| 00000a40 20 78 2a 63 2b 7a 2a 73 20 20 20 20 20 20 20 20 | x*c+z*s | 00000a50 20 58 20 3d 20 78 2a 63 2d 79 2a 73 0a 20 20 20 | X = x*c-y*s. | 00000a60 20 20 20 20 20 20 20 20 59 20 3d 20 79 2a 63 2d | Y = y*c-| 00000a70 7a 2a 73 20 20 20 20 20 20 20 20 20 59 20 3d 20 |z*s Y = | 00000a80 79 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 |y | 00000a90 59 20 3d 20 78 2a 73 2b 79 2a 63 0a 20 20 20 20 |Y = x*s+y*c. | 00000aa0 20 20 20 20 20 20 20 5a 20 3d 20 79 2a 73 2b 7a | Z = y*s+z| 00000ab0 2a 63 20 20 20 20 20 20 20 20 20 5a 20 3d 20 7a |*c Z = z| 00000ac0 2a 63 2d 78 2a 73 20 20 20 20 20 20 20 20 20 5a |*c-x*s Z| 00000ad0 20 3d 20 7a 0a 0a 4f 6e 63 65 20 77 65 20 68 61 | = z..Once we ha| 00000ae0 76 65 20 64 65 72 69 76 65 64 20 6f 75 72 20 6e |ve derived our n| 00000af0 65 77 20 72 6f 74 61 74 65 64 20 73 65 74 20 6f |ew rotated set o| 00000b00 66 20 63 6f 2d 6f 72 64 69 6e 61 74 65 73 2c 20 |f co-ordinates, | 00000b10 77 65 20 6d 75 73 74 20 74 68 65 6e 20 61 70 70 |we must then app| 00000b20 6c 79 0a 61 20 66 75 72 74 68 65 72 20 74 72 61 |ly.a further tra| 00000b30 6e 73 66 6f 72 6d 61 74 69 6f 6e 20 66 6f 72 20 |nsformation for | 00000b40 64 69 73 70 6c 61 79 20 77 69 74 68 69 6e 20 61 |display within a| 00000b50 20 74 77 6f 20 64 69 6d 65 6e 73 69 6f 6e 61 6c | two dimensional| 00000b60 20 70 6c 61 6e 65 20 2d 20 6f 75 72 0a 63 6f 6d | plane - our.com| 00000b70 70 75 74 65 72 20 73 63 72 65 65 6e 2e 20 52 65 |puter screen. Re| 00000b80 6d 65 6d 62 65 72 20 74 68 61 74 20 77 65 20 68 |member that we h| 00000b90 61 76 65 20 33 20 63 6f 2d 6f 72 64 69 6e 61 74 |ave 3 co-ordinat| 00000ba0 65 73 20 66 6f 72 20 65 61 63 68 20 62 61 6c 6c |es for each ball| 00000bb0 2c 20 61 6e 64 0a 6f 6e 6c 79 20 74 77 6f 20 61 |, and.only two a| 00000bc0 78 69 73 20 28 58 20 61 6e 64 20 59 29 20 6f 6e |xis (X and Y) on| 00000bd0 20 77 68 69 63 68 20 74 6f 20 70 6c 6f 74 20 74 | which to plot t| 00000be0 68 65 6d 2e 0a 0a 54 68 69 73 20 69 73 20 77 68 |hem...This is wh| 00000bf0 65 72 65 20 70 65 72 73 70 65 63 74 69 76 65 20 |ere perspective | 00000c00 69 73 20 61 70 70 6c 69 65 64 20 77 68 69 63 68 |is applied which| 00000c10 20 67 69 76 65 73 20 61 6e 20 69 6c 6c 75 73 69 | gives an illusi| 00000c20 6f 6e 20 6f 66 20 64 65 70 74 68 2c 20 61 6e 64 |on of depth, and| 00000c30 0a 69 73 20 72 65 61 6c 6c 79 20 6e 6f 74 20 73 |.is really not s| 00000c40 6f 20 63 6f 6d 70 6c 69 63 61 74 65 64 20 61 73 |o complicated as| 00000c50 20 69 74 20 73 6f 75 6e 64 73 2e 0a 0a 20 20 20 | it sounds... | 00000c60 20 20 20 20 20 20 20 20 20 20 58 32 44 20 3d 20 | X2D = | 00000c70 28 58 2a 73 63 61 6c 65 29 20 2f 20 28 5a 2b 72 |(X*scale) / (Z+r| 00000c80 68 6f 29 0a 20 20 20 20 20 20 20 20 20 20 20 20 |ho). | 00000c90 20 59 32 44 20 3d 20 28 59 2a 73 63 61 6c 65 29 | Y2D = (Y*scale)| 00000ca0 20 2f 20 28 5a 2b 72 68 6f 29 20 20 20 0a 0a 20 | / (Z+rho) .. | 00000cb0 20 57 68 65 72 65 20 58 2c 20 59 2c 20 61 6e 64 | Where X, Y, and| 00000cc0 20 5a 20 61 72 65 20 33 44 20 69 6e 70 75 74 20 | Z are 3D input | 00000cd0 63 6f 2d 6f 72 64 69 6e 61 74 65 73 0a 20 20 20 |co-ordinates. | 00000ce0 20 20 20 20 20 73 63 61 6c 65 20 69 73 20 61 6e | scale is an| 00000cf0 20 6f 76 65 72 61 6c 6c 20 73 69 7a 65 20 66 61 | overall size fa| 00000d00 63 74 6f 72 20 28 6f 72 20 76 69 65 77 69 6e 67 |ctor (or viewing| 00000d10 20 64 69 73 74 61 6e 63 65 29 0a 20 20 20 20 61 | distance). a| 00000d20 6e 64 20 20 20 72 68 6f 20 69 73 20 74 68 65 20 |nd rho is the | 00000d30 70 65 72 73 70 65 63 74 69 76 65 20 63 6f 6e 73 |perspective cons| 00000d40 74 61 6e 74 0a 0a 4f 70 74 69 6d 75 6d 20 76 61 |tant..Optimum va| 00000d50 6c 75 65 73 20 66 6f 72 20 27 73 63 61 6c 65 27 |lues for 'scale'| 00000d60 20 61 6e 64 20 27 72 68 6f 27 20 61 72 65 20 68 | and 'rho' are h| 00000d70 61 72 64 20 74 6f 20 64 65 66 69 6e 65 2c 20 61 |ard to define, a| 00000d80 6c 74 68 6f 75 67 68 20 6c 6f 77 65 72 0a 76 61 |lthough lower.va| 00000d90 6c 75 65 73 20 6f 66 20 72 68 6f 20 28 74 6f 77 |lues of rho (tow| 00000da0 61 72 64 20 7a 65 72 6f 29 20 75 73 75 61 6c 6c |ard zero) usuall| 00000db0 79 20 72 65 73 75 6c 74 20 69 6e 20 76 65 72 79 |y result in very| 00000dc0 20 65 78 61 67 67 65 72 61 74 65 64 20 70 65 72 | exaggerated per| 00000dd0 73 70 65 63 74 69 76 65 2e 0a 0a 41 73 20 61 20 |spective...As a | 00000de0 67 65 6e 65 72 61 6c 20 72 75 6c 65 2c 20 72 65 |general rule, re| 00000df0 61 73 6f 6e 61 62 6c 65 20 72 65 73 75 6c 74 73 |asonable results| 00000e00 20 61 72 65 20 75 73 75 61 6c 6c 79 20 61 63 68 | are usually ach| 00000e10 69 65 76 65 64 20 69 66 20 72 68 6f 20 69 73 20 |ieved if rho is | 00000e20 73 65 74 20 74 6f 0a 73 63 61 6c 65 2f 32 2e 0a |set to.scale/2..| 00000e30 0a 21 44 69 7a 7a 79 20 75 73 65 73 20 61 20 6c |.!Dizzy uses a l| 00000e40 6f 74 20 6f 66 20 27 74 72 69 63 6b 73 27 20 74 |ot of 'tricks' t| 00000e50 6f 20 67 61 69 6e 20 73 70 65 65 64 2e 20 4f 6e |o gain speed. On| 00000e60 65 20 73 75 63 68 20 74 72 69 63 6b 20 72 65 6d |e such trick rem| 00000e70 6f 76 65 73 20 74 68 65 20 6e 65 65 64 0a 66 6f |oves the need.fo| 00000e80 72 20 61 6e 79 20 64 69 76 69 73 69 6f 6e 20 28 |r any division (| 00000e90 61 20 73 61 64 6c 79 20 61 62 73 65 6e 74 20 41 |a sadly absent A| 00000ea0 52 4d 20 69 6e 73 74 72 75 63 74 69 6f 6e 29 20 |RM instruction) | 00000eb0 77 69 74 68 20 74 68 65 20 61 62 6f 76 65 0a 74 |with the above.t| 00000ec0 72 61 6e 73 66 6f 72 6d 61 74 69 6f 6e 20 61 6e |ransformation an| 00000ed0 64 20 69 73 20 62 61 73 65 64 20 6f 6e 20 74 68 |d is based on th| 00000ee0 65 20 74 68 65 6f 72 79 20 74 68 61 74 20 61 6c |e theory that al| 00000ef0 6c 20 64 69 76 69 73 69 6f 6e 20 63 61 6e 20 62 |l division can b| 00000f00 65 20 72 65 70 6c 61 63 65 64 0a 62 79 20 6d 75 |e replaced.by mu| 00000f10 6c 74 69 70 6c 69 63 61 74 69 6f 6e 20 69 66 20 |ltiplication if | 00000f20 79 6f 75 27 76 65 20 67 6f 74 20 74 68 65 20 73 |you've got the s| 00000f30 70 61 72 65 20 52 41 4d 21 20 4c 65 74 27 73 20 |pare RAM! Let's | 00000f40 65 6c 61 62 6f 72 61 74 65 2e 0a 0a 20 20 20 20 |elaborate... | 00000f50 65 2e 67 2e 20 20 20 20 31 30 30 2f 39 20 20 3d |e.g. 100/9 =| 00000f60 20 20 31 30 30 20 2a 20 28 31 2f 20 39 29 20 3d | 100 * (1/ 9) =| 00000f70 20 31 31 2e 31 31 31 31 31 0a 20 20 20 20 20 20 | 11.11111. | 00000f80 20 20 20 20 20 31 32 33 34 2f 38 31 20 3d 20 31 | 1234/81 = 1| 00000f90 32 33 34 20 2a 20 28 31 2f 38 31 29 20 3d 20 31 |234 * (1/81) = 1| 00000fa0 35 2e 32 33 34 35 39 33 0a 0a 41 6e 64 20 74 68 |5.234593..And th| 00000fb0 65 72 65 20 69 74 20 69 73 2e 20 57 65 20 73 69 |ere it is. We si| 00000fc0 6d 70 6c 79 20 6d 75 6c 74 69 70 6c 79 20 6f 75 |mply multiply ou| 00000fd0 72 20 6e 75 6d 62 65 72 20 62 79 20 74 68 65 20 |r number by the | 00000fe0 66 72 61 63 74 69 6f 6e 20 6f 66 20 74 68 65 0a |fraction of the.| 00000ff0 64 69 76 69 73 6f 72 2c 20 61 6e 64 20 61 73 20 |divisor, and as | 00001000 6c 6f 6e 67 20 61 73 20 77 65 20 63 72 65 61 74 |long as we creat| 00001010 65 20 61 20 6c 6f 6f 6b 75 70 20 74 61 62 6c 65 |e a lookup table| 00001020 20 6f 66 20 31 2f 78 20 66 75 6e 63 74 69 6f 6e | of 1/x function| 00001030 73 20 66 6f 72 20 65 76 65 72 79 0a 27 78 27 20 |s for every.'x' | 00001040 77 65 20 61 72 65 20 6c 69 6b 65 6c 79 20 74 6f |we are likely to| 00001050 20 75 73 65 2c 20 74 68 69 73 20 6d 65 74 68 6f | use, this metho| 00001060 64 20 69 73 20 70 65 72 66 65 63 74 6c 79 20 61 |d is perfectly a| 00001070 63 63 65 70 74 61 62 6c 65 2c 20 61 6e 64 20 72 |cceptable, and r| 00001080 65 71 75 69 72 65 73 0a 6a 75 73 74 20 6f 6e 65 |equires.just one| 00001090 20 4d 55 4c 20 69 6e 73 74 72 75 63 74 69 6f 6e | MUL instruction| 000010a0 2e 20 4f 6e 65 20 64 72 61 77 62 61 63 6b 20 6f |. One drawback o| 000010b0 66 20 74 68 69 73 20 73 63 68 65 6d 65 20 69 73 |f this scheme is| 000010c0 20 74 68 61 74 20 61 6e 79 20 72 65 6d 61 69 6e | that any remain| 000010d0 64 65 72 0a 69 73 20 64 69 73 72 65 67 61 72 64 |der.is disregard| 000010e0 65 64 2e 0a 0a 49 6e 20 74 68 65 20 63 61 73 65 |ed...In the case| 000010f0 20 6f 66 20 21 44 69 7a 7a 79 20 77 68 65 72 65 | of !Dizzy where| 00001100 20 77 65 20 61 72 65 20 64 69 76 69 64 69 6e 67 | we are dividing| 00001110 20 62 79 20 74 68 65 20 5a 20 63 6f 2d 6f 72 64 | by the Z co-ord| 00001120 2c 20 74 68 65 20 72 61 6e 67 65 20 69 73 0a 66 |, the range is.f| 00001130 72 6f 6d 20 61 70 70 6f 78 2e 20 2d 32 30 30 20 |rom appox. -200 | 00001140 74 6f 20 2b 32 30 30 2c 20 77 68 69 63 68 20 72 |to +200, which r| 00001150 65 71 75 69 72 65 73 20 61 20 34 30 30 2a 34 20 |equires a 400*4 | 00001160 3d 20 31 36 30 30 20 62 79 74 65 20 74 61 62 6c |= 1600 byte tabl| 00001170 65 2e 20 20 0a 0a 0a 53 6f 72 74 69 6e 67 20 28 |e. ...Sorting (| 00001180 74 68 61 74 20 6f 6c 64 20 63 68 65 73 74 6e 75 |that old chestnu| 00001190 74 21 29 0a 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d |t!).------------| 000011a0 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d |----------------| 000011b0 0a 0a 52 6f 74 61 74 69 6f 6e 20 61 6e 64 20 70 |..Rotation and p| 000011c0 65 72 73 70 65 63 74 69 76 65 20 61 72 65 20 61 |erspective are a| 000011d0 6c 6c 20 76 65 72 79 20 77 65 6c 6c 20 66 6f 72 |ll very well for| 000011e0 20 72 65 61 6c 69 73 6d 2c 20 68 6f 77 65 76 65 | realism, howeve| 000011f0 72 20 74 68 65 72 65 20 69 73 20 61 0a 66 69 6e |r there is a.fin| 00001200 61 6c 20 68 75 72 64 6c 65 20 62 65 66 6f 72 65 |al hurdle before| 00001210 20 61 6e 79 20 72 65 61 6c 20 69 6d 70 72 65 73 | any real impres| 00001220 73 69 6f 6e 20 6f 66 20 33 44 20 73 70 61 63 65 |sion of 3D space| 00001230 20 63 61 6e 20 62 65 20 61 74 74 61 69 6e 65 64 | can be attained| 00001240 2c 20 61 6e 64 0a 74 68 61 74 20 69 73 20 64 65 |, and.that is de| 00001250 70 74 68 20 73 6f 72 74 69 6e 67 2e 0a 0a 53 6f |pth sorting...So| 00001260 72 74 69 6e 67 20 68 61 73 20 6c 6f 6e 67 20 62 |rting has long b| 00001270 65 65 6e 20 74 68 65 20 62 61 6e 65 20 6f 66 20 |een the bane of | 00001280 61 6e 79 20 70 72 6f 67 72 61 6d 6d 65 72 73 20 |any programmers | 00001290 6c 69 66 65 20 61 6e 64 20 74 68 65 72 65 20 61 |life and there a| 000012a0 72 65 20 6d 61 6e 79 0a 64 69 66 66 65 72 65 6e |re many.differen| 000012b0 74 20 77 61 79 73 20 6f 66 20 73 6f 72 74 69 6e |t ways of sortin| 000012c0 67 20 64 61 74 61 2e 20 54 68 65 20 62 75 62 62 |g data. The bubb| 000012d0 6c 65 20 73 6f 72 74 20 69 73 20 74 68 65 20 73 |le sort is the s| 000012e0 69 6d 70 6c 65 73 74 2c 20 61 6e 64 0a 75 6e 66 |implest, and.unf| 000012f0 6f 72 74 75 6e 61 74 65 6c 79 20 6f 6e 65 20 6f |ortunately one o| 00001300 66 20 74 68 65 20 73 6c 6f 77 65 73 74 2e 0a 0a |f the slowest...| 00001310 21 44 69 7a 7a 79 20 6d 61 6b 65 73 20 75 73 65 |!Dizzy makes use| 00001320 20 6f 66 20 61 20 27 62 69 6e 27 20 73 6f 72 74 | of a 'bin' sort| 00001330 2c 20 77 68 69 63 68 20 6c 69 6b 65 20 65 76 65 |, which like eve| 00001340 72 79 74 68 69 6e 67 20 69 73 20 76 65 72 79 20 |rything is very | 00001350 73 69 6d 70 6c 65 20 69 6e 0a 74 68 65 6f 72 79 |simple in.theory| 00001360 2e 20 49 74 20 77 6f 72 6b 73 20 62 79 20 63 72 |. It works by cr| 00001370 65 61 74 69 6e 67 20 61 20 73 65 74 20 6f 66 20 |eating a set of | 00001380 27 70 69 64 67 65 6f 6e 20 68 6f 6c 65 73 27 20 |'pidgeon holes' | 00001390 66 6f 72 20 65 76 65 72 79 20 70 6f 73 73 69 62 |for every possib| 000013a0 6c 65 0a 76 61 6c 75 65 20 74 68 61 74 20 6d 61 |le.value that ma| 000013b0 79 20 65 78 69 73 74 20 77 69 74 68 69 6e 20 74 |y exist within t| 000013c0 68 65 20 64 61 74 61 20 74 6f 20 62 65 20 73 6f |he data to be so| 000013d0 72 74 65 64 2e 20 49 6e 20 74 68 65 20 63 61 73 |rted. In the cas| 000013e0 65 20 6f 66 20 21 44 69 7a 7a 79 2c 20 77 65 0a |e of !Dizzy, we.| 000013f0 61 72 65 20 6f 6e 6c 79 20 63 6f 6e 63 65 72 6e |are only concern| 00001400 65 64 20 77 69 74 68 20 73 6f 72 74 69 6e 67 20 |ed with sorting | 00001410 65 61 63 68 20 62 61 6c 6c 73 20 5a 20 63 6f 2d |each balls Z co-| 00001420 6f 72 64 69 6e 61 74 65 2c 20 61 6e 64 20 61 73 |ordinate, and as| 00001430 20 74 68 65 73 65 20 68 61 76 65 0a 61 6e 20 69 | these have.an i| 00001440 6d 70 6f 73 65 64 20 6c 69 6d 69 74 20 6f 66 20 |mposed limit of | 00001450 2d 31 36 30 20 74 6f 20 31 35 39 2c 20 77 65 20 |-160 to 159, we | 00001460 72 65 73 65 72 76 65 20 33 32 30 20 73 70 61 63 |reserve 320 spac| 00001470 65 73 2e 0a 0a 54 68 65 20 73 6f 72 74 20 72 6f |es...The sort ro| 00001480 75 74 69 6e 65 20 74 68 65 6e 20 73 63 61 6e 73 |utine then scans| 00001490 20 74 68 72 6f 75 67 68 20 74 68 65 20 63 6f 2d | through the co-| 000014a0 6f 72 64 69 6e 61 74 65 73 20 61 6e 64 20 73 6c |ordinates and sl| 000014b0 6f 74 73 20 65 61 63 68 20 5a 20 69 6e 74 6f 0a |ots each Z into.| 000014c0 69 74 27 73 20 72 65 73 70 65 63 74 69 76 65 20 |it's respective | 000014d0 61 64 64 72 65 73 73 2c 20 66 6f 72 20 69 6e 73 |address, for ins| 000014e0 74 61 6e 63 65 2c 20 61 20 5a 20 63 6f 2d 6f 72 |tance, a Z co-or| 000014f0 64 20 6f 66 20 35 20 67 6f 65 73 20 69 6e 74 6f |d of 5 goes into| 00001500 20 61 64 64 72 65 73 73 20 35 0a 61 6e 64 20 73 | address 5.and s| 00001510 6f 20 6f 6e 20 75 6e 74 69 6c 20 61 6c 6c 20 74 |o on until all t| 00001520 68 65 20 63 6f 2d 6f 72 64 73 20 68 61 76 65 20 |he co-ords have | 00001530 62 65 65 6e 20 61 6c 6c 6f 74 74 65 64 2e 0a 0a |been allotted...| 00001540 48 61 76 69 6e 67 20 64 6f 6e 65 20 74 68 69 73 |Having done this| 00001550 2c 20 69 74 20 69 73 20 61 20 73 69 6d 70 6c 65 |, it is a simple| 00001560 20 6d 61 74 74 65 72 20 6f 66 20 73 63 61 6e 6e | matter of scann| 00001570 69 6e 67 20 74 68 72 6f 75 67 68 20 74 68 65 20 |ing through the | 00001580 6c 69 73 74 20 66 72 6f 6d 0a 2d 31 36 30 20 74 |list from.-160 t| 00001590 6f 20 31 35 39 20 61 6e 64 20 70 6c 6f 74 74 69 |o 159 and plotti| 000015a0 6e 67 20 74 68 65 20 72 65 6c 65 76 61 6e 74 20 |ng the relevant | 000015b0 62 61 6c 6c 20 66 72 6f 6d 20 65 61 63 68 20 61 |ball from each a| 000015c0 64 64 72 65 73 73 2c 20 77 68 69 63 68 20 69 73 |ddress, which is| 000015d0 0a 61 6c 72 65 61 64 79 20 64 65 70 74 68 20 73 |.already depth s| 000015e0 6f 72 74 65 64 2e 0a 0a 53 69 6d 70 6c 65 20 68 |orted...Simple h| 000015f0 75 68 3f 20 57 65 6c 6c 20 6e 6f 2c 20 62 65 63 |uh? Well no, bec| 00001600 61 75 73 65 20 77 65 20 68 61 76 65 20 6f 76 65 |ause we have ove| 00001610 72 6c 6f 6f 6b 65 64 20 6f 6e 65 20 69 6d 70 6f |rlooked one impo| 00001620 72 74 61 6e 74 20 66 61 63 74 2e 20 57 68 61 74 |rtant fact. What| 00001630 20 69 66 0a 74 68 65 72 65 20 69 73 20 6d 6f 72 | if.there is mor| 00001640 65 20 74 68 61 6e 20 6f 6e 65 20 62 61 6c 6c 20 |e than one ball | 00001650 77 69 74 68 20 74 68 65 20 73 61 6d 65 20 5a 20 |with the same Z | 00001660 63 6f 2d 6f 72 64 3f 20 57 65 20 68 61 76 65 20 |co-ord? We have | 00001670 6f 6e 6c 79 20 72 65 73 65 72 76 65 64 0a 6f 6e |only reserved.on| 00001680 65 20 61 64 64 72 65 73 73 20 66 6f 72 20 65 61 |e address for ea| 00001690 63 68 20 62 61 6c 6c 73 20 5a 2c 20 61 6e 64 20 |ch balls Z, and | 000016a0 73 6f 20 69 66 20 74 68 65 72 65 20 61 72 65 20 |so if there are | 000016b0 74 77 6f 20 6f 72 20 6d 6f 72 65 20 62 61 6c 6c |two or more ball| 000016c0 73 20 77 69 74 68 20 74 68 65 0a 73 61 6d 65 20 |s with the.same | 000016d0 5a 2c 20 74 68 65 72 65 20 77 69 6c 6c 20 62 65 |Z, there will be| 000016e0 20 62 61 6c 6c 73 20 6d 69 73 73 69 6e 67 20 77 | balls missing w| 000016f0 68 65 6e 20 77 65 20 63 6f 6d 65 20 74 6f 20 70 |hen we come to p| 00001700 6c 6f 74 20 74 68 65 6d 2e 0a 0a 53 6f 6c 75 74 |lot them...Solut| 00001710 69 6f 6e 3a 20 52 65 73 65 72 76 65 20 61 6e 6f |ion: Reserve ano| 00001720 74 68 65 72 20 73 65 74 20 6f 66 20 70 69 64 67 |ther set of pidg| 00001730 65 6f 6e 20 68 6f 6c 65 73 20 69 6e 20 74 68 65 |eon holes in the| 00001740 20 67 75 69 73 65 20 6f 66 20 61 20 73 74 61 63 | guise of a stac| 00001750 6b 2c 20 74 6f 0a 20 20 20 20 20 20 20 20 20 20 |k, to. | 00001760 63 6f 6e 74 61 69 6e 20 61 6e 79 20 6f 76 65 72 |contain any over| 00001770 66 6c 6f 77 2e 0a 0a 53 6f 20 6e 6f 77 20 77 68 |flow...So now wh| 00001780 61 74 20 68 61 70 70 65 6e 73 20 69 73 2c 20 77 |at happens is, w| 00001790 68 65 6e 20 77 65 20 63 6f 6d 65 20 74 6f 20 70 |hen we come to p| 000017a0 6c 61 63 65 20 61 20 5a 20 63 6f 2d 6f 72 64 20 |lace a Z co-ord | 000017b0 69 6e 74 6f 20 69 74 73 20 61 6c 6c 6f 74 74 65 |into its allotte| 000017c0 64 0a 61 64 64 72 65 73 73 2c 20 77 65 20 6d 75 |d.address, we mu| 000017d0 73 74 20 66 69 72 73 74 20 63 68 65 63 6b 20 74 |st first check t| 000017e0 68 61 74 20 74 68 65 72 65 20 69 73 6e 27 74 20 |hat there isn't | 000017f0 61 6c 72 65 61 64 79 20 73 6f 6d 65 74 68 69 6e |already somethin| 00001800 67 20 69 6e 20 74 68 65 72 65 2e 20 49 66 0a 6e |g in there. If.n| 00001810 6f 74 2c 20 65 76 65 72 79 74 68 69 6e 67 20 69 |ot, everything i| 00001820 73 20 66 69 6e 65 20 2d 20 77 65 20 73 74 6f 72 |s fine - we stor| 00001830 65 20 69 74 20 61 6e 64 20 63 61 72 72 79 20 6f |e it and carry o| 00001840 6e 2e 0a 0a 49 66 20 68 6f 77 65 76 65 72 2c 20 |n...If however, | 00001850 74 68 65 20 61 64 64 72 65 73 73 20 69 73 20 61 |the address is a| 00001860 6c 72 65 61 64 79 20 66 75 6c 6c 2c 20 77 65 20 |lready full, we | 00001870 2a 73 74 61 63 6b 2a 20 74 68 65 20 6e 65 77 20 |*stack* the new | 00001880 7a 20 69 6e 20 74 68 65 20 72 65 73 65 72 76 65 |z in the reserve| 00001890 0a 61 64 64 72 65 73 73 2c 20 61 6e 64 20 61 64 |.address, and ad| 000018a0 64 20 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 6f |d a pointer to o| 000018b0 75 72 20 6f 72 69 67 69 6f 6e 61 6c 20 28 66 75 |ur origional (fu| 000018c0 6c 6c 29 20 61 64 64 72 65 73 73 20 74 65 6c 6c |ll) address tell| 000018d0 69 6e 67 20 75 73 0a 77 68 65 72 65 61 62 6f 75 |ing us.whereabou| 000018e0 74 73 20 6f 6e 20 74 68 65 20 73 74 61 63 6b 20 |ts on the stack | 000018f0 74 68 65 20 73 65 63 6f 6e 64 20 63 6f 2d 6f 72 |the second co-or| 00001900 64 20 69 73 2e 20 49 66 20 61 6e 79 20 6d 6f 72 |d is. If any mor| 00001910 65 20 64 75 70 6c 69 63 61 74 65 20 5a 0a 63 6f |e duplicate Z.co| 00001920 2d 6f 72 64 73 20 63 6f 6d 65 20 61 6c 6f 6e 67 |-ords come along| 00001930 2c 20 77 65 20 64 6f 20 74 68 65 20 73 61 6d 65 |, we do the same| 00001940 2c 20 62 75 74 20 61 64 64 69 6e 67 20 74 68 65 |, but adding the| 00001950 20 6c 61 73 74 20 70 6f 69 6e 74 65 72 20 74 6f | last pointer to| 00001960 20 74 68 69 73 20 6e 65 77 0a 5a 20 62 65 66 6f | this new.Z befo| 00001970 72 65 20 77 65 20 73 74 61 63 6b 20 69 74 2e 0a |re we stack it..| 00001980 0a 49 6e 20 74 68 69 73 20 77 61 79 2c 20 74 68 |.In this way, th| 00001990 65 20 66 69 72 73 74 20 28 66 75 6c 6c 29 20 61 |e first (full) a| 000019a0 64 64 72 65 73 73 20 77 65 20 63 6f 6d 65 20 61 |ddress we come a| 000019b0 63 72 6f 73 73 2c 20 41 4c 57 41 59 53 20 70 6f |cross, ALWAYS po| 000019c0 69 6e 74 73 20 74 6f 20 74 68 65 0a 6d 6f 73 74 |ints to the.most| 000019d0 20 72 65 63 65 6e 74 20 64 75 70 6c 69 63 61 74 | recent duplicat| 000019e0 65 20 74 68 61 74 20 68 61 73 20 62 65 65 6e 20 |e that has been | 000019f0 73 74 61 63 6b 65 64 2c 20 61 6e 64 20 77 68 65 |stacked, and whe| 00001a00 6e 20 77 65 20 72 65 74 72 69 76 65 20 74 68 61 |n we retrive tha| 00001a10 74 0a 64 75 70 6c 69 63 61 74 65 2c 20 69 74 20 |t.duplicate, it | 00001a20 70 6f 69 6e 74 73 20 74 6f 20 74 68 65 20 6f 6e |points to the on| 00001a30 65 20 62 65 66 6f 72 65 2c 20 61 6e 64 20 73 6f |e before, and so| 00001a40 20 6f 6e 20 75 6e 74 69 6c 20 74 68 65 72 65 20 | on until there | 00001a50 61 72 65 20 6e 6f 20 6d 6f 72 65 0a 70 6f 69 6e |are no more.poin| 00001a60 74 65 72 73 20 6d 65 61 6e 69 6e 67 20 74 68 61 |ters meaning tha| 00001a70 74 20 77 65 20 68 61 76 65 20 72 65 61 63 68 65 |t we have reache| 00001a80 64 20 74 68 65 20 76 65 72 79 20 66 69 72 73 74 |d the very first| 00001a90 20 64 75 70 6c 69 63 61 74 65 20 74 68 61 74 20 | duplicate that | 00001aa0 77 61 73 0a 73 74 61 63 6b 65 64 2e 0a 0a 45 78 |was.stacked...Ex| 00001ab0 61 6d 70 6c 65 73 2e 42 69 6e 53 6f 72 74 20 73 |amples.BinSort s| 00001ac0 68 6f 77 73 20 74 68 69 73 20 61 6c 67 6f 72 69 |hows this algori| 00001ad0 74 68 6d 20 77 6f 72 6b 69 6e 67 20 66 72 6f 6d |thm working from| 00001ae0 20 42 41 53 49 43 2e 0a | BASIC..| 00001ae8
.