3
\$\begingroup\$

I was recently reading up on Carmack's Adaptive Tile Refresh, of which was written extensively in this thread, to implement in a hobby gamedev project of mine: https://retrocomputing.stackexchange.com/questions/22175/what-is-adaptive-tile-refresh-in-the-context-of-commander-keen

I must admit that I know little of the exact ways the PC was limited at the time (as in limited fill rate, restrictive display modes and what not) so I don't entirely understand as to why some of the steps mentioned in the answer to the above thread were used. I also understand modern PCs can more than blaze past with naive techniques such as storing the level data entirely in memory, but I'd wanted to implement this since I found the idea exceedingly interesting

Here's what I understand of ATR so far:

  1. Assume the world map is stored in memory (not video memory)
  2. Carmack would use a special drawing mode that allowed to extend the video buffer by an extra few pixels (say, by 16 pixels) (enough to fit an extra tile) horizontally (in this case)
  3. Assume that the initial screen has been drawn (along with the extra tiles in the offscreen buffer) by loading them from the world map in main memory, to the buffer
  4. Pan the 'camera' pixel by pixel horizontally to smoothly scroll through the screen
  5. Once you've scrolled the entire length of the buffer along with the extra length of the offscreen buffer, this would mean i) The tile we initially had on the left side of the screen (assuming we were scrolling to the right) is now wiped out, stuck in another offscreen buffer to the left of the screen ii) The tile we initially had on the right-hand side off-screen buffer has now been fully 'drawn' into view
  6. 'Jolt' the screen back by 16 pixels, load in the next tile from the world map from the main memory to the offscreen buffer, repeat the process again (As for what happens to the tile that was in the left-hand side offscreen buffer after the jolt, I am not sure myself. Where would it go?)

What I don't get is the step wherein existing tiles on screen are compared before being drawn (I've left out the step here since I do not quite fully understand them)

Why are we checking if a tile's changed if we are panning through the buffer anyway? Assume we are drawing pixel by pixel, this would be the equivalent of simply changing the 'range' of values which we loop over and display right? It has to be drawn pixel by pixel if we want to smoothly scroll over tiles

I did think of one scenario where the tile checking would be useful:

If the display card renders tile by tile and is 'state-based', where the state are the values/data held by each tile (values/data as in the exact tile you want to display) ,where the process of checking if the previous and current frame's tile index match, and leaving them as is if so, or updating the tile state to match the new tile if not is cheaper than blindly updating and redrawing the state each time, tile checking would be more efficient

This would of course mean that smooth scrolling by going pixel-by pixel would be nigh impossible since all you ever have are tilemaps on hand, so you can't 'partially' scroll through a tile

I know I've gotten the concept horrifically wrong somewhere but I can't quite figure out where despite wracking my head it at it. Where exactly did I go wrong?

\$\endgroup\$
2
  • \$\begingroup\$ Although I love to dig deep into other people's implementations and discuss the theory at the core of their solutions, I'm afraid that "How does technology X work" is not the ideal question format for this website, and your question will be considered off-topic. \$\endgroup\$
    – liggiorgio
    Feb 4, 2023 at 11:08
  • \$\begingroup\$ This question looks on topic to me. We get a fair few "Help me understand this algorithm used in games" questions, and this seems to be in that vein. \$\endgroup\$
    – DMGregory
    Feb 5, 2023 at 13:42

1 Answer 1

1
+50
\$\begingroup\$

I haven't heard of this algorithm before, but I think I understand what you're missing.

'Jolt' the screen back by 16 pixels, load in the next tile from the world map from the main memory to the offscreen buffer, repeat the process again (As for what happens to the tile that was in the left-hand side offscreen buffer after the jolt, I am not sure myself. Where would it go?)

You're imagining that tiles are added at the right edge in some way, leaving the area of the video memory corresponding to the part of the level that stayed on screen untouched. That's not the case for the situation which this algorithm was used. Instead, the same region of video memory is always filled with currently visible or almost-visible tiles, exactly as if there was no smooth scrolling (every step is a whole tile).

Therefore, each scrolling step has to redraw tiles that are in the interior region of the screen, not just the edge.

The value of the comparison, then, is that the program can skip redrawing any tiles which haven't changed due to scrolling (because the old tile and its neighbor in the scrolling direction are identical), and it can do this purely by comparing the (small) tile map data, in order to decide whether it has to spend time writing every pixel of the tile into video memory.

And, entirely separately from this process, the sub-tile scrolling (0 to 15 pixels of distance) is handled not by writing anything to the video memory, but by writing to video card registers that tell it where to start reading from when generating the output video signal.

\$\endgroup\$
12
  • \$\begingroup\$ I thought they could use an offset window into the in-memory data with wrapping, so that "in memory columns 1-20" get rendered to "on-screen columns 41-60" and "in memory columns 21-60" get rendered to "on-screen columns 1-40" (being very crude with the details here). In such a situation, you really could leave most tiles as-is and only update the new column entering view, without gradually creeping across unbounded memory, just wrapping around instead. I show something conceptually similar in another context in this answer. Is that wrong? \$\endgroup\$
    – DMGregory
    Feb 14, 2023 at 20:17
  • \$\begingroup\$ @DMGregory My remark was assuming the old hardware that the algorithm would have been designed for — in which case to do what you describe you would have to convince the hardware scan-out to perform the necessary modulo operation to cause the wrap-around. I haven't heard of any early PC hardware supporting that (though it's certainly possible with modern programmable GPUs), and the goal of this answer is to explain what the algorithm was, not to propose different ones. But since this isn't actually Retrocomputing, I've clarified that it is possible to use the modulo strategy today. \$\endgroup\$
    – Kevin Reid
    Feb 14, 2023 at 21:24
  • 1
    \$\begingroup\$ Isn't that hardware modulo support what the linked page is referring to when it says "second gen [Keen 4-6] relied on 64k wrapping in EGA memory"? \$\endgroup\$
    – DMGregory
    Feb 14, 2023 at 22:04
  • \$\begingroup\$ @DMGregory Okay, I see. I've removed that part entirely, then. \$\endgroup\$
    – Kevin Reid
    Feb 14, 2023 at 22:09
  • 1
    \$\begingroup\$ @Hash Yes, given that "upon movement" we mean "coarse" movement by whole tiles and not the "fine" 0-15 pixel movement, and by "check" we mean check the level data and "replace tile" we mean write the tile's sprite into video memory. \$\endgroup\$
    – Kevin Reid
    Feb 18, 2023 at 17:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .