Suppose you're writing a scrolling game for very limited hardware. You have a frame buffer which is larger than the visible screen, but smaller than the entire level. So when the screen scrolls upwards (for example) you may need to plot a new set of tiles into the frame buffer just above the current screen position, so that the correct image will be displayed when the top of the visible screen overlaps the space where those tiles are plotted.
Now suppose that the hardware is so limited that there is not enough CPU time to plot an entire row of tiles each time you pass a tile boundary - perhaps you can get 60fps normally, but every time you pass a tile boundary you drop a frame or two while the new row of tiles is drawn into the frame buffer.
To avoid this glitch, instead of drawing all tiles at once, we can just draw one or two each frame. Suppose there are N tiles horizontally across the screen, and it takes M frames to scroll upwards by the span of 1 tile. Then we can draw N/M tiles each frame, and by the time the top of the screen gets to the bottom of a particular row of tiles, all of those tiles have been drawn.
Now we need to keep track of which tiles have been drawn and which haven't. The obvious way to do this would be to just have an array of bits, 1 for "tile has been drawn" and 0 for "tile needs to be drawn". Now, each frame when we draw a tile we can iterate through the array to find the first tile that hasn't been drawn and draw that one.
But what if there are rather a lot of tiles? Iterating through all those slots to find a "needs to be drawn" one could take a while, especially if all the undrawn slots are all the way over to the right. So we've turned a O(N) operation (N being the number of tiles drawn) into a O(N2) operation. Oh, and did I forget to mention that this is a 2D scrolling game? So we'll have a similiar list for each side of the screen, and each time we pass a tile boundary going vertically, we'll have to shift the left and right lists one tile.
How can we get rid of this quadratic behavior? Well, I think a data structure that should work well is a linked list. If we put the information about one tile slot in each node of the list, that makes it O(1) to shift the whole list one tile forwards or back for lateral scrolling, but doesn't fix the O(N2) search behavior. However, notice that we only need to store 1 bit of information about each tile slot. So what we can do is apply a run-length-encoding transformation to the list. Each node stores a pair of numbers - the length of a run of drawn tiles and the lengh of a run of undrawn tiles immediately following it.
Now all the operations we need are O(1). For the "top of screen" list, scrolling left or right by one tile just involves adding a slot to one end of the list and removing one from another. Finding the next tile to be drawn just involves looking at the first element of the list. We need two more operations: throwing away the entire list and replacing it with an "all drawn" list (for scrolling downwards) and throwing away the entire list (hopefully a single "all drawn" entry) and replacing it with a "none drawn" list (for scrolling downwards). Throwing away a list with potentially many entries sounds like it could potentially be an O(N) operation, but as it's a linked list we can move all the nodes to a "free nodes" list just by modifying the ends.
As always where performance is concerned, be sure to actually benchmark this before using it - depending on the hardware and the number of tiles in question, all that pointer chasing and cleverness may actually be slower than the naive bit array method. This is especially true if you're not in a hard-real-time situation, and the average case behavior matters more than the worst case behavior. Constant time algorithms have a definite appeal from an the aesthetics pespective, though.
I just don't get it:
Why not draw the tiles from left to right and keep one simple variable with the x-tile coordinate which one has been drawn last?
Just draw two tiles and increment by two.
Why is there an array with bits?
I probably should have elaborated on that a bit more, so I'll do that here. Suppose you scroll up and start filling in tiles from the left. You draw a few tiles, then stop scrolling so the rest of the row isn't needed. Then you scroll left, so the "drawn" tiles are no longer on the left but somewhere in the middle, horizontally. Then you start to scroll up again. Again you start filling in tiles from the left, so now the set of tiles you have drawn is non-contiguous. If you forget about the ones you've already drawn, there won't be enough time to draw the entire row before it scrolls onto the screen.
Not sure how I missed this basic concept during our prior conversations, but drawing only one tile per frame is a *brilliant* idea!
I still don't quite get the linked list idea; were I to implement something like this, I'd use a large 2-dimensional array for the tile map, and four smaller 1-dimensional arrays for each screen edge that held the tile status (drawn or not drawn). This uses more memory than a bitfield array but it's much faster because everything becomes direct simple addressing.
This sounds like something built almost entirely for software scrolling (such as early PC games). For platforms which already use hardware scrolling, such as many old game systems, and thus are already optimized for efficient scrolling and aren't that easy to reprogram.
Still, definitely seems pretty rad.
Yeah, the target system for this is CGA which has hardware scrolling in the form of a programmable start-address register with VRAM wrapping behaviour but no other hardware scrolling support (such as a sprite-and-tile system or a virtual screen wider than the physical screen). For machines designed with 2D scrolling in mind (like arcade boards and consoles) this technique wouldn't be necessary.