Wie überprüfe ich, ob im 2D-Bereich eine Kachelecke sichtbar ist?

Ich versuche, Nebel des Krieges umzusetzen, und bin in Schwierigkeiten geraten. Ich möchte überprüfen, ob der Spieler die Ecken jedes Plättchens innerhalb eines bestimmten Radius sehen kann. Ich bin mir jedoch nicht sicher, wie ich überprüfen soll, ob die Sicht auf die Ecken behindert werden soll oder nicht. Gibt es einen schnellen Weg, dies zu tun? Ich habe ein System zum Zeichnen einer Linie verwendet und überprüft, ob die Kacheln, auf denen sich die Linie befindet, feste Blöcke in einem Rougelike sind, aber ich bin mir nicht sicher, ob diese Methode geeignet wäre, da es möglich ist, Teile einer Kachel im Gegensatz zu einem Rougelike zu sehen wo es eine Ja oder Nein Typ Sache ist.

Zum Beispiel behindert die schwarze Kachel die Sicht teilweise auf die weiße Kachel.

Die roten Linien zeigen an, dass der Spieler die Ecke sehen kann, während die blauen Linien anzeigen, dass sie nicht sehen können (da das Schwarz sie behindert).

Um Nicks Antwort ein wenig zu präzisieren: Das Kernkonzept des DDA-Algorithmus (der in drei Dimensionen genauso gut funktioniert) besteht darin, dass Sie für jede Achse Ihres Gitters den nächsten "Kreuzungspunkt" für diese Achse in Bezug auf Ihre verfolgen Zeilenparameter; Jeder Schritt des Algorithmus besteht darin, herauszufinden, welche Achse den nächsten Kreuzungspunkt hat (was ein einfacher Vergleich in zwei Dimensionen ist), den entsprechenden Schritt auszuführen und die Werte für die nächste Kreuzung für jede Achse zu aktualisieren.

Die Zeile hier kann geschrieben werden als '(x, y) = (x0, y0) + t * (m, n)', wobei m = x1-x0 und n = y1-y0. Wenn die Dimensionen einer Gitterzelle gx und gy sind, kann dx - der Abstand (in Bezug auf den t-Parameter), den zum Überqueren einer Gitterzelle benötigt wird - mit ein wenig schneller Algebra ermittelt werden: aus dem Gleichungspaar x = x0 + m t, (x + gx) = x0 + m (t + dx) erhalten wir gx = m * dx oder mit anderen Worten dx = gx / m. Ebenso ist dy = gy / n. Der Algorithmus verfolgt next_x (den Abstand zum nächsten roten Punkt entlang der Linie) und next_y (den Abstand zum nächsten blauen Punkt entlang der Linie) und aktualisiert sie jedes Mal, wenn er auf eine andere Kreuzung trifft, sodass die zentrale Schleife ungefähr so ​​aussieht ::

while ( cur_t < t_max) {
  if ( next_x < next_y ) {
    cell_x++;
    cur_t += next_x;
    next_y -= next_x;
    next_x = dx;
  } else {
    cell_y++;
    cur_t += next_y;
    next_x -= next_y;
    next_y = dy;
  }
  // Process the cell (cell_x, cell_y)
}

Beachten Sie, dass in diesem Code viele Details fehlen - er sagt Ihnen beispielsweise nicht, wie Sie next_x und next_y initialisieren sollen. Es gibt Möglichkeiten, die meisten Teilungen zu beseitigen, um Sonderfälle wie vertikale und horizontale Linien einfacher behandeln zu können. Ob Sie cell_x und cell_y erhöhen oder verringern, hängt davon ab, in welchem ​​Quadranten sich Ihre Zeile befindet. Beachten Sie, dass Sie für meine Beispielzeile cell_x tatsächlich mit jedem Tick verringern würden, da m (x1-x0) negativ ist. Sie müssen auch entscheiden, wie Sie Fälle behandeln möchten, in denen Ihre Linie genau durch die Ecke zwischen Zellen verläuft, anstatt an einer Kante zu wechseln. Es gibt viele kleine Details, die schief gehen können, und es sind viele Tests erforderlich. Hoffentlich erhalten Sie dadurch ein Bild von der Kernidee des Algorithmus.

Der DDA-Algorithmus (Digital Differential Analyzer) von John Amanatides & Andrew Woo bietet alles, was Sie brauchen. Ich bin auf dem Handy so mühsam, den Link zu greifen, ohne diese Seite zu schließen. DDA ist O (n * m), wobei n die Anzahl der Kacheln ist, die entlang eines Strahls / Winkels gelaufen werden sollen, und m die Anzahl der Winkel.

Wenn Sie überprüfen müssen, ob kleinere Teile der Kachel weiter sichtbar sind (feinere Details), können Sie jede Kachel in ein separates Raster aufteilen und auch auf dieser Ebene DDA-Prüfungen durchführen.

Die einzige wesentlich andere Alternative, die ich sehen kann, ist das Raycast-Scannen (Linien-Linien-Schnittpunktprüfungen), das O (n * m) ist, wobei n die Anzahl der Kachelkanten innerhalb des interessierenden Bereichs und m die Anzahl der von Ihnen getesteten diskreten Winkel ist denn in jedem kreisförmigen Sweep (was bedeutet, dass es auch bei diesem Ansatz noch Probleme mit der Lösung gibt). Da jede Kachel mehrere Kanten enthält, kann DDA als effizienter angesehen werden.

Ein letzter Ansatz, der in den Sinn kommt, besteht darin, das Raycasrt-Scannen anzupassen, indem für jeden einzelnen Gitterschnittpunkt in Ihrem begrenzten Interessenbereich ein individueller Strahlwinkel festgelegt wird. Auf diese Weise können Sie genau bestimmen, wo die Okklusion in Ihrem Gitter auftritt (da Okklusionslinien immer an Ecken vorbeiführen), obwohl Sie Ihren Interessenbereich erheblich einschränken müssten, damit die Anzahl der Interstitialpunkte, die Ihre Strahlwinkel definieren, nicht außer Kontrolle gerät.