Diagonale Sichtlinie mit zwei Ecken

Im Moment verwende ich Bresenhams Linienalgorithmus für die Sichtlinie. Das Problem ist, dass ich einen Randfall gefunden habe, in dem Spieler durch Wände schauen können. Tritt auf, wenn der Spieler in bestimmten Winkeln zwischen zwei Ecken einer Wand mit einer Lücke auf der anderen Seite schaut.

Das gewünschte Ergebnis ist, dass die Kachel zwischen zwei Wänden als ungültig markiert wird.

Was ist der schnellste Weg, um den Linienalgorithmus von Bresenham zu modifizieren, um dies zu lösen? Wenn es keine gute Lösung gibt, gibt es einen besser geeigneten Algorithmus? Ideen sind willkommen. Bitte beachten Sie, dass die Lösung auch 3D unterstützen sollte.

Bearbeiten: Meine einfache Lösung bestand darin, zu überprüfen, ob beide Ecken geschlossen sind, wenn sich die x- und y-Koordinaten einer Linie ändern. Den funktionierenden Quellcode und eine interaktive Demo des fertigen Produkts finden Sie unter http://ashblue.github.io/javascript-pathfinding/.

Eric Lippert hat eine exzellente Serie über die Erzeugung von Sichtlinien in C # mit Shadow Casting auf einem rechteckigen planaren Gitter geschrieben.

Eric befasste sich unter anderem mit verschiedenen Fragen, die zu den Anforderungen an die Sichtlinie beantwortet werden müssen, die unterschiedliche Ergebnisse liefern, und gibt Beispiele für einige unterschiedliche Ergebnisse. Einer der Artikel befasst sich ausführlich mit einem Umstand, dass er um die Ecke schaut und in einer frühen Version seines Algorithmus aufgetreten ist.

Ich habe Eric-Algorithmus auf einem hexagonalen Gitter angepasst hier , und es erfolgreich auf großen hexagonalen Gitter verwendet (> 400 x 700) mit einer umfangreichen Sichtbarkeit Radius (> 60 Flüche). Diese Implementierung berechnet und zeigt das vollständige Sichtfeld so schnell ich kann mit einer einzigen i7-CPU an. Dies ist sicherlich schnell genug für alle Verwendungszwecke, die ich erwartet habe.

Update - Sichtlinie mit Höhe:
Die oben verknüpfte Hex-Grid-Implementierung berechnet die Sichtlinie mit Höhe, nicht nur Hindernissen. In den Dokumentationsnotizen wird auch eine zusätzliche Entscheidung erörtert, die in Bezug auf die Höhenberechnungen getroffen werden muss: Die Zielhöhe und die Beobachterhöhe. Die Standardauswahl besteht darin, beide gleich zu machen, wodurch ein symmetrisches Sichtfeld erzeugt wird. Es können jedoch auch Boden-Boden- und Beobachteraugen-Boden ausgewählt werden. (Der Code ist Open Source unter MIT-Lizenz)

Was ist, wenn Sie für die LOS-Berechnung ein separates Raster mit höherer Auflösung haben, das die Ecklücken ausfüllt? Ich dachte so etwas:

Das linke ist der ursprüngliche Blockabschnitt von 4 Quadraten.

Das rechte ist die "hochauflösende" Version, da Sie sehen können, dass jedes ursprüngliche Quadrat in Viertel unterteilt wurde und eine der Ecken ausgefüllt wurde. Ich bin mir nicht sicher, ob der Algorithmus dies sofort generiert, aber er kann vorberechnet werden von der aktuellen Karte.

Es bedeutet zwar, dass sich der Koordinatenraum vervierfacht, aber ich kann mir nicht vorstellen, dass dies ein erhebliches Leistungsproblem darstellt.