Was genau möchtest du machen? Willst du wissen welche Felder um das blaue Feld herum frei sind? Das ist ja ansich sehr einfach.

Bitte stell deine Frage noch etwas genauer.

Nein ich möchte die schwarzen Felder berechnen. In meinem Bild habe ich das schon erledigt.
Diese wären ansonsten weiß.

Naja dann geh doch einfach jedes Feld durch und schau ob es grau oder weiß ist ...

Was du ganz genau willst versteh ich trotzdem noch nicht.

Wenn das Ding schon ein Raster hat, dann wäre das meine Idee.
Vielleicht ist ja irgendwo die Information gespeichert, welches Feld vom einzelnen Raster als "belegt" markiertg ist oder nicht.

Andere Idee wäre (viel mir eben so ein) die Farbe auszulesen, falls diese immer diesen Farbton hat. Dabei muss man ja nicht jedes Pixel erfassen, wenn das Raster bekannt ist (wohl 7x8 Felder) dann das Bild auch so abtasten.

Meine Interpretation der Frage ist folgende:

Ich habe eine Menge von x,y Koordinaten, u.a. die von Position blau und die der darumliegenden Wände, die sich auf ein gemeinsames Raster beziehen. Der Rest ist unbekannt. Nun willst Du die noch unbekannten dahingehend bekanntmachen, dass ihre Position mit in die Menge wandert, insofern sie aus Blickrichtung der Position blau nicht hinter einer Wand liegen. Richtig verstanden?

Unterteil alles in Funktionen und logge jeden Funktionsaufruf mitsamt Ergebnis mit. Am besten schreibst du das ganze dann in ein Log, dass du dann praktisch "runterlesen" kannst, wenn was schiefgelaufen ist.

[1] Such dir ein Ziel (weiß/schwarz-Blöcke), sagen wir der Einfachheit halber den über Luftlinie am nahesten und markiere den Rand der Karte als virtuelle Mauer.
[2] Definiere eine Laufrichtung und Laufpriorität, falls sich ein Hindernis im Weg befindet (Uhrzeigersinn/gegen Uhrzeigersinn), möglichst abhängig von der Richtung, in der sich das Ziel befindet.
[3] Schau in Richtung Ziel, prüfe ob die beiden direktesten Wege (bis zur selben Höhe laufen, dann direkt drauf zu; oder bis zur selben Breite laufen und dann direkt drauf zu) zum Ziel führen. Wenn ja laufe diesen Weg und weiter bei Punkt [1]. Wenn nein:
[4] Prüfe anhand deiner Laufrichtung (z.B. gradeaus, Uhrzeigersinn), in welche Richtung du nun gehen solltest, ist ein Hindernis oder bereits komplett abgesuchter Block im Weg, drehe dich. Müsstest du dich 4x drehen, abbruch: Eingesperrt/Kein Weg [X]. Ansonsten markiere das aktuelle Feld als besucht und in welcher Richtung du es verlassen hast und laufe zum freien Feld weiter. Weiter bei Punkt [2].

[X] Neues Ziel suchen, falls kein neues Ziel verfügbar, virtuelle Mauern entfernen und diese ansteuern.

Den Weg aus Labyrinthen findest du damit ziemlich gut, einfach die Schulter an immer der selben Wand lassen und daran entlanglaufen. Wenn man an einen Punkt kommt, den man bereits kennt, kann (muss!) man diese Regel umkrempeln.

Warten wir lieber auf Tommek. Ich glaube nicht, dass er eine Lösung sucht, um einen Weg zu finden. Das Gehen will er glaube ich selbst übernehmen (Spiel?).

Ach jetzt verstehe ich, er will den Schatten berechnen, nicht erkunden. Woran scheiterst du denn genau?

"Schatten berechnen" das trifft es am besten.

Die Inhalte der Koordinaten sind allesamt bekannt, bewegen innerhalb des Labyrinths kann ich mich auch. Jetzt geht es darum, dass man nur das sieht was einem direkt sichtbar ist.

Blau soll also nicht durch Wände gucken.




Mein erster Gedanke war für die einzelnen Koordinaten abzuspeichern wann sie Sichtbar sind:
1/1 ist sichtbar wenn: 2/2 und 3/3 frei
3/7 ist sichtbar wenn: 3/6 und 4/5 und 4/6 frei
....

Das wird aber mit einem eventuell wachsenden Sichtfenster unüberschaubar viel.
Eine entsprechende Formel zu finden viel mir bisher schwer, da der "Blick" ja vom Zentrum ausgeht und nicht von einer feststehenden Ecke.

Vierecke als Punkte zu nehmen ist etwas verwirrend.

Ich würde dir auf jeden Fall zu einem Cache raten. Lass dir einmal durch einen Cronjob oder wenn du keine Lust auf die Knobelei hast, mach es von Hand ausrechnen, welche Mauerpunkte welchen Schatten erzeugen. Für diese Karte wären es 5x5 - 1 Hindernisse. Die am Rand liegen erzeugen ja keinen Schatten. Wenn du jetzt weißt, dass Hindernis 3/3 den Schatten 1/1 - 3/3 erzeugt, weil diese Information bei dir im Cache rumlümmelt, dann wirst du die Schattenerzeugung ziemlich schnell hinbekommen.

Bei einer Karte von 50x50 wären das dann 48x48 - 1 "Cache"-Einträge. 2303 Einträge. Eine recht gut handlebare Menge.


OK berechnen müsstest du den Quark für größere Karten trotzdem. Was anderes als Polygonberechnung für die Sichtlinien und die Kästchen fällt mir nicht ein, bestimmt gibts aber eine einfachere Lösung. Hätte mir gedacht du schaust, wie dein Weg zum Hindernis aussieht und läufst diesen Zickzackkurs dann einfach weiter.

Es ist noch komplizierter. Position Blau wird nämlich als Punkt betrachtet, die Wände aber mindestens als Kante quer zur Blickrichtung. So wird eigentlich schon strittig, ob im oberen Bsp. 1/3 3/1 7/3 7/5 ... überhaupt im Schatten liegen. Und da blau eben kein Punkt ist, ist auch die Betrachtungsweise different. Steht blau direkt an der Wand 4/5 mit Blickrichtung nach unten, würde er eigetnlich ab Zeile 5 oder 6 überhaupt nix mehr sehen. Idealisiert könnte man Sichtwinkel von 90° annehmen, das löst allerdings noch nicht die Aufgabe für Wand 6/4.

Du mußt erstmal einen theoretischen Algoritmus entwickeln, wann Objekte noch sichtbar sind. Also sozusagen die Nicht-Sicht Dreiecke für eine Wand auf den umliegenden Feldern definieren. Denkbar wäre eine Matrix, die die nächsten m x n Felder angibt. Für jedes Feld der bspw. umliegenden 5x5 Felder erstellst Du so eine Matrix und läßt sie über das Spielfeld berechnen. Bereits bestimmte Punkte überspringst Du (oder AND-operierst Sie mit vorhandenen Ergebnissen).

Nein nein So Kompliziert ist es dann doch nicht.

Die Kartengröße ist unbegrenzt. Der Bildausschnitt ist immer gleich groß wie im Beispiel. Blau wird nicht als Punkt gesehen, also eigentlich schon aber alle Felder sind gleich groß, dh. die anderen Felder sind auch Punkte. Die Kantengrenzen Interessieren nicht. Stellt euch ein Schachbrett vor mit quadratischen Säulen die aus einigen Feldern in die Höhe schießen. Blau ist dann eine quadratische Lampensäule in der Mitte (wobei Felder mit halben Schatten als beleuchtet gelten).

Ich möchte jetzt wirklich nur berechnen oben links von Blau ist eine Wand, also ist alles dahinter schwarz.

Alles außerhalb des Sichtbereiches von 7x7 Feldern interessiert in keinster Weise.

Dann würd ich das vielleicht wirklich zur runtime berechnen. 48 Matrizen erstellen, für jeden Punkt an dem eine Wand stehen kann und dahinterliegende Punkte mit bool false definieren.

Deine Sichtbarkeiten finde ich trotzdem strittig, die Betrachtungsweise als Säule machts noch schlimmer.

Japp, Berechnung zur Laufzeit ist die beste Lösung.
Deine Zeichnung ist schon OK. Schatten werden eben "gerundet".