spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Im einfachsten Fall ermittelst Du mittels Bresenhams Linienalgorithmus alle Felder zwischen Start und Ziel, und nimmst "Nicht sichtbar" an, falls eines der Felder besetzt ist.

Das wird bei so groben Feldern aber nur sehr grobe Ergebnisse liefern. Etwas besser wird es, wenn Du einen Strahl von Mitte des Startfelds zur Mitte des Zielfelds schießt und diesen Strahl gegen alle Grenz-Liniensegmente von besetzten Feldern schneidest. Noch besser wird es allerdings, wenn Du ein kleines Flächenintegral entlang einer "Linie mit Dicke" aufsetzt. Das kann mathematisch etwas herausfordernd werden, aber Du kannst es auch ganz profan imitieren, indem Du ein ganzes Rudel Strahlen verschickst und dabei Start- und Zielposition innerhalb eines gewissen Radius zufällig streust.

Du musst schon ein wenig mehr zu dem Problem sagen. So wie du es jetzt schilderst weisst du ja, dass 23 undurchsichtig ist. Also warum benutzt du nicht einfach die Position + Blickrichtung und bestimmst dann das nächste Feld und durch Zugriff auf die Matrix kannst du auslesen ob man durchsieht oder nicht.

Ganz simpel. Ansonsten musst du das Problem genauer beschreiben!

Ich denke hier geht es um einen Effekt wie er bei dem Spiel Die Hard verwendet wird. Das Spielgeschehen wird von oben gezeigt, aber Flächen, welche die Spielfigur theoretisch nicht sehen würde werden schwarz gefärbt. Dafür müsste man natürlich den Sichtkegel bestimmen. Dazu hat Schrompf ja schon eine ganz gute Antwort gegeben.

Wenn man wissen will, ob Feld x,y sichtbar ist, muss man doch lediglich ueberpruefen, ob sich zwischen der aktuellen Position und x,y ein Hindernis befindet, welches die Sicht blockiert. Das mit dem Kreis sollte funktionieren, ist aber wahrscheinlich sehr aufwendig, vor allem wenn der Kreis sehr gross ist. Ich wuerde die Frage einfach rekursiv loesen. Man beginnt mit dem ersten Tile, bei dem man sicher ist, das es sichtbar ist. naemlich das auf dem man gerade steht. Dann betrachtet man alle 4 Nachbarn davon. Ist so ein Feld nicht durchsichtig, so kann das Feld nicht gesehen werden und kann als unsichtbar markiert werden, super. Oder man muss von dem Feld in Richtung aktueller Position gehen, man ueberschreitet irgendwann die Grenze des Tiles und kommt auf das Naechste. Man trifft dann auf dein Tile, das entweder sichtbar oder unsichtbar ist, und damit ist auch bewiesen, ob dieses Feld sichtbar ist. Dann macht man das mit den Nachbarn der Nachbarn usw. Dabei betrachtet man nie ein Feld doppelt wie bei der Kreismethode wo der Strahl zum oberen Viertel ja immer durch das Feld noerdlich der Startposition laeuft und dessen Sichtbarkeit so zig mal berechnet wird.

Warum rekursiv?

Also wenn er nur wissen will ob in bestimmtes Feld sichtbar ist von einer Position, dann kann man ja einfach in die Richtung des Ziel Tiles marschieren (Bresenham) und dann ist man irgendwann dort und weiss die Antwort (oder hat schon vorher abgebrochen). Das geht eigentlich ähnlich, wenn du einen ganzen Sichtkegel hast. Du hast einfach verschiedene Linien (obwohl man da dann den Raum dazwischen noch gut handeln muss).

Wenn du allerdings eine Matrix haben möchtest, wo drin steht welche Tiles alle sichtbar sind von einer gegebenen Position, dann ist die rekursive Variante von TGGC sicher die Wahl. Im schlimmsten Fall O(n^2) wenn es korrekt implementiert ist, aber das ist, denke ich, auch die untere Schranke.

Also wenn n die Anzahl der Felder ist, dann ist hat der Algorithmus Laufzeit O(n). Die Frage nach dem Nachbarfeld ist immer gleich schwer.

Zitat von »drakon«

Warum rekursiv?

Weil ich mir das am leichtesten vorstellen kann. ;-)

Zitat von »TGGC«

Algorithmus Laufzeit O(n).

Oh, Natürlich. Habe die Breite des Feldes angenommen. Aber auch dann wäre es bei nicht-quadratischen Feldern O(m*n) gewesen.
Bezüglich rekursiv:
Ich habe während des schreibens bemerkt, dass nicht ganz klar ist was er genau möchte. (Start-Ein-Ende oder Start-Beliebiges-Ende). Da macht rekursiv je nachdem schon Sinn.