Fallstudie – Inside World Wide Maze

Saqoosha

World Wide Maze ist ein Spiel, bei dem Sie mit Ihrem Smartphone einen rollenden Ball durch 3D-Labyrinthe steuern, die aus Websites erstellt wurden, um die Zielpunkte zu erreichen.

Das Spiel nutzt zahlreiche HTML5-Funktionen. Das Ereignis DeviceOrientation ruft beispielsweise Neigungsdaten vom Smartphone ab, die dann über WebSocket an den PC gesendet werden. Dort können sich die Spieler durch 3D-Bereiche bewegen, die mit WebGL und Web Workers erstellt wurden.

In diesem Artikel erkläre ich genau, wie diese Funktionen verwendet werden, wie der gesamte Entwicklungsprozess abläuft und welche Punkte für die Optimierung wichtig sind.

DeviceOrientation

Mit dem Ereignis „DeviceOrientation“ (Beispiel) werden Neigungsdaten vom Smartphone abgerufen. Wenn addEventListener mit dem Ereignis DeviceOrientation verwendet wird, wird in regelmäßigen Abständen ein Callback mit dem DeviceOrientationEvent-Objekt als Argument aufgerufen. Die Intervalle selbst variieren je nach verwendetem Gerät. Beispiel: In iOS + Chrome und iOS + Safari wird der Rückruf etwa alle 20 Sekunden aufgerufen, während er in Android 4 + Chrome etwa alle 10 Sekunden aufgerufen wird.

window.addEventListener('deviceorientation', function (e) {
  // do something here..
});

Das DeviceOrientationEvent-Objekt enthält Neigungsdaten für jede der Achsen X, Y und Z in Grad (nicht in Radian). Weitere Informationen auf HTML5Rocks Die Rückgabewerte variieren jedoch auch je nach verwendeter Geräte- und Browserkombination. Die Bereiche der tatsächlichen Rückgabewerte sind in der folgenden Tabelle aufgeführt:

Die oben blau hervorgehobenen Werte sind in den W3C-Spezifikationen definiert. Die grün hervorgehobenen entsprechen diesen Spezifikationen, während die rot hervorgehobenen davon abweichen. Überraschenderweise wurden nur mit der Kombination aus Android und Firefox Werte zurückgegeben, die den Spezifikationen entsprachen. Bei der Implementierung ist es jedoch sinnvoller, häufig vorkommende Werte zu berücksichtigen. World Wide Maze verwendet daher standardmäßig die iOS-Rückgabewerte und passt sie für Android-Geräte entsprechend an.

if android and event.gamma > 180 then event.gamma -= 360

Nexus 10 wird jedoch weiterhin nicht unterstützt. Obwohl das Nexus 10 denselben Wertebereich wie andere Android-Geräte zurückgibt, gibt es einen Fehler, durch den die Beta- und Gammawerte umgekehrt werden. Dies wird separat bearbeitet. (Vielleicht ist das Querformat die Standardeinstellung?)

Wie dieses Beispiel zeigt, gibt es keine Garantie dafür, dass die zurückgegebenen Werte den Spezifikationen entsprechen, auch wenn für APIs mit physischen Geräten festgelegte Spezifikationen gelten. Daher ist es wichtig, sie auf allen potenziellen Geräten zu testen. Außerdem können unerwartete Werte eingegeben werden, für die dann Umgehungslösungen erforderlich sind. In World Wide Maze werden Neulinge in Schritt 1 des Tutorials aufgefordert, ihre Geräte zu kalibrieren. Die Kalibrierung auf die Nullposition funktioniert jedoch nicht richtig, wenn unerwartete Neigungswerte empfangen werden. Daher gibt es ein internes Zeitlimit und der Spieler wird aufgefordert, zur Tastatursteuerung zu wechseln, wenn die Kalibrierung innerhalb dieses Zeitlimits nicht abgeschlossen werden kann.

WebSocket

In World Wide Maze sind Ihr Smartphone und Ihr PC über WebSocket verbunden. Genauer gesagt sind sie über einen Relay-Server miteinander verbunden, d.h. Smartphone zu Server zu PC. Das liegt daran, dass WebSocket keine Möglichkeit bietet, Browser direkt miteinander zu verbinden. Die Verwendung von WebRTC-Datenkanälen ermöglicht eine Peer-to-Peer-Verbindung und macht einen Relay-Server überflüssig. Zum Zeitpunkt der Implementierung konnte diese Methode jedoch nur mit Chrome Canary und Firefox Nightly verwendet werden.

Ich habe mich für die Implementierung einer Bibliothek namens Socket.IO (Version 0.9.11) entschieden, die Funktionen für die Wiederherstellung einer Verbindung bei einer Verbindungs-Zeitüberschreitung oder einer Trennung enthält. Ich habe es zusammen mit NodeJS verwendet, da diese Kombination aus NodeJS und Socket.IO in mehreren WebSocket-Implementierungstests die beste serverseitige Leistung zeigte.

Koppeln nach Nummern

1. Ihr PC stellt eine Verbindung zum Server her.
2. Der Server weist Ihrem PC eine zufällig generierte Zahl zu und merkt sich die Kombination aus Zahl und PC.
3. Geben Sie auf Ihrem Mobilgerät eine Nummer an und stellen Sie eine Verbindung zum Server her.
4. Wenn die angegebene Nummer mit der Nummer eines verbundenen PCs übereinstimmt, ist Ihr Mobilgerät mit diesem PC gekoppelt.
5. Wenn kein PC zugewiesen ist, tritt ein Fehler auf.
6. Wenn Daten von Ihrem Mobilgerät eingehen, werden sie an den PC gesendet, mit dem es gekoppelt ist, und umgekehrt.

Sie können die Erstverbindung auch über Ihr Mobilgerät herstellen. In diesem Fall werden die Geräte einfach umgekehrt.

Tab-Synchronisierung

Die Chrome-spezifische Tab-Synchronisierungsfunktion macht das Koppeln noch einfacher. Damit können Seiten, die auf dem Computer geöffnet sind, ganz einfach auf einem Mobilgerät geöffnet werden (und umgekehrt). Der PC nimmt die vom Server ausgestellte Verbindungsnummer und fügt sie mit history.replaceState an die URL einer Seite an.

history.replaceState(null, null, '/maze/' + connectionNumber)

Wenn die Tab-Synchronisierung aktiviert ist, wird die URL nach wenigen Sekunden synchronisiert und dieselbe Seite kann auf dem Mobilgerät geöffnet werden. Das Mobilgerät prüft die URL der geöffneten Seite. Wenn eine Nummer angehängt ist, wird sofort eine Verbindung hergestellt. So müssen Sie keine Zahlen manuell eingeben oder QR-Codes mit einer Kamera scannen.

Latenz

Da sich der Relay-Server in den USA befindet, dauert es etwa 200 ms, bis die Neigungsdaten des Smartphones den PC erreichen, wenn darauf von Japan aus zugegriffen wird. Die Reaktionszeiten waren im Vergleich zu denen der lokalen Umgebung, die während der Entwicklung verwendet wurde, deutlich langsam. Durch Einfügen eines Tiefpassfilters (ich habe EMA verwendet) konnte ich sie jedoch auf ein unauffälliges Niveau senken. In der Praxis war ein Tiefpassfilter auch für Präsentationszwecke erforderlich. Die Rückgabewerte des Neigungssensors enthielten eine erhebliche Menge an Rauschen und die Anwendung dieser Werte auf das Display führte zu starken Erschütterungen. Das funktionierte nicht bei Sprüngen, die deutlich träge waren, aber es konnte nichts unternommen werden, um das Problem zu beheben.

Da ich von Anfang an mit Latenzproblemen gerechnet habe, habe ich erwogen, Relay-Server auf der ganzen Welt einzurichten, damit sich Clients mit dem nächstgelegenen verfügbaren Server verbinden und so die Latenz minimieren können. Ich habe jedoch die Google Compute Engine (GCE) verwendet, die damals nur in den USA verfügbar war.

Das Problem des Nagle-Algorithmus

Der Nagle-Algorithmus wird in der Regel in Betriebssysteme für eine effiziente Kommunikation durch Puffern auf TCP-Ebene eingebunden. Ich habe jedoch festgestellt, dass ich keine Daten in Echtzeit senden konnte, während dieser Algorithmus aktiviert war. (Insbesondere in Kombination mit der verzögerten TCP-Bestätigung. Auch wenn ACK nicht verzögert ist, tritt dasselbe Problem auf, wenn ACK aufgrund von Faktoren wie dem Standort des Servers im Ausland in gewissem Maße verzögert ist.)

Das Nagle-Latenzproblem trat nicht bei WebSockets in Chrome für Android auf, da diese die Option TCP_NODELAY zum Deaktivieren von Nagle haben. Es trat jedoch bei WebKit-WebSockets in Chrome für iOS auf, bei denen diese Option nicht aktiviert ist. (Safari, das dasselbe WebKit verwendet, hatte ebenfalls dieses Problem. Das Problem wurde über Google an Apple gemeldet und wurde offenbar in der Entwicklungsversion von WebKit behoben.

In diesem Fall werden Neigungsdaten, die alle 100 ms gesendet werden, in Chunks kombiniert, die den PC nur alle 500 ms erreichen. Das Spiel kann unter diesen Bedingungen nicht funktionieren. Daher wird diese Latenz vermieden, indem die Serverseite in kurzen Intervallen (etwa alle 50 ms) Daten sendet. Ich glaube, dass der Empfang von ACK in kurzen Intervallen den Nagle-Algorithmus dazu verleitet, zu glauben, dass es in Ordnung ist, Daten zu senden.

In den Diagrammen oben sind die Intervalle der tatsächlich empfangenen Daten dargestellt. Er gibt die Zeitintervalle zwischen den Paketen an. Grün steht für Ausgabeintervalle und Rot für Eingabeintervalle. Der Mindestwert liegt bei 54 ms, der Höchstwert bei 158 ms und der Mittelwert bei etwa 100 ms. Hier habe ich ein iPhone mit einem Relay-Server in Japan verwendet. Sowohl die Ausgabe als auch die Eingabe dauern etwa 100 Millisekunden und die Bedienung ist flüssig.

In diesem Diagramm sind dagegen die Ergebnisse der Nutzung des Servers in den USA zu sehen. Während die grünen Ausgabeintervalle bei 100 ms konstant bleiben, schwanken die Eingabeintervalle zwischen 0 ms und 500 ms. Das bedeutet, dass der PC Daten in Chunks empfängt.

Dieses Diagramm zeigt schließlich die Ergebnisse, die durch die Vermeidung von Latenz erzielt werden, wenn der Server Platzhalterdaten sendet. Die Leistung ist zwar nicht ganz so gut wie beim japanischen Server, aber die Eingabeintervalle bleiben relativ stabil bei etwa 100 ms.

Ein Programmfehler?

Obwohl der Standardbrowser in Android 4 (ICS) eine WebSocket API hat, kann keine Verbindung hergestellt werden. Dies führt zu einem Socket.IO-Ereignis vom Typ „connect_failed“. Intern tritt ein Zeitüberschreitungsfehler auf und auch die Serverseite kann keine Verbindung herstellen. (Ich habe das nicht nur mit WebSocket getestet, daher könnte es sich um ein Socket.IO-Problem handeln.)

Relay-Server skalieren

Da die Rolle des Relay-Servers nicht so kompliziert ist, sollte die Skalierung und Erhöhung der Anzahl der Server nicht schwierig sein, solange Sie darauf achten, dass derselbe PC und das Mobilgerät immer mit demselben Server verbunden sind.

Physik

Die Bewegung des Balls im Spiel (Bergabrollen, Zusammenstoß mit dem Boden, Zusammenstoß mit Wänden, Sammeln von Gegenständen usw.) wird mit einem 3D-Physiksimulator durchgeführt. Ich habe Ammo.js verwendet, eine Portierung der weit verbreiteten Bullet-Physik-Engine in JavaScript mit Emscripten, zusammen mit Physijs, um es als „Web Worker“ zu verwenden.

Web Worker

Web Workers ist eine API zum Ausführen von JavaScript in separaten Threads. JavaScript, das als Webworker gestartet wird, wird als separater Thread ausgeführt als der, der es ursprünglich aufgerufen hat. So können anspruchsvolle Aufgaben ausgeführt werden, während die Seite weiterhin reaktionsschnell bleibt. Physijs nutzt Webworker effizient, um die normalerweise intensive 3D-Physik-Engine reibungslos ausführen zu können. World Wide Maze verarbeitet die Physik-Engine und das WebGL-Bild-Rendering mit völlig unterschiedlichen Frameraten. Selbst wenn die Framerate auf einem Computer mit niedrigen Spezifikationen aufgrund einer hohen WebGL-Rendering-Last sinkt, hält die Physik-Engine selbst mehr oder weniger 60 fps aufrecht und beeinträchtigt die Spielsteuerung nicht.

Auf diesem Bild sind die resultierenden Frameraten auf einem Lenovo G570 zu sehen. Im oberen Feld sehen Sie die Framerate für WebGL (Bildrendering) und im unteren die Framerate für die Physik-Engine. Die GPU ist ein integrierter Intel HD Graphics 3000-Chip, sodass die Bildwiederholrate nicht die erwarteten 60 fps erreicht hat. Da die Physik-Engine jedoch die erwartete Framerate erreicht hat, unterscheidet sich das Gameplay nicht wesentlich von der Leistung auf einem leistungsstarken Computer.

Da Threads mit aktiven Webworkern keine Console-Objekte haben, müssen Daten über postMessage an den Hauptthread gesendet werden, um Debugging-Logs zu erstellen. Mit console4Worker wird das Äquivalent eines Konsolenobjekts im Worker erstellt, was den Debug-Prozess erheblich erleichtert.

In aktuellen Versionen von Chrome können Sie beim Starten von Webworkern Haltestellen setzen, was auch für das Debuggen nützlich ist. Sie finden sie im Bereich „Worker“ in den Entwicklertools.

Leistung

Bühnen mit einer hohen Polygonanzahl überschreiten manchmal 100.000 Polygone,die Leistung war aber auch dann nicht besonders beeinträchtigt, wenn sie vollständig als Physijs.ConcaveMesh (btBvhTriangleMeshShape in Bullet) generiert wurden.

Anfangs sank die Framerate, wenn die Anzahl der Objekte, für die eine Kollisionserkennung erforderlich war, zunahm. Durch die Beseitigung unnötiger Verarbeitung in Physijs konnte die Leistung jedoch verbessert werden. Diese Verbesserung wurde an einer Fork der ursprünglichen Physijs-Version vorgenommen.

Geisterobjekte

Objekte, die eine Kollisionserkennung haben, aber keine Auswirkungen auf andere Objekte haben, werden in Bullet als „Geisterobjekte“ bezeichnet. Physijs unterstützt zwar offiziell keine Geisterobjekte, aber es ist möglich, sie dort zu erstellen, indem du nach dem Generieren eines Physijs.Mesh mit den Flags herumspielst. In World Wide Maze werden Ghost-Objekte für die Kollisionserkennung von Objekten und Zielpunkten verwendet.

hit = new Physijs.SphereMesh(geometry, material, 0)
hit._physijs.collision_flags = 1 | 4
scene.add(hit)

Bei collision_flags ist 1 CF_STATIC_OBJECT und 4 CF_NO_CONTACT_RESPONSE. Weitere Informationen finden Sie im Bullet-Forum, auf Stack Overflow oder in der Bullet-Dokumentation. Da Physijs ein Wrapper für Ammo.js ist und Ammo.js im Grunde mit Bullet identisch ist, können die meisten Dinge, die in Bullet möglich sind, auch in Physijs ausgeführt werden.

Das Problem mit Firefox 18

Durch das Firefox-Update von Version 17 auf Version 18 wurde die Art und Weise geändert, wie Webworker Daten austauschen. Dadurch funktionierte Physijs nicht mehr. Das Problem wurde auf GitHub gemeldet und nach einigen Tagen behoben. Diese Open-Source-Effizienz hat mich beeindruckt, aber der Vorfall hat mich auch daran erinnert, dass World Wide Maze aus mehreren verschiedenen Open-Source-Frameworks besteht. Ich schreibe diesen Artikel in der Hoffnung, Ihnen Feedback geben zu können.

asm.js

Obwohl sich dies nicht direkt auf World Wide Maze bezieht, unterstützt Ammo.js bereits die kürzlich von Mozilla angekündigte asm.js. Das ist nicht überraschend, da asm.js im Grunde entwickelt wurde, um von Emscripten generiertes JavaScript zu beschleunigen, und der Erfinder von Emscripten auch der Erfinder von Ammo.js ist. Wenn Chrome auch asm.js unterstützt, sollte die Rechenlast der Physik-Engine erheblich sinken. Die Geschwindigkeit war bei Tests mit Firefox Nightly deutlich höher. Wäre es vielleicht am besten, Abschnitte, die mehr Geschwindigkeit erfordern, in C/C++ zu schreiben und sie dann mit Emscripten in JavaScript zu portieren?

WebGL

Für die WebGL-Implementierung habe ich die am aktivsten entwickelte Bibliothek verwendet: three.js (r53). Obwohl Version 57 bereits in den letzten Entwicklungsphasen veröffentlicht wurde, wurden an der API erhebliche Änderungen vorgenommen. Daher habe ich die ursprüngliche Version für die Veröffentlichung verwendet.

Glühen

Der dem Kern des Balls und den Gegenständen hinzugefügte Glüheneffekt wird mit einer einfachen Version der sogenannten Kawase-Methode MGF implementiert. Während bei der Kawase-Methode alle hellen Bereiche leuchten, werden bei World Wide Maze separate Renderziele für Bereiche erstellt, die leuchten sollen. Das liegt daran, dass für Bühnentexturen ein Screenshot einer Website verwendet werden muss. Wenn einfach alle hellen Bereiche extrahiert werden, würde die gesamte Website leuchten, wenn sie beispielsweise einen weißen Hintergrund hat. Ich habe auch darüber nachgedacht, alles in HDR zu verarbeiten, habe mich aber diesmal dagegen entschieden, da die Implementierung ziemlich kompliziert geworden wäre.

Oben links ist der erste Durchlauf zu sehen, bei dem die glühenden Bereiche separat gerendert und dann unscharf gestellt wurden. Unten rechts ist der zweite Durchlauf zu sehen, bei dem die Bildgröße um 50% reduziert und dann ein Weichzeichner angewendet wurde. Oben rechts ist der dritte Durchlauf zu sehen, bei dem das Bild wieder um 50% verkleinert und dann unscharf gestellt wurde. Die drei Bilder wurden dann überlagert, um das endgültige Bild unten links zu erstellen. Für das Weichzeichnen habe ich VerticalBlurShader und HorizontalBlurShader verwendet, die in three.js enthalten sind. Es gibt also noch Optimierungsmöglichkeiten.

Reflektierender Ball

Die Reflexion auf dem Ball basiert auf einem Beispiel aus three.js. Alle Richtungen werden von der Position des Balls aus gerendert und als Umgebungskarten verwendet. Umgebungskarten müssen jedes Mal aktualisiert werden, wenn sich der Ball bewegt. Da die Aktualisierung mit 60 fps jedoch sehr arbeitsintensiv ist, werden sie stattdessen alle drei Frames aktualisiert. Das Ergebnis ist nicht ganz so flüssig wie bei der Aktualisierung jedes Frames, aber der Unterschied ist praktisch nicht wahrnehmbar, es sei denn, er wird darauf hingewiesen.

Shader, Shader, Shader…

Für das gesamte Rendering in WebGL sind Shader (Vertex-Shader, Fragment-Shader) erforderlich. Die in three.js enthaltenen Shader ermöglichen zwar bereits eine Vielzahl von Effekten, für eine detailliertere Schattierung und Optimierung ist es jedoch unumgänglich, eigene zu schreiben. Da World Wide Maze die CPU mit seiner Physik-Engine beansprucht, habe ich versucht, stattdessen die GPU zu nutzen, indem ich so viel wie möglich in Shading Language (GLSL) geschrieben habe, auch wenn die CPU-Verarbeitung (über JavaScript) einfacher gewesen wäre. Die Ozeanwelleneffekte basieren natürlich auf Shadern, ebenso wie die Feuerwerke bei Toren und der Mesh-Effekt, der beim Erscheinen des Balls verwendet wird.

Das Bild oben stammt aus Tests des Mesh-Effekts, der beim Erscheinen des Balls verwendet wird. Das linke Bild zeigt das Modell, das im Spiel verwendet wird. Es besteht aus 320 Polygonen. Für das mittlere Modell werden etwa 5.000 Polygone verwendet, für das rechte Modell etwa 300.000 Polygone. Selbst bei dieser großen Anzahl von Polygonen kann die Verarbeitung mit Shadern eine stabile Framerate von 30 fps beibehalten.

Die kleinen Elemente, die über die Bühne verstreut sind, sind alle in einem Mesh integriert. Die einzelnen Bewegungen werden durch Shader gesteuert, die die einzelnen Polygonspitzen bewegen. Diese Grafik stammt aus einem Test, bei dem untersucht wurde, ob die Leistung bei einer großen Anzahl von Objekten beeinträchtigt wird. Hier sind etwa 5.000 Objekte zu sehen, die aus etwa 20.000 Polygonen bestehen. Die Leistung hat nicht gelitten.

poly2tri

Die Stadien werden anhand von Informationen zum Umriss gebildet, die vom Server empfangen und dann mit JavaScript in Polygone umgewandelt werden. Die Triangulation, ein wichtiger Teil dieses Prozesses, wird von three.js schlecht implementiert und schlägt in der Regel fehl. Daher habe ich beschlossen, selbst eine andere Triangulationsbibliothek namens poly2tri zu integrieren. Wie sich herausstellte, hatte three.js offenbar schon einmal versucht, dasselbe zu tun. Ich konnte das Problem also einfach beheben, indem ich einen Teil davon kommentierte. Dadurch konnten die Fehler deutlich reduziert werden, sodass viele mehr Level spielbar sind. Der gelegentliche Fehler bleibt bestehen und aus irgendeinem Grund verarbeitet poly2tri Fehler, indem Warnungen ausgegeben werden. Ich habe es daher so geändert, dass stattdessen Ausnahmen geworfen werden.

Oben sehen Sie, wie der blaue Umriss trianguliert und rote Polygone generiert werden.

Anisotrope Filterung

Da bei der standardmäßigen isotropen MIP-Mapping-Technologie Bilder sowohl in horizontaler als auch in vertikaler Richtung verkleinert werden, sehen Texturen am anderen Ende von World Wide Maze-Levels aus schräger Perspektive wie horizontal verstreckte Texturen mit niedriger Auflösung aus. Das Bild rechts oben auf dieser Wikipedia-Seite ist ein gutes Beispiel dafür. In der Praxis ist eine größere horizontale Auflösung erforderlich, die WebGL (OpenGL) mithilfe einer Methode namens anisotroper Filterung löst. In three.js wird durch Festlegen eines Werts für THREE.Texture.anisotropy, der größer als 1 ist, der anisotrope Filter aktiviert. Diese Funktion ist jedoch eine Erweiterung und wird möglicherweise nicht von allen GPUs unterstützt.

Optimieren

Wie auch in diesem Artikel zu WebGL-Best Practices erwähnt, ist die wichtigste Maßnahme zur Verbesserung der WebGL-Leistung (OpenGL), die Anzahl der Draw-Aufrufe zu minimieren. Während der ursprünglichen Entwicklung von World Wide Maze waren alle Inseln, Brücken und Leitplanken im Spiel separate Objekte. Das führte manchmal zu über 2.000 Draw-Aufrufen, was komplexe Ebenen unhandlich machte. Nachdem ich jedoch dieselben Objekttypen in ein Mesh verpackt hatte, sanken die Draw-Aufrufe auf etwa 50 und die Leistung verbesserte sich erheblich.

Ich habe die Chrome-Tracing-Funktion für eine weitere Optimierung verwendet. Mit den Profilern in den Chrome-Entwicklertools können Sie die Verarbeitungszeiten der Methoden insgesamt bis zu einem gewissen Grad bestimmen. Mithilfe von Tracing können Sie jedoch genau sehen, wie lange jeder Teil dauert, bis auf eine Tausendstelsekunde genau. In diesem Artikel finden Sie weitere Informationen zur Verwendung von Tracing.

Die obigen Ergebnisse stammen aus dem Erstellen von Umgebungskarten für die Reflexion des Balls. Wenn wir console.time und console.timeEnd an scheinbar relevanten Stellen in three.js einfügen, erhalten wir ein Diagramm, das so aussieht: Die Zeit vergeht von links nach rechts und jede Schicht ist so etwas wie ein Aufrufstapel. Wenn Sie „console.time“ in „console.time“ verschachteln, können Sie weitere Messungen vornehmen. Das obere Diagramm zeigt die Daten vor der Optimierung, das untere nach der Optimierung. Wie die obere Grafik zeigt, wurde updateMatrix (das Wort ist abgeschnitten) während der Voroptimierung für alle Render 0–5 aufgerufen. Ich habe sie jedoch so geändert, dass sie nur einmal aufgerufen wird, da dieser Vorgang nur erforderlich ist, wenn sich Objekte in Position oder Ausrichtung ändern.

Der Tracing-Prozess selbst beansprucht natürlich Ressourcen. Wenn Sie console.time zu häufig einfügen, kann dies zu einer erheblichen Abweichung von der tatsächlichen Leistung führen, was es schwierig macht, Bereiche für die Optimierung zu ermitteln.

Leistungseinstellung

Aufgrund der Natur des Internets wird das Spiel wahrscheinlich auf Systemen mit sehr unterschiedlichen Spezifikationen gespielt. In Find Your Way to Oz, das Anfang Februar veröffentlicht wurde, werden mithilfe der Klasse IFLAutomaticPerformanceAdjust Effekte entsprechend den Schwankungen der Framerate skaliert, um eine flüssige Wiedergabe zu ermöglichen. World Wide Maze basiert auf derselben IFLAutomaticPerformanceAdjust-Klasse und reduziert die Effekte in der folgenden Reihenfolge, um das Gameplay so flüssig wie möglich zu gestalten:

1. Wenn die Bildrate unter 45 fps fällt, werden Umgebungskarten nicht mehr aktualisiert.
2. Falls die Framerate immer noch unter 40 fps liegt, wird die Renderingauflösung auf 70% (50% des Oberflächenverhältnisses) reduziert.
3. Falls die Framerate immer noch unter 40 fps fällt, wird FXAA (Anti-Aliasing) deaktiviert.
4. Falls die Framerate weiterhin unter 30 fps liegt, werden die Glüheneffekte entfernt.

Speicherleck

Mit three.js ist es etwas mühsam, Objekte sauber zu entfernen. Wenn ich sie jedoch einfach so stehen ließe, würde das natürlich zu Speicherlecks führen. Deshalb habe ich die folgende Methode entwickelt. @renderer bezieht sich auf THREE.WebGLRenderer. (Die neueste Version von three.js verwendet eine etwas andere Methode zur Deaktivierung, daher funktioniert das wahrscheinlich nicht so wie es ist.)

destructObjects: (object) =>
  switch true
    when object instanceof THREE.Object3D
      @destructObjects(child) for child in object.children
      object.parent?.remove(object)
      object.deallocate()
      object.geometry?.deallocate()
      @renderer.deallocateObject(object)
      object.destruct?(this)

    when object instanceof THREE.Material
      object.deallocate()
      @renderer.deallocateMaterial(object)

    when object instanceof THREE.Texture
      object.deallocate()
      @renderer.deallocateTexture(object)

    when object instanceof THREE.EffectComposer
      @destructObjects(object.copyPass.material)
      object.passes.forEach (pass) =>
        @destructObjects(pass.material) if pass.material
        @renderer.deallocateRenderTarget(pass.renderTarget) if pass.renderTarget
        @renderer.deallocateRenderTarget(pass.renderTarget1) if pass.renderTarget1
        @renderer.deallocateRenderTarget(pass.renderTarget2) if pass.renderTarget2

HTML

Ich persönlich finde, dass das Beste an der WebGL-App die Möglichkeit ist, das Seitenlayout in HTML zu entwerfen. Das Erstellen von 2D-Oberflächen wie Punktzahlen oder Textanzeigen in Flash oder openFrameworks (OpenGL) ist ziemlich mühsam. Flash hat zumindest eine IDE, aber openFrameworks ist schwierig, wenn Sie nicht daran gewöhnt sind. Mit etwas wie Cocos2D kann es einfacher werden. HTML hingegen ermöglicht eine präzise Steuerung aller Frontend-Designaspekte mit CSS, genau wie beim Erstellen von Websites. Komplexe Effekte wie sich zu einem Logo zusammenballende Partikel sind zwar nicht möglich, aber einige 3D-Effekte sind mit CSS-Transforms möglich. Die Texteffekte „GOAL“ und „TIME IS UP“ von World Wide Maze werden mithilfe der Skalierung im CSS-Übergang animiert (implementiert mit Transit). (Natürlich wird für die Hintergrundabstufungen WebGL verwendet.)

Jede Seite im Spiel (Titel, RESULT, RANKING usw.) hat eine eigene HTML-Datei. Sobald diese als Vorlagen geladen sind, wird $(document.body).append() zum richtigen Zeitpunkt mit den entsprechenden Werten aufgerufen. Ein Problem war, dass Maus- und Tastaturereignisse nicht vor dem Anhängen festgelegt werden konnten. Daher funktionierte el.click (e) -> console.log(e) vor dem Anhängen nicht.

Internationalisierung (i18n)

Die Arbeit in HTML war auch beim Erstellen der englischsprachigen Version praktisch. Für meine Anforderungen an die Internationalisierung habe ich i18next, eine Web-I18N-Bibliothek, verwendet, die ich unverändert verwenden konnte.

Die Bearbeitung und Übersetzung des In-Game-Texts erfolgte in einer Google Docs-Tabelle. Da i18next JSON-Dateien benötigt, habe ich die Tabellen in TSV exportiert und dann mit einem benutzerdefinierten Konverter konvertiert. Ich habe kurz vor der Veröffentlichung viele Änderungen vorgenommen. Die Automatisierung des Exportprozesses aus der Google Docs-Tabelle hätte die Arbeit viel einfacher gemacht.

Die automatische Übersetzungsfunktion von Chrome funktioniert ebenfalls normal, da die Seiten mit HTML erstellt wurden. Manchmal wird die Sprache jedoch nicht richtig erkannt, sondern fälschlicherweise als eine ganz andere Sprache identifiziert (z.B. Vietnamesisch), sodass diese Funktion derzeit deaktiviert ist. Sie kann mit Meta-Tags deaktiviert werden.

RequireJS

Ich habe RequireJS als JavaScript-Modulsystem ausgewählt. Die 10.000 Zeilen Quellcode des Spiels sind in etwa 60 Klassen (= Coffee-Dateien) unterteilt und in einzelne JS-Dateien kompiliert. RequireJS lädt diese einzelnen Dateien in der richtigen Reihenfolge basierend auf der Abhängigkeit.

define ->
  class Hoge
    hogeMethod: ->

Die oben definierte Klasse (hoge.coffee) kann so verwendet werden:

define ['hoge'], (Hoge) ->
  class Moge
    constructor: ->
      @hoge = new Hoge()
      @hoge.hogeMethod()

Damit es funktioniert, muss „hoge.js“ vor „moge.js“ geladen werden. Da „hoge“ als erstes Argument von „define“ festgelegt ist, wird „hoge.js“ immer zuerst geladen (und nach dem Laden von „hoge.js“ zurückgerufen). Dieser Mechanismus wird AMD genannt. Jede Drittanbieterbibliothek kann für dieselbe Art von Rückruf verwendet werden, sofern sie AMD unterstützt. Auch solche, die dies nicht tun (z.B. three.js), funktionieren ähnlich, solange die Abhängigkeiten im Voraus angegeben werden.

Das ist vergleichbar mit dem Importieren von AS3 und sollte nicht allzu verwunderlich sein. Wenn Sie mehr abhängige Dateien haben, ist dies eine mögliche Lösung.

r.js

RequireJS enthält einen Optimierer namens r.js. Dadurch werden die Haupt-JS-Datei und alle abhängigen JS-Dateien in einer Datei zusammengefasst und dann mit UglifyJS (oder Closure Compiler) minimiert. Dadurch wird die Anzahl der Dateien und die Gesamtmenge der Daten reduziert, die der Browser laden muss. Die Gesamtgröße der JavaScript-Datei für World Wide Maze beträgt etwa 2 MB und kann durch die Optimierung von r.js auf etwa 1 MB reduziert werden. Wenn das Spiel mit gzip verteilt werden könnte, würde sich das weiter auf 250 KB reduzieren. (Aufgrund eines Problems mit GAE können keine GZIP-Dateien mit einer Größe von mindestens 1 MB übertragen werden. Das Spiel wird daher derzeit unkomprimiert als 1 MB reiner Text verteilt.)

Stage Builder

Die Daten der Phase werden so generiert, wobei der gesamte Vorgang auf dem GCE-Server in den USA ausgeführt wird:

1. Die URL der Website, die in eine Bühne umgewandelt werden soll, wird über WebSocket gesendet.
2. PhantomJS erstellt einen Screenshot und die Positionen der div- und img-Tags werden abgerufen und im JSON-Format ausgegeben.
3. Anhand des Screenshots aus Schritt 2 und der Positionierungsdaten von HTML-Elementen löscht ein benutzerdefiniertes C++-Programm (OpenCV, Boost) nicht benötigte Bereiche, generiert Inseln, verbindet die Inseln mit Brücken, berechnet die Position von Leitplanken und Elementen, legt den Zielpunkt fest usw. Die Ergebnisse werden im JSON-Format ausgegeben und an den Browser zurückgegeben.

PhantomJS

PhantomJS ist ein Browser, der keinen Bildschirm benötigt. Es kann Webseiten laden, ohne Fenster zu öffnen. Daher kann es in automatisierten Tests oder zum Erstellen von Screenshots auf der Serverseite verwendet werden. Die Browser-Engine ist WebKit, die auch von Chrome und Safari verwendet wird. Daher sind die Layout- und JavaScript-Ausführungsergebnisse mehr oder weniger mit denen von Standardbrowsern identisch.

Bei PhantomJS werden JavaScript oder CoffeeScript verwendet, um die Prozesse zu schreiben, die ausgeführt werden sollen. Das Erstellen von Screenshots ist ganz einfach, wie in diesem Beispiel gezeigt. Ich arbeitete auf einem Linux-Server (CentOS) und musste Schriftarten installieren, um Japanisch anzuzeigen (M+ FONTS). Das Schriftbild wird aber anders als unter Windows oder macOS gerendert, sodass dieselbe Schriftart auf anderen Computern anders aussehen kann. Der Unterschied ist jedoch minimal.

Die Abrufpositionen von img- und div-Tags werden im Grunde genauso wie auf Standardseiten verarbeitet. Auch jQuery kann problemlos verwendet werden.

stage_builder

Ich habe zuerst einen eher DOM-basierten Ansatz zur Generierung von Ebenen in Betracht gezogen (ähnlich dem 3D-Inspektor von Firefox) und eine Art DOM-Analyse in PhantomJS versucht. Letztendlich habe ich mich jedoch für einen Ansatz zur Bildverarbeitung entschieden. Dazu habe ich ein C++-Programm mit OpenCV und Boost namens „stage_builder“ geschrieben. Sie führt folgende Aktionen aus:

1. Ladet den Screenshot und die JSON-Datei(en)
2. Wandelt Bilder und Text in „Inseln“ um.
3. Erstellt Brücken, um die Inseln zu verbinden.
4. Entfernt unnötige Brücken, um ein Labyrinth zu erstellen.
5. Große Elemente platzieren
6. Platz für kleine Gegenstände.
7. Leitplanken platzieren
8. Gibt Positionsdaten im JSON-Format aus.

Die einzelnen Schritte werden unten ausführlich beschrieben.

Screenshot und JSON-Dateien laden

Zum Laden von Screenshots wird die übliche Taste cv::imread verwendet. Ich habe mehrere Bibliotheken für die JSON-Dateien getestet, aber picojson schien am einfachsten zu handhaben.

Bilder und Text in „Inseln“ umwandeln

Oben sehen Sie einen Screenshot des Bereichs „News“ von aid-dcc.com (auf das Bild klicken, um die Originalgröße zu sehen). Die Bilder und Textelemente müssen in Inseln umgewandelt werden. Um diese Bereiche zu isolieren, sollten wir die weiße Hintergrundfarbe löschen, also die am häufigsten vorkommende Farbe im Screenshot. Das sieht dann so aus:

Die weißen Bereiche sind die potenziellen Inseln.

Der Text ist zu dünn und scharf. Wir vergrößern ihn mit cv::dilate, cv::GaussianBlur und cv::threshold. Auch Bildinhalte fehlen. Wir füllen diese Bereiche daher mit Weiß aus, basierend auf der img-Tag-Datenausgabe von PhantomJS. Das resultierende Bild sieht so aus:

Der Text bildet jetzt geeignete Klumpen und jedes Bild ist eine richtige Insel.

Brücken zur Verbindung der Inseln erstellen

Sobald die Inseln fertig sind, werden sie durch Brücken verbunden. Jede Insel sucht links, rechts, oben und unten nach benachbarten Inseln und verbindet dann eine Brücke mit dem nächstgelegenen Punkt der nächstgelegenen Insel. Das sieht dann in etwa so aus:

Entfernen unnötiger Brücken, um ein Labyrinth zu erstellen

Wenn alle Brücken erhalten bleiben würden, wäre die Bühne zu einfach zu befahren. Daher müssen einige entfernt werden, um ein Labyrinth zu schaffen. Eine Insel (z.B. die oben links) wird als Ausgangspunkt ausgewählt und alle Brücken bis auf eine (zufällig ausgewählt) werden gelöscht. Dann wird der Vorgang für die nächste Insel wiederholt, die über die verbleibende Brücke verbunden ist. Sobald der Pfad zu einer Sackgasse führt oder zu einer zuvor besuchten Insel zurückführt, wird er bis zu einem Punkt zurückverfolgt, von dem aus eine neue Insel erreicht werden kann. Das Labyrinth ist fertig, sobald alle Inseln auf diese Weise verarbeitet wurden.

Große Elemente platzieren

Je nach Größe der Insel werden eine oder mehrere große Elemente platziert. Dabei werden die Punkte ausgewählt, die am weitesten von den Rändern der Inseln entfernt sind. Diese Punkte sind unten rot dargestellt, auch wenn sie nicht sehr deutlich zu erkennen sind:

Von allen möglichen Punkten wird der Punkt links oben als Startpunkt (roter Kreis) und der Punkt rechts unten als Ziel (grüner Kreis) festgelegt. Aus den übrigen Punkten werden maximal sechs für die Platzierung großer Artikel (violetter Kreis) ausgewählt.

Kleine Gegenstände platzieren

Eine geeignete Anzahl kleiner Elemente wird entlang von Linien in festgelegten Abständen von den Rändern der Insel platziert. Das Bild oben (nicht von aid-dcc.com) zeigt die projizierten Platzierungslinien in grau, versetzt und in regelmäßigen Abständen von den Rändern der Insel. Die roten Punkte zeigen an, wo die kleinen Elemente platziert sind. Da dieses Bild aus einer Version stammt, die sich in der Mitte der Entwicklung befindet, sind die Elemente in geraden Linien angeordnet. In der endgültigen Version sind sie jedoch etwas unregelmäßiger zu beiden Seiten der grauen Linien verteilt.

Schutzmaßnahmen platzieren

Die Leitplanken werden grundsätzlich entlang der Außengrenzen der Radfahrstreifen platziert, müssen aber an Brücken unterbrochen werden, um den Zugang zu ermöglichen. Die Boost-Geometriebibliothek erwies sich dabei als nützlich, da sie geometrische Berechnungen vereinfachte, z. B. die Bestimmung, wo Inselgrenzdaten mit den Linien auf beiden Seiten einer Brücke übereinstimmen.

Die grünen Linien, die die Inseln umreißen, sind die Leitplanken. Auf diesem Bild ist es vielleicht schwer zu erkennen, aber an den Stellen, an denen sich Brücken befinden, sind keine grünen Linien zu sehen. Das ist das endgültige Bild, das für das Debuggen verwendet wird. Es enthält alle Objekte, die in JSON ausgegeben werden müssen. Die hellblauen Punkte sind kleine Elemente und die grauen Punkte sind vorgeschlagene Startpunkte. Wenn der Ball ins Meer fällt, wird das Spiel am nächsten Startpunkt fortgesetzt. Neustartpunkte sind in etwa so angeordnet wie kleine Elemente, in regelmäßigen Abständen in einer festgelegten Entfernung vom Rand der Insel.

Positionierungsdaten im JSON-Format ausgeben

Ich habe auch picojson für die Ausgabe verwendet. Sie schreibt die Daten in die Standardausgabe, die dann vom Aufrufer (Node.js) empfangen wird.

C++-Programm auf einem Mac erstellen, das unter Linux ausgeführt werden soll

Das Spiel wurde auf einem Mac entwickelt und in Linux bereitgestellt. Da OpenCV und Boost für beide Betriebssysteme verfügbar waren, war die Entwicklung selbst nicht schwierig, sobald die Kompilierungsumgebung eingerichtet war. Ich habe die Befehlszeilentools in Xcode verwendet, um den Build auf dem Mac zu debuggen, und dann mit automake/autoconf eine Konfigurationsdatei erstellt, damit der Build unter Linux kompiliert werden konnte. Dann musste ich einfach „configure && make“ in Linux verwenden, um die ausführbare Datei zu erstellen. Aufgrund von Unterschieden zwischen Compilerversionen sind einige Linux-spezifische Fehler aufgetreten, die ich mit gdb relativ einfach beheben konnte.

Fazit

Ein solches Spiel könnte mit Flash oder Unity erstellt werden, was zahlreiche Vorteile bietet. Diese Version erfordert jedoch keine Plug-ins und die Layoutfunktionen von HTML5 + CSS3 haben sich als äußerst leistungsfähig erwiesen. Es ist definitiv wichtig, für jede Aufgabe die richtigen Tools zu haben. Ich war persönlich überrascht, wie gut das Spiel geworden ist, obwohl es vollständig in HTML5 erstellt wurde. Auch wenn es in vielen Bereichen noch verbesserungswürdig ist, bin ich gespannt, wie es sich in Zukunft entwickelt.