Sorting numbers - quickest way?

[Cybergoth]

Hi there!

 

manuel, coming from atari 800 with 4 players instead of 2600 2... i am playing around with this kind of sprite engine for couple of years... is your approach suitable for 4 hardware sprites as well or is it optimised for 2600 only?

 

Hm... rather *compromised* than optimized

 

Well, generally it should work with 4 hardware sprites as well. A lot better actually, as you wouldn't run into the "3 sprites worst case" scenario we've been discussing for the 2600 right now. I'd let it run for 4 iterations of the Bubble Sort each frame.

 

With more RAM you can optmize the sorting by using index values. This'll immensly speed it up. After the 4 iterations you then need to swap all data only once according to the resulting indexes. (Maybe the 800 has even enough horsepower to handle quick repositionings via indexing, so you might even get away completely without swapping any data.)

 

Another thing that may change on the 800 is the "magic" value in the line

SBC #$03

This value adjusts the compare because the VCS needs 2 lines to reposition and because I ignore the carry in the subtractions (2+1).

 

Greetings,

Manuel

[Heaven/TQA]

i'll play around with my code...

 

 

here is the actual sorting version:

 

;"Dragon Breed" sorting routine
; www.student.oulu.fi/~loorni/covert/rants/sprite.htm

;sprite sorter
sprite_sort  lda	#1  ;by default all sprites visible
 ldx #max_sprites-1
sort00	sta sortsprvisible,x-
 sta line,x
 bpl sort00
 ldx #0
sortloop ldy sortorder+1,x
 lda spry,y
 ldy	sortorder,x
 cmp spry,y
 bcs sortskip
 stx sortreload+1
sortswap lda sortorder+1,x
 sta sortorder,x
 sta temp2
 tya
 sta	sortorder+1,x
;  lda temp2  	;really necessary?
; sty sortorder+1,x not available on atari just c64
 cpx	#0
 beq	sortreload
 dex
 ldy sortorder+1,x
 lda	spry,y
 ldy sortorder,x
 cmp spry,y
 bcc sortswap
sortreload  ldx #0
sortskip  inx
 cpx #max_sprites-1
 bcc sortloop
;now copy sprite variables to the sorted table
;sprites must be rejected who want to be on the same scanline

;copy the 1st 4 virtual sprites as they are accepted anyway to the
;4 hardware sprites
 ldx #0
 ldy sortorder
 lda spry,y
 sta sortspry
 lda sprx,y
 sta sortsprx
 lda sprc,y
 sta sortsprc
 inx
 ldy sortorder,x
 lda spry,y
 sta sortspry,x
 lda sprx,y
 sta sortsprx,x
 lda sprc,y
 sta sortsprc,x
 inx
 ldy sortorder,x
 lda spry,y
 sta sortspry,x
 lda sprx,y
 sta sortsprx,x
 lda sprc,y
 sta sortsprc,x
 inx
 ldy sortorder,x
 lda spry,y
 sta sortspry,x
 lda sprx,y
 sta sortsprx,x
 lda sprc,y
 sta sortsprc,x
 inx
sort3  ldy	sortorder,x
 lda spry,y
 sta sortspry,x
 sub spry-4,y	;actual position - 8 pixel (y-size of sprite)
 cmp #8
 bcs sort4  ;reject	if less than 8 scanlines ypos=0=invisible	
 lda #0  	;move off the screen
 sta sortsprvisible,x
 sta line,x
sort4  lda sprx,y
sort6  sta sortsprx,x
 lda sprc,y
 sta sortsprc,x
 inx
 cpx	#max_sprites
 bcc	sort3
 rts

[Heaven/TQA]

and as most of you are not familiar with atari800win or 800 anyway here is a screenshot:

 

the white rasterlines are indivators where a so called DLI (Display List Interrupt) is set. so at this screen position we are doing a complete repositioning of the 4 hardware sprites...

 

the players are filled with chars "A"... to make them visible...

 

these DLIs are set dynamicly each VBL based on the sorted y-sprite list...

 

the only issue which is not implemented yet into my engine is the fact that rejected sprites (5th,6th,... sprite on the same scanline or overlapping) are really rejected so not visible at all until they can be displayed without any overlapping... so no inteligent flicker algorithm working yet... and that's my search for the holy grail...