Tutorials


Facebook    reddit    Tweet this page    forum
YouTube Adventure Channel    englische flagge




Sprite Multiplexing

in der deutschen Übersetzung...

englische Version

original file


Sprite multiplexing by Cadaver
Deutsche Übersetzung von selmiak
--------------------------------

Hier geht es darum mehr als 8 Sprites auf dem Bildschirm darzustellen (sie
wiederzuverwenden, und dadurch also zu "multiplexen")


0. Hintergrundinformationen

Sprite Multiplexing wird in seinem vollen Umfang (wie es in Spielen wie Green
Beret oder Ghosts'n Goblins benutzt wird, in denen das freie Benutzen von mehr
als 8 Sprites überall auf dem Bildschirm mit jeder Farbe und jedem Frame
möglich ist) selten in Magazinen und ähnlichem thematisiert. Oft dreht es sich
nur darum Sprites wiederzuverwenden oder es geht um die "Zone Split" Technik.

Als ich wieder anfing mich mit der Softwareentwicklung auf dem C64 zu
beschäftigen habe ich für mich entschieden, wenn ich ein Spiel mache, dann
wird es definitiv mehr als 8 Sprites darstellen müssen. Ich habe versucht im
Internet Informationen dazu zu finden aber fand eigentlich nichts außer ein
paar Programmierer Tagebücher, zum Beispiel Andrew Braybrooks Morpheus diary,
welches einige der anstehenden Probleme eher unverständlich behandelte.

Also musste ich anfangen die Sprite Sortier/Multiplex Routinen von Spielen wie
Green Beret, Midnight Resistance, u.ä. zu reverse engineeren um ein tieferes
Verständis zu erlangen, wie das ganze vor sich geht. Meine erste Sortierroutine
war natürlich der Bubblesort Algorithmus, aber dieser läuft sehr langsam...


1. "Zone split" Technik

Fangen wir also mit den Hardware Eigenschaften, die für einen einfacheren
Ansatz benötigt werden an. Stell dir nun die Situation in Turrican vor, in der
der Spieler gegen den ersten Bossgegner kämpft, die riesige "Faust": Einmal ist
der Spieler Charakter zu sehen, der aus 3 Sprites besteht (2 multicolor Sprites
und ein singlecolor Sprite in weiß, der auf der Y-Achse gestreckt ist
obendrauf) und die "Faust", die aus 5 Sprites pro Reihe in 4 Reihen besteht (20
Sprites insgesamt). Hier ist ein Diagram der Sprite Nummern auf dem Bildschirm,
wobei der 3. (der singlecolor Sprite, der obendrauf liegt) ausgelassen wurde.

              4 5 6 7 8
              4 5 6 7 8
              4 5 6 7 8
         1    4 5 6 7 8
         2
______________________________

Also, die Idee dahinter ist folgende: Ein Raster Interrupt wird vor dem Start
einer jeden Spritezeile des Bossgegners ausgelöst und darin werden die
Y-Koordinaten, die Sprite Frames und die Farben der Sprites 4-8 neu geschrieben
um die Sprites wiederzuverwenden. Die X-Koordinaten ändern sich über die Zeilen
nicht und können vorher gesetzt werden.

Eine der wichtigsten Hardware Eigenschaften, die dabei beachtet werden muss ist
folgende: Die Y-Koordinaten der Sprites müssen gesetzt werden bevor die
Rasterzeile diese Y-Position erreicht, oder der wiederverwendete Sprite wird
gar nicht erst angezeigt!

Das ist gar nicht so schlimm wie es klingt. Die Y-Koordinate kann ein gutes
Stück vorher gesetzt werden, gleich nachdem begonnen wurde, die vorherige
Spritezeile darzustellen. Die Y-Koordinate mitten während der Darstellung eines
Sprites zu verändern wird diesen Sprite nicht abschneiden oder ähnliches.

Tatsächlich hat man mehr Ärger mit den Frames und den Farben. Es wird
mindestens eine Rasterzeile benötigt um die Frame- und Farbregister
umzuschreiben, also ist es sehr wahrscheinlich, dass die letzte Pixelspalte der
"vorherigen" (aktuellen) Spritezeile bereits die Grafik und Farbe der letzten
Pixelspalte der "neuen" Spritezeile anzeigt (wir sind zu früh). Oder aber die
erste Pixelspalte der "neuen" Spritezeile hat noch die Grafikdaten und Farben
der vorherigen Zeile (wir sind zu spät). Zumindest bei einigen Sprites kann
dies passieren.
Es kommt also auf sorgfältige Timing Einstellungen an und empfehlenswerterweise
designt man die Sprites so, dass es keinen Unterschied macht, wenn Frame- und
Farbregister zu spät umgeschrieben werden (wenn nur multicolor und nicht die
Sprite Farbe in der ersten Pixelspalte benutzt wird)

Ein Beispiel für Code der das Register Überschreiben in der Situation hier
drüber übernimmt könnte wie folgt aussehen:

                lda $d007              ;Nimm die Y-Koordinate des 4. Sprites,
                clc                    ;setze sie 21 Pixel tiefer und
                adc #21                ;schreibe das in die Y-Koord von Spr 4-8
                sta $d007              ;Das muss passiert sein, ehe die Raster-
                sta $d009              ;zeile die neue Y-Koordinate erreicht,
                sta $d00b              ;oder die Sprites werden nicht angezeigt
                sta $d00d
                sta $d00f
                ldx spriteindex
                lda frametable,x       ;Hier wird X mit einem Index in die
                sta $c3fb              ;Sprite Frame und Farbtabelle des Bosses
                lda frametable+1,x     ;geschrieben. Screen Memory ist bei
                sta $c3fc              ;$c000
                lda frametable+2,x
                sta $c3fd
                lda frametable+3,x
                sta $c3fe
                lda frametable+4,x
                sta $c3ff
                lda colortable,x
                sta $d02a
                lda colortable+1,x
                sta $d02b
                lda colortable+2,x
                sta $d02c
                lda colortable+3,x
                sta $d02d
                lda colortable+4,x
                sta $d02e
                txa                    ;Sprite Index um 5 erhöhen
                clc                    ;für die nächste Spritezeile
                adc #5
                sta spriteindex

Tatsächlich jedoch habe ich nie einen Multiplexer dieser Art geschrieben und
werde es wahrscheinlich auch nie tun. Natürlich erlaubt es einem beeindruckend
große Gegnersprites darzustellen, aber man verliert die Freiheit alles was man
will mit den Sprite zu tun, und daher kommen wir zum nächsten Punkt...


2. Echtes (übliches) Sprite Multiplexing

Mit dieser Methode ist es möglich Sprites frei zu benutzen, als ob mehr als 8
verfügbar wären (Green Beret, Ghosts'n Goblins, Midnight Resistance, Turrican
wenn man gerade *nicht* gegen einen Boss kämpft und viele mehr.) Da kommen
natürlich die Limits der Hardware ins Spiel: Es ist einfach unmöglich mehr als
8 Sprites in der selben Rasterzeile anzuzeigen. Und weil es ein Stück dauert
die Sprite Register neu zu beschreiben, kann es zu hässlichen Grafikeffekten
kommen, die angezeigt werden, wenn Sprites zu dicht gepackt werden und die
Register tatsächlich neu beschrieben werden während gerade Sprites angezeigt
werden.

Der Ansatz zum normalen Multiplexen besteht darin, die Sprites in einer Liste
von oben nach unten sortiert zu haben (mit Hilfe der Y-Koordinate), so dass die
Raster Interrupts, die das Wiederverwenden der Sprites steuern, immer kontrol-
liert von oben nach unten durchlaufen.

Das ist ein bisschen komplizierter als das Zone Split Multiplexing aus
Kapitel 1, aber die Komplexität ist in der Sprite Sortier Routine und in den
Raster Interrups verborgen, die die Sprites tatsächlich darstellen. Für den
Rest des Programms wird es somit einfach sein, die Sprites so anzusprechen, als
ob sie Hardwaresprites wären. Eigentlich ist es noch einfacher, da die Sprite
Sortier Routine auch Bit Manipulationen ausführen kann, wie zum Beispiel die
höchsten Bits auf der X-Koordinate oder durch Sprites (frei)geschaltete Bits.

Also muss folgendes getan werden:

- Sortiere die Sprites ansteigend nach der Y-Koordinate. Das heißt, dass die
  Sprites am oberen Rand des Bildschirms zuerst kommen. (Dies wird in der
  Sprite Sortier Routine gelöst.)

- Mappe (zeichne) die "virtuellen" Sprites auf die 8 physikalisch vorhandenen
  Sprites des C64. (Dies wird in der Sprite Sortier Routine oder in den Raster
  Interrupts gelöst).

- Schreibe die korrekten Werte in die Sprite Hardware Register damit die
  "virtuellen" Sprites so genau wie möglich dargestellt werden können. (Dies
  wird in den Raster Interrups gelöst.)

- Wenn die Darstellung der Sprites beendet ist, ihre Position auf die niedrigst
  mögliche Bildschirmposition setzen (255). Damit wird sichergestellt, dass
  kein Sprite im nächsten Frame zu früh dargestellt wird wenn sich die Sprites
  nach unten bewegen. Wenn die ersten 8 Sprites ein gutes Stück vor dem
  Anzeigen der Sprites geschrieben werden kann dies ausgelassen werden!

Optional können wir:

- Sprites auslassen, die außerhalb der sichtbaren X- oder Y-Koordinaten
  Bereiche liegen (das könnte auch in der Verantwortung des Hauptprogramms
  liegen)

- Sprites auslassen, wenn mehr als 8 in einer Reihe sind (in der Sprite Sortier
  Routine oder im Raster Interrupt eingebettet). Wenn das nicht gemacht wird
  werden einige sehr hässliche Grafikfehler auftauchen wenn mehr als 8 Sprites
  auf einer einzigen Rasterzeile existieren wollen.

- Vorher schon alle Raster Interrupt Positionen und die darin enthaltenen
  (überschriebenen) Sprite Nummern herausfinden.

- Die Werte des Registers $d010 vorher berechnen um die Raster Interrupts
  schneller auszuführen.

- Einen Doppelpuffer (doublebuffer) für die vom Raster Interrupt benutzte
  "Sortierte Sprite Liste" einbauen. Damit kann man die Sprites bereits für
  den nächsten Frame sortieren während die vorherigen Sprites noch angezeigt
  werden.


2.1 Die Sprites sortieren

Bitte beachten: Der Sortier Algorithmus in Kapitel 2.1.5 (der "Ocean"
Algorithmus) scheint allen anderen in diesem Dokument beschriebenen Algorithmen
überlegen zu sein. Ich benutze ihn in MW4 und bin sehr zufrieden damit. Bitte
ziehe es in Erwägung diesen für deine C64 Projekte zu benutzen und die anderen
hier vorgestellten Algorithmen nur als Lehr- und Anschauungsmaterial anzusehen.

Ich werde hier hauptsächlich an C angelehnten Pseudocode angeben. Ja, irgendwie
ist das 'cheaten' wenn man ein C64 Programmierdokument schreibt, aber ich bin
mir sicher, dass es besser zum Verständnis beiträgt als einen kryptischen und
bereits optimierten ASM Code anzugeben, (und wenn du anfängst Spiele zu reverse
engineeren wirst du letzteres in Massen finden.)

Also, der Punkt an dem wir einsteigen ist vermutlich eine zufällige Anordnung
von Y-Koordinaten im "Virtuelle Sprites" Y-Koordinaten Array (also was auch
immer das Hauptprogramm ausspuckt). Das Endergebnis, welches wir anstreben,
soll eine schön nach Y-Koordinaten sortierte Liste der Sprites sein, mit der
wir dann weiter arbeiten können.

Jetzt ist es auch an der Zeit die Array Namen, die in diesen Beispielen benutzt
werden zu erklären. (Es sind die selben, die ich auch in meinem C64 Sourcecode
benutze.)

Die "virtuellen" Sprite Arrays (unsortiert):
sprx - Unsortierte X Koordinaten
spry - Unsortierte Y Koordinaten
sprc - Unsortierte Farben
sprf - Unsortierte Sprite Frame Nummern

Die sortierten Sprite Arrays:
sortsprx  - Sortierte X Koordinaten
sortspry  - Sortierte Y Koordinaten
sortsprc  - Sortierte Farben
sortsprf  - Sortierte Sprite Frame Nummern
sortorder - Sortierte Liste der Indizes relativ zur unsortierten Liste (wird
            nicht in jedem Beispiel verwendet)


2.1.1 Bubblesort

Beim Bubblesort geht es darum die Y-Koordinaten so lange auszutauschen, bis
diese in der richtigen Reihenfolge sind. Das geht schnell, wenn nur ein paar
Sprites zu bearbeiten sind, aber wenn die Anzahl der Sprites steigt, steigt die
Zeitdauer proportional im Quadrat (N^2) zur Anzahl der Sprites N.

Natürlich reicht es nicht, nur die Y-Koordinaten zu sortieren. Wir müssen ja
auch wissen zu welchem Sprite die Koordinaten gehören, ansonsten ist die
sortierte Liste nutzlos. Dazu brauchen wir einen Index Array, der die Beziehung
zum unsortierten Array erhält. Der Index wandert dann zusammen mit der
Y-Koordinate während dem Sortiervorgang.

Also machen wir das wie folgt:

;Arrays für das Sortieren initialisieren

for (sprite=0; sprite < maximum_sprites; sprite++)
{
  sortspry[sprite] = spry[sprite];
  sortorder[sprite] = sprite;
}

;Das eigentliche Sortieren

for (outer = 0; outer < maximum_sprites-1; outer++)
{
  for (inner = outer+1; inner < maximum_sprites; inner++)
  {
    if (sortspry[inner] < sortspry[outer])
    {
      swap(sortspry[inner], sortspry[outer]);
      swap(sortorder[inner], sortorder[outer]);
    }
  }
}

Ein weiterer Nachteil dieses Algorithmus ist, dass es keinen klar definierten
Punkt gibt, an dem man die mehr-als-8-Sprites-in-einer-Reihe-Auslassung
einfügt; einen Sprite aus dem sortierten Array zu entfernen bedeutet, dass man
tatsächlich Speicherblöcke umherschiebt, und das ist langsam.

Man könnte das ganze auch so implementieren, dass gar keine Liste mit
sortierten Y-Koordinaten vorhanden ist. Stattdessen greift man ständig von der
Index Liste aus auf die unsortierte Liste zu. Damit kann man auf das
vertauschen der Y-Koordinaten verzichten, aber das Vergleichen der
Y-Koordinaten würde länger dauern.


2.1.2 Wie man die nächst niedrigere Y-Koordinate findet

Diese Methode benötigt kein Vertauschen und es gibt einen klar definierten
Punkt, an dem die Sprite Auslassung eingefügt werden kann. Sie eignet sich
auch gut dazu, die Innere Vergleichsschleife aus Geschwindigkeitsgründen
komplett aufzufalten. Die Ausführungsdauer wächst jedoch immer noch propor-
tional zu N^2.

Hier muss eventuelle eine "temporäre" Y-Koordinate benutzt werden, da Werte aus
dieser Liste "zerstört" werden. Es ist egal, ob alle Sprite Koordinaten für
jeden neuen Frame erneut berechnet werden. Ich zeige hier jedenfalls ein
Beispiel in dem der Temp-Array vorkommt.

;temp Array initialisieren

for (sprite = 0; sprite < maximum_sprites; sprite++)
{
  temp_y[sprite] = spry[sprite];
}

;Sortieren

sorted_sprites = 0;   ;Zähler der Sprites die bereits durch das Sortieren              
                          ;durch sind

while (true)   ;unbegrenzte Schleife
{
  lowest_found_y = 255;      ;Maximale bisher gefundene Y-Koordinate
  lowest_spritenumber = 255; ;Das ist ein ungültiger Wert der benutzt wird
                             ;um die Schleife abzubrechen, wenn keine
          ;weiteren Sprites mehr gefunden werden

  for (sprite = 0; sprite < maximum_sprites; sprite++)
  {
    if (temp_y[sprite] < lowest_found_y)
    {
      lowest_found_y = temp_y[sprite];
      lowest_spritenumber = sprite;
    }
  }

  if (lowest_spritenumber > maximum_sprites) break; ;Sortiervorgang beendet,
    ;Schleife abbrechen
  temp_y[lowest_spritenumber] = 255; ;Dieses Sprite nun für die nächste
                                     ;Sortierrunde ausschließen

  if (sprite_not_rejected)       ;Hier kommt die Sprite Auslassung,
                                    ;falls benötigt
  {
    ;Als nächstes können wir entweder die Sprite Variablen in die sortierte
    ;Liste kopieren, oder den Index benutzen

    ;In die sortierte Liste kopieren
    sortspry[sorted_sprites] = spry[lowest_spritenumber];
    sortsprx[sorted_sprites] = sprx[lowest_spritenumber];
    sortsprf[sorted_sprites] = sprf[lowest_spritenumber];
    sortsprc[sorted_sprites] = sprc[lowest_spritenumber];
    sorted_sprites++;

    ;den Index benutzen
    sortorder[sorted_sprites] = lowest_spritenumber;
    sorted_sprites++;
  }
}


2.1.3 Sortieren nach Y geteilt durch 8 (falsch)

Diese Sortierungsmethode garantiert keine korrekte Reihenfolge der Sprites, ist
dafür aber sehr schnell (die Ausführungszeit ist proportional zu N). Diese
Methode habe ich in MW1-3 benutzt, werde sie aber nicht weiter benutzen - da
sie eigentlich nur den letzten Schritt der Basis Sortierung benutzt.

Diese Methode basiert auf der Idee der "Eimer" in denen Sprites gespeichert
werden. Diese Eimer mit C64 ASM zu realisieren benötigt einiges an Kreativität,
aber du kannst in den Quellcode schauen um zu sehen wie ich es gemacht habe.
Im Grunde besteht meine Lösung darin, keine zweidimensionalen Arrays zu
benutzen, sondern die tatsächliche Anzahl der Sprites in einem Eimer
herauszufinden ehe du anfängst die Sprites in die Eimer zu stecken. Deshalb
kann der Inhalt der Eimer nebeneinander im Speicher stehen und die Reihenfolge
der sortierten Sprites kommt dann direkt aus dem Eimer-Speicherbereich, ohne
dass man jeden einzelnen Eimer durchgehen muss, wie in diesem Beispiel.

Wenn das kompliziert klingt, mach dir nichts draus, das ist sowieso keine gute
Lösung. Wir kommen zur meiner Meinung nach besten Lösung als letztes...

;Die Anzahl der Sprites in jedem Eimer auf 0 zurücksetzen. Wir brauchen so
;viele Eimer wie es Zeichenzeilen im sichbaren Spritebereich gibt.

for (bucket = 0; bucket < maximum_buckets; bucket++)
{
  amount_in_bucket[bucket] = 0;
}

;Sprites in den Eimern entsprechend ihrer Y-Koordinate speichern.
;Die Eimer sind eigentlich zwei-dimensionale Arrays.

for (sprite = 0; sprite <  maximum_sprites; sprite++)
{
  bucket_number = spry[sprite] / 8;
  bucket[bucket_number][amount_in_bucket[bucket_number]] = sprite;
  amount_in_bucket[bucket_number]++;
}

;Alle Eimer durchgehen um die Reihenfolge der Sprites festzustellen. In diesem
;Beispiel werden die Sprites direkt in die sortierte Liste kopiert.

sorted_sprites = 0;

for (bucket = 0; bucket < maximum_buckets; bucket++)
{
  for (index = 0; index < amount_in_bucket[bucket]; index++)
  {
    sprite = bucket[bucket][index];
    sortspry[sorted_sprites] = spry[sprite];
    sortsprx[sorted_sprites] = sprx[sprite];
    sortsprf[sorted_sprites] = sprf[sprite];
    sortsprc[sorted_sprites] = sprc[sprite];
    sorted_sprites++;
  }
}


2.1.4 Basis Sortierung

Diese Methode garantiert eine korrekte Reihenfolge der Sprites, ist aber
kompliziert. Die Zeit, die zur Ausführung benötigt wird ist, wie im vorherigen
Beispiel, proportional zu N, aber der Code selbst kann relativ langsam sein.
Diese Methode basiert auch auf der "Eimer"-Idee, aber in 2 Passes, also 2
Durchgängen. Als erstes wird nach dem Rest der Division der Y-Koordinate durch
16 sortiert, dann nach dem tatsächlichen Ergebnis der Division.

;Eimer leeren für beide Durchgänge.

for (bucket = 0; bucket < maximum_buckets; bucket++)
{
  amount_in_bucket1[bucket] = 0;
  amount_in_bucket2[bucket] = 0;
}

;Sprites im First-Pass-Eimer speichern, entsprechend dem Rest der Y-Koordinate
;dividiert durch 16.

for (sprite = 0; sprite < maximum_buckets; sprite++)
{
  bucket1_number = spry[sprite] & 15;
  bucket1[bucket1_number][amount_in_bucket1[bucket1_number]] = sprite;
  amount_in_bucket1[bucket1_number]++;
}

;Alle First-Pass-Eimer durchgehen um die Reihenfolge des ersten Sortier-
;Durchgangs herauszufinden. Gleichzeitig werden die Sprites entsprechend dem
;Ergebnis der Division der Y-Koordinate durch 16 in den Second-Pass-Eimer
;gesteckt.

for (bucket = 0; bucket < maximum_buckets; bucket++)
{
  for (index = 0; index < amount_in_bucket1[bucket]; index++)
  {
    sprite = bucket[bucket][index];
    bucket2_number = spry[sprite] / 16;
    bucket2[bucket2_number][amount_in_bucket2[bucket2_number]] = sprite;
    amount_in_bucket2[bucket2_number]++;
  }
}

;Die Second-Pass-Eimer durchgehen um die endgültige Sprite Reihenfolge heraus-
;zufinden. In diesem Beispiel werden die Sprites direkt in die sortierte
;Liste kopiert.

sorted_sprites = 0

for (bucket = 0; bucket < maximum_buckets; bucket++)
{
  for (index = 0; index < amount_in_bucket2[bucket]; index++)
  {
    sprite = bucket2[bucket][index];
    sortspry[sorted_sprites] = spry[sprite];
    sortsprx[sorted_sprites] = sprx[sprite];
    sortsprf[sorted_sprites] = sprf[sprite];
    sortsprc[sorted_sprites] = sprc[sprite];
    sorted_sprites++;
  }
}

Wie du siehst ist dies kompliziert und braucht einiges an Speicher, und dazu
mindestens drei Schleifen um alles gebacken zu bekommen.


2.1.5 Ständiges Einfügen Sortieren

Diese Methode wirst du häufig in Ocean/Imagine Spielen wie Green Beret oder
Midnight Resistance finden. Ähnliche Algorithem findet man auch in Dragon Breed
und SWIV.

Diese Sortier Routine ist anders als alle bisher aufgeführten. Sie benutzt
einen Reihenfolgen-Array, der nicht jedes mal wieder resetted wird. Daher ist
jeder Sortiervorgang eine Fortsetzung des Vorhergehenden und wenn sich nicht
viel geändert hat (also keine Sprites in der Y-Richtung aneinander vorbei-
gezogen sind) ist dieser Algorithmus sehr schnell, da er eigentlich nichts
machen muss. Es besteht jedoch die Möglichkeit, dass er sehr lange braucht,
wenn sich in einem Frame viel an der Spritereihenfolge geändert hat.

Als erstes müssen wir den Sortierreihenfolgen-Array initialisieren. Dies
geschieht nur einmalig zu Beginn des Programms. Eine Möglichkeit ist es,
erstmal nach der Spritenummer zu sortieren, von 0 bis zur höchsten Nummer:

for (sprite = 0; sprite < maximum_sprites; sprite++)
{
  sortorder[sprite] = sprite;
}

Als nächstes kommt die Sortierroutine. Beachte folgende Eigenart: Was, wenn
sich die Anzahl der dargestellten Sprite auf dem Bildschirm ändert, wie kommt
die Sortierroutine damit zurecht? Offensichtlich kann sie das nicht direkt
erkennen. Um dem entgegen zu wirken müssen wir zum Beispiel die maximale
Y-Koordinate mit dem Wert 255 benutzen um ungenutzte Sprites zu markieren;
diese rutschen dann ans Ende der sortierten List durch und machen keinen Ärger
(der Code, der die Sprites dann darstellt kann dann recht einfach den ersten
ungenutzen Sprite erkennen und die Routine verlassen).

sprite1 = 0;

while (true)
{
  if (spry[sortorder[sprite1+1]] < spry[sortorder[sprite1]])
  {
    sprite2 = sprite1;

    while (true)
    {
      swap(sortorder[sprite2], sortorder[sprite2+1]);
      if (sprite2 == 0) break;
      sprite2--;
      if (spry[sortorder[sprite2+1]] >= spry[sortorder[sprite2]]) break;
    }
  }
  sprite1++;
  if (sprite1 == maximum_sprites - 1) break;
}

Hier ist die ASM Implementierung, die in vielen Ocean Spielen genutzt wird:

                ldx #$00
sortloop:       ldy sortorder+1,x
                lda spry,y
                ldy sortorder,x
                cmp spry,y
                bcs sortskip
                stx sortreload+1
sortswap:       lda sortorder+1,x
                sta sortorder,x
                sty sortorder+1,x
                cpx #$00
                beq sortreload
                dex
                ldy sortorder+1,x
                lda spry,y
                ldy sortorder,x
                cmp spry,y
                bcc sortswap
sortreload:     ldx #$00
sortskip:       inx
                cpx #MAXSPR-1
                bcc sortloop

Und hier ist eine Variante die von SWIV adaptiert wurde (SWIV sortiert die
Sprites von unten nach oben, dementsprechend ist die Sortierreihenfolge in
diesem Fall umgekehrt). Dies benötigt ein paar Zeropage Temp-Variablen und
benutzt einen laufenden Vergleichswert, der für eine bessere Performance im
Akku gespeichert wird.

                ldx #$00
                txa
sortloop:       ldy sortorder,x
                cmp spry,y
                beq noswap2
                bcc noswap1
                stx temp1
                sty temp2
                lda spry,y
                ldy sortorder-1,x
                sty sortorder,x
                dex
                beq swapdone
swaploop:       ldy sortorder-1,x
                sty sortorder,x
                cmp spry,y
                bcs swapdone
                dex
                bne swaploop
swapdone:       ldy temp2
                sty sortorder,x
                ldx temp1
                ldy sortorder,x
noswap1:        lda spry,y
noswap2:        inx
                cpx #MAX_SPR
                bne SSpr_Loop1

Diese Sortierschleife produziert einen sortierten Index Array der Sprites.
Dieser kann dann durchgegangen werden und die Sprites können, wenn nötig, in
die sortsprx, sortspry, usw. Arrays kopiert werden. Ich glaube dies ist der
beste Algorithmus den ich bisher gefunden habe, zumindest wenn es um Spiele-
programmierung geht.


2.2 Die "virtuellen" Sprites auf echte Sprites mappen

Es bleibt dir eigentlich kaum eine andere Wahl, die Idee hinter dem Ganzen ist
so lange durch die tatsächlichen Sprites durchzugehen, bis alle "virtuellen"
Sprites angezeigt wurden. Also werden der 1. - 8. virtuelle Sprite (sortiert)
auf die tatsächlichen Sprites 1-8 abgebildet, der virtuelle Sprite 9 wird dann
wieder auf Sprite 1 gemappt, der virtuelle Sprite 10 auf Sprite 2 und so
weiter.

Wenn du eine andere Priorität für die Sprites möchtest kannst du das Ganze auch
anders herum angehen und den 1. virtuellen Sprite auf den 8. tatsächlichen
Sprite mappen, den 2. virtuellen auf den 7 physikalisch vorhandenen und so
weiter.

Hier ist ein Beispiel des Sprite Mappings, so in etwa könnte es auch in Green
Beret (erster Level) aussehen. Da rennen die 2-Sprites Soldaten herum, der
Spieler springt in die Luft und ein Flammenwerfer hängt links in der Luft
(1 Sprite)

                          1
                4         2       3
              __5_____         ________
             /       6\       /     7
       _____/________8_\_____/______1__
      /           2            3
     /____________4____________5_______

In BOFH:Servers Under Siege geschieht das Sprite Mapping basierend auf der
Priorität der Sprites. Das ist komplizierter: Wenn die Prioritätsklasse des
Sprites NIEDRIG ist (für z.B. Körper, Items), versucht die Sprite Mapping
Schleife einen freien tatsächlichen Sprite in folgender Reihenfolge zu finden:
8,7,6,5,4,3,2,1. Bei MITTLERER Priorität (Spieler, Gegner) ist die Reihenfolge
5,4,6,3,7,2,8,1 und bei HOHER Priorität (Feuer, Explosionen) ist die Reihen-
folge 1,2,3,4,5,6,7,8. Ein "freier" tatsächlicher Sprite bedeutet in diesem
Fall ein Sprite dessen vorheriger virtueller Sprite auf der Y-Achse weit genug
entfernt vom neuen virtuellen Sprite ist, am besten mindestens 21 Pixel.


2.3 Sprites auslassen, wenn sie der 9. Sprite in einer Reihe sind

Dies ist relativ einfach. Stellen wir uns vor, wir gehen den sortierten Sprite
Array durch, etwa so einen wie der Algorithmus hier drüber produziert. Die
virtuellen Sprites werden auf die tatsächlichen Sprites mit der Immer-wieder-
Durchgehen-Methode gemappt, next_sprite ist der nächste Spriteindex in der
sortierten Reihenfolge und es gibt eine Variable sorted_sprites (wie in den
Beispielen zuvor), die angibt wie viele Sprites bisher "akzeptiert" wurden. Die
bisher akzeptierten Sprites werden in den sortierten Array kopiert (sortsprx,
sortspry etc.)

Der Test sieht so aus:
if (spry[next_sprite] - sortspry[sorted_sprites - 8] < 21) then reject();

Du siehst, dieser Test kann nicht für die ersten 8 Sprites durchgeführt werden,
da der Index des sortierten Array negativ werden würde. Das ist logisch, der
Test ist für die ersten 8 Sprites unnötig, da diese immer akzeptiert werden
können. Der Grundgedanke für die weiteren Sprites ist, dass jeweils mit der
Y-Koordinate des vorherigen "virtuellen" Sprites der auf diesen tatsächlichen
Sprite gemappt wird verglichen wird. Wenn der Abstand weniger als 21 Pixel
beträgt wäre der Sprite zu dicht dran und könnte von der Hardware nicht
dargestellt werden.


2.4 Bestimmen welche tatsächlichen Sprites geschrieben werden, und wann.

Dies kann entweder "Im Vorbeigehen" in den Raster Interrupts geschehen oder
vorherberechnet werden. Es gibt grundsätzlich 2 Möglichkeiten, finde heraus,
welche dir besser passt.

2.4.1 Kurz vor dem neuen Sprite

Der Gedanke dabei ist, zu warten, bis wir nahe genug an der Y-Koordinate an der
der Sprite startet dran sind um dann die Sprite Register zu schreiben. Wenn der
darauf folgende Sprite auch nahe dran ist kann er im selben Raster Interrupt
geschrieben werden.

Also was heißt nun "nahe genug"? Es ist die Dauer der Rasterzeit, die benötigt
wird um alle 8 Sprites unter den schlechtesten anzunehmenden Bedingungen zu
schreiben. Wenn wir näher an die Y-Koordinate eines Sprites kommen bevor die
Register geschrieben sind besteht die Möglichkeit, dass wir nicht genug Zeit
haben um alle 8 Sprites zu schreiben wenn alle die gleiche Y-Koordinate haben.
Aber umso näher wir rankommen können, umso besser und dichter gepackt werden
die Sprite Formationen aussehen (mit weniger Grafikfehlern).

Wenn die Raster Interrupts vorher berechnet werden (wann sie stattfinden, von
welchem Sprite aus angefangen wird, wie viele Sprites geschrieben werden
müssen) gibt es zwei Vorteile:

- Der "nahe genug"-Faktor (Anpassung an die Raster Interrupt Position) kann
  anhand der Anzahl der Sprites, die im nächsten Raster Interrupt geschrieben
  werden entschieden werden. Wenn es zum Beispiel nur einen Sprite zu schreiben
  gibt, kann der Interrupt zum Beispiel nur zwei Zeilen vor seiner Y-Koordinate
  geschehen. Wenn aber alle Sprites angezeigt werden, muss er ungefähr 10-12
  Zeilen vorher passieren.

- Die Y-Koordinaten sind entscheidend, sie müssen fertig sein wenn die Sprites
  angezeigt werden, alles andere ist Kosmetik. Also schreiben wir im Raster
  Interrupt die Y-Koordinaten zuerst, da wir wissen, welche Sprites geschrieben
  werden sollen, und erst danach wird der Rest geschrieben (X-Koordinaten,
  Frame, Farbe)

2.4.2 Kurz nach dem alten Sprite

Für diese Methode müssen die ersten 8 Sprites im oberen Teil des Frames
geschrieben werden. Dann warten wir auf die Rasterzeile gleich unter dem ersten
Sprite und schreiben dann die neuen Sprite Register Werte um den Sprite wieder-
zuverwenden. Wir wiederholen dies für den zweiten Sprite und so weiter, bis die
letzten Registerwerte des letzten virtuellen Sprites geschrieben sind.

Wenn wir die Y-Koordinate als letztes schreiben, stellen wir sicher, dass keine
Darstellungsfehler möglich sind: Für den Fall, dass der neue Sprite zu nahe am
alten Sprite ist oder der Schreibvorgang durch etwas anderes verzögert wird,
wird der neue Sprite einfach nicht angezeigt!

Diese Methode ist einfacher und sauberer, aber in Spielen, in denen die Sprites
dicht gepackt sind (wie in Green Beret) und sich dies auch nicht vermeiden
lässt, ist es doch so, dass es nicht akzeptabel ist, dass Sprites fehlen, auch
wenn dadurch Darstellungsfehler vermieden werden.


2.5 Doppelpuffern

Dies ist nicht so kompliziert wie es klingt. Reserviere zweimal so viel Platz
für den Sortierte-Sprites-Array (wenn du zum Beispiel 24 Sprites benutzt halte
Platz frei für 48). Wenn die Raster Interrupts die Sprites 0-23 anzeigen kannst
du die Sprites 24-47 modifizieren und umgekehrt. Dadurch wird der Code etwas
komplizierter, aber an sich ist es nicht sonderlich schwer.

Um das Hauptprogramm übersichtlich zu halten sollte der Unsortierte-Sprites-
Array nicht doppelt gepuffert werden.


2.6 Der Raster Interrupt Code

Das Ziel ist einfach: die benötigten Sprite Register Werte so schnell wie
möglich zu schreiben. Viele kommerzielle Spiele haben dies sehr ineffizient
implementiert. Der folgende Quellcode soll ungefähr den typischen Code in einem
Ocean Spiel wiedergeben:
(In diesem Fall nehmen wir an, dass Y die "virtuelle" Spritenummer enthält)

                tya
                and #$07                    ;Hole tatsächliche Spritenummer
                tax                         ;in X
                lda sortsprc,y
                sta $d027,x
                lda sortsprf,y
                sta $c3f8,x                 ;Schreib den Frame in beide Screens
                sta $c7f8,x                 ;des doppelgepufferter Screens
                                            ;(unötig!)
                txa
                asl
                tax
                lda sortspry,y
                sta $d001,x
                lda sortsprx,y              ;Multipliziere Sprite X-Koord mit 2
                asl                         ;dadurch keine 1-Pixel Genauigkeit
                sta $d000,x
                bcc msb_low
msb_high:       lda $d010
                ora ortbl,x
                sta $d010
                jmp nextsprite
msb_low:        lda $d010
                and andtbl,x
                sta $d010
nextsprite:     iny
                ...

ortbl:          dc.b 1
andtbl:         dc.b 255-1
                dc.b 2
                dc.b 255-2
                dc.b 4
                dc.b 255-4
                dc.b 8
                dc.b 255-8
                dc.b 16
                dc.b 255-16
                dc.b 32
                dc.b 255-32
                dc.b 64
                dc.b 255-64
                dc.b 128
                dc.b 255-128

Wie kann man also den Prozess optimieren?

- Schreibe ein eigenes Stückchen Code für jeden tatsächlichen Sprite
- Berechne die Werte von $d010 im Vorraus (natürlich geht die dafür benötigte
  Zeit woanders verloren, aber bei schnellem Raster Interrupt Code treten
  erheblich weniger Grafikfehler bei dicht gepackten Spriteformationen auf)
- Schreib Frame nur auf einen Screen gleichzeitig; Der Raster Interrupt Code
  kann an den momentan gebrauchten Screen angepasst werden

Und jetzt schau dir dieses zweite Beispiel an:
(Die virtuelle Spritenummer steckt wieder in Y)

sprite0:        lda sortspry,y
                sta $d001
                lda sortsprx,y
                sta $d000
                lda sortsprd010,y
                sta $d010
                lda sortsprf,y
frame0:         sta $c3f8
                lda sortsprc,y
                sta $d027
                iny
                cpy endspr
                bcs done

sprite1:        lda sortspry,y
                sta $d003
                lda sortsprx,y
                sta $d002
                lda sortsprd00,y
                sta $d010
                lda sortsprf,y
frame1:         sta $c3f9
                lda sortsprc,y
                sta $d028
                iny
                cpy endspr
                bcs done
                ...

Sieht ein bisschen schneller aus, oder? Wir würden das Highbyte der Framewrite
STA Anweisung entsprechend der Seite des doppeltgepufferten Screens
modifizieren. Natürlich müssen wir auch passend zum Sprite, das zuerst
geschrieben wird, an die richtige Stelle im Code springen. Also ist diese
Methode nicht ganz so einfach...


2.7 Flackern während den Raster Interrups vermeiden

Sprite Multiplexing in Spielen ist eine sehr unvorhersehbare Operation, da die
Sprites überall sein können. Wenn man nun einfach nur blind die sortierten
Y-Koordinaten durchläuft und die Raster Interrupts dementsprechend setzt,
können Flackern, Geschwindigkeitsverlust und Ruckeln (dadurch bedingt, weil der
neue Raster Interrupt höher oder an der selben Stelle wie der momentane $d012
Wert ist) in wenigstens einem dieser Fälle auftreten:

- Der nächste Raster Interrupt ist so nahe am aktuellen, dass wir dafür schon
  zu spät dran sind (nach $d012)

- Der untere Punkteanzeige Raster Interrupt wurde wegen dem Sprite Multiplexing
  verpasst (okay, nicht jedes Spiel hat eine Punkteanzeige am unteren Rand,
  aber viele)

Das erste, auf das man achten muss ist, sicherzustellen, dass Sprites, die sich
außerhalb des sichtbaren Bildschirmbereichs befinden nicht angezeigt werden.
Außerdem ist es eine gute Idee ein paar extra Zeilen vom unteren Rand des
Bildschirms zu entfernen: Wenn die Punkteanzeige bei Zeile 200 anfängt erlauben
wir es nicht, dass Sprites mit der Y-Koordinate 198 und 199 angezeigt werden.

Das zweite ist, einfach diesen Prüfcode am Ende eines jeden Raster Interrupts
einzufügen, dessen Position wir nicht sicher bestimmen können. In diesem
Beispiel enthält der Akku die Position des nächsten Raster Interrupts.

                sta $d012
                sec
                sbc #$03
                cmp $d012                       ;Zu spät vom letzten IRQ?
                bcc go_to_irq_directly

Beachte, das das go_to_irq_directly jeden Register Speichern/Wiederherstellen
Vorgang überspringen sollte, wie auch das Bestätigen des Interrupts (was
offensichtlich sein sollte). Es mag dir vielleicht ein wenig übervorsichtig
vorkommen zur "Sicherheit" 3 Zeilen vom Interrupt auszulassen, aber ich hatte
tatsächlich in seltenen Fällen ein Flackern als ich nur 2 ausgelassen habe.

Diese zwei Punkte verhindern kein langsames Ausführen des Programms, wenn die
CPU einfach zu viel zu tun hat, genauso wie sie keine Grafikfehler verhindern,
wenn sich einfach zu viele Sprites auf einem Haufen tummeln, aber immerhin
verhindern sie das gefürchtete Flackern und Musik die langsamer wird. :)


3. Fazit

Um echte und komplette Multiplexer, die in ASM geschrieben sind zu sehen
empfehle ich das folgende:

Ein Beispiel für einen echten (üblichen) Multiplexer
("Ocean" Sortierung, jetzt auch mit $d010 Betrieb)

In den folgenden Spielen sind die Quellcode Dateien, die Multiplexing behandeln
sprite.s und raster.s.

Metal Warrior 3 Quellcode
(Doppelpuffern, fehlerhaftes "Y geteilt durch 8" Sortieren, Vorherberechnen der
Raster Interrupts)

The Freedirectional Scrolling test program
(Doppelpuffern, Basissortieren der Y-Koordinaten)

BOFH Quellcode
(Doppelpuffern, Basissortieren der Y-Koordinaten, ein Prioritätsmechanismus,
der stehende Charaktere über, zum Beispiel Leichen und Items anzeigt, nicht
dahinter)

Außerdem könntest du versuchen dein Lieblingsspiel, von dem du weißt, dass es
mehr als 8 Sprites anzeigt, zu reverse engineeren! In einem Maschinencode
Monitor kannst du nach den Bytes $01 und $d1 suchen, diese schreiben die
Y-Koordinaten der ersten Sprites, oder suche andere Spriteregister. Oder schaue
in der Gegend der IRQ Adresse in den Code, normal ist der Mulitplexing Code in
der Nähe.

Wenn du dir den indizierten Zugang, der im Sprite Interrupt Code steht ansiehst
wirst du normalerweise einen Speicherzugriff entdecken, dessen Ergebnis nicht
in ein Sprite I/O Register geschrieben wird, sondern als Index (entweder im X
oder Y Register) für den Zugriff auf andere Sprite Arrays benutzt wird. Dies
ist höchstwahrscheinlich der Sprite-Sortier-Array, und wenn du nach den
Speicherreferenzen dazu suchst, findest du die Sortierrountine.

Viel Glück mit deinen Multiplexer Experimenten! Und denke daran, wenn dein
Multiplexer läuft, unterziehe ihn einem Stresstest mit abnormal übertrieben
vielen Sprites...


                                                  Lasse Öörni
                                                  loorni@gmail.com
                                                  
                                                  Übersetzung
                                                  selmiak
                                                  www.selmiak.de.vu

Facebook    reddit    Tweet this page    forum
YouTube Adventure Channel    englische flagge

Main   c64 Main forum Main    englische flagge    up

User Kommentare:

1) Oliver      (mail versteckt)
schrieb am: 2013-06-14 10:24:17

Vielen Dank für diesen ausgesprochen verständlichen und gelungenen Artikel. Das macht echt Lust, mich wieder nach langer Zeit der C64-Assemblerprogrammierung zu widmen.
2) selmiak      (mail versteckt)
schrieb am: 2013-06-16 22:46:15

Das Kompliment gebe ich mal an Cadaver weiter, er hat das ja alles geschrieben, ich habe es nur übersetzt. Es war aber auch nicht immer leicht das alles verständlich (und gelungen) auszudrücken ;)
Viel Spaß mit dem Assembler und hoffentlich gibts da auch mal was zu sehen =)


Text:
*
Name:
*
web:
 


email:
*
Mail-Adresse verstecken?

bitte 3439 eintragen
*
Spamschutz!





up

..:: © by selmiak/Cadaver 2012-2019 ::..