Routenberechnung

Sebastian Stock

Hat der Agent ein Ziel ausgewählt, muss als nächstes eine Route berechnet werden. Diese soll möglichst so verlaufen, wie auch menschliche Spieler gehen könnten und würden. Daher bietet sich auch hier das Kartenmaterial von OpenStreetMaps an, welches auch schon vom Server für die Verteilung der Tresore und Geschenke verwendet wird. Es wird allerdings nicht direkt mit diesen Daten die Route geplant, sondern ein von CloudMade bereitgestellter Webservice zur Routenplanung benutzt.

CloudMade

CloudMade ist ein Unternehmen, das APIs, gerenderte Karten und positionsbasierte Webservices auf Basis von OpenStreetMaps anbietet. Einer dieser Webservices führt eine Routenberechnung zwischen zwei Geo-Koordinaten durch 1. Der Dienst ist kostenlos. Allerdings ist eine Registrierung notwendig, um einen API-Key zu erhalten, der bei jeder Anfrage mitgesendet werden muss. Eine Anfrage muss die Start- und Endpunkte als Geo-Koordinaten, die Art der Fortbewegung (Auto, Fahrrad oder Fußgänger) und das Ausgabeformat (JSON oder GPX) enthalten. Optional sind außerdem Zwischenpunkte, die Sprache der Anweisungen, die Längeneinheit und eine Angabe ob die kürzeste oder die schnellste Route bevorzugt werden soll. Beispielsweise liefert folgende Anfrage eine sehr kurze Route für einen Fußgänger von der Startposition (52.286585, 8.024641), welcher auf der Sedanstraße in Osnabrück liegt, zur Zielposition (52.286547, 8.024300) auf der Barbarastraße, im Datenformat JSON:

http://routes.cloudmade.com/BC9A493B41014CAABB98F0471D759707/api/0.3/52.286585,8.024641,52.286547,8.024300/foot.js

Die Antwort besteht aus einer Liste von Zwischenpunkten als Geo-Koordinaten, die auf der Route liegen, Fahranweisungen und allgemeinen Routeninformationen wie Gesamtlänge, geschätzte Dauer und Straßennamen des Start- und Zielpunktes. Die obige Anfrage liefert folgendes Ergebnis:

{   "version":0.3,
    "status":0, 
    "route_summary": {
        "total_distance":28,
        "total_time":20, 
        "start_point":"Sedanstraße",
        "end_point":"Barbarastraße"
    },
    "route_geometry": [
        [52.28656,8.02464], [52.286591,8.02429], [52.286549,8.02428]
    ],
    "route_instructions":[
        ["Richtung West auf Sedanstraße", 24, 0, 17, "24 m", "W", 277.2],
        ["Bei Barbarastraße links abbiegen", 4, 1, 3, "4 m", "S", 190.4, "TL", 273.3]
    ]
}

Zusätzlich gibt es von CloudMade auch eine Java-API, welche das Erstellen der Anfrage aus Java heraus noch weiter vereinfacht und die Antwort bereits verarbeitet. Damit wird die obige Routenberechnung folgendermaßen durchgeführt:

Point start = new Point(52.286585, 8.024641);
Point goal = new Point((52.286547, 8.024300);
CMClient cmClient = new CMClient(APIKEY);
Route route = cmClient.route( start, goal, RouteType.FOOT, null, null, "en", MeasureUnit.KM);

Verarbeitung der Route und aufgetretene Probleme

Die so erhaltene Route kann nicht direkt übernommen werden, sondern muss noch an die Bedürfnisse des Agenten angepasst werden. Ausgangsbasis ist eine Liste von Zwischenpunkten vom Typ Point, welche in Route enthalten ist. Diese besteht aus allen Eckpunkten der Route, zwischen denen sie gradlinig verläuft. Kurven der Straße werden so bereits von CloudMade durch eine größere Anzahl von Zwischenpunkten interpoliert, wodurch auch Routen auf nicht geradlinigen Straßen gut eingezeichnet werden können, indem diese Zwischenpunkte durch Linien verbunden werden, wie sich später in der Darstellung im Gameviewer zeigen wird.

Eine Route als Liste von Punkten ist für den Agenten vorteilhaft, da er so für die Simulation seiner Bewegnung nur über diese iterieren muss. Für eine flüssige Bewegung liegen die von CloudMade berechneten Punkte allerdings teilweise noch zu weit auseinander. Ziel ist es, dass zwischen zwei Updates der eigenen Position eine vorgegebene Dauer nicht überschritten wird. Daher werden zwischen zwei Punkten der Route weitere eingefügt, deren Abstand der Agent in der vorgegebenen Zeit zurücklegen kann.

Es sind teilweise Probleme mit den Startpunkten der von CloudMade berechneten Route aufgetreten. Der übergebene Startpunkt lag bei Tests mehrmals nicht am Anfang der berechneten Route, sondern in der Mitte. Dadurch lief der Agent in diesen Fällen erst zurück in die falsche Richtung. Um dieses abzufangen muss zunächst in der Liste der von CloudMade berechneten Punkte derjenige Punkt gesucht werden, der den geringsten Abstand zum Startpunkt hat und die vorherigen Punkte müssen verworfen werden. Die auf diese Weise generierte Route wird an den Server gesendet um sie im Gameviewer anzuzeigen. So kann einfach verfolgt werden, welchen Plan der Agent verfolgt.


1 http://developers.cloudmade.com/projects/show/routing-http-api


Page last modified on March 21, 2011, at 03:54 PM