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

Registered: Apr 2002
Posts: 4058

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 :)
... 59 posts hidden. Click here to view all posts....
2007-10-09 16:24

Registered: Apr 2002
Posts: 4058
btw some inspiration on the attack waves, and enemies: http://youtube.com/watch?v=Aj23K8Ri68E&mode=related&search= a lot if this could be done on a c64 imho.
2007-10-09 16:47

Registered: Dec 2001
Posts: 8120
an ikaruga-like shooter would be generally a cool idea :)
2007-10-10 11:00

Registered: Aug 2004
Posts: 620
Yeah, the movement is largely horizontal, with a few loop-the-loops, and that "X of death" formation the reviewer complained of. The times I drop a formation in from above or raise it from below it can struggle a little if there's already a dense formation it has to cross over.

A danmaku shooter like Ikaruga would indeed be awesome, but also a serious challenge to implement!
2007-10-10 13:37

Registered: Dec 2001
Posts: 871
I don't think I've ever done a multiplexor where the sprites could move freely around, but is it really necessary to sort them?

Wouldn't it be enough with a map consiting of a byte per rasterline where the bit pattern indicated which sprites were used. To allocate a new sprite, just ora all the bytes for the sprite's y-position and 21 positions down, and see which 0's are left, or if the result is $ff it's too bad.

21 oras per sprite might still be a little heavy, but this could of course be optimized by reducing the precission a bit, e.g. to 3rd line, which means only 7 oras/sprite.

Edit: And of course you need to insert 7 values in the table afterwards as well. :-) Still think it's faster than sorting though.
2007-10-10 13:48

Registered: Oct 2004
Posts: 209
I guess that's basically a "zone" multiplexer except with better granularity, sort of.. Don't forget that you've got to search through the scanlines first to see if any sprite channel is free all the way down before marking them. Then you'd also need another set of tables to keep track of which virtual sprite is bound to which sprite channel.
Finally you'd have to walk through the array line-by-line to figure out when to trigger the interrupts. I suppose the easiest way would be to walk the array from the bottom up to find the earliest possible line to program the sprite.

Except it'd have to be fairly coarse to win-out over a sort-based approach.

edit: I suppose you wouldn't have to check all entries, just the first and the last one. Or maybe only the first if the flag was interpreted to mean that the sprite is free to be reused here. Hmm..

Either way I figure it'd be a nice way to deal with y-expanded sprites and other special cases for linked sprites as well as for dealing with sprite priorities, i.e. the sprites would be allocated in the order of priority.
2007-10-10 14:04

Registered: Apr 2002
Posts: 4058
mixing some ideas this could be powerful. I'm thinking of a chained list of rasterlines having sprites, and each element in this list would point to another list having the sprites. ;)
2007-10-10 14:08

Registered: Oct 2004
Posts: 209
Quote: mixing some ideas this could be powerful. I'm thinking of a chained list of rasterlines having sprites, and each element in this list would point to another list having the sprites. ;)

Care to elaborate?
Superficially that sounds exactly like what my bucket sort does today, except I think you meant something entirely different..
2007-10-10 14:23

Registered: Apr 2002
Posts: 4058
well at a second look it might be not a good idea, as walking the chain each time a new sprite is inserted is something like an insertion sort using doublechained elements :P it would be better not to chain the raster list, instead using a 256 byte table, the end result would be counting sort with chained sprites :) or if you want like your radix sort without separate lsd/msd :)

edit, ok this one fails when you have to reset the 256 byte table :P maybe you could collect the used entrys somewhere during the proces tho.
2007-10-10 16:00

Registered: Aug 2004
Posts: 620
Hmm. Perhaps you could insert 'start actor' and 'end actor' events into one each of (say) 50 buckets, one every four rasters.

Then whenever an actor is done with you could add the sprite you used to a free list, and whenever a sprite is required you could take one off the free list. No sorting required - you just need to look ahead in the bucket table to see when the next raster interrupt is required.
2007-10-10 20:20

Registered: Apr 2002
Posts: 4058
how about binary trees? %)
Previous - 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 - 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
Users Online
Zaz/Dual Crew
Knut Clausen/SHAPE
Guests online: 43
Top Demos
1 Uncensored  (9.7)
2 Edge of Disgrace  (9.7)
3 Coma Light 13  (9.6)
4 The Shores of Reflec..  (9.6)
5 Lunatico  (9.6)
6 Comaland 100%  (9.5)
7 Incoherent Nightmare  (9.5)
8 Wonderland XII  (9.5)
9 Comaland  (9.5)
10 Wonderland XIII  (9.5)
Top onefile Demos
1 Veterans of Style  (9.5)
2 Dawnfall V1.1  (9.5)
3 Daah, Those Acid Pil..  (9.5)
4 Treu Love [reu]  (9.4)
5 Dawnfall  (9.3)
6 SidRok  (9.3)
7 F1 Evolution  (9.3)
8 One-Der  (9.2)
9 Tunnel Vision  (9.2)
10 Game of Thrones [2sid]  (9.1)
Top Groups
1 Pond  (10)
2 Booze Design  (9.4)
3 Censor Design  (9.4)
4 Oxyron  (9.4)
5 Crest  (9.3)
Top Swappers
1 Jerry  (10)
2 Zyron  (10)
3 Derbyshire Ram  (10)
4 Splatterhead  (9.8)
5 Walker  (9.7)

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