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äumereienDa 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.
SichtlinieZurü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 MathematikDa 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.
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).
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 arDeltanDann, 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…
// arDeltas = new Array (-3,-3,1);
arDelta1 = new Array (-1,-1,-2,-2);
Der große ZusammenhangDie 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…
function LOS (3,3,0,0) {
…
}
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 arDelta
1, 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…
[codestart]if (feld2,2 == “wand” or feld1,1 == “wand”) {
// dann keine LOS gegeben!
}[codeend]
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.
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.