[CSDb] - User Forums

You are not logged in - nap

CSDb User Forums

Forums > C64 Coding > Sorting

2007-10-08 16:08

Oswald

Registered: Apr 2002
Posts: 5017

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 :)

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

2020-05-09 09:11

Oswald

Registered: Apr 2002
Posts: 5017

ldy sorted_indexz+1
lda object_yl,y

why not use lda (),y for this ? you can do the indirection in one step: zp pointers are the sorted indexes, and Y points to Y coordinate attribute within virtual sprite data

2020-05-09 17:53

mhindsbo
Account closed

Registered: Dec 2014
Posts: 50

Good question @Oswald that sent me on a spin incl. considering if I would use (zp,x) instead. I had not really contemplated using the index as an index of 16 bit addresses, rather than a simple list of 8 bit numbers.

However unless I misunderstand you the resulting code including the swapping of indexes would become:

@loop           sty current_pos                         ; position in the index 
                lda (sorted_indexz),y                   ; y coordinate of object  
                ldx sorted_indexz,y                     ; object number/index 
                stx current_index
                
@in_right_place cmp (sorted_indexz-2),y                 ; compare to y coordinate of next object in index                      
                bcs @next_position
                ldx sorted_indexz-2,y                   ; move compared objects index to the right sorted index list  
                stx sorted_indexz,y
                dey
                dey 
                
@compare        cmp (sorted_indexz-2),y                 
                bcs @found_place 
                ldx sorted_indexz-2,y
                stx sorted_indexz,y
                            
                dey
                dey 
                bne @compare 

@found_place    ldx current_index 
                stx sorted_indexz,y

@next_position  ldy current_pos
                iny
                iny
                cpy #2*NUM_SPR_OBJ
                bcc @loop

which is actually a couple of cycle longer per iteration and the index will be twice as long in zp. Also when I later populate the sprite IRQ's I will have two dey's to iterate through the indexes (small extra cost, but still).

It might be worth noting that all my (virtual) sprite data sits in array's of similar properties. I.e. y1,y2,y3, ... x1,x2,x3, ... and not y1,x1 ... y2,x2. I access all values using the index of the object and not the index of the attribute.

I could have missed something. It is early on a Saturday and I have not had enough coffee yet :-)

PS: I did spot a possible optimization more that I will take a look at now.

2020-05-10 12:52

Oswald

Registered: Apr 2002
Posts: 5017

I mean to use that kind of indirection every time when you want to read Y coo.

so instead of

ldy sorted_virtual_sprite_pointers
lda ycoordinates,y
ldy sorted.....+1
cmp ycoordinsates,y

lda (sortedpointers),y
cmp (sortedpointers+2),y

2020-05-10 18:50

mhindsbo
Account closed

Registered: Dec 2014
Posts: 50

Yes that is what I did above. The load and cmp of y coordinates is faster, but the sorting of the indexes becomes slower. And with the double dey all in all the original implementation is faster (unless I missed something).

2020-05-11 11:13

Oswald

Registered: Apr 2002
Posts: 5017

I see, too bad