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


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

Registered: Apr 2002
Posts: 5007
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 :)
 
... 193 posts hidden. Click here to view all posts....
 
2017-09-24 16:22
Rastah Bar

Registered: Oct 2012
Posts: 336
See posts #91 and #101. It is about 3*k+43*n.
For lft's Field Sort (post #126) it is 2*k+55*n.
2017-09-24 23:25
Trash

Registered: Jan 2002
Posts: 122
I have made a mistake in my earlier posting about how to reduce the accuracy of the sorter...

Imagine you have 32 actors you want to sort and that K is 200, what you need is to reduce K so it holds the upper 5 bits (%11111 = 31).

The result will be a fast sorter that is inaccurate but accurate enough for sprite sorting.

64tass-style:

; YSortPositions contains the reduced spritepositions in Y
NUMBEROFBYTESTOBESORTED = 32
; With tables on zero-page
; 2 + ((3 + 9 + 6 + 19) * NUMBEROFBYTESTOBESORTED) - 3 + 2 + 3 + 12 = 1200

; With tables not on zero-page
; 2 + ((4 + 11 + 8 + 22) * NUMBEROFBYTESTOBESORTED) - 4 + 2 + 3 + 12 = 1455

DoSort
	lda #0				;  2
.for i = 0, i < NUMBEROFBYTESTOBESORTED, i = i + 1
	sta SortTable + i		;  4 /  3
.next
.for i = 0, i < NUMBEROFBYTESTOBESORTED, i = i + 1
	ldx YSortPositions + i		;  4 /  3
	inc YSortPositions,x		;  7 /  6
					;--------
					; 11 /  9
.next
	clc				;  2
.for i = 0, i < NUMBEROFBYTESTOBESORTED, i = i + 1
	sta SortOrder + i		;  4 /  3
	.if i < (NUMBEROFBYTESTOBESORTED - 1)
		adc SortTable + i	;  4 /  3
	.fi
					;--------
					;  8 / 6
.next
.for i = 0, i < NUMBEROFBYTESTOBESORTED, i = i + 1
	ldx ySortPos + i		;  4 /  3
	ldy SortOrder,x			;  4
	inc SortOrder,x			;  7 /  6
	lda #i				;  2
	sta Sorted,y			;  5 /  4
					;--------
					; 22 / 19
.next
	rts				; 12 (jsr + rts)
2017-09-25 05:02
lft

Registered: Jul 2007
Posts: 369
Typo on line 4, should increment at SortTable,x.

The problem with this approach is that you have to compute the upper 5 bits of the y-position somehow, and that will take time. It can be done during sorting, at the cost of an additional 2 cycles per actor, like this:

DoSort
    lda #0
.for i = 0, i < NUMBEROFBYTESTOBESORTED, i = i + 1
    sta SortTable + 8*i
.next
    lda #$f8
.for i = 0, i < NUMBEROFBYTESTOBESORTED, i = i + 1
    ldx YSortPositions + i
    sbx #0
    inc SortTable,x
.next
...


But I'm not convinced that the quality of this "rough sorting" is comparable with the real thing. Consider for instance the case where all actors are positioned 3 rasterlines apart. Whenever a hardware sprite becomes free, the multiplexer must take the next sprite according to the true sorting order, otherwise all sprite units will be busy eight actors later, so an actor must be dropped.

Nevertheless, it is nice to know that this option is available, in situations where the sprites aren't packed too closely but rastertime is tight.
2017-09-25 06:32
Trash

Registered: Jan 2002
Posts: 122
Quoting lft
Typo on line 4, should increment at SortTable,x.



Thanks, missed that..


Quoting lft
The problem with this approach is that you have to compute the upper 5 bits of the y-position somehow, and that will take time. It can be done during sorting, at the cost of an additional 2 cycles per actor, like this:


Or it could be done in a precalculated table, whatever fits your needs..

Quoting lft
Nevertheless, it is nice to know that this option is available, in situations where the sprites aren't packed too closely but rastertime is tight.


Yes, but if you have small amounts of rastertime you either should pre-sort your data or have data that fits with a bubblesort like the one THCM implemented...

I am (like you) not convinced that this sorter is the best for all use-cases but for some it's certainly the best option.
2017-09-25 08:13
The Human Code Machine

Registered: Sep 2005
Posts: 109
In most game scenarios an optimized bubble sort with special routines to add or remove an actor should be faster. In my example the sorter takes ~20 raster lines most of the time with sprites moving up and down. For a game, accurate sorting is important, to get an optimal multiplexing result with reusing a free sprite slot as soon as possible. (as lft said above)
2017-09-25 20:35
Digger

Registered: Mar 2005
Posts: 420
btw. Nice tool for visualising various sorting algos, Counting Sort included: https://visualgo.net/en/sorting
2017-09-25 20:57
ChristopherJam

Registered: Aug 2004
Posts: 1359
Well, an unrolled bubble iteration should only take about 8 lines for 32 actors if there's no change, 10ish if there are four or five swaps.

I do like Falco Paul's suggestion of kicking off an Ocean Sort but aborting and switching to bucket sort (or some other constant time algorithm) if the number of swaps passes a certain threshold.
(cf http://www.codebase64.org/doku.php?id=base:sprite_multiplexer_s.. )

As for making lft's suggestion a little more memory flexible, I'm wondering if writing an RTS into the increment field could be cost effective?
2017-09-26 04:52
lft

Registered: Jul 2007
Posts: 369
I have thought of a different way to relax a memory constraint. Consider this variant of the bucket-emptying routine:

        sty     endptr+1
        lax     ylink,y
        pha
        lda     actorlink,x
        sta     ylink,y
        bpl     endptr

        sta     inyfield,y
endptr  jmp     inyfield


The worst-case execution time is the same, while the case of multiple actors in the same bucket is now slower. But now the location of the link table is unconstrained.
2017-09-26 04:59
lft

Registered: Jul 2007
Posts: 369
Quoting ChristopherJam
I'm wondering if writing an RTS into the increment field could be cost effective?


That would imply a JSR out of the increment field, right? That still means you have to put the bucket-emptying routine in four different, fixed places. Meanwhile the execution time increases by a rasterline.

Perhaps you meant the other way around, JSR into the increment field and RTS to the bucket-emptying routine. That would indeed make the memory layout more flexible, but at the cost of three rasterlines.

(Edit: I see now that I misread your post. Of course you mean the second thing.)
2017-09-26 06:54
lft

Registered: Jul 2007
Posts: 369
(removed)
Previous - 1 | ... | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 - 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
Frostbyte/Artline De..
icon/The Silents, Sp..
Matt
Laurent
t0m3000/ibex-crew
Guests online: 310
Top Demos
1 Next Level  (9.8)
2 Mojo  (9.7)
3 Coma Light 13  (9.7)
4 Edge of Disgrace  (9.6)
5 No Bounds  (9.6)
6 Comaland 100%  (9.6)
7 Uncensored  (9.6)
8 The Ghost  (9.6)
9 Wonderland XIV  (9.6)
10 Bromance  (9.6)
Top onefile Demos
1 Party Elk 2  (9.7)
2 Cubic Dream  (9.6)
3 Copper Booze  (9.5)
4 Rainbow Connection  (9.5)
5 TRSAC, Gabber & Pebe..  (9.5)
6 Onscreen 5k  (9.5)
7 Dawnfall V1.1  (9.5)
8 Quadrants  (9.5)
9 Daah, Those Acid Pil..  (9.5)
10 Birth of a Flower  (9.5)
Top Groups
1 Booze Design  (9.3)
2 Nostalgia  (9.3)
3 Oxyron  (9.3)
4 Censor Design  (9.3)
5 Crest  (9.3)
Top Logo Graphicians
1 Sander  (10)
2 Facet  (9.7)
3 Mermaid  (9.4)
4 Pal  (9.4)
5 Shine  (9.3)

Home - Disclaimer
Copyright © No Name 2001-2024
Page generated in: 0.042 sec.