Log inRegister an accountBrowse CSDbHelp & documentationFacts & StatisticsThe forumsAvailable RSS-feeds on CSDbSupport CSDb Commodore 64 Scene Database
You are not logged in 
CSDb User Forums


Forums > C64 Coding > Sorting
2007-10-08 18:08
Oswald

Registered: Apr 2002
Posts: 4065
Sorting

are sorters really so slow in games? :) I have made my unrolled version for my theoretical game (;), and it takes 132 rlines to sort 32 numbers o_O worst case is ~200 lines. tho when its the case of 4 numbers have to be swapped only it does the job in ~10 lines. wastes a lot of memory but I like it :)
 
... 137 posts hidden. Click here to view all posts....
 
2017-09-13 09:16
Color Bar

Registered: Oct 2012
Posts: 130
Great! I still have to study your post in detail, but maybe another 64 cycles gain be gained by adding 3 NOPs before the first sprite in the bucket, like this:
.bucketK
bcc .nextBucket
lda #sprite_index8
pha
...
nop
nop
nop
lda #sprite_index1
pha
sty .bucketK+1


Then the TAY can be removed from the fill code:
ldy .bucketK+1
lda newBranchValue,y
sta .bucketK+1
txa
sta .bucketK,y

and the branch value table changes to:
newBranchValue
 BYTE 0 x x 0 x x 3 x x 6 x x 9 x x 12 x x 15 x x 18 x x 21 x x x x x 27 x

Worst case for the phase 2 code is still 948 cycles, I think.
2017-09-13 09:46
ChristopherJam

Registered: Aug 2004
Posts: 641
Ah, so you're always storing 3 bytes earlier than the previous branch target?

I like it, but I'm not sure if that works for the very first sprite inserted into that bucket, unless you have the branch starting out by landing on the sty .bucketK+1

..which would then cost you an extra four cycles per empty bucket.
2017-09-13 09:53
Color Bar

Registered: Oct 2012
Posts: 130
Quoting ChristopherJam
Got a new record now, I think.

We can pack 221 addresses into a 222 byte table by using the high byte of each address as the low byte of the next address.

Clever idea!

I am not familiar with this notation
for i in 0..73:
    .byt 64+(i%74)*(1+i//74*24)%74)

What do i%74 and i//74 mean?
2017-09-13 10:01
ChristopherJam

Registered: Aug 2004
Posts: 641
Thanks!

Mod and divide (TBH I should have dropped from // back to / when I switched from python to pseudo asm). Oh, and that loop should have been to 74*3

Really, better expressed as

for i in 0..73:
    .byt 64+(i*1)%74

for i in 0..73:
    .byt 64+(i*25)%74

for i in 0..73:
    .byt 64+(i*49)%74
2017-09-13 10:10
Color Bar

Registered: Oct 2012
Posts: 130
Quote: Ah, so you're always storing 3 bytes earlier than the previous branch target?

I like it, but I'm not sure if that works for the very first sprite inserted into that bucket, unless you have the branch starting out by landing on the sty .bucketK+1

..which would then cost you an extra four cycles per empty bucket.


Yes, you are right.
2017-09-13 12:18
Color Bar

Registered: Oct 2012
Posts: 130
Quoting ChristopherJam


The bucket emptying code remains the same as in Color Bar's original:
.bucketK ;32 bytes
    bcc .nextBucket        ;Branches always: decrease this value by 3 with selfmodifying code in phase 1 for every new sprite in the bucket.
    !byt 0,0,0
    lda #sprite_index   ; repeat lda/pha eight times
    pha
...
    sty .bucketK+1


!byt 0,0,0 could be replaced by LDA #value + PHA, i.e., allow a maximum of 9 sprites per bucket, but I guess it doesn't really matter.
2017-09-14 16:12
ChristopherJam

Registered: Aug 2004
Posts: 641
The Human Code Machine, thanks for that codebase link. Must admit, I didn't find that area when I added the flagged bucket sort to the maths and algorithms section. Might need to add some crosslinks..

FWIW though, looks like that one has the same worst case as the one Oswald referenced in the opening remark to this thread. (32*31/2)=496 swaps, 26 cycles per swap, 496*26/63=204 raster lines.
2017-09-14 16:19
Frantic

Registered: Mar 2003
Posts: 1307
I added some crosslinks @ codebase to make people aware about this partial overlap in contents in the two different sections.

Preferably generic sorting algorithms should be placed in the maths and algorithms section, and sorting tailored specifically towards fast sorting of sprites/multiplexing could be kept on the sprites page, if someone feels like cleaning this up.
2017-09-15 05:47
ChristopherJam

Registered: Aug 2004
Posts: 641
Thanks Frantic, I'll move my post.
2017-09-16 09:31
Color Bar

Registered: Oct 2012
Posts: 130
Quoting ChristopherJam

    ;code to fill out bucketK.   24 bytes, 36 cycles
fillK
    ldy .bucketK+1
    lda newBranchValue,y
    sta .bucketK+1         ; 12
    tay
    txa
    sta .bucketK+3,y       ;  9

    dex
    lda Yvalues,x
    sta *+4
    jmp ($xxxx)            ; 15

    ; 36*32 =  1152 cycle, 36 per actor


I think another 2 cycles per actor can be gained by using A as the actor counter:
ldy .bucketK+1
ldx newBranchValue,y
stx .bucketK+1
sta .bucketK+3,x
sbc #$01
.start
tax
ldy Yvalues,x
sty *+4
jmp ($xxxx)

Initialize with SEC, LDA #$1f, JMP .start

Total time: 220*3+43*32 = 2036 cycles or 32.3 rasters!
Previous - 1 | ... | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 - Next
RefreshSubscribe to this thread:

You need to be logged in to post in the forum.

Search the forum:
Search   for   in  
All times are CET.
Search CSDb
Advanced
Users Online
Unkle K/Reset Magazi..
Stein/Prosonix/Offence
j0x
Fabs/Hokuto Force
lft
GI-Joe/MYD
Claus_2015
Guests online: 43
Top Demos
1 Uncensored  (9.7)
2 Edge of Disgrace  (9.7)
3 Coma Light 13  (9.6)
4 Quad Core 100%  (9.6)
5 The Shores of Reflec..  (9.6)
6 Lunatico  (9.6)
7 Comaland 100%  (9.5)
8 Incoherent Nightmare  (9.5)
9 Wonderland XII  (9.5)
10 Comaland  (9.5)
Top onefile Demos
1 Pandemoniac Part 2 o..  (9.6)
2 Field Sort  (9.6)
3 Dawnfall V1.1  (9.5)
4 Daah, Those Acid Pil..  (9.5)
5 Treu Love [reu]  (9.4)
6 Dawnfall  (9.2)
7 Veterans of Style  (9.2)
8 KAOS 64  (9.2)
9 One-Der  (9.2)
10 Game of Thrones [2sid]  (9.2)
Top Groups
1 Blazon  (9.5)
2 Booze Design  (9.4)
3 Censor Design  (9.4)
4 Oxyron  (9.4)
5 Crest  (9.3)
Top Crackers
1 Mr. Z  (9.9)
2 Mitch  (9.8)
3 Mr Zero Page  (9.8)
4 Snacky  (9.8)
5 MWS  (9.8)

Home - Disclaimer
Copyright © No Name 2001-2017
Page generated in: 0.277 sec.