Erstellung einer Landkarte

Wege auf Landkarten finden

Man will sich ja nicht nur vorstellen wie ein Schiff von einer Stadt zur anderen fährt, sondern es am besten auch auf der Landkarte sehen können. Dafür wird erst mal eine ganz einfache Karte per Gimp erstellt. Dafür reichen im ersten Versuch bereits ein paar schwarze Flecken (die Inseln) auf weißen Hintergrund.

Für die Wegeberechnung selber kann man wunderbar den A* Algorithmus verwenden, man muss aber aufpassen, wie groß die Karte wird. Bei diesem Algorithmus werden extrem viele Punkte berechnet, im ungünstigsten Fall sogar alle Punkte der Karte. Dies würde bei einem Spielfeld von 1280×1024 Pixeln bereit  Punkte 1.310.720 ergeben. Ein paar einfache Tests den besten Weg auf einer Karte ohne Hindernisse zu finden (hierbei werden alle Punkte berechnet) ergeben eine PHP Programmlaufzeit von 30sek auf einem Intel i7 🙁

Optimierungen

Da die Laufzeit des Algorithmus mit der Größe der Karte exponentiell steigt, ist der einfachste Weg der Beschleunigung entweder die Kartengröße, oder die Anzahl der zu berechnenden Punkte, zu reduzieren. Als nächste Iteration für dieses Problem mache ich einfach beides!

Erstmal erstelle ich von der Ausgangskarte kleinere Versionen mit weniger Pixeln. Insgesamt generiere ich 5 Versionen der Karte. Danach berechne ich den Weg auf der Karte mit der 25fachen Verkleinerung. Diese hat nur noch 52×41 Bildpunkte, und der Weg ist im Bruchteil einer Sekunde berechnet. Diesen Weg nehme ich als Filter für die nächst größere Karte mit einer 10fachen Verkleinerung. Dadurch ergibt sich ein „Tunnel“, in welchem, der auf dieser Karte zu berechnende Weg liegt – die Anzahl der zu berechnenden Punkte wird massiv eingeschränkt.

Dies mache ich Schritt für Schritt weiter, bis ich eine Route auf der Karte in Originalgröße habe.

Visuelle Rechenschritte

So sehen die einzelnen Rechenschritte beispielhaft aus:

Weg auf Map 5fach

Weg auf Map 25fach

Tunnel auf Map 10fach

Das ganze Prozedere ist für die Wegefindung auf der Ausgangskarte mit den Ausmaßen 1280×1024 in unter 1 Sekunde erledigt, definitiv schnell genug für ein Browsergame! 😀

Ich definiere: ist fertig – auf zur nächsten Aufgabe!