Wieso sind Sprites 16x16 Pixel groß?

[rapso]

Long John Gold schrieb:

Aber bei einem DOS-Spiel hat man einfach ein 320x200 Bytes großes Array, in das man beliebig die Pixel zeichnen kann. Programmiertechnisch macht es doch hier eigentlich keinen Unterschied, ob ein Sprite 16x16 Pixel groß ist oder 34x27.

programmieren ist halt nicht nur es lauffaehig zu bekommen (wenn auch man das heutzutage oft so beigebracht bekommt), sondern es auch mit guter geschwindigkeit lauffaehig zu haben. indizieren in einem 2d array dessen rand power of 2 ist, ist ein simpler shift, das koennen alte CPUs die man unter DOS nutzte oft neben einem anderen integer befehl ausfuehren. Manchmal ist es sogar kostenfrei wenn die indirekte addressierung der CPU das unterstuetzt. bei nicht power of two ist es hingegen ein Mul, oft ist diese instruktion nicht komplett in hardware gewesen, sondern ueber microcode ausgefuehrt worden. waehrend dieser microcode laeuft ist die CPU oft nicht faehig irgendwas anderes zu tun und bei MUL kann das uU 40cycles sein. du hast also die wahl zwischen "for free" oder "verdammt langsam" und wofuer sollte man unbedingt non power of 2 brauchen? ob 15x15 oder 16x16 oder 17x17 macht an sich fast nie einen triftigen unterschied.

und da sprites oft nicht nur einzelne pixel brauchen, sondern wirklich massive die performance definieren, ist das ein entscheidener punkt. im besonderen wenn sprites rotiert werden konnten.
(es gab natuerlich noch viel mehr optimierungen zu dos zeiten, z.b. wurde bei C&C unter dos nur der teil der karte neu gezeichnet der neu reingescrollt wurde, der rest wurde nur moeglichst effizient kopiert. wenn einheiten rumfuhren, wurden die pixel wo sie vorher waren ausradiert mit dem orginal wert und dann die einheit an neuer stelle gezeichnet).

bei den 16-40MHz und 320x200 pixeln hast du im optimalfall nur 625cycle pro pixel pro sekunde, bei 30fps bist du auf 20cycle runter und da kannst du es dir nicht erlauben 40cycle fuer ein mull zu verschwenden.

entsprechend die entscheidung -> hat keine nachteile -> hat triftige vorteil -> power of two sprites.

btw. das ist nicht nur langsam, wenn man es in Hardware giesst, ist es auch viel aufwand. deswegen haben z.B. Atom cpus bei SSE 4add/sub einheiten die pro cycle laufen koennen, nur 2 mul einheiten die jeden zweiten cycle laufen und eine div einheit die sehr langsam ist (es lohnt sich das eine element das man dividieren will in einem SIMD register in den ersten slot zu rotieren, single-div [statt parallel div] auszufuehren udn dann wieder zurueck zu rotieren).

ich hoffe das hilft

[hustbaer]

@rapso
Um ein Sprite zu zeichnen indiziert man normalerweise nicht in ein 2D Array (abgesehen von der Startposition am Bildschirm, die man bei 16x16 Sprites genau so berechnen muss). Man schnappt sich den Zeiger auf's erste Pixel und verschiebt den dann bloss.

Nur wenn das Sprite nicht komplett auf den Bildschirm passt müsste man multiplizieren. Aber auch nur ein paar wenige male pro Sprite, die "pro Pixel" Sachen bestehen wieder bloss aus einfachen Befehlen.

Und spätestens zu Pentium Zeiten konnte man sich ein paar Multiplikationen pro Sprite ganz locker leisten.

BTW: viele DOS Grafik-Engines haben Sprites RLE-komprimiert. Da kann man dann nichtmal mehr mit nem Shift reinadressieren. Schneller war es trotzdem, weil man halt meistens vollständig sichtbare Sprites zeichnet, und die Zeit die man bei den vollständig sichtbaren Sprites mit dem überspringen der durchsichtigen Pixel spart wiegt den Overhead auf den man sich mit teilweise sichtbaren Sprites dabei einhandelt.

----

Warum Sprites früher mal mit 2er Potenzen gemacht wurden ist ja (hoffentlich) jebem klar. Die Frage war aber warum sich das so lange gehalten hat.

[blard]

Das mit den Multiklikationen ist Quatsch. Man kann einen nicht rotierten Sprite mit einer Multiplikation malen, egal wie groß er ist.

const size_t wsx = window.size.x;
const size_t wsy = window.size.y;
const size_t px = sprite.pos.x;
const size_t yp = sprite.pos.y;
const size_t x = sprite.size.x;
const size_t y = sprite.size.y;

uint32_t *out = window.buffer+px+py*wsx;
const size_t line_jump = wsx-x;

uint32_t *in = sprite.buffer;

for(size_t i = 0; i != y; i++)
{
  const uint32_t *line_end = out+x;
  while(out != line_end)
  {
    *in = *out;
    in++;
    out++;
  }
  out += line_jump;
}

(Sollten 5 instructions im inneren Loop sein, wenn ich mich grade nicht irre; dürfte wahrscheinlich noch schneller gehen)

(Könnte jetzt ein off-by-1 Fehler drin sein.)

Wenn der Sprite nur Teilweise auf dem Bildschirm ist, wird es etwas ekelig (lowlevel high performance code halt), geht aber vom Konzept gleich.

Das einzige was 2^n Sprites möglich machen ist das triviale Unrollen des loops. Ob es das Wert ist halte ich für fragwürdig.

Wobei man das heute sowieso alles auf der GPU machen sollte und man sich da ganz gut anstrengen muss um mit seinen Sprite malen ersthaft Zeit zu verbrauchen.

[hellihjb]

Es ist sogar so, dass aktuelle Nvidia-Karten noch alle Non-Power-Of-Two Texturen auf die naechste Zweierpotenz erweitern um die genannten Adressierungsvorteile nutzen zu koennen.

[hustbaer]

blard schrieb:

Wenn der Sprite nur Teilweise auf dem Bildschirm ist, wird es etwas ekelig (lowlevel high performance code halt), geht aber vom Konzept gleich.

Im Prinzip funktioniert das gleich, ja. Ich kenne aber keine Möglichkeit dann mit nur einer Multiplikation pro Sprite auszukommen.
Wenn das Sprite den oberen Bildschirm-Rand schneidet muss man ja irgendwie die nicht sichtbaren Zeilen in der Sprite-Grafik überspringen.

Das bedeutet entweder eine 2. Multiplikation. Oder man muss die Zeilen-Schleife ab Sprite-Zeile 0 laufen lassen, und bei Zeilen ausserhalb des Bildschirms dann die Pixel-Schleife überspringen. Was im Prinzip auch nix anderes ist als eine Multiplikation, nur halt ausgeführt als wiederholte Addition.

[rapso]

hustbaer schrieb:

@rapso
Um ein Sprite zu zeichnen indiziert man normalerweise nicht in ein 2D Array (abgesehen von der Startposition am Bildschirm, die man bei 16x16 Sprites genau so berechnen muss). Man schnappt sich den Zeiger auf's erste Pixel und verschiebt den dann bloss.

das klappt nur im sonderfall dass du pixel zu pixel mappst, das ist eher uninteresant und nicht performance kritisch wenn auch damit das meiste an pixeln gefuellt wird. kritisch wird es wenn du skalierung, rotation und sherung hast. bei shumps wird das bei allen einheiten und schuessen gemacht, nur der background hat die 1:1 optimierung. bei RTS sind es die ganzen units die bewegt werden und wie ich oben sagte, den hintergrund zeichnet man nicht neu (auch wenn das der schnelle teil waere), sondern maskiert die pixel aus pro einheit, zeichnet die einheit und im naechsten frame setzt man die ausmaskierten pixel wieder zurueck. entsprechend ist das zeichnen der einheiten der meiste aufwand.

Nur wenn das Sprite nicht komplett auf den Bildschirm passt müsste man multiplizieren. Aber auch nur ein paar wenige male pro Sprite, die "pro Pixel" Sachen bestehen wieder bloss aus einfachen Befehlen.

nein, du brauchst nicht zu multiplizieren, du addierst einfach pitch pro zeile, du zeichnest diese art von sprites eh zeilenweise, da sie eine andere breite als der bildschirm haben (normalerweise).

Und spätestens zu Pentium Zeiten konnte man sich ein paar Multiplikationen pro Sprite ganz locker leisten.

er sprach von dos spielen, das ist fuer mich alles ab 80x86, nicht nur die letzte generation, auch heute macht man spiele nicht nur fuer GTX680.

BTW: viele DOS Grafik-Engines haben Sprites RLE-komprimiert. Da kann man dann nichtmal mehr mit nem Shift reinadressieren. Schneller war es trotzdem, weil man halt meistens vollständig sichtbare Sprites zeichnet, und die Zeit die man bei den vollständig sichtbaren Sprites mit dem überspringen der durchsichtigen Pixel spart wiegt den Overhead auf den man sich mit teilweise sichtbaren Sprites dabei einhandelt.

RLE war eine moeglichkeit, eine andere war z.B. VQ, beide male hat man durch weniger memory traffic performance gewonnen, VQ erlaubte es jedoch es auch fuer beliebige sprites und sogar texturen zu nutzen.

[hustbaer]

rapso schrieb:

hustbaer schrieb:

@rapso
Um ein Sprite zu zeichnen indiziert man normalerweise nicht in ein 2D Array (abgesehen von der Startposition am Bildschirm, die man bei 16x16 Sprites genau so berechnen muss). Man schnappt sich den Zeiger auf's erste Pixel und verschiebt den dann bloss.

das klappt nur im sonderfall dass du pixel zu pixel mappst, das ist eher uninteresant und nicht performance kritisch wenn auch damit das meiste an pixeln gefuellt wird. kritisch wird es wenn du skalierung, rotation und sherung hast. bei shumps wird das bei allen einheiten und schuessen gemacht, nur der background hat die 1:1 optimierung. (...)

also die klassischen DOS shumps die ich so kenne haben überall 1:1 pixel-mapping verwendet, rotation etc. gab es da nicht. wenn etwas rotiert wurde, dann hatte man dafür einen haufen eigene grafiken. live rotation/skalierung war damals den automaten (bzw. einigen konsolen) vorbehalten, die das mit eigener hardware gemacht haben.

rapso schrieb:

Nur wenn das Sprite nicht komplett auf den Bildschirm passt müsste man multiplizieren. Aber auch nur ein paar wenige male pro Sprite, die "pro Pixel" Sachen bestehen wieder bloss aus einfachen Befehlen.

nein, du brauchst nicht zu multiplizieren, du addierst einfach pitch pro zeile, du zeichnest diese art von sprites eh zeilenweise, da sie eine andere breite als der bildschirm haben (normalerweise).

ach rapso das ist mir auch klar
aber sag mir mal wie du den startpunkt in der sprite grafik ermitteln willst, wenn der opere rand abgeschnitten ist (die oberen N zeilen ausserhalb des bildschirms liegen), und das sprite nicht 2^n breit ist (wovon ich hier ja rede). dafür brauchst du pro sprite eine zusätzliche multiplikation. oder du lässt die zeilen-schleife immer komplett laufen, und überspringst bei zeilen die oberhalb des bildschirmrandes liegen die pixel-schleife -- was im endeffekt auch nix anderes ist als eine multiplikation, nur halt implementiert als eine additions-schleife.

BTW: viele DOS Grafik-Engines haben Sprites RLE-komprimiert. Da kann man dann nichtmal mehr mit nem Shift reinadressieren. Schneller war es trotzdem, weil man halt meistens vollständig sichtbare Sprites zeichnet, und die Zeit die man bei den vollständig sichtbaren Sprites mit dem überspringen der durchsichtigen Pixel spart wiegt den Overhead auf den man sich mit teilweise sichtbaren Sprites dabei einhandelt.

RLE war eine moeglichkeit, eine andere war z.B. VQ, beide male hat man durch weniger memory traffic performance gewonnen, VQ erlaubte es jedoch es auch fuer beliebige sprites und sogar texturen zu nutzen.

du willst mir jetzt erzählen dass man VQ dekomprimierung mit einem 386er oder 486er "live" machen kann, ohne dabei langsamer zu werden als unkomprimiert?
RLE wurde ja nicht nur verwendet um speicherbandbreite zu sparen, sondern damals auch hauptsächlich damit transparente bereiche in den sprites komplett übersprungen werden können (=rechenzeit sparen).

[rapso]

hustbaer schrieb:

rapso schrieb:

hustbaer schrieb:

@rapso
Um ein Sprite zu zeichnen indiziert man normalerweise nicht in ein 2D Array (abgesehen von der Startposition am Bildschirm, die man bei 16x16 Sprites genau so berechnen muss). Man schnappt sich den Zeiger auf's erste Pixel und verschiebt den dann bloss.

das klappt nur im sonderfall dass du pixel zu pixel mappst, das ist eher uninteresant und nicht performance kritisch wenn auch damit das meiste an pixeln gefuellt wird. kritisch wird es wenn du skalierung, rotation und sherung hast. bei shumps wird das bei allen einheiten und schuessen gemacht, nur der background hat die 1:1 optimierung. (...)

also die klassischen DOS shumps die ich so kenne haben überall 1:1 pixel-mapping verwendet, rotation etc. gab es da nicht. wenn etwas rotiert wurde, dann hatte man dafür einen haufen eigene grafiken. live rotation/skalierung war damals den automaten (bzw. einigen konsolen) vorbehalten, die das mit eigener hardware gemacht haben.

Das haengt immer von der zeit ab auf die du referenzierst, die graphik ist natuerlich nicht stehengeblieben. auf 8086 mit 4.77MHz hast du Po2 verwendet, weil indizieren in eine nicht Po2 palette von sprites schon zuviel der Muls waere. spaetere CPUs die das schnell genug konnten, hat man lieber zum rotieren von sprites verwendet als non-Po2 sprites einzubauen, es bringt visuel viel mehr.
Es gab einige shumps die portiert wurden von arcades und consoles und du konntest die rotation oder skalierung nicht einfrieren ohne das gameplay sehr zu aendern.

aber sag mir mal wie du den startpunkt in der sprite grafik ermitteln willst, wenn der opere rand abgeschnitten ist (die oberen N zeilen ausserhalb des bildschirms liegen), und das sprite nicht 2^n breit ist

wir haben fuer Mul und Div (sowie sin,cos, sqrt) LUTs verwendet. damals (<80x386 bzw 80x486) gab es kein cache etc. da war ein 16bit speicher zugriff billiger als jede multiplikation. Falls du dich also entschieden haettest 17x17 zu verwendet, haettest du ein

short Mul17[17]={...};

erstellt bzw haben wir sowas kritisches in assembler geschrieben, also

Mul17 dw 11h

woher soll einer wissen welche grundlagen du weisst und welche nicht?

BTW: viele DOS Grafik-Engines haben Sprites RLE-komprimiert. Da kann man dann nichtmal mehr mit nem Shift reinadressieren. Schneller war es trotzdem, weil man halt meistens vollständig sichtbare Sprites zeichnet, und die Zeit die man bei den vollständig sichtbaren Sprites mit dem überspringen der durchsichtigen Pixel spart wiegt den Overhead auf den man sich mit teilweise sichtbaren Sprites dabei einhandelt.

RLE war eine moeglichkeit, eine andere war z.B. VQ, beide male hat man durch weniger memory traffic performance gewonnen, VQ erlaubte es jedoch es auch fuer beliebige sprites und sogar texturen zu nutzen.

du willst mir jetzt erzählen dass man VQ dekomprimierung mit einem 386er oder 486er "live" machen kann, ohne dabei langsamer zu werden als unkomprimiert?
RLE wurde ja nicht nur verwendet um speicherbandbreite zu sparen, sondern damals auch hauptsächlich damit transparente bereiche in den sprites komplett übersprungen werden können (=rechenzeit sparen).

jap, VQ ist schneller als RAW sprites und texturen, wenn du transformationen hast auf CPUs die cache haben.
z.B. aus den worten einer externen quelle:

http://www.gamasutra.com/view/feature/131499/image_compression_with_vector_.php?page=2 schrieb:

When we put the VQ compression described above in our renderer, we expected to get slightly worse performance but were ready to live with it, because it took about 20MB off our memory footprint. However, profiles showed that rendering has actually gained about 15 to 20 percent performance, probably due to decreased memory traffic.

neben caches auf CPU musstest du auch segmente wechseln und mit der zeit auch sowas wie XMS, EMS etc. arbeiten. die renderreihenfolge war mehr oder weniger vorgegeben, sodass es ebenfalls gut war den speicher kompakt zu halten um moeglichst wenig switching zu haben.

[hustbaer]

Ja, an Lookup-Tables für Multiplikationen hab' ich jetzt nicht gedacht.

auf 8086 mit 4.77MHz hast du Po2 verwendet, weil indizieren in eine nicht Po2 palette von sprites schon zuviel der Muls waere.

Kann man allerdings auch über nen einfachen Lookup-Table machen.

Gerade zu DOS-Zeiten hatte man ja oft keine klassischen Sprite-Sheets, sondern einfach die Sprite-Grafiken irgendwo im Speicher liegen.
Statt einem Shift kann man dann genau so gut die Startadresse von Sprite N aus einem Table laden.

Bei Rotation etc. hast du natürlich recht - das geht mit beliebigen Grössen überhaupt nicht gut, weil man zu oft multiplizieren müsste. Wobei man natürlich auch hier wieder LUTs verwenden könnte - langsamer als mit power-of-two Grafiken wird das aber vermutlich auch sein.

[raps]

hustbaer schrieb:

Ja, an Lookup-Tables für Multiplikationen hab' ich jetzt nicht gedacht.

auf 8086 mit 4.77MHz hast du Po2 verwendet, weil indizieren in eine nicht Po2 palette von sprites schon zuviel der Muls waere.

Kann man allerdings auch über nen einfachen Lookup-Table machen.

problem ist nur dass deine LUT zur compile zeit nicht bekannt ist, muestest du also im 'level' ablegen. haettest also lookup zum lookup, dann lookup, dann erst zugriff auf das asset. waere in alten zeiten schon ein wenig aufwendig (zumal es vermutlich nicht mit 16bit getan waere, also 32bit reads (seg:offset) und das mehrmals.

Gerade zu DOS-Zeiten hatte man ja oft keine klassischen Sprite-Sheets, sondern einfach die Sprite-Grafiken irgendwo im Speicher liegen.
Statt einem Shift kann man dann genau so gut die Startadresse von Sprite N aus einem Table laden.

je nachdem wieviel cycles du dafuer verschwenden moechtest. irgendwie dachte man da frueher anders drueber. ich hatte neben jeder meiner c zeilen die anzahl der zyklen stehen und alles was ein wenig zeit brauchte, von simplen clear, ueber memcpy etc. wurde dann eh frueher oder spaeter in assembler gewandelt. pro sprite 10cycles oder so verschwenden haette einem programmiererherz wehgetan ;), heute schert sich die welt nichtmal bei pixelshadern so drum wie damals beim cpu code.

Bei Rotation etc. hast du natürlich recht - das geht mit beliebigen Grössen überhaupt nicht gut, weil man zu oft multiplizieren müsste. Wobei man natürlich auch hier wieder LUTs verwenden könnte - langsamer als mit power-of-two Grafiken wird das aber vermutlich auch sein.

fuer performance haette man damals alles getan, das ist heute irgendwie schwer rational zu erklaeren.

[hustbaer]

raps schrieb:

hustbaer schrieb:

Ja, an Lookup-Tables für Multiplikationen hab' ich jetzt nicht gedacht.

auf 8086 mit 4.77MHz hast du Po2 verwendet, weil indizieren in eine nicht Po2 palette von sprites schon zuviel der Muls waere.

Kann man allerdings auch über nen einfachen Lookup-Table machen.

problem ist nur dass deine LUT zur compile zeit nicht bekannt ist, muestest du also im 'level' ablegen. haettest also lookup zum lookup, dann lookup, dann erst zugriff auf das asset. waere in alten zeiten schon ein wenig aufwendig (zumal es vermutlich nicht mit 16bit getan waere, also 32bit reads (seg:offset) und das mehrmals.

verstehe ich grad nicht was du meinst. du kannst in jedem fall den shift durch einen einzigen lookup ersetzen. wenn die frame-anzahl bekannt ist, dann kann der table auch auf einer konstanten adresse sitzen, so dass kein load nötig ist um die table-startadresse zu laden. ob die werte bereits vom compiler/linker beim bauen reingeschrieben werden, oder erst beim laden des levels, spielt dabei ja keine rolle.
u.u. kann man sich sogar die addition der "base address" sparen - wenn man flat-mode verwendet bzw. sowieso alles in 64KB platz hat kann man ja fertige adressen in den table reinschreiben.

klar, es wäre etwas mehr aufwand, und so lange kein guter grund dafür spricht wird man es dann nicht machen. rein von der geschwindigkeit her sehe ich da aber kein echtes problem.

ich hatte neben jeder meiner c zeilen die anzahl der zyklen stehen und alles was ein wenig zeit brauchte, von simplen clear, ueber memcpy etc. wurde dann eh frueher oder spaeter in assembler gewandelt. pro sprite 10cycles oder so verschwenden haette einem programmiererherz wehgetan ;), heute schert sich die welt nichtmal bei pixelshadern so drum wie damals beim cpu code.

da hast du sicher auch recht. ich glaube nur dass damals z.T. auch sachen optimiert wurden, die schon damals egal waren. weil es damals einfach OK war dinge bis zum abwinken zu optimieren, und optimieren macht spass, also optimiert man einfach alles - egal ob es sinn macht oder nicht.
10 zyklen pro sprite sparen, wenn das zeichnen des sprites insgesamt 50-100 zyklen braucht ist ja noch OK. 10 zyklen sparen wenn das zeichnen >= 1000 zyklen braucht ist mMn. sinnfrei. bzw. war es auch damals schon.

Bei Rotation etc. hast du natürlich recht - das geht mit beliebigen Grössen überhaupt nicht gut, weil man zu oft multiplizieren müsste. Wobei man natürlich auch hier wieder LUTs verwenden könnte - langsamer als mit power-of-two Grafiken wird das aber vermutlich auch sein.

fuer performance haette man damals alles getan, das ist heute irgendwie schwer rational zu erklaeren.

ja... ich hab die zeit ja noch am rande miterlebt. ich hab' zwar damals keinen produktiven code geschrieben, aber ich hab' am amgia 500 zu programmieren angefangen (erst assembler, später dann C). waren zwar alles nur hobby-projekte, und kaum etwas ist wirklich fertig geworden. aber was man da alles machen konnte (und auch gemacht hat) um performance zu schinden ist mir zumindest nicht ganz fremd.