Aw: Re: [stella] Star Fire: Getting Closer: Perfect Sorting solution

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