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-20 17:42
Rastah Bar

Registered: Oct 2012
Posts: 336
Quote: Yes, nice work! This will take some investigating to unravel.
SHX $FE00,Y
^ is basically stx $fe00,y on account of the mask being $fe+1, yes?


Yes, check out this document (pages 38 and 41):
No More Secrets v0.91
2017-09-20 17:47
chatGPZ

Registered: Dec 2001
Posts: 11088
lft: now it would be very cool if you could expand this routine to handle excess sprites in a way that they will be displayed on alternating frames ("interlaced") - then it would work perfectly fine for a game (MUCH better than sprites disappearing)
2017-09-20 21:13
ChristopherJam

Registered: Aug 2004
Posts: 1359
Dear lords. So the n-actors snippets leading up to $fe00 insert each actor ID in to a linked list with the head at $aa00+yposition, and the 'next' pointers are at $10+actorID, and also replaces the INY at $fe00+yposition with a JMP to a bucket emptying routine.

Here's a sample snippet:
.C:fb52  A4 90       LDY $90+0     ; Y coordinate of actor 0
.C:fb54  9E 00 FE    SHX $FE00,Y   ; this is effectively STX $fe00,y
.C:fb57  B9 00 AA    LDA $AA00,Y   ; bucket head
.C:fb5a  85 10       STA $10+0     ; next pointer for actor 0
.C:fb5c  A9 00       LDA #$00      ; actor id 0
.C:fb5e  99 00 AA    STA $AA00,Y


The INYs that fill $fe00 to $feff increment Y through all the potential bucket indices, jumping off to a bucket emptying routine wherever an INY has been replaced with a JMP

There are four routines at 4c4c, 4cc8, c84c and c8c8 to handle each of the cases where zero to two of the next two buckets are also nonempty.

The bucket emptying routine takes advantage of the list heads being stored in page $aa to reuse the $aa as a TAX instruction when looping over a bucket that contains more than one actor, and the lists are terminated with $c8, which is both negative and doubles as the INY that needs to be written back to $fexx to clear the bucket for the next frame. (it's also written to $aaxx, just like the flagged bucket sort on codebase).

Each bucket emptying routine returns to the scene of the crime after writing the INY back, which bumps Y the value needed for the next bucket. Hence, the four bucket emptying routines are in fact identical; here's a sample:
.C:4c4c  8C 5E 4C    STY $4C5E     ; patch return address
.C:4c4f  BF 00 AA    LAX $AA00,Y   ; fetch bucket head
.C:4c52  48          PHA
.C:4c53  B5 10       LDA $10,X     ; read 'next' pointer.
.C:4c55  10 FA       BPL $4C51     ; Actor ids are positive, INY is not
.C:4c57  99 00 FE    STA $FE00,Y   ; restore INY
.C:4c5a  99 00 AA    STA $AA00,Y   ; empty linked list
.C:4c5d  4C 7E FE    JMP $FE7E


I think that just about covers it. Lft, that's a mighty fine piece of work.
2017-09-20 21:24
ChristopherJam

Registered: Aug 2004
Posts: 1359
Color Bar, thanks for the No More Secrets rec; I wasn't familiar with that one.
2017-09-20 22:57
Trash

Registered: Jan 2002
Posts: 122
The sorting algorithm implemented by HCL is actually called Counting Sort (I just found that out..) and it is considered to be O(n).

It should be competive to the discussed code both in size and speed.
2017-09-20 23:03
Cruzer

Registered: Dec 2001
Posts: 1048
Hilariously constrained addresses indeed. :) And my respect for lft just grew even higher.

Quoting Groepaz
lft: now it would be very cool if you could expand this routine to handle excess sprites in a way that they will be displayed on alternating frames ("interlaced") - then it would work perfectly fine for a game (MUCH better than sprites disappearing)
I would like no interlacing or disappearing sprites even better. In the ideal world, the routine moving the sprites around should avoid situations with >8 sprites on the same line. And the multiplexor should of course strive for being able to display any situation with <=8 sprites per line.
2017-09-20 23:54
chatGPZ

Registered: Dec 2001
Posts: 11088
thats not really useful for a game - in a demo of course that is always preferred - but in a game it would be SO much better if you could move around a large amount of objects without having to care about multiplexer limitations in the game logic. (if you look at gameboy or NES games for example - thats how a lot of them work)
2017-09-21 03:27
ChristopherJam

Registered: Aug 2004
Posts: 1359
…or then there was Alien Syndrome, where you could never have more than one alien on any given raster 😂
2017-09-21 05:28
lft

Registered: Jul 2007
Posts: 369
Quoting Trash
The sorting algorithm implemented by HCL is actually called Counting Sort (I just found that out..) and it is considered to be O(n).

It should be competive to the discussed code both in size and speed.


Thanks for the link! That does indeed seem useful.

Here is a straighforward implementation:

for each actor i
   ldx ypos+i
   inc count,x

   lda #0
   clc
for each count k
   sta start+k
   adc count+k

for each actor i
   ldx ypos+i
   ldy start,x
   lda #i
   sta output,y
   inc start,x
   lda #0
   sta count,x


Total number of cycles is 10*i + 4 + 8*k + 28*i, so for our benchmark case with 32 actors and 220 y-positions that would be 2980 cycles, or 47.3 rasterlines. So the above implementation is not competitive.

So I suppose the game is on to try to improve it!
2017-09-21 06:21
Trash

Registered: Jan 2002
Posts: 122
Quoting lft
So I suppose the game is on to try to improve it!


Try losing precision on K by the right amount and in the right way and it will improve without losing to much accuracy....
Previous - 1 | ... | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | ... | 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
JackAsser/Booze Design
AMB/Level 64
kbs/Pht/Lxt
Airwolf/F4CG
curtcool
iAN CooG/HVSC
Guests online: 314
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 Graphicians
1 Sulevi  (10)
2 Mirage  (9.8)
3 Lobo  (9.7)
4 Mikael  (9.7)
5 Archmage  (9.7)

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