Page 1 of 1

A couple of technical questions about the Keen games

Posted: Thu Apr 09, 2020 4:35
by entropicdecay
So I've messed around a bit with some basic DOS programming, and I've noticed that at least with the methods I've tried, drawing graphics onto the screen is both a bit slow and can be flickery when rapidly drawing changing visuals on the whole screen. I've noticed that in DOS games, for example the various Commander Keens, let's take Keen 1 specifically as the example, the graphics don't generally seem flickery when they're changing as you scroll through the level. I have a couple of questions if anybody knows the technical details of some of this stuff:

1) I presume that when the screen is scrolled the game has to redraw the whole screen rapidly as it scrolls. How is this done as fast as it needs to be to look basically seamless (or close enough)? Can this only be achieved by writing the whole of the code that draws the graphics to the screen in assembly or can it be achieved in higher level languages if you use a particular method of putting the graphics data into the graphics memory?

Also, does the game redraw the screen only if something on screen has changed or does it redraw it constantly anyway? And if you're not scrolling but a sprite like an enemy is moving is it redrawing the whole screen then or does it just redraw the background tiles that sprite is overlapping and then redraw the sprite in its new position, each time the sprite moves?

2) I notice that unlike some DOS games, Keen doesn't generally seem to run faster or slower if you change the cycles in DOSbox. How is this in non-processor-speed-dependent timing achieved in DOS games?

Re: A couple of technical questions about the Keen games

Posted: Thu Apr 09, 2020 22:47
by K1n9_Duk3
As always, there are multiple different approaches to display graphics in a game and make it more or less flicker-free. The solution varies from game to game, and different graphics modes (CGA, EGA, VGA) all require slightly different solutions.

The most basic solution is to use "double buffering". That means you have two image buffers. You always draw to one buffer while the other buffer is being displayed. The only reason why you see flickering is that the video card is displaying the image while you're modifying it (i.e. drawing or erasing something). Using double buffering avoids that issue for the most part.

EGA graphics modes have the benefit of providing more than enough video memory to store multiple full-screen images at 320x200 pixels in the video memory. So you basically get hardware double-buffering for EGA graphics. A 16-color 320x200 pixel screen only takes up about 32k of video memory and most EGA/VGA cards have at least 256k of video memory, so you can store up to 8 full EGA screens in video memory.

VGA requires more memory for 320x200 pixels at 256 colors (64k per screen) and with regular VGA (and the mostly VGA-compatible MCGA), you can only access 64k of video memory, so you would have to keep the second buffer in main memory and draw to that buffer, then copy (parts of) it into video memory to display them. You can also change into "planar" VGA (sometimes referred to as "mode Y"), which allows you to use four 64k blocks of video memory (256k total), which gives you enough space to store four screens in video memory.

CGA is a bit different. As far as I know, CGA doesn't provide enough video memory to store more than 1 screen (320x200 pixels, 4 colors) in video memory, so you'll have to create a second buffer in main memory if you want to use double buffering.

The benefit of having both buffers in video memory (EGA and planar VGA) is that you can tell the video card which buffer it should display. That means you can "flip" the buffers almost instantly and don't have to copy the entire buffer into video memory. Copying the buffer can be very slow and can cause "screen tearing", which means the upper part of the screen is showing the new image while the bottom is still showing the old image (because the CPU has not yet finished copying the entire screen).

But the most important thing is that you want to avoid re-drawing things as much as possible. Back when Keen 1 was made, CPUs simply weren't fast enough to redraw the entire screen every time and still achieve "playable" frame rates. That's why the technology that John Carmack had created was such a huge deal back then.

To understand how the scrolling in Keen 1 works, you should know that the EGA card has a couple of nice features that make it extremely powerful, but not very straight-forward to use. You can reprogram the EGA to essentially make the video buffer wider than the actual screen. So instead of a 320x200 pixel buffer, you can use a 384x224 pixel buffer. Other features of the EGA card allow you to make the card "scroll" within this larger buffer (see: "panning register").

So this means that when Keen 1 wants to scroll the screen by 1 pixel (in any direction), it doesn't actually have to redraw anything in most cases. It's already drawn in the "invisible" parts of the screen buffer. Once the screen scrolls so far that it reaches the end of the buffer, the buffer is re-drawn. This is where "adaptive tile refresh" comes into play. The whole buffer basically scrolls by 1 tile at this point. And since the game always remembers which tile number was drawn at which point of the video buffer, only the tiles that actually change after scrolling need to be redrawn.

The sprites are drawn on top of the tiles and when a sprite is drawn, it marks all the tiles that are covered by the sprite image. That means it sets the tile number at that location to -1 or some other value to force the game to redraw the background tile for the next refresh. Redrawing the background tiles effectively erases the sprite. This allows the engine to skip drawing the parts of the screen that haven't changed.

In Keen 1, all of the tile drawing (and the adaptive redrawing of the tiles) is done in pure assembly. You can write your tile drawing code in a high-level language like C or Pascal (or Basic), but it will never be as fast as well optimized assembly.

A completely different approach can be seen in Duke Nukem 1. That game uses hardware double buffering, but it doesn't do any adaptive tile refresh. That game literally just redraws the entire screen (or at least the part that shows the level) every single frame. But Duke 1 also doesn't do any smooth scrolling (the camera moves in multiples of 8 pixels) and is limited to around 18 frames per second, while Keen 1 can go a lot faster (24 fps). If Duke 1 used a full-screen view instead of the relatively small view window, it would get even slower.

Another aspect worth mentioning here is that both Keen 1 and Duke 1 store their tile graphics in EGA memory. That means the tile graphics can be drawn with "hardware acceleration" where CPU uses an instruction to copy 1 byte, but the EGA card (which handles all access to its video memory) copies 4 bytes all at once. But again, nobody says that you absolutely have to copy the tile graphics into EGA memory. Dark Ages (which is very similar to Duke 1 and shares some low-level code with Duke 1) doesn't load it's tile graphics into EGA memory and it still works ... at least to some extend.

Now for your second question.

Most games hook up their own interrupt handler to interrupt vector 8 and reprogram the PIT (programmable interrupt timer) to run at a frequency that's a little higher than the standard 18.2 Hz. They usually use 140 Hz or something similar. The interrupt handler increases a "timer" variable every single time it is executed and then usually does something else, like handling sound effects.

Once you have your timing service running in the background, you can monitor the "timer" variable to make your game run at the right speed. The easy way is to go for a constant frame rate (like in Duke 1). For this, you set the timer variable to 0 before you start updating your game objects and drawing stuff to the screen. Once you're done, you wait until "timer" reaches a certain value. With this approach, your game will never run too fast, but it may run in "slow motion" if the system isn't fast enough to update and draw everything within this predefined time limit.

The other way is to monitor how much time it actually took to update the game objects and draw everything. For this, you wait until the "timer" variable is at least 1, then you copy the value into another variable ("speed") and reset the "timer" variable to 0. Then you update the game objects, but you multiply all movement speeds by "speed" (or you update every object "speed" times, but that's probably more CPU intensive). The problem with this approach is hit detection. If the frame rate drops too low, the speed values may get so high that objects end up moving through each other without actually touching each other. So you'll probalby want to put a safety check somewhere to make sure "speed" never exceeds a certain value. The result of such a restriction will be that the game will again appear to run in slow motion when the system is too slow to update and drawn everything in the desired time frame.

What you should never do is to put some delays with a fixed duration in your main game loop. That's what Dark Ages did. And that's why Dark Ages runs at hyper speed on anything faster than a 486 DX 40 - if it runs at all and doesn't crash right away with a divide error. With a constant delay in the main game loop, the frame rate will depend entirely on the CPU speed. That should be avoided at any cost. Don't repeat the same mistakes that were made 30 years ago.

Re: A couple of technical questions about the Keen games

Posted: Fri Apr 10, 2020 8:48
by entropicdecay
Thank you very much for all of the information!

Re: A couple of technical questions about the Keen games

Posted: Sun Apr 12, 2020 2:20
by Quillax
Whoa! Looks like K1n9_Duk3 strikes again with good, interesting technical info behind DOS games! :O I'll have to read the whole thing at some point -- looks like there's a lot to learn from!