I'm currently re-making an old Missile Command-esque ZX Spectrum Next game I wrote a couple of years back that, to be honest, could have been way better (but I really didn't know any better back in those days). There are some graphical differences I want to make, and one of the major considerations regarding graphics is how I can get more speed when it comes to creating linear missile trails.
So - how would I go about coding something in an interpreted language (NextBASIC) that runs at a speed fast enough to pull off a missile command style of game? Well, its all down to the algorithms and making sure I made the most of using commands and techniques that minimise the amount of time the computer has to take to do things.
TECHNICAL NOTE : I use the Next's LAYER 2 graphics mode - this starts the pixel coordinate system at the top-left of the screen (unlike the original Spectrum that starts at bottom). The code examples assume that this is the case (ie. you have switched to that mode).
Drawing a line the DDA-way...
One very easy way to create a linear path is to simply use a floating point increment that gradually changes a value over time. In this case, the x-distance of a line / y-distance to travel. Often you might hear this called a Digital Differential Analyzer (or DDA for short)
Here's an example in NextBASIC. I've extrapolated the code out to help make more sense.
10 x = %RND 245+5 : ; random start X coordinate
15 u = %RND 245+5 : ; random end X coordinate
20 y = 0 : v = 191: ; start Y coordinate, v = end Y coord
22 ; dx defines the x-distance to travel
23 ; slope is the increment to add to X coord
25 dx = u-x : slope = dx/v
30 ;
35 ; LOOP TO DRAW LINE
40 ;
45 PLOT x,y : ; Draw a Pixel
50 x = x + slope : y = y + 1 : ; Move the pixel
55 IF y < v THEN GO TO 45 : ; Loop til whole line drawn
It's not too bad - but it uses one thing we want to try and avoid - floating point arithmetic! The slope variable is a small increment that is added to x gradually, and while it may not seem to be too slow, once we have a few of these on screen at the same time, it will quickly become noticeable.
And one thing, especially in a game, that we don't want is noticeable speed issues.
A Pennywise for your thoughts...
So, how do we avoid floats? Well, we look at the famous (as in well-known by nerds everywhere famous) Bresenham's line drawing algorithm! It's an algorithm that simply relies on an incremental value to make a decision whether the x coordinate value should change - and best part - it works using integers which computers deal with way faster. And when it comes to games, faster is always better...
So, how does Bresenham's algorithm work?
I'll be honest - straight up - I am no mathematician. There's a detailed break down of the mathematical reasoning behind it (as well as pseudo code, etc.) on Wikipedia However based on the equations and simple algorithm behind it, its relatively easy to implement in code. Here's how it works...
x, y = Start coordinates at top of screen
u, v = End coordinates at bottom of screen
dX = (u - x), horizontal distance to travel
mX = dX direction (+ or -), dX is set to be positive
Bresenham's changes the X based on a decision value that is constantly incremented. We start out generating our first value and store it as e.
e = (dX * 2 - v)
The drawing algorithm then makes use of e throughout to do its work.
LOOP
Plot pixel at x, yIf our decision value (e) is greater than 0:
x = x + mXe = e + (dX-v)*2
Else:
e = e + (dX * 2)
y = y + 1if y < v, repeat the LOOP
In code, that looks something like this. I am making use of the NextBASIC integer values/variables (prefixed with a % character) as they tend to calculate a lot faster and more efficiently. Like the first example, I've extrapolated this out - I'll show a much more optimal version (and a few tips) at the end of this article how it can be improved (i.e. made faster).
20 %x = % RND 245+5 : ; random start X coordinate
25 %u = % RND 245+5 : ; random end X coordinate
27 %y = 0: %v = 191
28 ; %d defines the x-distance to travel
30 %d = %u - x
33 ; %d needs to be converted to a positive value
34 ; %m will store the increment needed for x
35 IF % SGN {d} < 0 THEN %m = -1:%d=% SGN {-d}: ELSE %m=1
38 ; %e contains a 'should I move' decision value
39 ; and is the core of how bresenhams works
40 %e = %(d * 2) - v
45 ;
50 ; LOOP TO DRAW LINE
55 ;
60 PLOT %x,%y : ; Draw a Pixel
63 ; If %e > 0, we should update X. We also recalculate %e
64 ; If not, we recalculate the value of %e (but no move)
65 IF % SGN {e} > 0 THEN %e=%e+( SGN {d-v} * 2):%x=%x+ SGN {m}: ELSE %e=%e+(d * 2)
70 %y=%y+1 : ; Move the Pixel down
75 IF %y < v THEN GO TO 60
Sometimes its easier to see than read...
Let's do a bit of desk checking (old-school way of manually testing values to see what they become after the calculations are done). We'll use this to visualize how the values relate to pixels.
We're going to keep the line short - a few pixels - just so we can see the result quickly. We begin setting up the variables.
x = 8, y = 0u = 7, v = 4d = (u - x) (7 - 8 = -1)d = ABS d , m = -1e = (d * 2) - v (2 - 4 = -2)
We begin our line draw loop here. This is where we're going to see the way that these calculations do their magic.
Draw the pixel at 8,0
y = 0, e = -2IF e > 0<nope>ELSEe = e + d*2 (-2 + (1*2) = 0)y = y + 1
Draw Pixel at 8,1
y = 1, e = 0IF e > 0 (0)<nope>ELSEe = e + d*2 (0 + (1*2) = 2)y = y + 1
Draw Pixel at 8,2
y = 2, e = 2IF e > 0x = x + m (8 + -1 = 7)e = e + (d-v)*2 (2 + (1 - 4)*2 = -4)
ELSE<nope>
y = y + 1
Draw Pixel at 7,3
y = 3, e = -4IF e > 0<nope>ELSEe = e + d*2 (-4 + 2 = -2)y = y + 1
Draw Pixel at 7,4
At this stage, we've reached the end of the line, so we can end here.
Make this faster - Any sneaky tips?
There are a few things we can do with our code that take advantage of things that we can do with an integer value (and in particular, 16 bit and 8 bit values). Here's a re-working of the code above, with some notes on things as we go.
20 %x = % RND 245+5:%y=%0
25 %u= % RND 245+5:%v=%191
30 %d = %u - x
Unsigned integer values
NextBASIC integer values are unsigned - which means any value lower than 0 instead wraps around to a high 16-bit value. For instance, -1 is an integer value of 65535. This high value decrements as numbers go into negative (i.e. -2 is 65534, -3 is 65533 and so on).
As we saw in the original code example, we can convert this to an actual signed value (-1) using %SGN{} - however why waste time converting when we only need to see if it is a value higher than 65000 (I use 65000 - no reason really (apart from being a high value). It just needs to be higher then whatever the maximum positive value you need to test for is if you think about it).
HANDY TIP : As mentioned, testing for a negative value just means testing for any value higher than the maximum positive one. You can take advantage of this as a way to check if a value is within screen bounds of 0 to 176 (say, in the case of testing for a Y axis value) by simply using IF %y > 176... Any value less than 0 will of course also be way higher then 176... Nice & efficient.
Another tip - also related to unsigned values - regarding the adding and subtracting a value from our X coordinate (stored in %m).
The ZX Spectrum Next screen has a resolution of 256 pixels. The nice thing about 256 - it's the max an 8-bit value can have. If we think of our X coordinate as a value that loops around between 0 and 255, adding 256 pixels to the value would simply return to the same location (being 256 pixels wide).
However, if we add one less - 255 - it would end 1 pixel to the left. We can set that here rather than using a value of -1.
33 IF %d > 65000 THEN %m = 255:%d=% SGN {-d}: ELSE %m=1
Bit shift for multiplication
A fast way to multiply a value by 2 is to use a bitwise operation and shift all its bits to the left by one bit. I've used this << 1 wherever this simple multiplication is needed. (Hint - shifting bits to the right will divide by 2)
35 %e = %(d << 1) - v
Do it once - removing repetition using constants
Something worth considering is removing repeated calculations where values do not change. As the decision value calculation relies on adding the values (d-v)*2 and d*2 to it (these are the same each iteration), its quicker to just replace the result of this constant repeated value as a variable we can just reference. We've done it here in %f and %g for now.
37 %f=%SGN{d-v}<<1: %g=%d<<1
Then the line drawing I have done in two lines, using a simple REPEAT/REPEAT UNTIL loop.
Anything not 0 is true
Any logic testing of values will always be true if the resulting value is not 0. Testing for a positive value can leverage on the unsigned high values. If we're testing for a value greater than 0, it's obviously less then 65000. However a value of 0 is also less than 65000... To prevent this being true when %e is 0, we simply multiply the logic test (e < 65000) by the value in %e - if it's 0, the numerical result of the IF statement will be false.
Bit mask with AND to prevent huge X coordinates
We are using a value of 255 added to the X coordinate to decrease the value. As the integer variables on the next are 16 bit, that will quickly increase to large numbers that exceed the 256 pixel range... However don't worry - this is easily remedied by applying an AND bit mask of 255 ( &255 ) to clip the value to a range between 0 and 255.
40 REPEAT : PLOT %x,%y: IF %(e < 65000) * e THEN %e=%e+f:%x=%x+m&255: ELSE %e=%e+g
45 %y=%y+1: REPEAT UNTIL %y > v
Ready for action!
As you can see, the algorithm is relatively easy to implement. And being integer based, its pretty snappy. In fact, just looking at that BASIC code, it wouldn't be difficult to translate into assembler to give it a real speed kick...
Missile command is just one that comes to mind, but I am sure there are a lot of ways in which this can be used for those alien attacks, bouncing platforms and more... Once you know how it works, be creative in what you can do with it.
0 comments:
Post a Comment