# Problem mit Sichtfeld/Licht in einem Raster



## stevey (5. Jun 2012)

Hi Leute,
ich bin mal wieder dabei, ein Spiel zu programmieren. Dieses spielt sich innerhalb eines Rasters ab. Nun will ich eine Art Sichtfeld für die Spieler einbauen, man könnte das auch als Taschenlampe ansehen. Mein Problem dabei ist, den Teil, den man nicht sieht, also den Schatten, den Objekte werfen zu berechnen/herauszufinden. Alle Objekte sind in einem 2-dimensionalen Array gespeichert und sind streng an das Raster gebunden. So soll es auch mit dem Sichtfeld und dem Schatten sein.

Ich hab das ganze mal als Screenshot angehängt, um es zu verdeutlichen. 
Gelb markierte Felder = Sichtfeld/Licht
Kisten = Objekte, die die Sicht blockieren/Schatten werfen

Meine Frage ist also, wie würde sich ein Schatten hier verhalten und wie berechnet man ihn?

Danke , euer stevey


----------



## SlaterB (5. Jun 2012)

ein paar Regeln musst du selber festlegen, 
nimm die erste Kiste 4 Felder vom friedlichen Spieler entfernt, was ist mit dem Feld direkt nördlich, 
soll dieses vom Spieler komplett sichtbar oder komplett schattig oder (hoffentlich nicht) gemischt sein?

wenn mir ein recht spontaner Versuch erlaubt ist, es mag noch bessere geben: 
nimm von Kisten in nördliche Richtung jeweils die obere linke und untere rechte Ecke, 
bilde zwei mathematische Linien, etwa zum Mittelpunkt des Spieler-Kästens, 
(das muss also in einem etwas genaueren mathematischen Koordinatensystem passieren,  , Kästenbreite 1,
außerdem öde Mathe-Geraden usw., doch mal wieder zu was gute)

gehe von der Kiste aus weiter in x-Richtung, soweit nötig, berechne für ein x und das nächste x, x+1, die 4 y-Werte für diese beiden Linien, 
auf einer Papierskizze wirst du die Schnittpunkte erkennen und auch welche Kästchen ganz oder teilweise (gar % abschätzen) davon umschlossen werden,
bisschen Arbeit das in Java zu übersetzen, aber nichts was man nicht gezielt mit Grundmitteln erarbeiten kann,
diese gefundenen Felder liegen dann im Schatten, falls nicht sowieso schon von vorherigen Durchläufen für andere Kisten, 
falls nicht selber eine Kiste usw.

nach Süden hin entsprechend alles andersrum, oder gespiegelt für entsprechende Kisten im Norden ausrechnen,
und die leicht zu denkenden passenden Felder im Süden markieren


----------



## Marco13 (5. Jun 2012)

Ja, das ist eigentlich "ganz normale" Schattenberechnung, aber eben ... komisch durch das grobe Raster. Vielleicht macht es das einem auch etwas leichter. @SlaterB Der Ansatz klingt nahe liegend, aber das mit dem "Norden" und "Süden" habe ich nicht ganz kapiert: Spontan würde ich von der Lichtquelle aus Strahlen durch die Ecken der Objekte schießen, und dahinter ein Polygon erstellen, das dem "2D-Shadow-Volume" entspricht. Dadurch, dass es ja nur um wenige Blöcke geht, kann man dann wohl recht schnell testen, ob die anderen Blöcke dort drin liegen.

Was zum Staunen, Weinen oder sonstwas: Left 4k Dead


----------



## fastjack (6. Jun 2012)

Ich würde mich an Ultima 4 orientieren, bisschen googlen (line of sight), dann findest Du den Algorithmus, ich glaube als Assembler, aber sehr gut dokumentiert. Für 2d mit Feldern ist das der beste meiner Meinung nach, den es je gab.

Ah, habs noch als Lesezeichen: 

Crafting a Vintage CRPG: Part 4


----------



## stevey (7. Jun 2012)

Vielen Dank an alle, das war gar nich so schwer wie erwartet .
Die Beschreibung von SlaterB hat mich ziemlich schnell auf die Idee mit den Polygonen, wie es Marco13 beschrieben hat gebracht, wodurch es mit relativ wenig aufwand möglich war, die Schatten zu berechnen.  Folgendes Problem :


> nimm die erste Kiste 4 Felder vom friedlichen Spieler entfernt, was ist mit dem Feld direkt nördlich


hab ich dann so gelöst, dass er nur Felder, die zu mehr als 50% in dem Polygon sind als Schatten dargestellt werden.

@Marco13
Left 4k Dead kannte ich schon und hab immer diesen Schattenwurf bewundert, aber jetzt weiß ich ungefähr wie so etwas funktioniert :applaus:.

@fastjack
hab mir den Link mal flüchtig angeschaut, aber da ich mit der Lösung durch Polygone schon recht weit war, hab ich mir den Artikel nicht genau durchgelesen. trotzdem danke dafür.

Und hier noch das Endergebnis:




Nochmals Danke, euer stevey


----------



## stevey (7. Jun 2012)

sry für den Doppelpost, aber ich hab jetzt noch eine Lösung gefunden, die sich speziell bei der Umsetzung in solch einem Raster anbietet. Und zwar prüfe ich einfach ob sich die Linien von jedem Punkt zu dem Spieler mit einem blockierenden Objekt schneidet. Wenn ja, wird dieses Rasterfeld als Schatten gekennzeichnet. Natürlich gehe ich dabei immer von dem Mittelpunkt der Kästchen aus. Der Vorteil von dieser Methode ist in meinen Augen eine bessere Performance und ein übersichtlicherer Code. Beides ist natürlich von der Art der Umsetzung beider Lösungen abhängig^^


----------

