Subject: Aw: Re: [stella] Star Fire: Getting Closer: Perfect Sorting solution From: cybergoth@xxxxxxxx Date: Thu, 28 Mar 2002 11:31:05 +0100 (MET) |
Hi Thomas! > >As a result of all the sorting discussions, I finally > >found the perfect solution for my problem, by inventing > >a totally new sorting method! ;-) > Really? Tell us please. :-) Yep, I did! Well, when you found the bug in my sorting algorithm in the last discussions, there was one thing that kept my brain going: If the sorting algorithm was buggy, why the hell was the output exactly what I want? Slowly the answer creeped in my mind, finally it made *click* Tada: ->Even though the routine was buggy, it constantly _improved_ the sorting! Now, exploiting that knowledge, I just do the following: I let the outer loop of a bubble sort run _exactly_ 2 times, every frame. While this addmittedly never produces a perfect sort, it is -> constantly improving the result. Thus I christian the method I invented "Improving Sort", please remember that, when writing the next book about sorting Algorithms :-) Ok, lets analyse, what's happening. Assuming there's 10 moving objects onscreen, it'll take a max of 5 frames until the array is sorted. Once it is is sorted, it'll constantly correct itself. Assume two objects are swaping positions, well - the same frame their indexes are swapped too. Assuming we meet a worst case scenario, we get this: Frame - Objects in order: 1 - 2 or more 2 - 4 or more 3 - 6 or more 4 - 8 or more 5 - 10 This is the worst case. But remember this: The player won't hardly notice anything of that, since it takes only ~ 8 Milliseconds until the sort order is completely restored. Besides, I can't even imagine how a worst case could happen at all. By running two times, the algorithm can correct 2 swaps per frame and it is very unlikely, that there's more elements swapping at once. Another downside is that you're limited to ~ 10 objects. But that fits perfect for Star Fire, I think 8 objects are already almost too much onscreen at once. And, maybe you can just run the loop three three times, if you really need more objects. So, now that we have discussed the neg. side, here's the plus: - No bail out code, no overhead - Constant running time, it's never able to take too long, like even a Bail-Out-Bubble-Sort - 2*(n-1) compares - 2*(n-1) is the maximum of swaps, too So, you see, it's not only ultra-fast, but very predictable, too. > Looks really good, but sometimes (mainly small) objects > disappear completely (e.g. the red fighter). Is that > intentional? Hm... I've yet to analyse that. Do they only disappear when near the top or bottom? Or do they disappear, when there's 3 or more objects in line? On the flicker itself I've yet to work a little. I fixed some bugs yesterday, but it's still imperfect and damn slow :-) Greetings, Manuel ----------------------------------------------------------------------- Riester-Rente - Kassieren Sie das Geld vom Staat: Zum Förderungsrechner! http://www.arcor.de/home/redir.php/riesterrente ----------------------------------------------------------------------- ---------------------------------------------------------------------------------------------- Archives (includes files) at http://www.biglist.com/lists/stella/archives/ Unsub & more at http://www.biglist.com/lists/stella/
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
RE: [stella] Star Fire: Getting Clo, Manuel Polik | Thread | Aw: Re: [stella] Star Fire: Getting, Thomas Jentzsch |
Re: [stella] Star Fire: Getting Clo, Thomas Jentzsch | Date | Aw: Re: [stella] Star Fire: Getting, Thomas Jentzsch |
Month |