Berechnung des Lebenszustands in Javascript
Ich habe eine Life-Implementierung in Javascript erstellt, um so schnell wie möglich zu sein. Mit dem Rendering bin ich zufrieden (siehe Bild unten). Die nächste Zustandsberechnung ist jedoch sehr langsam und ich habe keine Ahnung, wie ich beschleunigen soll es noch mehr.
Aktueller Stand der Implementierung
Rendern
Screenshot des Spiels
ich erreicht, indem ich regl zum Rendern und Verschieben der Berechnung der sichtbaren Zellen in einen separaten Thread verwendet habe (ein dafür vorgesehener Web-Worker ist hervorgegangen). Ich denke, dies erfordert keine Optimierung, vielleicht die Art und Weise, wie ich die sichtbaren Zellen berechne.
Wie ich sichtbare Zellen berechne
onmessage = function (e) {
var visibleCells = [];
for (const x of e.data.grid.keys()) {
if (x < -(e.data.offsets.X+1)) continue; //Continue until reaches the visible part
if (x > -e.data.offsets.X+e.data.width) break; //Stop after leaving visible part
for (const y of e.data.grid.get(x).keys()) {
if (y < e.data.offsets.Y-1) continue;
if (y > e.data.offsets.Y+e.data.height) break;
visibleCells.push([x, y]);
}
}
this.postMessage({result: visibleCells})
}
Darstellung des "Universums"
Ich hatte einige Ideen, wie man das Lebensuniversum darstellt, aber ich bleibe bei der letzten Option, da sich herausstellte, dass sie die beste Leistung erbringt. (Beachten Sie, dass diese Implementierung den Speicherplatz nicht einschränkt, sodass es sich um ein unendliches Raster handelt.)
1.1 Verwenden eines 2D-Arrays als cellState = grid [x] [y];
Da es sich um ein unendliches Gitter handelt, kann dieses nicht verwendet werden
1.2 Verwenden eines 2D-Arrays als Raster [[x, y], [x1, y2], ...]
Speichern nur der Koordinate der lebenden Zelle. Dies hat das Problem möglicher Duplikate. Außerdem habe ich einige Tests auf jsbench.me durchgeführt und festgestellt, dass dies langsamer ist als der zweite Weg (der nächste).
2. Verwenden eines Objekts
Festlegen der Eigenschaften eines Objekts, um die Illusion eines 2D-Arrays zu erzeugen. Dies funktionierte etwas, hatte jedoch das Problem des Overheads, der durch die Konvertierung von int in einen String und umgekehrt entsteht, da bei der Objektindizierung Strings als Schlüssel verwendet werden
//Defining grid
var grid = {};
//Creating a cell at (x;y)
if (grid[x] == undefined) grid[x] = {};
grid[x][y] = null;
//Killing a cell at (x;y)
delete grid[x][y];
if (Object.keys(grid[x]).length == 0) delete grid[x];
3. Verwenden von Karten und Sets (aktuell)
Auf diese Weise kann ich Ganzzahlen als Indizes verwenden und muss mich nicht mit der Möglichkeit einer doppelten Zelle befassen
//Defining grid
var grid = new Map();
//Creating a cell at (x;y)
if (!grid.has(x)) grid.set(x, new Set());
grid.get(x).add(y);
//Killing a cell at (x;y)
grid.get(x).delete(y);
if (grid.get(x).size == 0) grid.delete(x);
Die nächste Zustandsberechnung
Deshalb schreibe ich diese Frage. Ich weiß nicht, wie ich die Leistung hier weiter verbessern kann.
Der Code zur Berechnung des nächsten Zustands
onmessage = function (e) {
var newGrid = new Map();
var sketch = new Map();
var start = performance.now();
for (var x of e.data.grid.keys()) {
var col1 = x - 1, col3 = x + 1;
if (!sketch.has(col1)) sketch.set(col1, new Set());
if (!sketch.has(x)) sketch.set(x, new Set());
if (!sketch.has(col3)) sketch.set(col3, new Set());
for (var y of e.data.grid.get(x).keys()) {
var row1 = y - 1, row3 = y + 1;
sketch.get(col1).add(row1);
sketch.get(col1).add(y);
sketch.get(col1).add(row3);
sketch.get(x).add(row1);
sketch.get(x).add(row3);
sketch.get(col3).add(row1);
sketch.get(col3).add(y);
sketch.get(col3).add(row3);
}
}
for (var x of sketch.keys()) {
for (var y of sketch.get(x).keys()) {
//Count neighbours
var c = 0;
var col1 = x - 1, col3 = x + 1;
var row1 = y - 1, row3 = y + 1;
if (e.data.grid.has(col1)) {
//1st col
var col = e.data.grid.get(col1);
c += col.has(row1)
c += col.has(y)
c += col.has(row3)
}
if (e.data.grid.has(x)) {
//2nd col
var col = e.data.grid.get(x);
c += col.has(row1)
c += col.has(row3)
}
if (e.data.grid.has(col3)) {
//3rd col
var col = e.data.grid.get(col3);
c += col.has(row1)
c += col.has(y)
c += col.has(row3)
}
if (c == 3) { //If a cell has 3 neighbours it will live
if (!newGrid.has(x)) newGrid.set(x, new Set());
newGrid.get(x).add(y);
continue;
}
//but if it has 2 neigbours it can only survive not born, so check if cell was alive
if (c == 2 && (e.data.grid.has(x) && e.data.grid.get(x).has(y))) {
if (!newGrid.has(x)) newGrid.set(x, new Set());
newGrid.get(x).add(y);
}
}
}
postMessage({ result: newGrid, timeDelta: performance.now() - start });
}
Wenn der Worker das anfängliche Raster empfängt, werden zwei neue Raster erstellt: sketchDieses Raster enthält potenzielle neue Zellen (als ich dies schrieb, habe ich gerade bemerkt, dass ich diesem Raster nicht nur die benachbarten (x; y) hinzufüge und es funktioniert immer nochIch werde dies genauer untersuchen, nachdem ich mit dem Schreiben fertig bin) 1 , und newGriddie das Endergebnis enthalten wird. Auf diese Weise schleife ich nur durch die Zellen, die möglicherweise den Status ändern.
1 Es stellte sich heraus, dass es nach vielen Umgestaltungen ein glücklicher Fehler war. Es funktioniert, weil seine Nachbarn es der Liste hinzufügen werden, aber wenn es keine Nachbarn hat, stirbt es
Aktuelle Leistung
+------------------------+-----------+--------+------+
| Population | 6,986,628 | 64,691 | 3 |
+------------------------+-----------+--------+------+
| Iteration time (ms/i) | 23925 | 212 | 0.16 |
+------------------------+-----------+--------+------+
| FPS (all cell visible) | 900+ | 70 | 60 |
+------------------------+-----------+--------+------+
Bevor Sie fragen, weiß ich nicht, warum die fps größer sind, wenn mehr Zellen gerendert werden, aber wenn Sie wissen, schreiben Sie es bitte in einen Kommentar
Versuche zu optimieren
Teilen Sie die Arbeit auf CPUcores-2-Mitarbeiter auf
Dies war unbrauchbar. Eine Iteration dauerte Minuten, um eine ~ 700K-Population zu berechnen. Ich denke, weil das Objekt auf jeden Worker kopiert wird, war der Overhead viel größer als bei Verwendung nur eines Workers.
Antworten
Schleifenleistung
Die Verwendung von for...ofSchleifen sorgt für eine gute Lesbarkeit, kann jedoch in Bezug auf die Leistung kostspielig sein, da sie Interatoren intern verwenden 1 . Wie in diesem Beitrag erläutert, können umgekehrte forSchleifen die beste Leistung bieten. Dieser neuere Artikel vergleicht auch forSchleifen mit for...inund den Schleifen im funktionalen Programmierstil forEach.
ES6-Schlüsselwörter
Beim Schreiben von modernem JavaScript nützt es wenig var. Best Practices consterfordern heutzutage die Standardeinstellung - auch für Arrays, in denen Elemente nur über die Push-Methode übertragen werden - und genau dann, wenn eine Neuzuweisung als notwendig erachtet wird, letz for. B. in diesen Schleifen.
Gleichheitsvergleiche
Eine gute Gewohnheit und Empfehlung von vielen Styleguides ist strikte Gleichheitsoperatoren zu verwenden (dh ===, !==). Das Problem bei losen Vergleichen ist, dass es so viele seltsame Regeln gibt, die man sich merken müsste, um sicher zu sein, dass sie richtig verwendet werden.