General 8-way scrolling: algorithms/etc

[chadderack]

It is said that you can't solve a problem in code unless you understand the problem. And 8-way scrolling still seems to be difficult/impossible for many people--including myself.

There's a great download "ScrollingTricks.lha" (which apparently was done by board user aros-sg) that really does a great job describing several different types of scrolling and the algorithms that should be used. Apologies to him if it seems like I'm trying to replace his wonderful work there. I'm just still having issues with the problem--especially trying to understand the special cases. I ran into difficulty doing a 1-to-1 translation from the example code he used into something tailored to my project. I hope it's OK to kind of hash out the problem in a different way here--and maybe I'll learn something in the process. Maybe it will also help others having difficulties with 8-way scroll.

Anyway, I'd initially written a successful 8-way scroller (based on aros-sg's source) with the initial iteration of my Black Tiger arcade port project--but it was using a source bitmap that was only 16 tiles high. So when scrolling diagonally, I didn't see a number of problems that started to crop up when I used a source map that was 48 tiles high.

....

The issues/complications of using an 8-way scroller seem to be these:

• A limited screen buffer that is only as big as the visible screen, plus two fill columns and two fill rows... and some extra rows of bytes to account for horizontal scrolling through the entire map
• A fill row that was just used for downward scroll might--if the player suddenly changes direction--now need to display blocks from above the visible screen.
• Right scrolling blits one planeline lower into the far left fill column so that when the buffer pointers are moved forward, the block appears in the far right column aligned properly. This can cause ugly artifacts when switching directions.

In my current project, I've slightly modified the algorithm by aros-sg (the XYLimited2 one); instead of using a buffer that surrounds the visible screen on all sides (top/bottom/right/left) my buffer uses the right and left fill columns, plus two fill rows at the bottom. When scrolling down, you blit to the bottom fill row. When scrolling up, you blit to the top fill row. I changed it because of problems with the "vertical split."

Anyway, if you read up on ScrollingTricks.lha--specifically YUnlimited2--it explains the vertical split used on an Amiga in the copperlist.

My buffer shape allows the vertical split to move continuously up and down without needing re-calculation. Before--because my visible screen was only 14 tile rows high (224 px), the vertical split would pause for two whole tile rows before continuing (either up or down).

....

If you're able to follow directions from ScrollingTricks.lha reasonably carefully, then you should be able to code a horizontal scroller or a vertical scroller without much trouble. The complications start when combining directions.

I'll tackle the RIGHT+DOWN scroll problem first.

When scrolling right AND down, you need to pick blocks from the column in the source map just to the right of the screen buffer. This is because everything in the right fill column is already ready to be displayed. So--when scrolling right, you want to keep those blocks. So you blit all your "right scroll" blocks to the LEFT fill column. When you then move the buffer pointers to the right (2 bytes per 16px tile) the blocks that were in the left column get "dragged" into the right column, one plane line higher.

Likewise because of the DOWN element, you need to pick source blocks from one row below the row that will show on screen next... which would mean one row below the TOP fill row. So whatever blocks correspond to two rows under the current visible screen are the correct blocks.



We want to start our right scrolling blits (tile 0h) on the same tile row as the top of the visible screen. This is because we won't need to see any blocks that are more than one tile row above our current top row (we're going down). For the blocks to blit--if we just go with the blocks immediately to the right of the screen buffer and below the top fill row, we have what is shown in the aqua. Those blocks get blitted into the LEFT column and BOTTOM row of the screen buffer.

Now the whole trick with a "scrolling buffer" is moving the pointers. When scrolling right by one tile, we add 2 bytes to the bitplane pointers (if we have 2 bytes per planeline per tile and 16px tile blocks). When scrolling down by one tile, we add an ENTIRE ROW of bytes (in my case, it would be $B40...((18 columns x 16 pixels per column) / 8 bits per pixel) x 5 bitplanes x 16 rasterlines high).

Moving a row down means that the row that was on the bottom is now one row higher--in the top fill row (or the next row to be shown when scrolling down). And the row that used to be the top row (visible screen) is pushed into the BOTTOM fill row. As you can see by the last graphic, the blocks that were in the left fill column are now in the right fill column. The blocks that were in the bottom fill row are now in the top fill row.

That presents us with the problem--the first tile blitted by the vertical scroll (downward scroll) (I'm calling 0v) gets dragged into the rightmost column. Not only does it not belong there--it is planeshifted one row up. So when you continue your diagonal scroll, an ugly block will appear in the lower right of the visible screen--unless you do something about it. That would continue as shown by the pink trail.

The solution would seem to be--blit two tiles into the right fill column on the LAST BLIT during right scroll. That would over-blit block "0v" and the problem will disappear. However, there is one big complication--what happens if your two vertical blits are separated on the vertical split? You have to special case that... and blit one block to the "top" of the buffer and the other to the "bottom" of the buffer.

...

There still seem to be complications--especially if starting a diagonal scroll on an "uneven tile boundary"... if the x-position isn't divisible by 16. The "last blit" done by the right scroll doesn't line up with the bottom right corner block--the "error block" gets shifted right or left. Worse, because the screen isn't only 16 tiles wide--there are double blocks (I'm doing double horizontal blocks on step 4 and 11)... I have to replace blocks in the fill row on 15 of the 16 steps during a diagonal blit.

Maybe this is a problem only because of where/how I do horizontal blits into the fill column. I use absolute map positions for those so that I can use a lookup table for the offsets. Meaning... if I'm on tile row 0, my vertical blits start with block 0 (a row higher that the visible screen) and that would go into the bottom of the fill column. The rest of the blocks start at the top of the fill column. If on row 1 or 2 or 15, the blit positions remain the same.

If I instead used relative map positions (relative to the screen buffer's y position) then maybe the problem would work itself out. However, my brain is now a pretzel and I start to lose interest when my brain turns into a German treat

...

All this said... in my current project, things are working about 95%. The diagonal blits mostly work. However, because of the absolute positioning of the horizontal blits, I end up with a situation where if a person scrolls to the right... stops... scrolls down 10 rows... and then scrolls left... there are blocks on the screen that do not belong there on the left column. Similar if you scroll left, then a vertical scroll, then a right scroll.

I'll pick this up later--trying to explain more of the problem to myself--with a different combination of directions. None of these would be too complicated if people never quickly switched directions when scrolling :-)

[Retro1234]

I did it once kind of like this
http://eab.abime.net/showthread.php?t=80646
So the screen was twice the height and width with 2 or 3 columns/rows for some buffering
if I scrolled down diagonal I noticed I ended up with the screen split into 4 identical screens or something like that but what always bothered me was there must be a perfect mathematical formula that if your visible screen is blah and tiles blah to reach perfect scroll i.e after diagonal scroll such and such it's been ages so can't remember and others probably know better ways but it always bothered me there must be a perfect formula instead of my guess work. Anyway good luck dude.

[chadderack]

Originally Posted by Retro1234

I did it once kind of like this
http://eab.abime.net/showthread.php?t=80646
So the screen was twice the height and width with 2 or 3 columns/rows for some buffering
if I scrolled down diagonal I noticed I ended up with the screen split into 4 identical screens or something like that but what always bothered me was there must be a perfect mathematical formula that if your visible screen is blah and tiles blah to reach perfect scroll i.e after diagonal scroll such and such it's been ages so can't remember and others probably know better ways but it always bothered me there must be a perfect formula instead of my guess work. Anyway good luck dude.

Interesting approach. Thank you for your post, Retro1234. But using a larger/taller buffer, it would still be necessary (*using my current code) to correct blocks that are out of place. With a small screen buffer, I can leave the fill columns visible so that while debugging, the problems might appear. Vertical scroll seems to have virtually no issues when combined with horizontal... it's the horizontal that has the issues. So a taller buffer might not help.

...

To have smooth scrolling (in an algorithm similar to mine), you need to re-use fill columns for left vs. right and re-use fill rows for top vs bottom. The "double duty" of the fill columns is why incorrect blocks show up. People can and will switch directions--which switches the context of the fill row into a source row and the fill column into a source column.

So it's almost like you have to keep track of the last x-direction moved--just to correct blocks that are out of place. Testing this, it seems that if you scroll horizontally, then scroll down or up such that you are on a different "map y block", the difference between that block location and the map y block location where you stopped will be the number of rows you need to re-blit into the fill column (for the x-direction you are moving). That is, unless you scroll up or down less than 16 rows. If you scroll up or down more than that, just AND the difference with 15 (since my buffer is 16 rows tall).

This issue doesn't seem to crop up with up/down scroll... the problems always appear on the left or right edge of the screen. I need to test this hypothesis. This will also play into the "saveword" when switching directions left or right... the map y block delta should be used to compensate for the vertical location of the saveword in the buffer.

[aros-sg]

Originally Posted by chadderack

So it's almost like you have to keep track of the last x-direction moved--just to correct blocks that are out of place. Testing this, it seems that if you scroll horizontally, then scroll down or up such that you are on a different "map y block", the difference between that block location and the map y block location where you stopped will be the number of rows you need to re-blit into the fill column (for the x-direction you are moving). That is, unless you scroll up or down less than 16 rows. If you scroll up or down more than that, just AND the difference with 15 (since my buffer is 16 rows tall).

During X scrolling when you ~"cross over into new" block (like scrolling right from scrollxpos = 15 to scrollxpos = 16, or scrolling from scrollxpos
= 32 to scrollxpos = 31) the Y (!) fill row needs to be"fixed", because it is in the wrong place now.


During Y scrolling when you ~"cross over into new" block (like scrolling right from scrollypos = 15 to scrollypos = 16, or scrolling from scrollypos
= 32 to scrollypos = 31) the X (!) fill colum needs to be"fixed", because it is in the wrong place now.


See this (A), (B), (C) images in xylimited-uk.html in ScrollingTricks. (A) is before scrolling. (B) is after scrolling before the "fix". And (C) is after the scrolling with the "fix" applied.

[chadderack]

Originally Posted by aros-sg

During X scrolling when you ~"cross over into new" block (like scrolling right from scrollxpos = 15 to scrollxpos = 16, or scrolling from scrollxpos
= 32 to scrollxpos = 31) the Y (!) fill row needs to be"fixed", because it is in the wrong place now.


During Y scrolling when you ~"cross over into new" block (like scrolling right from scrollypos = 15 to scrollypos = 16, or scrolling from scrollypos
= 32 to scrollypos = 31) the X (!) fill colum needs to be"fixed", because it is in the wrong place now.


See this (A), (B), (C) images in xylimited-uk.html in ScrollingTricks. (A) is before scrolling. (B) is after scrolling before the "fix". And (C) is after the scrolling with the "fix" applied.

Hey aros-sg, thank you! I'll check xylimited-uk.html and see where I'm going wrong. Much appreciated! The approach that I described in my previous post (fixing the fill column) seems to be working... (for right scroll--haven't fixed left scroll) but maybe aros-sg's explanation can make the algorithm even simpler. I'll try it.

[chadderack]

aros-sg: Maybe you have a minute to help. Here's my issue. I take the x-step from the x-map position ONLY. In other words, [MAPX POS & $000F]. Here's a typical example. Let's say I'm at x=356h and y=b2h. The column highlighted in RED is the right fill area--but I'm blitting to the left fill column. The blocks in the red column are blitted blocks shown one step later.




Now I want to move down three "tile block heights" (rounded to the nearest block height)... so 3 tile moves down. I end up at Y=E1h.



If I don't fix up the fill column, the three blocks shown in yellow will remain on the screen. It's because of the X-step (I believe)



Should I be combining the x-step AND y-step ... or should I just add the MAP-Y block to the X-step so that every "step" corresponds to the same visible row on the screen? Currently I have code that figures out how many column tiles to replace--but it is slow. I'm guessing that's the wrong way to go about things.

Thank you!

[aros-sg]

As you scroll around,the visible part of the bitmap moves around in memory (and vertically also wraps around most of the time). And the blit positions for a step are always relative to that current ~view_start_place in memory. Place == multiple of 16 (tile size). So pixel_scroll_position rounded down to tile grid.

So if y_scroll_pos_in_pixels is 0 .. 15, a stepx of 0 does not blit to the same address in memory, as a stepx of 0 would if y_scroll_pos_in_pixels was 16 .. 31. In memory they would be 16 lines apart.

Everything is always relative to current visible bitmap position/layout (y split/wrap) in memory.

So stepx = 0 always blits to the same "virtual" place, but "physical" may be different as subject to position in memory/vertical wrapping of visible bitmap inside memory of bitmap.

[chadderack]

Originally Posted by aros-sg

As you scroll around,the visible part of the bitmap moves around in memory (and vertically also wraps around most of the time). And the blit positions for a step are always relative to that current ~view_start_place in memory. Place == multiple of 16 (tile size). So pixel_scroll_position rounded down to tile grid.

So if y_scroll_pos_in_pixels is 0 .. 15, a stepx of 0 does not blit to the same address in memory, as a stepx of 0 would if y_scroll_pos_in_pixels was 16 .. 31. In memory they would be 16 lines apart.

Everything is always relative to current visible bitmap position/layout (y split/wrap) in memory.

So stepx = 0 always blits to the same "virtual" place, but "physical" may be different as subject to position in memory/vertical wrapping of visible bitmap inside memory of bitmap.

Ah, thank you. This is where I must have gone wrong. I'll have to re-work horizontal scroll to do things this way. Thanks again!

[chadderack]

I'm not exactly implementing aros-sg's algorithm the same way he explains. I blit some "overlapping" blocks--sometimes the horizontal scroll blits to the "fill row" and sometimes the vertical scroll blits to the "fill column." For another, I don't set up the buffer the same way as in his source. His source suggests a buffer with an extra tile row for the top and one for the bottom. Both of my rows are at the bottom of the screen buffer--below the visible screen. (Done to make vertical split code simpler).

So I find myself checking for horizontal blits where the Y-step is uneven... then increment a counter each time this happens. When switching back to vertical blit--if the counter > 0, I "fix up" the row (if necessary)... if I was blitting up blocks into this row, replace the whole row with down blocks. Too complicated. Even when it "works" I end up with occasional artifacts, and some blocks out of place (every 16th or so).

What I want to do is break down the explanation of how to handle the "problem blocks" from xylimited-uk.html.
I'm trying to figure out if this is correct:

FIXING UP THE BUFFER AFTER...

RIGHT SCROLL:
------------------

HELPFUL REALIZATION:    DOWN BLOCKS WILL BE IN THE FILL ROW (AT BOTTOM--ONLY ROW NOT PARTIALLY SHOWING ON SCREEN)
WHEN:                   ON UNEVEN Y STEP/EVEN X STEP
COLUMN BLIT:            TOP BLOCK OF RIGHTMOST (NON-FILL) COLUMN WITH NORMAL (UP) BLOCK
ROW BLIT (FILL):        Y-STEP BLOCK (FROM DOWN SOURCE AS A FILL (DOWN) BLOCK)

LEFT SCROLL:
----------------

HELPFUL REALIZATION:    DOWN BLOCKS WILL BE IN THE FILL ROW (AT BOTTOM--ONLY ROW NOT PARTIALLY SHOWING ON SCREEN)
WHEN:                   ON UNEVEN Y STEP/EVEN X STEP
COLUMN BLIT:            TOP BLOCK OF FILL COLUMN WITH FILL (DOWN) BLOCK
ROW BLIT (FILL):        Y-STEP BLOCK (FROM UP SOURCE AS A NORMAL (UP) BLOCK)

DOWN SCROLL:
------------------
HELPFUL REALIZATION:    RIGHT BLOCKS WILL BE IN THE FILL COLUMN (AT LEFT--ONLY COLUMN NOT PARTIALLY SHOWING ON SCREEN)
WHEN:                   ON UNEVEN X STEP/EVEN Y STEP
ROW BLIT:               FIRST BLOCK OF FILL ROW WITH NORMAL (UP) BLOCK (NO PLANE SHIFT)
COLUMN BLIT (FILL):     X-STEP BLOCK FROM RIGHT SOURCE (PLANE SHIFTED) (IF LAST X-DIRECTION WAS RIGHT) OR LEFT SOURCE (IF LAST X-DIRECTION WAS LEFT)

UP SCROLL:
-------------
HELPFUL REALIZATION:    RIGHT BLOCKS WILL BE IN THE FILL COLUMN (AT LEFT--ONLY COLUMN NOT PARTIALLY SHOWING ON SCREEN)
WHEN:                   ON UNEVEN X STEP/EVEN Y STEP
ROW BLIT:               X-STEP BLOCK OF FILL ROW WITH NORMAL (UP) BLOCK (NO PLANE SHIFT)
COLUMN BLIT (FILL):     FIRST BLOCK FROM RIGHT SOURCE (PLANE SHIFTED) (IF LAST X-DIRECTION WAS RIGHT) OR LEFT SOURCE (IF LAST X-DIRECTION WAS LEFT)