Zum Inhalt

LOS oder auch Line of Sight

LOS oder die Berechnung oder Herleitung derselben für meine seit Jahren gehegten „Kachelbasierten Spiele“ (engl.: tile-based games) hat mich schon sehr lange gefesselt, frustriert und beschäftigt.

Vor ein paar Tagen habe ich es aufgegeben, eine wirkliche Berechnungsmethode zu schaffen. Statt dessen arbeite ich seit gestern erstmal mit einer LUT oder Look-up table, in der für eine auf 10 Felder begrenzte Sichtweite einer Spielfigur Werte abzulesen sind.

Was sind „tile-based games“?
Für den uneingeweihten Mitleser (oder für mich selbst, sollte ich jemals einen Gedächtnisverlust erleiden) hier kurz noch die Hintergründe.
In tile-based games wird die Spielwelt aus kleinen „Kacheln“ zusammengesetzt. Eine „Kachel“ kann dabei – je nach Maßstab – ein Stück Grasland, ein Baum, ein Haus, ein Dorf oder ähnliches darstellen. Wenn man genügend verschiedene „Kacheln“ gestaltet hat, kann man eine nette Landschaft zusammenbauen. Wie mit einem Baukasten.
In der Regel unterliegt so einem Spiel ein schlichtes Raster, das stark an Schiffeversenken oder eine Exceltabelle erinnert; es gibt Felder in horizontaler und in vertikaler Richtung und jedes davon lässt sich eindeutig benennen, z.B. mit „A1“ oder „(3,5)“, je nach Bezeichnung der zwei Achsen.
Nun faszinieren mich besonders KoSims oder Konfliktsimulationsspiele. Berühmte Vertreter dieses Genres sind Risiko, Axis and Allies oder Diplomacy. Bei diesen Spielen geht es also um die Inszenierung von Konflikten und der spielhaften Auseinandersetzung mit der jeweiligen Rolle des Spielers dabei. Langer Rede kurzer Sinn: es wird Krieg gespielt. Spieler A haut Spieler B, der haut zurück, usw.
Ein Aspekt unter vielen bei solchen Spielen kann die „Sichtlinie“ (engl. „Line Of Sight“ oder kurz „LOS“) sein, d.h. kann Spielfigur X die Spielfigur Y sehen oder stehen/liegen Hindernisse dazwischen, die den Sichtkontakt verhindern?

Träumereien
Da ich bereits seit Flash 4 kleine tile-based games entwickele, habe ich inzwischen genügend Erfahrungen gesammelt, die das Erschaffen einer ansehnlichen Spielwelt erlauben. Daher wurde es allmählich Zeit, ein, zwei Dinge zu finden, die in heute im Internet verfügbaren Flashspielen noch nicht oder nur schwach umgesetzt enthalten sind.
Ich stelle mir vor, dass zwei oder mehrere Spieler mit ihren Einheiten (welcher Art auch immer) durch meine Spielwelt laufen/fahren/schleichen/fliegen und einen Konflikt austragen, ohne die jeweils gegnerischen Einheiten ständig sehen zu können, wie es z.B. beim Schach möglich ist. Eher in Richtung Stratego, wo zwar die Einheiten sichtbar sind, aber nicht deren Rang. Um ehrlich zu sein, will ich eines Tages auf ein Niveau von Fallout Tactics hinaus. Ja, ich weiß – ich hab‘ ’nen Vogel, aber träumen werde ich wohl noch dürfen. Auf dem Weg zu diesem (zumindest mit Flash) unerreichbaren Ziel fällt sicher das eine oder andere markttaugliche Produkt ab. Da bin ich mir sicher.

Sichtlinie
Zurück zur LOS. Kurz die Problembeschreibung:
In einem 2D-Raster gibt es einerseits freie Flächen (Felder) und auf der anderen Seite für Spielfiguren undurchsichtige, undurchdringliche Hindernisse, wie z.B. Wände. Die Aufgabe, die gelöst werden soll, lautet, „besteht zwischen zwei gegebenen Feldern in diesem Raster eine Sichtlinie?“
Der Einfachheit halber wird festgelegt, dass die Sichtlinie blockiert ist, wenn sich auf dem Weg zwischen dem Start- und dem Zielfeld auch nur ein einziges Wand-Feld befindet.
Zur Ermittlung der LOS werden die Mittelpunkte der beiden Felder verbunden mit der vermeintlichen Sichtlinie.

Handarbeit statt Mathematik
Da mir keine mathematische Formel einfallen will, mittels derer ich herausfinden kann, welche Felder bei einer beliebigen Start-/Zielfeld-Paarung auf Vorhandensein einer Wand kontrolliert werden müssen, nehme ich diese Überprüfungen manuell vor und speichere diese Werte in Arrays. Die in Abb. 1 rot gekennzeichneten Felder müssten bei der Ermittlung der LOS auf Vorhandensein einer Wand geprüft werden.

los_abb1
Abb. 1: „Sehstrahl“ (Anm. „LOT“ ist falsch; „LOS“ ist gemeint)

Mir geht es bei dieser manuellen Lösung darum, die Werte, die ich durch viel Handarbeit erhalten werde, möglichst unabhängig von der späteren Beschaffenheit des Rasters einsetzen zu können. Daher bilde ich im ersten Schritt so genannte Delta-Werte, die die aktuelle „Prüfsituation“ beschreiben sollen.
Das Startfeld liegt bei (3,3), das Zielfeld bei (0,0), daher notiere ich als varDeltaX eine -3 (0 minus 3 gleich -3) und als varDeltaY ebenfalls eine -3.
Es mag bei allem, was ich hier beschreibe, sehr viel elegantere Wege geben. Da meine Kenntnisse auf dem Gebiet der OOP (Objekt Orientierte Programmierung) allerdings begrenzt sind, nehme ich das, was mir vertraut ist. In diesem Fall eine Kombination aus Variablen, Funktionen und Arrays. Am Ende soll eine Funktion entstehen, die aus Start- und Zielfeldkoordinaten einen Wert zurückgibt, der aussagt, ob LOS besteht oder nicht.

Das Array arDeltas…
Für meinen nächsten Schritt gebe ich jedem Feld meines Rasters noch eine eindeutige Nummer (Abb. 2).

los_abb2
Abb. 2: Durchnummerierte Felder

In einem Array arDeltas speichere ich nun zunächst die folgenden Werte:
-3, -3, 1. Warum das? Das sind die drei Werte, die die „Prüfsituation“ beschreiben, wie sie in der Abbildung zu sehen ist; varDeltaX, varDeltaY und die zugehörige Feldnummer. Die fertige Funktion soll später erst im Array arDeltas nachschauen, welche Feldnummer bei der gerade aktuellen „Prüfsituation“ zum tragen kommt.

…und die Arrays arDelta1 bis arDeltan
Dann, in einem weiteren Array, dessen Name etwa arDelta1 lautet, wird gezielt nachgeschaut, welche Felder auf Hindernisse geprüft werden müssen. Bei arDeltas und der Durchnummerierung des Rasters handelt es sich also lediglich um einen nötigen Umweg, da ich in Flash nicht direkt schreiben kann delta_-3_-3 = …; Dies führte zu einem Syntaxfehler.
Wie auch immer. In arDelta1 notiere ich jetzt tatsächlich die Delta-Werte der zwei oben rot gekennzeichneten Felder, so dass ich erhalte…

 

Der große Zusammenhang
Die fertige Funktion bekommt ja später die X- und Y-Koordinaten des Start- und Zielfeldes übergeben, zwischen denen auf Vorhandensein einer LOS geprüft werden soll, also wie im Beispiel oben…

 

Daraus ermittelt die Funktion LOS dann die zwei Abstände oder Delta-Werte varDeltaX = -3 und varDeltaY = -3.

Diese Werte werden in arDeltas gesucht und die damit verknüpfte Feldnummer 1 gefunden.

Daraufhin werden in genau einem weiteren Array, nämlich hier arDelta1, die Delta-Werte gefunden, die relativ zur aktuellen infrage kommenden Spielfigurposition geprüft werden müssen, hier also |-1, -1| und |-2,-2|.

Die Funktion prüft daraufhin effektiv die zwei Felder 2,2 (denn 3,3 als Startfeld mit Delta |-1,-1| bearbeitet führt zu Feld 2,2) und 1,1…

 

So etwas in der Art jedenfalls.

Nun ist der oben abgebildete Fall einer der einfachsten. Wenn alle „Prüfsituationen“ so überschaubar wären, bräuchte ich nicht auf eine handgemachte LOT ausweichen. Sind sie aber nicht, wie Abb. 3 zeigen soll. Dort ist zu erkennen, dass der „Sehstrahl“ vom Start zum Ziel mehrere Felder kreuzt, schneidet oder durchläuft, die alle auf Vorhandensein einer LOS behindernden Wand geprüft werden müssten.

los_abb3
Abb. 3: Kompliziertere „Prüfsituation“

Wie man sich denken kann, ist das Linienziehen und Array-Füllen einige Arbeit, um wenigstens eine halbwegs brauchbare LOT für Sichtweiten bis 5 Felder zu erhalten. Aus diesem Grund erstellte ich mir per Flash, PHP und lokalem Webserver eine kleine Hilfsapplikation, mit der das ganze Unterfangen schon einfacher und fast schon unterhaltsam wurde (einfache Gemüter sind leicht zu erfreuen).
Diese Applikation ergab dann ein arDeltas-Array mit 1323 Elementen und 441 arDeltaX-Arrays, die für Sichtweiten bis 10 Felder und entsprechende LOS-Ermittlungen ausreichen dürften. Klar, dieselbe Arbeit würde ich mir erneut machen müssen, wenn ich größere Sichtweiten zulassen wollte. Aber fürs erste reicht das.

Mein Plan für heute ist es, die fertige Funktion einzusetzen in einem „Spiel“, wo der Spieler lediglich durch einen Irrgarten rennen kann. Vor Spielbeginn hat der Computer eine Handvoll Felder des Irrgartens mit „Gegnern“ besetzt, per Zufall verteilt. Die Positionen dieser „Gegner“ sind dem Spieler verborgen.
Immer wenn die Spielfigur ein neues Feld betritt, wird die LOS-Funktion abgefeuert und geprüft, ob die Spielfigur in den Sichtbereich einer der „Gegner“ geraten ist. In dem Fall wird der „Gegner“ sichtbar.
Das soll’s auch schon sein – ich habe die Angewohnheit, beim Programmieren nur kleine Schritte zu unternehmen. Danach sehen wir weiter.

Update (23.03.2016):

Offenbar habe ich seinerzeit mein Vorhaben in die Tat umgesetzt. Herausgekommen war die folgende Flashanwendung: Line of Sight Test
Hier können die Rasterfelder geklickt werden, woraufhin Flash prüft, ob die LOS blockiert ist. Sichtlinie blockierende „Wände“ werden entsprechend gekennzeichnet.

Screenshot von Line of Sight Test

Veröffentlicht inSpielprogrammierung
Loading Facebook Comments ...

Schreibe den ersten Kommentar

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.


Warning: Declaration of sk2_rbl_plugin::treat_this($cmt_object) should be compatible with sk2_plugin::treat_this(&$cmt_object) in /www/htdocs/w00e0042/christianscholz.com/wp-content/plugins/SK2/sk2_plugins/sk2_rbl_plugin.php on line 342

Warning: Declaration of sk2_captcha_plugin::output_plugin_UI() should be compatible with sk2_plugin::output_plugin_UI($output_dls = true) in /www/htdocs/w00e0042/christianscholz.com/wp-content/plugins/SK2/sk2_plugins/sk2_captcha_plugin.php on line 70

Warning: Declaration of sk2_pjw_simpledigest::output_plugin_UI() should be compatible with sk2_plugin::output_plugin_UI($output_dls = true) in /www/htdocs/w00e0042/christianscholz.com/wp-content/plugins/SK2/sk2_plugins/sk2_pjw_daily_digest_plugin.php on line 277

Warning: Declaration of sk2_referrer_check_plugin::output_plugin_UI() should be compatible with sk2_plugin::output_plugin_UI($output_dls = true) in /www/htdocs/w00e0042/christianscholz.com/wp-content/plugins/SK2/sk2_plugins/sk2_referrer_check_plugin.php on line 78