[CSDb] - User Forums - Release id #150179 : Differential Scrolling

You are not logged in - nap

CSDb User Forums

Forums > CSDb Entries > Release id #150179 : Differential Scrolling

2016-08-28 23:19

Compyx

Registered: Jan 2005
Posts: 631

Release id #150179 : Differential Scrolling

Guess I'll start the discussion then,

I don't see any advantage of using this technique over traditional ways of scrolling, and I'll leave VSP out of the equation for now.

Seems to me that when using actual 'level' data using a tile based approach would be faster and a lot less memory hungry. Not to mention it would allow scrolling backwards, something this differential scrolling would have a hard time to do.

Also I don't get the 'full screen' update when scrolling left-to-right at one pixel at a time, seems incredibly wasteful.

Well, I said my piece, now for the actual coders ;)

... 19 posts hidden. Click here to view all posts....

2019-04-25 00:39

ChristopherJam

Registered: Aug 2004
Posts: 1409

Ah, so the speedcode would be generated from the chars and colours, but possibly with some initial processing when the level is loaded.

As for the char/colour alignment, I'm wondering if that could be fruitfully avoided by for each column
- initialising a colour->charcode mapping to [0..15]
- then reading through the character codes and overwriting mapping[charcode&15] with charcode
- then using mapping[colour] instead of colour when subsequently building the speedcode for the column.

That way the speedcode could make use of any charcodes that happen to line up with colour codes, but without constraining the artists to a set ratio.

2019-04-25 12:11

Oswald

Registered: Apr 2002
Posts: 5095

for this "one to many" problem I found lda ($00,x) adressing useful.

set up the zeropage so that each consecutive zp pointer points to a table.

like: $10 -> $1000, $12 -> $1100, etc.

then when you scan a column of colors simply load the (asl-ed) color value into the X register which will select you the table where you note down where that color was used. do an inc $xx,x aswell to increase the pointer for the next entry.

with this you can scan the column fast to find where same color / char was used.

2019-04-25 13:14

ChristopherJam

Registered: Aug 2004
Posts: 1409

Yup, I was using sta(zp,x) for the code generator for my d800 scroller; one pointer for each chunk of code, one chunk of code for each colour.

2019-04-26 03:37

TBH

Registered: Mar 2010
Posts: 21

I tried a different method to handle the one-to-many problem. Basically, an inelegant iteration through a constantly reducing search-space.

Below is the routine I wrote to handle it. It is in C64 Prg Studio format.

The new columns of chars and colours are output to the NewChars and NewCols tables respectively.

The tables of 25 chars and 25 colours are adjacent, and the routine treats them as a single 50 element table for the purpose of ignoring unrequired writes. A table of AND values (25 values of 255 and 25 values of 15) is used to avoid conditional logic for the char-colour value comparison. The table OldValues maintains the previous columns of chars and colours that are compared to find differences.

Basically, it walks through the list of values that are to be written to text or colour matrices, compares each with those proceeding it, marks matches as "handled" so they are not checked again, and copies new values into OldValues. If a matched colour is found, the index (25-49) is placed in the sequence of indices for that value.

The chars and colours are treated as a single unit as much as possible (hence the use of the ValueAnd table).

Where possible, char values will be co-opted for writes to colour memory. If none is found for a colour then a separate LDA for the color value is used.

The resulting values and row indices (text row indices are 0-24, colour rows are 25-49) are placed into the Scheduler table in the format:
Char/Colour value, Row Index [, Row Index...], Index_Sequence_Terminator [...], Value_Sequence_Terminator

For example:
Char_TopBrick, Row_0, Row_2, Terminator, Char_BottomBrick, Row_1, Row_3, Terminator, Colour_Red, Row_25, Row_26, Row_27, Row_28, Terminator, Terminator

Note that the Terminator value is 0, and indexing starts at 0. But in the Scheduler table, a row index of 0 will always be the first element in any row index sequence proceeding a value, so will never be tested as a potential termination by the Code Generator.

The Code Generator (not listed here) sequentially reads the Scheduler table (which contains the most recent set of formatted column information), and constructs code using opcode constants, the Scheduler's values and addresses from lookup tables retrieved using the Scheduler's row indices.

; ----------
NewValues
NewChrs bytes cRows                 ; 25
NewCols bytes cRows

OldValues bytes 255*cCombinedRows   ; 50
ValueAnd bytes 255*cRows, 15*cRows

Scheduler bytes cTotalUniqueRW      ; 92
cRowCnt = cCombinedRows - 1

ScanValues
         ; Init Scheduler address
         lda #<Scheduler
         sta StoreToScheduler + 1
         lda #>Scheduler
         sta StoreToScheduler + 2

         ldx #0
@Loop    lda NewValues,X
         beq @Next                  ; Marked as handled, so skip
         cmp OldValues,X
         beq @Next                  ; No difference, so skip

         ; Add to scheduler
         sta OldValues,X
         jsr StoreToScheduler       ; Add the Load Value to Scheduler

         ; Search for duplicate Char and Colour Load Values
         txa
         tay
         jmp @Index                 ; Store index of New Value before search

@SLoop   lda NewValues,Y
         beq @Cont                  ; Marked as handled, so skip
         cmp OldValues,Y
         beq @Cont                  ; No difference, so skip
                  
         ; Compare value with original
         and ValueAnd,Y
         cmp NewValues,X
         bne @Cont
         
         ; Mark NewValue as having been handled
         lda NewValues,Y
         sta OldValues,Y
         lda #0
         sta NewValues,Y

         ; Add the Index Value to Scheduler
         tya
@Index   jsr StoreToScheduler       

@Cont    iny
         cpy #cCombinedRows
         bne @SLoop

         ; Add Index Terminator to Scheduler
         lda #0
         jsr StoreToScheduler

@Next    inx
         cpx #cCombinedRows
         bne @Loop

         ; Add Value Terminator to Scheduler
         lda #0
         jmp StoreToScheduler

StoreToScheduler
@SMC     sta $FFFF
         inc @SMC + 1
         bne @Exit
         inc @SMC + 2
@Exit    rts

2019-04-26 07:05

Oswald

Registered: Apr 2002
Posts: 5095

that seems super complicated. this is the loop with (,x)

lda colorvalues,y
asl
tax ;can be just lax with pre asl
tya
sta (occurancetables,x)
inc occurancecounter,x
iny
cpy #25
bne -

in the end each table belongs to a color value, each has a counter that says that color needs to be sta'-ed how many times and each entry in the table is the Y value the color was seen at.

2019-05-03 05:25

TBH

Registered: Mar 2010
Posts: 21

Quote:

that seems super complicated. this is the loop with (,x)

It does seem complicated, but I haven't found a better solution. It's doing a lot in there:
- selecting only chars and colours that need to be written to the column
- combining char and colour LDA if lower nybbles match

I couldn't find a way to apply the ZP vector bucket method used for chars. It needs either 256 vectors and tables to handle all potential 256 chars (plus another 16 for colours) or else reuse a limited amount of vectors, which means loops and vector rewrites.

So I simplified the differential routine by removing the schedule table and embedded the code generation in its place.

This works surprisingly well. With the test data (in my earlier post) used, a full-screen differential screen shift for both char and colour is completed in less than 2800 CPU cycles and the maximum code length is about 1800 bytes.

The code generation for the columns (using the test data) never exceeds 3500 cycles and I think that speed can be optimised by a further 50%. For a 1px/frame scroll the code generation can be split across the 7 fine-scroll frames (about 500 CPU cycles/frame before optimisation).

Even without splitting the code generation across frames, it significantly lessens the CPU load for full-colour scrolling, and removes the need for a second screen buffer.

One thing though - if there is a practical way to extend the 16-colour sort (zp,X) method to all characters then could someone enlighten me? I might have overlooked some blindingly obvious method.

2019-05-03 14:01

Oswald

Registered: Apr 2002
Posts: 5095

one way would be doing 2 pass, skipping half of the values with bmi bpl, and forbidding use of chars #$00 and #$80 to avoid $00/$01. + and #$7f for the > $7f bytes.

2019-05-03 14:04

Oswald

Registered: Apr 2002
Posts: 5095

can go as far as storing the map twice, so the BMI BPL AND #$7f and the ASL can be all skipped. Because the 2 versions have the char values already asl-ed and stored twice for =<$7f and >=$80 values. Going this far the differential checking could be also precomputed.

...aand one more edit: instead of char values and 2 maps, 16bit pointers could be stored that are pointing to the occurence tables directly + the precomputed differential info stored somehow.

...and one more: the whole map could be just info on how to generate those speedcodes.

2019-05-04 00:50

TBH

Registered: Mar 2010
Posts: 21

Thanks, Oswald. Those comments clarify a few things.

It now seems obvious there are two ways to approach this:

1) Just-In-Time:
Low-friction. Generate a chunk of speedcode from raw char and colour values for each column prior to the text/colour matrix shift. It doesn't care how the screen map is stored.

This is what my code currently does.

Regarding 2-pass sort, since this would prevent a program using zeropage for other things, then perhaps half of ZP could be made available by using 4 passes, with BMI and BVS to test bits 7 and 6.

2) Precalculate speedcode info:
Use the screen map data to precalculate info on how to generate the speedcode.

This info would either replace the screen map statically (ie done before or during compilation/assembly), probably only if it didn't require more RAM than the stored map (compressed/tiles/etc). Or else it could be done at runtime before scrolling begins and temporarily stored in spare RAM until no longer needed (eg generate this info once at the start of each game level).

2019-05-09 17:02

TBH

Registered: Mar 2010
Posts: 21

This little coding exercise has turned out quite interesting.

I realised that much of the task was simply one of grouping, not sorting, so tried a variation of the previously mentioned zp vector and table method: generate a linked list of indexes for each set of matching values.

The snippet of code below is for the linked-list routine. It groups chars and colours together for use by the code generation routine.

The routine examines each member of the combined char and colour column once only, discards unchanging chars and colours , inserts a terminator or index in a 256-byte master table, and updates an 8-bit link in another 50-byte link table at the index of the char or colour.

The code generation loop just rolls backward through the links, fetches the index for use in a CPU index register to access the various tables and spits out code in the form LDA #First_Occurence_Of_Value : STA $First_Row_In_List : STA $Second_Row_In_List, etc..

Even unoptimised, the CPU time to do this is negligible. The grouping routine is about half a raster per char and colour, and a little bit over half a raster line to output each STA for those chars and colours. The test data averages around 400 char and colour changes onscreen, and uses about 40 rasters to examine and generate a full column-worth of code (keep in mind this work can be split across non-shift frames), and 50 raster lines to execute the shift-code, which is effectively a full screen shift (40x25 chars and colours).

GroupValues
         ldx #255
         stx GroupCount
         ldx #49

@Loop1   lda NewValues,X   ; Get a value
         cmp OldValues,X   ; Compare with old values
         beq @Next
         sta OldValues,X   ; Modify OldValues

         tay
         lda GroupLinkPtr,Y         ; 
         sta GroupLinks,X           ; Terminator or index
         bpl @Another               ; Has it been encountered before? No = Bit7
         
         ; store Current rX Index to GroupLinkStart. This is copied to the next group member's link table
@New     inc GroupCount
         ldy GroupCount
         txa
         sta GroupLinkStart,Y
         ldy NewValues,X

         ; Change Link at LinkPtr then put new index to LinkPtr
@Another txa
         sta GroupLinkPtr,Y

@Next    dex
         bpl @Loop1

This piece of code generates the shift-code for the column (some of the support stuff wrapping it has been removed for clarity):

         ldx #0
         stx zCodePtr

@Loop2   ldy GroupCount
         bmi @Cleanup               ; No new chars
         dec GroupCount
                  
         ldx GroupLinkStart,Y
         ldy NewValues,X
         ldx GroupLinkPtr,Y         ; Most recent Link Index found for that group

         lda #255
         sta GroupLinkPtr,Y         ; Cleanup as we go

         ; --------------------
         ; Write lda #nn
         ;
         ldy zCodePtr

         lda #cLDA_imm
         sta (zVecCode),Y
         iny
         lda NewValues,X
         sta (zVecCode),Y
         iny
         sty zCodePtr

         ;TestEndOfBuf prior to each STA 
@Loop2I  ldy zCodePtr
         lda zCodeEOB + 1
         bne @Cont         ; HI > 0, so skip rest of test
         cpy zCodeEOB
         bmi @Cont         ; LO < BufEnd, so exit (eg $4000 < $40FF)
@Reset   jsr CodeBufReset
         ldy zCodePtr

         ; --------------------
         ; Write sta $nnnn
         ;
@Cont    lda #cSTA_x
         sta (zVecCode),Y
         iny
         lda RowLO,X
         sta (zVecCode),Y
         iny
         lda RowHI,X
         sta (zVecCode),Y
         iny
         sty zCodePtr

         lda GroupLinks,X  ; Get index of next group element 
         tax
         bpl @Loop2I
         jmp @Loop2

         ; Cleanup
@Cleanup ldy zCodePtr
         lda #cINX
         sta (zVecCode),Y
         iny

         lda #cRTS
         sta (zVecCode),Y
         sty zCodePtr

Previous - 1 | 2 | 3 - Next

Refresh

Subscribe to this thread: