Coloured walls and FPS counters
Monday, 17th July 2006
I fixed most of the wall filling code. It now fills by scanline (so is considerably faster), which gives me more flexibility over what I can do with it.
For the moment, I have sacrificed speed with a routine that can handle three different fills - black, white, or 50% dithered. The routine will always blank the wall, mask out the pattern you wish to fill then OR it - which works nicely, but wastes time if you are filling plain black or white walls.
The result is quite pleasing:
As you can also see, I added scrolling skies.
The dithered walls look a bit nicer on hardware. The option to switch the initial dither pattern on alternate frames (resulting in a pseudo-greyscale) can be switched on or off, as it looks rather bad in emulators.
There is one horrible problem with the physical LCD, though - it really cannot cope with columns of alternating pixels. Compare the two shots, one being much closer to the wall (and so having more columns of alternating pixels):
Not so good. Hopefully the world in-game will have enough content to break up the columns, but I'll have to wait and see on that count.
One major concern I've had is keeping the speed of the engine constant. Just moving the player X units per frame is not an option, as the framerate can vary wildly. I need some sort of timing!
Luckily, the calculator has fairly limited timing hardware built-in. I can use this timer via interrupts. There are various pieces of hardware that can trigger interrupts - including the On key, activity on the link IO port (any line held low will trigger an interrupt) or this timer. The TIOS seems to use this timer to scan the keypad a few times a second, so it can read a key and store it for the key reading routines.
Fortunately, it is possible to take advantage of interrupt mode 2 on these calculators to install your own handler. When the engine is initialised, it adds the new handler - which is very simple. All it does is increment a 16-bit counter!
I added a piece of code that read this value and set it to zero each frame, displaying the result (ticks). I then added a piece of code that toggled the data lines of the link IO port, and used a PC program to monitor this rate (I used this technique before to work out interrupt-based timing for the 60Hz CHIP-8 clock). By comparing two extremes - a large viewpoint where I could see all of the walls, close up and a viewpoint where I could see nothing, I could see that one view ran at 16FPS and accounted for 20 ticks, and another ran at 44FPS and accounted for 8 ticks. This shows that one tick is approximately 3ms long, and that a FPS counter could be implemented by dividing 333 by the tick count.
A quick check with my PC program shows that the counter is fairly accurate (close enough for my liking). I can now use these tick counts to scale the movement of the player, so the speed is consistent. Another advantage is that I can set the SE edition calculators to 15MHz, and they can benefit from more fluid framerates (nb: any program I run will still need to run merrily on the 6MHz calcs for me to be happy. I'm not going SE-only!)
That's not to say I can now go and build an exciting level and release a nifty demo. There are still big holes in the engine - simple graphics bugs, like the wall filling code still not supporting top edge slopes with a y difference of over 127: (overflow-related bug)
...to there still not being any proper occlusion (sorting)...
I'd like to get occlusion up and running, so I can throw a nifty level together (for example, showing off non-90° walls). Thing is, it's tricky trying to show off cool stuff and not walk into an area where you can see the world isn't quite as solid as it should be. 
Filling
Friday, 7th July 2006
I chucked some simple filling in to the engine as a test. It scans along the top and bottom edges of the shape, then fills columns. This is rather inefficient (filling scanlines is much faster - the screen is shorter than it is wide, so tracing Ys for the boundaries is faster than scanning Xs, and when filling by scanline you can write 8 pixels - a byte - in a single shot) but it served the purpose of a quick demo. It's rather broken, and doesn't match the lines correctly (so there are slight gaps and overflows). It's only temporary.
I'd like to extend the filling to support different dithered fills - white, 25%, 50%, 75% and black walls would look nice.
There is no sorting as yet, I just arranged the walls in back-to-front order in the level file.
@philipptr: I don't know if you ever completed your triangle filling, but the way I've done it in the past is to split the triangle into two halves (y0→y1 and y1→y2, where y0<y1<y2). I would then trace down the sides of the triangle, calcuating the X bounds for the top and bottom halves (Bresenham), then filling in the horizontal lines using these values. Only uses integer arithmetic, so nice and fast.
Whether this will be turned into a game or not depends on whether I can get it to scale sensibly with decent-sized levels; especially with the addition of scaled sprites. If I can get a nice sized level that you can walk around nicely, then I'll try and add a game - pointless planning a game around an engine that isn't up to par!
Clipping works! (Almost)
Monday, 3rd July 2006
Clipping now works in nearly all cases:
One of the problems was lack of precision. Here's the typical case that worked, running in my mockup:
In this case, where |dX| > |dY|, all is good. However, switch that around so that |dY| > |dX|, and you get the following:
(Fixed point isn't so good for holding values that tend towards infinity). The solution is to have two branches for the clipping arithmetic, switching to the alternative form when |dY| > |dX|.
Preparation:
m = (Y1 - Y0) ÷ (X0 - X1) ; m is negative gradient.
c = Y0 + m × X0 ; Not sure what to call this, but it's used in all the below calculations
Clipping to y = 0:
x = c ÷ m
y = 0
Clipping to y = +x:
y = c ÷ (1 + m)
x = +y ; not used as we can skip having to transform.
Clipping to y = -x:
y = c ÷ (1 - m)
x = -y ; not used as we can skip having to transform.
The reason for clipping to y = 0 is to make sure the line is clipped to the correct side.
If you look at the red and blue lines, you can see that the far out-of-range points both have x < 0. This indicates that you should clip to y = -x. However, the green line also has the far end at x < 0, but we actually need to clip to y = +x. We can fix this problem by first clipping to y = 0, then checking the sign of x.
To fix the steep gradient problem, I just need to switch to these alternative sums:
First up, the gradient and c are calculated as:
m = (X0 - X1) ÷ (Y1 - Y0) ; Flipped
c = X0 + m × Y0 ; Again, X/Y flipped.
For clipping to y = 0:
x = c ; No need to divide by m!
The only other difference is to make sure that when clipping y = -x:
y = c ÷ (m - 1) ; as opposed to (1 - m)
...and all is hunky-dory.
The only remaining problem is if you are positioned directly inside a wall, which collision detection should fix.
Clipping
Tuesday, 27th June 2006
Clipping (adjusting walls to ensure that they are in the field of view so that they can be drawn correctly is being a right pain).
Firstly, I rewrote some of the really ugly wall-handling code:
Clipping follows the fairly simple maths:
(Where m is the gradient of the wall). The resulting Clip value then corresponds to the new (X,Y) coordinate - if you want to clip to x=-y all that's needed is (1 - m) becomes (1 + m) and Clip must be negated before using it as the new X coordinate.
The result (with added adjustment layer to turn the grey clipped line into red for clarity's sake) seems to work pretty well.
...or not. When implemented with the rest of the code, something goes rather wrong when I look at the wall from the wrong side. Thankfully, that was a simple bug in the division routine, causing it to trash the accumulator when one of the operands was negative (the accumulator itself formed part of one of the operands).
With that fixed, things look a bit more positive, but it's still rather unstable.
Latenite 1.0.6.0
Tuesday, 20th June 2006
There's a new Latenite beta - 1.0.6.0 - available from my site. I hope this is the last Latenite 1 release; I'm moving away from the current IDE towards a revised Latenite 2, the focus more on interactivity with the assembler and the debugger (better 'Intellisense', breakpoints, variable watching and so on). This mainly revolves around a much improved text editor, currently in the works.
Not a very exciting thing to look at, but handling text selection, editing, copying, pasting, and highlighting - and keeping it fast - is being a bit of a pain.
For the most part, it is fast enough, but gets seriously sluggish when scrolling up and down at high resolutions (has to repaint the entire control as none of it is buffered).
That little 3D engine for the calculator I was working for (codenamed Nostromo) is not dead, as you might have thought;
(Old screenshot to refresh your collective memories). I have recently 'ported' the TASM-style code to the new Brass syntax, rewritten all of the wall handling code for increased performance and fixed some of the graphical glitches caused by overflow (lines wrapping incorrectly around the display). I have increased the resolution and accuracy of the maths in use as well, but it's still pretty sluggish with large amounts of data and still lacks occlusion and wall clipping to the view.
One (easy) way of speeding things up would be to split the world up into 'rooms' (or zones, pick whatever terminology you like) where each room is entirely self-contained and cannot be seen from any other room. By opening and closing doors between rooms you can add and remove which rooms are in the list to be drawn, keeping the geometry count low.
Of course, for this to work, I'd need a bit of collision detection to be able to work out which room the camera is in.
In terms of occlusion, I'm a bit stumped. As far as I can tell, BSP might be the way to go, but have never been able to write a working 'BSP engine'. If anyone had any links they'd recommend on the theory and implementation behind this, I'd be very grateful.