"Adaptive Tile Refresh" is the strategy of maintaining a software-drawn tilemap in memory in place by redrawing only the tiles which differ after moving a logical camera across a grid of tile indices to scroll the screen, or are dirtied by an overdrawn sprite.
Quotes from Carmack and Romero:
Carmack:
The trick behind the scrolling in the first Commander Keen games was to only redraw tiles that actually changed after panning 16 pixels, since most maps had large swathes of constant background. Text consoles have similar statistics with spaces, so the same trick is a big win.
First gen keen only smooth panned a single tile, and relied on there being lots of identical tile values to reduce cost at the tile switch. Second gen [Keen 4-6] relied on 64k wrapping in EGA memory. Had to add a compatibility mode for some SVGA that did a full refresh at the wrap point.
Romero:
Each Keen engine was different. The Keen 1-3 engine worked [...] using the EGA panning register to get pixel-smooth scrolling and when it was about to hit a tile boundary it refreshed only those tiles on the screen that needed to change (thus "smart tile refresh").
Demonstration of ATR for camera movement:
Let's look at Episode 1: Marooned on Mars. This is the first level of Marooned, immediately to the right of the crashed Bean-with-Bacon Megarocket.
The camera freely moves horizontally and vertically to keep Keen centred on screen when he moves close to the border. Hardware scrolling in EGA is done by setting the CRTC Start Address and Horizontal PEL Panning Registers. The Start Address specifies where in video RAM the screen data to be shown begins: if the address is increased by the size of one screen line in bytes, the screen appears to be shifted one pixel upwards. This alone only provides coarse horizontal scrolling. In EGA's planar graphics modes, the eight bits in each byte of video RAM correspond to eight consecutive pixels on-screen, so the Horizontal PEL Panning Register is needed to refer to the eight pixels within the byte specified by the CRTC Start Address.
I captured the above GIF in Dosbox. We can modify Dosbox's source code to disable changes to those EGA registers. This will force the emulated display to show the contents of video RAM starting at address zero always, disabling hardware scrolling entirely! The game itself will be completely unchanged.
Let's look at the same level with these changes.
This GIF shows the contents of video RAM starting at address zero. As Keen travels through the level, the visible window isn't moving through VRAM. Every time Keen moves sixteen pixels in any direction, the entire level seems to be 'jolted' back a full tile, pushing the player back into this region of VRAM near address zero.
Here's a pair of screenshots from the beginning of the level, before and after a 'jolt':
They look almost identical to the naked eye, don't they? The second screenshot is after Keen has moved 16 pixels to the right through the world.
This is the result if I do a difference operation on the two images:
This image shows all the tiles that have changed as a result of the 'jolt'. (Ignore Keen himself.) The long platform in the centre-left of the image has almost entirely vanished since it consists of a repeating pattern of tiles.
These tiles shown are the only ones that the CPU has to redraw to update the screen. Also, this only needs to happen each time Keen moves 16 pixels.
The illusion of a contiguous, large playfield is provided by EGA hardware scrolling within this region of memory close to address zero. These screenshots show only a 320x200 region - the intended visible region extends slightly to the right and below these screenshots - the intended visible region is most likely a 336x216 region to allow hardware scrolling into an additional 16x16 border. Whenever the camera scrolls off the edge of this border, a 'jolt' occurs and the level is 'shifted' back by drawing new tiles. Until that happens, the game doesn't need to use any CPU time to scroll the screen within the currently drawn region.
On bitmapped displays without hardware scrolling, the entire screen would have to be erased and redrawn in the slightly shifted position.
Note that since the tiles are guaranteed to lie on a 16 pixel boundary in video RAM, manipulating the EGA registers to rotate the data to slide it left or right when drawing it is not required.
Here's another example from the world map screen in between levels:
Notice how most of the surface of Mars consists of large regions of identical terrain.
Difference operation:
These are the invalidated tiles after horizontal 'jolt'.
The number of drawing operations required during each 'jolt' is controllable by the level designer. If they choose to place large regions of identical tiles (the 'large swathes of constant background' Carmack mentions), less redrawing is required. This is especially noticeable in areas like this dark room.
In an extreme case, if Keen was walking horizontally in a featureless flat corridor consisting of repeating tiles with no gaps in the floor or background details, no tiles would have to be redrawn whatsoever: the design of the corridor would look identical in memory before and after every 'jolt' even as Keen appeared to be making forward progress.
Commander Keen's ATR algorithm:
Assuming Chocolate Keen is an accurate C implementation of a disassembly of Keen:
- The tile index number of the last tile rendered is stored for every grid slot on each display page.
- When a sprite is drawn, it invalidates all the drawn tiles that its bounding box intersects.
- The background tilemap is redrawn once every frame:
- The ATR function scans through every tile in the current display page and compares them against the corresponding tile from the world/level map one by one - the cursor used to scan the world/level map is offset based on the current scroll X and Y values.
- If the stored tile index number at a grid slot doesn't match the one in the world/level map, it is redrawn.
The engine doesn't have any way to track large objects or platforms in the world to know to only update their sides, and doesn't cache the sets of tiles needed to perform any given 'jolt' - the comparison is a naive linear loop through the current display page.
Impact on Commander Keen as a whole:
Thinking of "Adaptive Tile Refresh" as a tile-update strategy by itself is too narrow a view to appreciate its benefit to Keen. Carmack's earlier Gauntlet-like Catacomb even has the same tile invalidate/update algorithm just with simpler (8x8) tiles - look for CgaRefresh in CATASM.ASM in the Catacomb source code. The modified GIFs even resemble Catacomb's motion.
It was the experiments leading Carmack and Romero to design a complete engine design combining EGA hardware scrolling over a fixed memory region with intelligent tile replacement within that region (and fast free-positioned sprite drawing, and page flipping*...) to make Keen (or its prototype predecessors) a viable full-screen free-scrolling game.
* Changing the CRTC registers also has the benefit of allowing double-buffering (so a half-redrawn screen is never accidentally shown). My Dosbox modification prevents page flipping from working, so the locked Keen gifs above appear to run at a halved frame rate compared to their normal counterparts.
When is Keen-like ATR useful for scrolling?:
Keeping track of tiles that are invalidated by overdrawn sprites can help avoid redrawing the entire screen in systems with a single bitmapped drawing layer, regardless of whether the screen scrolls. There are other ways to do this, of course.
It is useful on EGA and VGA Mode X and other bitmapped modes since drawing tiles is considerably more costly than comparing two tile index values to see if a re-draw is necessary. If more video memory can be used, locking the visible region in place and using Keen-like scrolling isn't necessary. Jazz Jackrabbit and Commander Keen 4-6 don't use a Keen-like scrolling system.
(Coincidentally, the lower half of a VGA split-screen can be pixel panned but not coarse scrolled from its start address of zero, so it works like Keen's fixed 'jolting' region of memory.)
It would not be very useful on any system where exchanging tiles is equal or less costly than the comparison required to check if they should be changed. For example, on systems with hardware implemented tilemaps (C64, NES, SNES, Game Boy, Master System, Mega Drive), writing a tile can be as simple as changing one byte (give or take applying modifier flags to the index). These systems wouldn't be very good candidates for ATR unless they used large metatiles or the tilemap was being used in some other non-standard way (e.g. manually altering tile graphic contents to fake parallax scrolling). If you have very constrained space in a tilemap, ATR can be used if the programmer is willing to forego the built-in wrapping behaviour of their hardware tilemap to keep track of the moving tiles manually with ATR.
