quick sort beispiel in assembler?

ich habe bei einem freund ein snake game gesehen, welches nur mit directdraw programmiert wurde (also ohne Direct3D) diese snake ist in einem iso-3d gelände und ist selber incl. aller gegenstände auch in iso-3d persp. dargestellt.

ich habe nun (natürlich im moment noch sehr simpel) das ganze mal versucht nachzubauen und bin dabei auf folgende lösung gestossen:

1. um bei einfachen blits die blittreihenfolge der einzelteile richtig darstellen zu können, muss ich je nach position der teile die reihenfolge neu bestimmen (ist halt keine 3d engine)

2. um positionen sortieren zu können eignet sich ein int array für x, y, art, und ob das jeweilige teil zu sehen ist (snake wird länger oder kürzer)

3. ich muss das y array sortieren (richtige blitreihenfolge) und nun natürlich die zugehörigen werte in den anderen array auch.

ich hoffe es verständlich beschr. zu haben

volkard

Original erstellt von <Gast>:
2. um positionen sortieren zu können eignet sich ein int array für x, y, art, und ob das jeweilige teil zu sehen ist (snake wird länger oder kürzer)
3. ich muss das y array sortieren (richtige blitreihenfolge) und nun natürlich die zugehörigen werte in den anderen array auch.
ich hoffe es verständlich beschr. zu haben

jo, glaub schon.
allgemein ist zum sortieren quicksort am schnellsten.
hier wäre zu überlegen, ob nicht ein indexfeld sortiert werden sollte, um weniger kopieren zu müssen.
außerdem kackt quicksort fürchterlich ab, wenn das feld bereits vorsortiert ist. ist es vielleicht so, daß die daten von bild zu bild kaum geändert werden? also sagen wie mal nur 10 objekte ändern ihre position? dann wäre bubble evtl schneller. oder am besten werden die objekte, die ihre position ändern angeschubst, sich neu einzusortieren.
oder entstehen und verschwinden andauernd ein paar objekte? das sähe nach einem baum aus, den man dann in order durchgeht, um alle zu zeichnen.

wenn ich mal so drüber nachdenke...
ich denke, es gibt recht wenige mögliche y-positionen? dann wär da ein array voller doppelt verketterer listen ideal, würd ich sagen.
einfügen in O(1).
löschen in O(1).
kein Sortierbedarf.

oder brauchste auch suche nach x und y? jo, könnt ein array von bäumen werden, denke mal ein array von hashtables oder ein 2d-baum wär übertrieben.

oder gibts nur relativ wenige positionen, wo überhaupt objekte sein können und an jeder postion nur eins? das wäre dann ein dickes array of art.

verstehste jetzt, warum ich quicksort erstmal einfach angezweifelt hab? je mehr man über die genauen anforderungen weiß, desto genauer kann man ne gut angepaßte datenstruktor und gute algorithmen auswählen. und gut angepaßte dinge machen standard-dinge mit links platt. vergäude deine zeit also erstmal nicht damit, ein gutes allgemeines quicksort in c zu einem guten allgemeinen quicksort in asm zu machen, selbst wenn 20% mehr speed drinne ist. mach das erst, wenn du ganz sicher bist, daß dir kein besseres verfahren einfallen wird.

vielen dank für eure bemühungen, ich habe mittlerweile von herrn heinzig den quellcode welchen er verwendet hat bekommen, ist übrigens kompl. in assembler und verfolgt den gleichen grundgedanken welchen ich hatte.

Hey, magste den mal posten? Ich will sehen ob der schneller ist und wenn ja wieviel

volkard

da gibt man sich so ne mühe mit den jungen leuten...

und dann kommt einer und gibt mir den ganzen source und erklärt mir den auch noch und hilft mir diesen in mein programm einzubauen

nein, mal ganz ehrlich, ich danke dir, nur ist es so halt viel einfacher für mich und wann bekommt mann schon mal die möglichkeit mit so einem programmierer zusammenarbeiten zu können? nochmals vielen dank an alle und vor allem natürlich an maik!!!