SP1 Scrolling: Test 3

It can be found in the src/sp1-partial-inv-1 directory. Based on Test 2, but this one keeps track of the tiles that are present on each column, and only invalidates the cells that are affected by them. It also keeps track of how the tiles walk down the screen, and propery moves the cells to invalidate.

The information on drawn tiles is known when printing tiles on the top non-visible row.

The basic idea to explore is column cell-range invalidation:

• Instead of invalidating the whole scroll area with a single sp1_Invalidate() call, we will run an invalidation per column.
• On each column, only cells that have moving content will be invalidated, taking into account that e.g. a 2-row tile will most of the time invalidate a 3-row area due to vertical pixel offset.
• Initially, only one range per column will be invalidated (for efficiency reasons). That is, if we have tiles in rows 4-5 and 10-11, the whole 4-11 range will be invalidated.
• For each column, there is a (min,max) pair which holds the current range of cell invalidations to be done for that column. This pairs are moved down for all columns every 8 scrolled pixels (cell changes occur every 8 scrolled lines). So if scroll is 1-pixel, it will be done every 8 scroll cycles; if scroll is 2-pixel, every 4 scroll cycles; etc.
• Since these min and max values will be cell-based, and in ranges 0-31/0-23, they will be of type int8_t (signed) and we will use min = -128 (NO_RANGE) to signal that there is no invalidation to be done on that column.
• Initially, each column starts with a (NO_RANGE,NO_RANGE) pair (no invalidation)
• When printing a tile on the top non-visible row:
  • Set MIN to -(height of top non-visible row)
  • If MAX is NO_RANGE, set MAX to 0
• Every 8 scrolled pixels, do the following for each of the columns:
  • Adjust MIN and MAX (add 1 to each of them, saturating at the maximum row value)
  • If MIN is out of the scroll area, set both MIN and MAX to NO_RANGE
• The previous adjustments and movements will have to take into account 1 additional cell due to the pixel offsets mentioned above.

We could keep track of all tiles on each columns and only invalidate the strictly necesary, but this would imply having a changing list for each column, which means more processing on a critical code path. If we have several tiles on the same column, I have assumed that it’s probably cheaper to simply invalidate everything in-between than trying to cherry-pick cells to invalidate.

An enhanced version of this schema will be tested in Test 4, though.

My findings with this test:

• The idea of only invalidating the needed areas is good and adds speed to the test
• The current algorithm is not so good: given that on any given column, only a single range of rows can be tracked and invalidated, it quickly degenerates into the full-column invalidation case. E.g.: when the map has few and vertically sparse tiles, the algorithm works well (it can be appreciated at the beginning of the demo, when only a few background tiles can be seen on the screen); but when more tiles start to appear, suddenly all the columns have several tiles and almost the full column is invalidated, defeating the optimization.
• A better algorithm which really keeps track of all the on-screen tiles and their invalidating rectangles will be explored in Test 4.

New stack-based scrolling routine

Also in Test 3, a new stack-based scrolling function has been developed and tested.

I have found that the regular unrolled LDD version is hard to beat, mainly due to the fact that when moving the bytes, the source and destination ranges mostly overlap, and this makes it more difficult to optimize the stack transfer.

The approximate T-state count for each of the versions is commented in the code.

As usual, click here for the TAP file and the source code.