Ich benutze C # und XNA. Mein aktueller Algorithmus für die Beleuchtung ist eine rekursive Methode. Es ist jedoch teuer , bis zu dem Punkt, an dem alle 5 Sekunden ein 8x128x8-Block berechnet wird.
- Gibt es andere Beleuchtungsmethoden, die Schatten mit variabler Dunkelheit erzeugen?
- Oder ist die rekursive Methode gut, und vielleicht mache ich es einfach falsch?
Es scheint nur so, als ob rekursives Zeug grundsätzlich teuer ist (gezwungen, ungefähr 25.000 Blöcke pro Block zu durchlaufen). Ich habe überlegt, eine Methode zu verwenden, die der Raytracing-Methode ähnelt, aber ich habe keine Ahnung, wie dies funktionieren würde. Eine andere Sache, die ich versuchte, war, Lichtquellen in einer Liste zu speichern und für jeden Block den Abstand zu jeder Lichtquelle zu ermitteln und diesen zu verwenden, um sie auf das richtige Niveau zu bringen, aber dann würde die Beleuchtung durch Wände gehen.
Mein aktueller Rekursionscode ist unten. Dies wird von jeder Stelle im Chunk aufgerufen, die keine Lichtstärke von Null aufweist, nachdem das Sonnenlicht und das Fackellicht gelöscht und erneut hinzugefügt wurden.
world.get___atist eine Funktion, die Blöcke außerhalb dieses Chunks abrufen kann (dies ist innerhalb der Chunk-Klasse). Locationist meine eigene Struktur, die a ähnelt Vector3, aber Ganzzahlen anstelle von Gleitkommawerten verwendet. light[,,]ist die Lightmap für den Chunk.
private void recursiveLight(int x, int y, int z, byte lightLevel)
{
Location loc = new Location(x + chunkx * 8, y, z + chunky * 8);
if (world.getBlockAt(loc).BlockData.isSolid)
return;
lightLevel--;
if (world.getLightAt(loc) >= lightLevel || lightLevel <= 0)
return;
if (y < 0 || y > 127 || x < -8 || x > 16 || z < -8 || z > 16)
return;
if (x >= 0 && x < 8 && z >= 0 && z < 8)
light[x, y, z] = lightLevel;
recursiveLight(x + 1, y, z, lightLevel);
recursiveLight(x - 1, y, z, lightLevel);
recursiveLight(x, y + 1, z, lightLevel);
recursiveLight(x, y - 1, z, lightLevel);
recursiveLight(x, y, z + 1, lightLevel);
recursiveLight(x, y, z - 1, lightLevel);
}
Antworten:
LR.|VP - LP| < LRDabei ist VP der Positionsvektor des Voxels in Bezug auf den Ursprung undLPder Positionsvektor des Lichts in Bezug auf den Ursprung. Erhöhen Sie den Lichtfaktor für jedes Licht, in dessen Radius sich das aktuelle Voxel befindet, um den Abstand vom Lichtzentrum|VP - LP|. Wenn Sie diesen Vektor normalisieren und dann seine Größe ermitteln, liegt dieser im Bereich von 0,0 -> 1,0. Die maximale Lichtstärke, die ein Voxel erreichen kann, beträgt 1,0.Die Laufzeit ist
O(s^3 * n), wosist die Seitenlänge (128) Ihrer Voxel-Region undnist die Anzahl der Lichtquellen. Wenn Ihre Lichtquellen statisch sind, ist dies kein Problem. Wenn sich Ihre Lichtquellen in Echtzeit bewegen, können Sie nur an Deltas arbeiten, anstatt jedes Update neu zu berechnen.Sie können sogar die Voxel, auf die sich jedes Licht auswirkt, als Referenzen in diesem Licht speichern. Auf diese Weise können Sie, wenn sich das Licht bewegt oder zerstört wird, genau diese Liste durchgehen und die Lichtwerte entsprechend anpassen, anstatt das gesamte kubische Gitter erneut durchlaufen zu müssen.
quelle
Minecraft selbst macht das Sonnenlicht nicht so.
Sie füllen einfach das Sonnenlicht von oben nach unten, jede Schicht sammelt das Licht der Nachbarvoxel in der vorherigen Schicht mit Dämpfung. Sehr schnell - einfacher Durchlauf, keine Listen, keine Datenstrukturen, keine Rekursion.
Sie müssen in einem späteren Durchgang Fackeln und andere nicht flutende Lichter hinzufügen.
Es gibt so viele andere Möglichkeiten, um dies zu tun, einschließlich einer ausgefallenen gerichteten Lichtausbreitung usw., aber sie sind offensichtlich langsamer und Sie müssen herausfinden, ob Sie angesichts dieser Nachteile in den zusätzlichen Realismus investieren möchten.
quelle
Jemand hat gesagt, Sie sollen Ihre eigene Frage beantworten, wenn Sie es herausgefunden haben. Hat eine Methode gefunden.
Was ich tue, ist dieses: Zuerst verursachen Sie ein boolesches Array 3d von „bereits geänderten Blöcken“, die über dem Block überlagert werden. Füllen Sie dann das Sonnenlicht, das Fackellicht usw. aus (zünden Sie einfach den Block an, der noch nicht überflutet ist). Wenn Sie etwas geändert haben, drücken Sie die "geänderten Blöcke" an dieser Stelle auf "Wahr". Gehe aber auch und ändere jeden massiven Block (und deswegen brauchst du keine Beleuchtung dafür zu berechnen) auf "bereits geändert".
Nun zu den schweren Sachen: Geht durch den gesamten Block mit 16 Durchgängen (für jede Lichtstufe) und wenn sich das 'bereits geändert' hat, macht einfach weiter. Holen Sie sich dann das Lichtniveau für die Blöcke um sich herum. Holen Sie sich die höchste Lichtstärke von ihnen. Wenn dieser Lichtpegel dem Lichtpegel des aktuellen Durchgangs entspricht, setzen Sie den Block, auf dem Sie sich befinden, auf den aktuellen Pegel und setzen Sie "Bereits geändert" für diesen Standort auf "Wahr". Fortsetzen.
Ich weiß, wie kompliziert es ist, ich habe versucht, mein Bestes zu erklären. Aber die wichtige Tatsache ist, dass es funktioniert und schnell ist.
quelle
Ich würde einen Algorithmus vorschlagen, der Ihre Multi-Pass-Lösung mit der ursprünglichen rekursiven Methode kombiniert und höchstwahrscheinlich viel schneller ist als beide.
Sie benötigen 16 Listen (oder jede Art von Sammlungen) von Blöcken, eine für jede Lichtstufe. (Eigentlich gibt es Möglichkeiten, diesen Algorithmus so zu optimieren, dass weniger Listen verwendet werden. Diese Methode ist jedoch am einfachsten zu beschreiben.)
Löschen Sie zuerst die Listen und setzen Sie die Lichtstärke aller Blöcke auf Null. Initialisieren Sie dann die Lichtquellen wie in Ihrer aktuellen Lösung. Fügen Sie danach (oder währenddessen) alle Blöcke mit einer Lichtstärke ungleich Null zur entsprechenden Liste hinzu.
Gehen Sie nun die Liste der Blöcke mit Lichtstärke 16 durch. Wenn einer der benachbarten Blöcke eine Lichtstärke von weniger als 15 aufweist, stellen Sie die Lichtstärke auf 15 ein und fügen Sie sie der entsprechenden Liste hinzu. (Wenn sie sich bereits auf einer anderen Liste befunden haben, können Sie sie daraus entfernen, aber es schadet nicht, auch wenn Sie es nicht tun.)
Wiederholen Sie dies für alle anderen Listen in absteigender Reihenfolge der Helligkeit. Wenn Sie feststellen, dass ein Block in der Liste bereits eine höhere Lichtstärke hat, als es sein sollte, um auf dieser Liste zu sein, können Sie davon ausgehen, dass er bereits verarbeitet wurde, und sich nicht einmal die Mühe machen, seine Nachbarn zu überprüfen. (Andererseits ist es möglicherweise schneller, nur die Nachbarn zu überprüfen - es hängt davon ab, wie oft dies passiert. Sie sollten es wahrscheinlich in beide Richtungen versuchen und feststellen, welcher Weg schneller ist.)
Möglicherweise haben Sie festgestellt, dass ich nicht angegeben habe, wie die Listen gespeichert werden sollen. Eigentlich sollte es so ziemlich jede vernünftige Implementierung tun, solange das Einfügen eines bestimmten Blocks und das Extrahieren eines beliebigen Blocks beide schnelle Operationen sind. Eine verknüpfte Liste sollte funktionieren, aber auch eine halbwegs anständige Implementierung von Arrays variabler Länge. Verwenden Sie einfach, was für Sie am besten funktioniert.
Nachtrag: Wenn sich die meisten Ihrer Lichter nicht sehr oft bewegen (und die Wände auch nicht), ist es möglicherweise noch schneller, für jeden beleuchteten Block einen Zeiger auf die Lichtquelle zu speichern, die die Lichtstärke bestimmt (oder auf eine der beiden) wenn mehrere gebunden sind). Auf diese Weise können Sie globale Beleuchtungsaktualisierungen fast vollständig vermeiden: Wenn eine neue Lichtquelle hinzugefügt wird (oder eine vorhandene aufgehellt wird), müssen Sie nur einen einzigen rekursiven Beleuchtungsdurchlauf für die umliegenden Blöcke durchführen, während eine entfernt wird (oder) abgeblendet) müssen Sie nur die Blöcke aktualisieren, die darauf verweisen.
Sie können sogar mit Wandänderungen auf folgende Weise umgehen: Wenn eine Wand entfernt wird, starten Sie einfach einen neuen rekursiven Beleuchtungsdurchlauf an diesem Block. Wenn einer hinzugefügt wird, führen Sie für alle Blöcke, die auf dieselbe Lichtquelle verweisen wie der neu ummauerte Block, einen Beleuchtungsneuberechnungsvorgang durch.
(Treten mehrere Beleuchtungsänderungen gleichzeitig auf - z. B. wenn eine Beleuchtung bewegt wird, was als Entfernung und Hinzufügung gilt -, sollten Sie die Aktualisierungen unter Verwendung des obigen Algorithmus zu einer einzigen kombinieren. Grundsätzlich können Sie die Beleuchtungsstärke aller auf Null setzen Blöcke, die auf entfernte Lichtquellen zeigen, fügen Sie alle sie umgebenden beleuchteten Blöcke sowie alle neuen Lichtquellen (oder vorhandenen Lichtquellen in den auf Null gestellten Bereichen) zu den entsprechenden Listen hinzu, und führen Sie die Updates wie oben beschrieben aus.)
quelle