24

The question Did John Carmack really invent "Adaptive Tile Refresh"? asks about the origins of the scrolling and drawing techniques used to allow an MS-DOS PC to provide a NES console-like gameplay experience with an eight-directional free scrolling playfield.

There's many conflicting and overlapping definitions of the term "Adaptive Tile Refresh", but not very many good examples. (Leading to me conflating a few different concepts in my answer to that question.)

What is "Adaptive Tile Refresh" in the context of Commander Keen, and why was it so important?

42

"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.

enter image description here

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.

enter image description here

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':

enter image description here enter image description here

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:

enter image description here

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:

enter image description here enter image description here

Notice how most of the surface of Mars consists of large regions of identical terrain.

enter image description here enter image description here

Difference operation:

enter image description here

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.

enter image description here enter image description here

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.

16
  • 1
    Pardon my skepticism, but "only redraw that which has changed" seems fairly obvious. Is the significant part figuring out how to do this on the hardware available? (I am no graphics nor game programmer) Nov 5 '21 at 14:19
  • 3
    I read it as being the sum total of using a single buffer only 16 pixels and taller than the display with a hardware pan to provide a smooth scroll over a large playfield. Whereas on other framebuffer machines with a pan but greater overall flexibility such as the Amiga you might more usually use a total buffer a bit more than twice the width of the screen, jumping back from the end to the start in order to cover up the lack of wraparound.
    – Tommy
    Nov 5 '21 at 14:35
  • 1
    Very much liked this answer, and the animated illustrations. Though I think they would work even better if they depicted the exact same playthrough, so the exact same frames could be viewed as displayed and as held in memory. Nov 5 '21 at 17:14
  • 3
    @another-dave No, I think this is all ATR -specifically- refers to. Given the Johns' quotes and the animations I made, there's nothing else it could be. I think it's a catchy bit of history that sounds complicated until it gets explained, and there's a lot of romance to the idea of one man somehow coming up with a special technique that nobody else had ever seen and founded an important company on the back of it, and so the term sort of took on a life of its own. That's why I wrote this q/a, to finally figure out what the reality of it was. Everything is simple in hindsight though!
    – knol
    Nov 5 '21 at 22:16
  • 3
    @knol - well, I "invented" the same technique 2 or 3 times over on character-cell terminals :-). If you're at the other end of a 300 bps dialup, it's worth spending some time reducing the number of characters you send to the terminal. ("Invented" in quotes since I was under no such illusion: though in one case I did have a novel refresh algorithm that started at the current cursor position, and users hated it because it "looked weird"). Nov 5 '21 at 23:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.