Artikelempfehlungen, interessante Publikationen o.Ä.

[Alexander Kornrumpf]

Das kam gerade über twitter rein, und da ich weiß dass mindestens Thomas sich mit sowas beschäftigt, geb ich es einfach mal weiter ohne es selbst gelesen zu haben:

Navigation Queries from Triangular Meshes
http://graphics.ucmerced.edu/papers/10-mig-navq.pdf

[Tejio]

Von Nex, erschienen am 30.06.2010
http://dailydpad.de/6711/in-game-moral- ... n-spielen/

[anonym]

Principles of Digital Image Synthesis, Volume 1, Andrew S. Glassner, Morgan Kaufmann Publishers, 1995
Principles of Digital Image Synthesis, Volume 2, Andrew S. Glassner, Morgan Kaufmann Publishers, 1995
via Real-Time Rendering

[Chromanoid]

DiGRA Digital Library
Hier gibt es die teils sehr interessanten Beiträge zu den Konferenzen der "Digital Games Research Association" zum Herunterladen.

Ein Artikel den ich interessant finde:
The Quest in a Generated World, Ashmore Calvin & Nitsche Michael, Situated Play, Tokyo: The University of Tokyo, September, 2007
Ein Artikel über das Generieren von Quests


Kleine Anmerkung: Bei Links bitte wenigstens den Titel des ganzen mit angeben, sonst wird das so chaotisch. Am Besten einfach das Template im ersten Beitrag benutzen...

[Alexander Kornrumpf]

A Survey of General-Purpose Computation on Graphics Hardware

http://www.idav.ucdavis.edu/publication ... pub_id=907

Älterer Artikel der technisch schon überholt ist. Postenswert fand ich aber vor allem die Grafik auf S. 89 (10) Figure 5 wie katastrophal MSVC gegenüber dem Intel-Compiler abschneidet.

[TheBenji]

http://www.wolfgang-back.com/knowhow_home.php ;-)

Sowas in der Art haben wir tatsächlich auch mal in der Berufsschule benutzt.
Es nannte sich dort "Bleistiftcomputer".
Es war ein Blatt papier was aber sonst im Prinzip genauso funktioniert hat, wirklich schön um die grundfunktionen darzustellen.
Aber heutzutage ist der unterschied zwischen der einfachheit dieses papiercomputers und einem higth-tech laptop wohl einfach zu krass als das sich jeder was darunter vorstellen kann.
Ich persönlich fand das eine super Idee mit dem Bleistiftcomputer (und es war auch sehr unterhaltsam) aber ich habe auch da schon gemerkt das es für eingie einfach zu hoch ist *lach*

[CodingCat]

Der gigantische Verschnitt von PSSM hat mich schon immer geärgert, hätte ich Zeit, würde ich das hier auf der Stelle testweise implementieren:
http://visual-computing.intel-research. ... ions/sdsm/ (akkurate Partitionierung des Frustums basierend auf dem bereits gerenderten Tiefenbild, d.h. tatsächlich sichtbaren Pixeln)

[Krishty]

Optimizing software in C++ — An optimization guide for Windows, Linux and Mac platforms
http://www.agner.org/optimize/optimizing_cpp.pdf

Leider in einigen Teilen überholt, aber vieles hat weiterhin seine Gültigkeit. Meine Notizen:

• „Pointers versus references“ auf Seite 36 ist oberflächlich. Natürlich sind Zeiger und Referenzen an sich gleich schnell; allerdings: In dem Augenblick, in dem ich eine Variable zu einem Zeiger statt einer Referenz mache, ist ein nullptr-Zustand explizit erlaubt und ich muss – im Gegensatz zur Nutzung einer Referenz – auch Arbeit aufwenden um diesen entsprechend zu behandeln. Ob ich mit Zeigern oder Referenzen arbeite hat eine fundamental unterschiedliche Semantik und kann es mir selten frei aussuchen, auch, wenn die Rohleistung gleich ist.
• „7.10 Arrays“ auf Seite 38 ist unvollständig. Statt ein Array-Attribut mit memset() zu nullen, kann ich Default-Konstruktion erzwingen (:a() in der Initialisierungsliste), die bei PoD-Typen immer in Nullinitialisierung resultiert. Da dem Compiler deren Auswirkung – im Gegensatz zu einem memset()-Aufruf – als der Sprache inhärente Eigenschaft bekannt ist, kann es mindestens gleich gut optimiert werden, wenn nicht gar besser.
• „Use inline functions“ auf Seite 48 ist Unsinn. Das inline-Schlüsselwort hat nichts damit zu tun, ob der Compiler eine Funktion inlinet. Außerdem entscheiden das aktuelle Compiler völlig eigenmächtig (bei Visual C++ mit LTCG weiß ich das sicher, bei GCC aus zweiter Hand).
• „Use fastcall functions“, Seite 49: Unsinn. Mit globalen Optimierungen entscheidet der Compiler die optimalen Aufrufkonventionen eigenständig; wenn man überall __fastcall reinhaut macht man ihm das eher noch kaputt. Für x64 gilt es sowieso nicht.
• „7.21 Runtime type identification (RTTI)“, Seite 54: „Runtime type identification adds extra information to all class objects and is not efficient.“ Komplett falsch. Information wird nicht Instanzen hinzugefügt, sondern Typen, und zwar nur solchen, die bereits polymorph sind (also bereits über virtuelle Funktionen verfügen; dort geschieht die Typbestimmung über die eh vorhandene Virtual Function Table). Ein Spezialfall sind Instanzen, die im Zuge einer Ausnahme geworfen oder gefangen werden – aber auch wirklich nur die (nicht alle Instanzen ihres Typs) … und wenn ich aufzählen würde, was der Compiler bei Ausnahmen außer RTTI noch alles an Informationen dranhängt, würde den meisten schlecht werden. Außer zusätzlichen Bytes Read-Only-Daten hat RTTI so gut wie keinen Einfluss auf die Programmleistung und erledigt seinen Zweck üblicherweise besser als es selbergebaute Lösungen tun.
• „Do not make a destructor if it is not necessary“ auf Seite 55 kann ich nur unterstreichen – gerade Visual C++ hat extreme Probleme mit der Optimierung von D’toren, selbst, wenn sie leer sind.
• „7.25 Bitfields“ auf Seite 55: Was nicht erwähnt ist, ist, dass der Compiler für Zugriffe auf Bit Fields mehr Maschinentext erzeugt und man vorsichtig sein muss, dass dieser Mehrverbrauch den gespeicherten Platz nicht wieder aufbraucht.
• Über „7.30 Exceptions and error handling“ auf Seite 60 lässt sich auch streiten – es gibt viele Beispiele, in denen Exception Handling weitaus performantere Programme liefert als herkömmliche Fehlerbehandlung (u.A. den schon leistungskritischen PlayStation 2-Emulator PCSX2) weil die Mehrkosten für Stack Unwinding durch gesparte Sprünge bei der Auswertung von Rückgabewerten, höhere Lokalität und besseren Programmentwurf mit Leichtigkeit ausgeglichen werden. Gegenteile Benchmarks kommen in der Regel von Leuten, die Fehlerbehandlung mit Nichtstun gleichsetzen. Wer Exception Handling verinnerlicht hat, wird damit üblicherweise leistungsfähigere Programme schreiben; wer noch in der Return Value-Mentalität festhängt, wird über Leistungseinbußen fluchen. (Wie es mit Structured Exception Handling aussieht, weiß ich nicht – aber das brauchen sowieso die wenigsten Programme.)
• Funktionen throw() zu deklarieren, wie auf Seite 61 empfohlen, ist vergebene Liebesmüh’. Ich habe es mit 400 gemacht und es hat nicht ein Bit Unterschied bewirkt; offensichtlich kriegt Visual C++’ LTCG das ganz gut alleine hin. Die einzige Stelle, wo es lohnt, sind Deklarationen von Funktionen aus dynamischen Bibliotheken, die LTCG nicht kennen und analysieren kann – aber sowas hat man eh eher selten an leistungskritischen Stellen. Ganz abgesehen davon, dass es kein vertretbarer Wartungsaufwand ist.
  Eine Ergänzung zu __restrict auf Seite 76: Bei Visual C++ hat es keine Auswirkung mehr, weil LTCG Aliasing mittlerweile sehr gut ausschließen kann; selber dekorieren lohnt nicht mehr.
• „Keywords that work on all C++ compilers“, Seite 81: register hat schon lange keine Wirkung mehr und const hat so gut wie keine Auswirkung auf Optimierungen. Man nutzt es, um Wirkungen zu kontrollieren, und nicht, um Optimierungen zu steuern.

Die wirkungsvollste Optimierung ist also im Augenblick, globale Optimierungen / Whole Program Optimization / Link-Time Code Generation / Wieauchimmereseuercompilerherstellernennt zu aktivieren.

[Chromanoid]

Lectures der Casual Connect sind kostenlos online zu sehen (slides zum runterladen sind auch dabei):
http://europe.casualconnect.org/content.html

[Schrompf]

Eine Menge aktuellen Materials für Spieleentwickler findet sich unter http://www.gdcvault.com/free/gdc-11 - leider ist eine Menge davon nur als Video verfügbar. Das macht die Konsumierung etwas mühsamer.

[Top-OR]

@Schrompf: Danke für die Quelle. Da sind ja ein paar sehr interessante Schätzchen dabei. Besonders die "klassischen" Videos/Folien über Doom oder Maniac Mansion hab ich wirklich genossen. Seeeehr schön, dankesehr!

[donelik]

Viele Physik-Engines wollen am Liebsten immer einen festen Wert als "delta timestep" übergeben bekommen. Wie kann man das erreichen? Herr Fiedler erklärt das m.E. ziemlich gut:

http://gafferongames.com/game-physics/f ... -timestep/

Ich finde die Idee mit der Interpolation ziemlich genial.

[Chromanoid]

Übersichtsseiten zu Publikationen verschiedener Firmen:

Valve
Von Rendering Wounds in Left 4 Dead 2 bis Valve's Approach to Playtesting: The Application of Empiricism ist alles dabei.

Crytek
Vor allem technische Aspekte werden hier vorgestellt.

Dice
Alle Gebiete der Spieleentwicklung sind hier übersichtlich aufgeführt und vertreten.

[RustySpoon]

Depixelizing Pixel Art

Es wird ein Algorithmus vorgestellt, der 8-Bit Sprites vektorisiert. Die Ergebnisse sind imho ungefähr vergleichbar mit hq4x, nur das man halt hinterher 'ne vorteilhafte Vektorgrafik hat.

Bekommt man doch gleich Bock, das SNES mal wieder rauszukramen.

[Tejio]

Heise Developer: Einleitung zu eventbasierten Komponenten
Einstieg in das Thema Eventbasierte Komponenten
Beschreibung des Zusammenspiels der Komponenten
Ein Muster für EBC

Durch Heise bin ich auf dieses Thema gestoßen, vllt kann jemand damit etwas anfangen ;)

[Krishty]

The Architecture of Open Source Applications
Die Architektur von quelloffenen Anwendungen erklärt; von Eclipse & LLVM bis Audacity.

[Mr. S]

Tolle DirectX-Tutorials, vergleichbar mit den alten ZFX-Artikeln. Nur halt DX9 und nicht 8:

http://www.chadvernon.com/blog/resources/directx9/

[eXile]

Loop Recognition in C++/Java/Go/Scala von Robert Hundt, Google.

Der Titel hört sich zuerst wie ein abstraktes Paper zur Programmanalyse aus der funktionalen Programmierung an. Dem ist aber nicht so. Ziel der Veröffentlichung ist ein „fairer Vergleich“ der Sprachfeatures, Codekomplexität, Compiler, Zeit zum Kompilieren und der resultierenden Programmgröße, Laufzeit und Speicherverwendung der oben genannten Programmiersprachen.

Leider musste ich auch solche Sachen lesen:

Doug Rhode created a greatly improved version, which improved performance by 3x to 5x. […] At the time of this writing, the code was heavily dependent on several Google internal data structures and could not be open sourced.

Dennoch wird diese optimierte Version zu Vergleichszwecken herangeführt. In solchen Fällen muss ich leider – obwohl der Rest der Veröffentlichung sehr fundiert aussieht – sagen, dass keine wissenschaftliche Nachprüfbarkeit besteht, und darum dies für Vergleichszwecke ungeeignet ist. Ich halte Hundt dennoch zu Gute, dass er sehr detailliert die dabei enthaltenen Änderungen erläutert hat. Leider erklärt er nicht, wofür denn nun eigentlich die „ Google internal data structures“ verwendet werden – an der Stelle habe ich das Gefühl, dass Teile der „magic sauce“ nicht offengelegt werden sollen. Die nach dem Zitat folgende Änderungsliste referenziert nämlich deren interne Datenstrukturen in keiner Weise. Ebenso meine ich zu erkennen, dass bei der C++-Version erheblich mehr Optimierungsaufwand betrieben wurde (unabhängig von der Verwendung von externen Libraries, die ja gar nicht zur Sprache gehören).

Schließlich macht dies es auch unmöglich, den Implementierungsaufwand abzuschätzen. So kommt er auch zum Schluss:

We find that in regards to performance, C++ wins out by a large margin. However, it also required the most extensive tuning efforts, many of which were done at a level of sophistication that would not be available to the average programmer.

Ein weiterer Kritikpunkt könnte sein, dass eine Optimierung der Programmgröße nicht stattfand. Die Wichtigkeit betont Hundt aber selber:

It should also be noted that for large binaries, plain binary size matters a lot, as in distributed build systems, the generated binaries need to be transferred from the build machines, which can be bandwidth limited and slow.

Abschließend muss ich noch erwähnen, dass natürlich ein Algorithmus ausgewählt wurde, der sehr, sehr stark mit Googles Beschäftigungsfeld im Zusammenhang steht: Graphtraviersierung und Schleifenerkennung in Graphen. Es aber schön zu sehen, dass die Hauptbeschleunigung bei der Optimierung der C++-Version durch die Wahl anderer Algorithmen (hash_map, Wahl der Haskkeys, etc.) zu Stande kam.

[Chromanoid]

Wenn man Performance verschiedener Sprachen vergleichen möchte, finde ich diese Benchmark-Seite eigentlich nicht schlecht: The Computer Language Benchmarks Game

[eXile]

Das ist jetzt zwar nur ein kleiner Link, aber vielleicht doch für einige interessant. Die Tabelle zeigt den aktuellen Stand der Implementierung von C++0x-Sprachfeatures in den Compilern verschiedener Hersteller.

http://wiki.apache.org/stdcxx/C++0xCompilerSupport

(Leider ist die Tabelle doch ein wenig undetailliert, darum immer als Ergänzung noch die und die hier daneben legen.)

[Thoran]

Sehr interessanter Blog-Artikel über Hobbyspieleentwicklung, für all diejenigen, die des Englischen mächtig sind.
6 Challenges to the Hobbyist Game Developer, and How to Overcome Them

Thoran

[Top-OR]

Ist das ne Anspielung auf Hobbyprojekte? ^^

Error establishing a database connection

[Krishty]

War bei mir auch; geht wieder ;)

WLARGH zu früh kluggeschissen

[Top-OR]

Über den Link kommt bei mir immernoch der Fehler, aber über die Startseite kommt man ja auch zu Artikel: Sehr interessant, finde ich - und stimmen tuts auch. (Zumindest das, was ich gelesen habe.)

[CodingCat]

Typical C++ Bullshit - Provokant. Lehrreich? Denkanstöße.

[eXile]

Typical C++ Bullshit - Provokant. Lehrreich? Denkanstöße.

Naja, irgendwelchen hergelaufenen Code (welcher vermutlich in wenigen Minuten runtergehackt wurde) zu kritisieren stufe ich jetzt als minder sinnvoll ein. Außer man macht sich einen Spaß daraus, in zehn Minuten etwas hinzuklatschen, was andere dann stundenlang kritisieren, und man sich über deren verlorene Zeit erfreut. Natürlich hat der Code Macken. Natürlich geht es besser, und ich bin dem Autor auch dankbar, eben solche Denkanstöße zu bieten. Aber es gibt nun einmal solchen und solchen Code: Einerseits für Programme, die einmal laufen, und dann gelöscht werden könnten, andererseits Heimprojekte, die man stundenlang bis zur scheinbar perfekten Lösung massiert. Meine Pseudocode-VM war ein Programm der ersten Kategorie: Schnell geschrieben, sehr langsam, hat seine Aufgabe gelöst, Code ging ins Archiv und bleibt dort auch für immer.

Lustig fande ich die Stelle „When was the last time you had (exactly) one plane and (exactly) one sphere?“. Na ganz offentlich genau hier. Sonst hätte der das ja nicht implementiert. Seine Hipster-Postits kann er da auch bleiben lassen.

[Top-OR]

Mensch, ein Glück sagt das mal jemand. Ich hatte schon ein schlechtes Gewissen, weil ich meine Heugabel und Fackel irgendwie nicht rauskramen wollte/konnte.

Sooo schlimm finde ich das Konstrukt nicht; außer dass es kein Klassenmenber ist, sondern freifliegend, die Formatierung nicht mit meiner persönlichen Norm übereinstimmt und und und ...

Nee, im Ernst. Es erfüllt sicher seinen Zweck. Vielleicht geht der Code auch eleganter/schneller, aber wichtiger ist, dass das Projekt auch mal läuft und seinen Sinn erfüllt. Man kann JAHRE an Software rumdesignen und keinen Schritt weiter kommen. Man kann IMMER etwas bemängeln, wenn man das will ...

[Krishty]

Ihr habt doch keine Ahnung … ich meine: Das Programm schreibt in ein Attribut statt in eine lokale Variable. Wenn ihr nur halb so viel Ahnung hättet wie Mike, würdet ihr jetzt hamsterkaufen gehen!

Das Problem an dem Artikel ist sein Titel. Mikes Aufgabe war „Optimize this!“ (siehe Bild 3). Und er analysiert den Text tatsächlich ziemlich gut unter dem alleinigen Gesichtspunkt der Leistung – Lokalität, Konvertierungen, Verzweigungen. Leider lässt einen der Titel glauben, er analysiere das Fragment generell auf Qualität. Die spielt hier aber keine Rolle. Stellt euch einfach vor, da stünde „Typical Perfomance Bullshit“ drüber (Doppeldeutigkeit erwünscht).

[Top-OR]

"Von Einem" ... was? Und was soll ich mit nem Hamster?

in ein Attribut statt in eine lokale Variable

Tut es das? O_o

Ich seh nur ne freifliegende Funktion, die zu keiner Klasse gehört (naja). Wie hätte mans "richtiger" lösen können?

[eXile]

Ihr habt doch keine Ahnung … ich meine: Das Programm schreibt in ein Attribut statt in eine lokale Variable.

Und woran soll ich das jetzt genau sehen? Das steht dort nirgends, dass man das vielleicht nicht doch braucht (wie viele Threads laufen da überhaupt?). Was ich kritisiere ist, dass er dort herumkritisiert, aber seine Kritik nicht nachvollziehbar darlegt. Das fängt beim Titel an, geht weiter mit seinen Post-its die die Hälfte vom Bild verdecken, dem Code, welchen man sich aus mehreren Bildern zusammenbasteln muss, und darüber hinaus das aller Gravierendste: So ist überhaupt gar keine algorithmische Optimierung möglich. Woher soll ich als Leser wissen, dass vielleicht nicht doch eine Funktion, welche exakt zwei solche Objekte entgegen nimmt, in diesem Falle genau das richtige ist, weil es nun einmal der Algorithmus so vorsieht? Warum nicht Tests vermeiden, statt bloß ihre Reihenfolge zu ändern? Die Bezeichnung „Typical C++ Bullshit“ ist falsch, die Bezeichnung „Typical Perfomance Bullshit“ immer noch.

Hätte das Paper einen Titel verdient, wäre es wohl eher „Common low-level inefficiencies when writing code in five minutes in C/C++“. In diesem Falle gebe ich dem Autor Recht. Nur eine Überschrift zu wählen, welche ein gigantisches Publikum anzieht, um dann doch nur alles bis auf einen ganz kleinen Aspekt zu reduzieren, ist Etikettenschwindel und Bauernfängerei.

Nachtrag: Offensichtlich habe ich meinen Ironiedetektor fehlkalibriert. Dennoch meine ich das wirklich, was ich hier geschrieben habe. ;)

>My face when I was finished with Mikes paper: