4. Sichbarkeit von Objekten in einem Koordinatensystem vom Punkt (x,y)

Sichbarkeit von Objekten in einem Koordinatensystem vom Punkt (x,y)

  • L

    Hallo Leute,

    ich bin dabei ein Spiel zu Programmieren, habe dabei ein Problem mit Sichtbarkeiten:

    Man stelle sich ein Koordinatensystem vor, in dem eine Strecke (Weg) verläuft mit je einem Anfangs und Endpunkt (x1,y1) und (x2, y2).
    Links und rechts befinden sich u.U mehrere zufällige Quadrate (4 Eckpunkte (x_i, y_i) | i aus {1,2,3,4}).

    Wenn der Spieler entlang des o.g. Weges entlang läuft, soll berechnet werden welche der Quadrate vollständig, teilweise oder gar nicht gesehen werden können?

    Die naheliegenste Art ist, immer vom jeweiligen aktuellen Standort Vektoren zu den Eckpunten der Quadrate zu ziehen und auf mögliche Schnitte zu prüfen. Jedoch kommt mir das ineffzient vor.

    Vielleicht kennt jemand ja einen cleveren Algorithmus?

    Für hilfreiche Antworten bedanke ich mich schonmal.

    Viele Grüße
    Lespaul

    0
  • Mod

    lespaul schrieb:

    Wenn der Spieler entlang des o.g. Weges entlang läuft, soll berechnet werden welche der Quadrate vollständig, teilweise oder gar nicht gesehen werden können?

    Ist das wirklich die Problemstellung oder geht es eigentlich um ganz was anderes und du denkst bloß, dass diese Information dabei ein essentieller Zwischenschritt wäre?

    0
  • L

    SeppJ schrieb:

    Ist das wirklich die Problemstellung oder geht es eigentlich um ganz was anderes und du denkst bloß, dass diese Information dabei ein essentieller Zwischenschritt wäre?

    Ich möchte die Sichtbarkeit von versch. Objekten an einem Punkt x,y auf einer Geraden bewerten (zB von 0.0 (unsichtbar, hinter zich anderen Quadraten) bis 1.0 (ich stehe gerade davor)).

    Das mit dem Spieler davor stehen und laufen habe ich geschrieben um meine Problemstellung metaphorisch zu erläutern. Dann kann man sich mehr darunter vortstellen.

    0
  • Mod

    Ich nehme mal an, keine Überschneidungen? Falls ja:

    • Sortiere alle Eckpunkte nach ihrem Winkel bezüglich des Ausgangspunktes (dazu ist es nicht nötig, die Winkel explizit zu berechnen!).
    • Wähle einen der Eckpunkt, beispielsweise den mit dem kleinsten Winkel. Die Verbindung vom Ausgangspunkt zu diesem Eckpunkt ist dein Sichtstrahl.
    • Mache eine Liste der derzeit im Sichtstrahl befindlichen Wände. Mir fällt gerade keine bessere Methode ein, als einfach alle Wände zu prüfen. Eventuell kann man irgendwas besseres machen, indem man die unten erklärte Schleife einfach 1.5 Mal laufen lässt, aber ganz exakt habe ich das nicht durchdacht.
    • Finde die zum Ausgangspunkt nächstgelegene Wand aus der Liste der Wände. Dazu wirst du möglicherweise den Abstand vom Ausgangspunkt zum Schnittpunkt des Sichtstrahls mit den Wänden berechnen müssen. Zumindest im allgemeinen Fall. Wenn du irgendwelche Einschränkungen hast (z.B. alle Wände gleich lang oder alle Wände entlang bestimmter Achsen orientiert) kann das auch wesentlich einfacher gehen. Die nächstgelegene Wand ist die in der aktuellen Blickrichtung sichtbare Wand.
    • Iteriere der Reihe nach über alle Eckpunkte, ausgehend von dem, den du zuerst gewählt hast:
    • Merke dir das vorderste Element aus der Liste der Wände (sofern die Liste nicht leer ist)
    • Füge der Liste der Wände all diejenigen Wände hinzu, die an diesem Eckpunkt beginnen. D.h. der Winkel zwischen diesem Endpunkt, dem Ausgangspunkt und dem anderen Endpunkt der Wand liegt zwischen 0° und 180° (alle Winkel seien auf den Bereich -180° bis 180° gemappt). Hierzu ist es nicht nötig, den Winkel explizit zu berechnen!
    • Entferne aus der Liste der Wände all diejenigen Wände, die an diesem Eckpunkt enden
    • Finde die nächstgelegene Wand aus der Liste der Wände.
    • Ist die nächstgelegene Wand ein andere als die vorherige?
    • Falls ja: Die alte nächstgelegene Wand ist nur bis zum Schnittpunkt mit dem Sichtstrahl sichtbar. Die neue nächstgelegene Wand ist die sichtbare Wand, bis zum nächsten Wechsel.
    • Falls nein: Die nächstgelegene Wand ist nach wie vor die entlang der Sichtlinie sichtbare Wand.
    • Betrachte zum Abschluss noch einmal den Eckpunkt, mit dem du begonnen hast.
    0
  • L

    SeppJ schrieb:

    [*]Mache eine Liste der derzeit im Sichtstrahl befindlichen Wände.

    Also ein Schnittpunkt mit einem anderen Quadrat gelle?

    0
  • Mod

    lespaul schrieb:

    SeppJ schrieb:

    [*]Mache eine Liste der derzeit im Sichtstrahl befindlichen Wände.

    Also ein Schnittpunkt mit einem anderen Quadrat gelle?

    Eine Liste aller Seiten, die diesen Strahl schneiden.

    0
Anmelden zum Antworten