Tutorial zur Erstellung polygonbasierter Karten

In diesem Beitrag möchte ich erklären, wie man polygonbasierte Karten erzeugen kann. Die Art und Weise, wie man diese erzeugen kann, habe ich aus dem Blog-Post von Amit Patel übernommen. Ich werde auf die ersten Schritte detailliert eingehen und mit Code-Beispielen in Java versuchen die Nachimplementierung einfach zu gestalten. Amit Patel hat die Generierung in Actionscript geschrieben. Wem das eher liegt kann sich seinen Code hier anschauen. Vorerst beschreibe ich nur die notwendigen Schritte, um eine polygonbasierte Karte zu erstellen. Sofern ich es für eigene Spielideen benötige, folgt hier gegebenenfalls eine Beschreibung der weiteren Schritte zur Anreicherung der Karten durch Höheninformationen, Gewässer und Flüsse.

So nun aber los: Was wir vor haben ist die Generierung von benachbarten Polygonen, die möglichst gleichmäßig verteilt und ähnliche Größe besitzen. Die Anzahl Kanten soll dabei variieren, um eine ansprechende und abwechslungsreiche Karte zu erhalten. Dafür gibt es eine Technik, die uns sehr schnell zu genau diesem Ziel führt. Wir generieren zufällige Punkte und bestimmen darauf eine Delaunay Triangulation die wir in ein Voronoi Diagramm überführen. Das Voronoi Diagramm stellt dabei unsere generierte Polygonkarte dar. Klingt schwierig, deshalb erstmal ein Link zu einem Java Applet, dass die Triangulierung und das resultierende Voronoi Diagramm darstellt. Durch Klicken kann man im Applet Punkte einfügen und sich dann wahlweise die Triangulierung oder das Voronoi Diagramm darstellen lassen.

Als Startpunkt benötigen wir also zufällig verteilte Punkte:

 

private void generateRandomPoints(int numberOfPoints) {
    final Random random = new Random();
    points = Lists.newLinkedList();
    for (int i = 0; i < numberOfPoints; i++) {
        Point2D randomPoint = new Point2D.Double(
        	random.nextDouble() * width,
        	random.nextDouble() * height);
        points.add(randomPoint);
    }
}

 

Als nächstes soll das Voronoi Diagramm anhand der Triangulierung bestimmt werden. Beide Schritte kann das oben erwähnte Java Applet berechnen. Da der Source-Code des Applets ebenfalls auf der Seite angeboten wird, können wir diesen hierfür verwenden. Da in diesem Code allerdings eigene Datenstrukturen verwendet werden, müssen wir ein Mapping in diese vornehmen. Für das Mapping und die Abstraktion von der Berechnung führen wir eine eigene Klasse ein. Dieser übergeben wir die gewünschte Kartengröße und alle Punkte, zu denen das Voronoi Diagramm berechnet werden soll.

private void createVoronoi() {
    voronoi = new Voronoi(new Rectangle2D.Double(0.0, 0.0, width, height));
    for (Point2D point : points) {
        voronoi.addPoint(point);
    }
}

Im Konstruktor der Klasse Voronoi erzeugen wir die Triangulierung, indem wir ein Startdreieck vorgeben. Das Startdreieck muss die gesamte Spielfeldfläche beinhalten um sicherzustellen, dass alle Punkte innerhalb des Dreiecks liegen. Die Berechnung der Punkte des Startdreiecks kann man dabei sehr einfach gestalten, indem man das Startdreieck so wählt, dass es aus 4 identischen Dreiecken besteht, die um das Spielfeld herum liegen. Die linke untere Ecke liegt somit bei der x-Koordinate des Spielfelds abzüglich der halben Spielfeldbreite. Die rechte untere Ecke bei x+width+width/2 und die obere bei x+width/2. Die y-Koordinaten der Punkte sind bei den unteren Ecken identisch zur y-Koordinate des Spielfelds. Für die obere Ecke wird die doppelte Spielfeldhöhe aufaddiert.

public class Voronoi {
 
    private Triangulation triangulation;
    private final Rectangle2D bounds;
 
    public Voronoi(Rectangle2D bounds) {
        this.bounds = bounds;
        triangulation = new Triangulation(createSurroundingTriangle(bounds));
    }
 
    private Triangle createSurroundingTriangle(Rectangle2D bounds) {
        Pnt left = new Pnt(bounds.getX() - bounds.getHeight(), bounds.getY());
        Pnt right = new Pnt(bounds.getX() + bounds.getWidth() + bounds.getHeight(),
        	bounds.getY());
        Pnt upper = new Pnt(bounds.getX() + bounds.getWidth() / 2.0,
        	bounds.getY() + bounds.getHeight() + bounds.getWidth() / 2.0);
 
        return new Triangle(left, right, upper);
    }
 
    public void addPoint(Point2D point) {
        triangulation.delaunayPlace(transformPoint(point));
    }
}

Nachdem wir ein Startdreieck für die Triangulierung vorgegeben haben, werden nach und nach alle zuvor zufällig gewählten Punkte hinzugefügt. Die Triangulierung wird dabei für jeden Punkt inkrementell aktualisiert. Dabei werden Dreiecke gebildet, die jeweils die Umkreisbedingung erfüllen. Die Umkreisbedingung besagt, dass kein anderer Punkt im Umkreis liegen darf, der entsteht, wenn man die Punkte eines Dreiecks durch einen Kreis verbindet. Im Beispiel ist die Umkreisbedingung für die linke Triangulierung erfüllt, während die rechte eine Verletzung der Umkreisbedingung darstellt.

Aus der fertigen Triangulierung können wir nun als letzten Schritt das Voronoi Diagramm berechnen. Dabei werden zu jedem Punkt die Mittelpunkte der tangierenden Umkreise als Polygon verbunden.

Triangulierung

Umkreise der Triangulierung

Polygon aus den Mittelpunkten der Umkreise

Um diesen Schritt umzusetzen, schreiben wir eine Methode, die uns zu einem gegebenen Punkt das umgebende Polygon berechnet. Zunächst wird ein Dreieck aus der Triangulierung herausgesucht, dass den gesuchten Punkt als Eckpunkt enthält. Dieses Dreieck kann nachfolgend als Startpunkt genutzt werden um alle weiteren Dreiecke die ebenfalls den gesuchten Punkt besitzen zu erhalten. Die Rückgabe ist dabei startend beim gegebenen Dreieck im oder gegen den Uhrzeigersinn sortiert. Diese Sortierung ist notwendig, da das resultierende Polygon andernfalls mit überschneidenden Linien im Zickzackkurs verbunden wäre. Für jedes Dreieck der Rückgabe wird der Umkreismittelpunkt bestimmt und als Polygonpunkt verwendet.

public Poly getPolygon(Point2D point) {
    List<Triangle> triangles = findSurroundingTriangles(point);
    Poly polygon = new PolySimple();
    for (Triangle triangle : triangles) {
        polygon.add(transformPoint(triangle.getCircumcenter()));
    }
    return polygon;
}
 
private List<Triangle> findSurroundingTriangles(Point2D point) {
    Pnt site = transformPoint(point);
    Triangle triangle = triangulation.locate(site);
    List<Triangle> list = triangulation.surroundingTriangles(site, triangle);
    return list;
}
 
private static Point2D transformPoint(Pnt point) {
    return new Point2D.Double(point.coord(0), point.coord(1));
}
 
private static Pnt transformPoint(Point2D point) {
    return new Pnt(point.getX(), point.getY());
}

Wenn wir für jeden Punkt ein Polygon bestimmen, erhalten wir nun bereits eine Karte. Diese hat allerdings noch ein Problem: Durch das vorgegebene Startdreieck, welches aus Punkten außerhalb des Spielfeldes besteht, und die Möglichkeit das Umkreismittelpunkte der Triangulierung außerhalb des Spielfeldes liegen können, gibt es Polygone die teilweise außerhalb des gewünschten Spielfeldes liegen oder aus diesem herausragen.

Das Problem lässt sich allerdings durch ein einfaches Clipping mit dem Spielfeld lösen. Für das Clipping zwischen Rechteck und Polygon verwende ich die Java-Portierung des General Poly Clipper Algorithmus von Alan Murta. Die Portierung wurde von Solution Engineering, Inc. vorgenommen. Deren Webseite ist aktuell “Under Construction“, sodass ich aktuell nur auf ein Web-Archiv verlinken kann. Die Implementierung und Lizenzbestimmungen finden sich hier. Prinzipiell kann aber auch jede andere Implementierung verwendet werden.

private Poly getClippedPolygon(Point2D point) {
    Poly polygon = voronoi.getPolygon(point);
    return Clip.intersection(polygon, createMapBoundsPolygon());
}
 
private Poly createMapBoundsPolygon() {
    Poly rectangle = new PolySimple();
    rectangle.add(0.0, 0.0);
    rectangle.add(width, 0.0);
    rectangle.add(width, height);
    rectangle.add(0.0, height);
    return rectangle;
}

Durch diese kleine Anpassung erhalten wir nun eine benutzbare Karte, wie im Bild rechts. Allerdings sind die Polygone noch ungleichmäßig und oft sehr schmal. Dies entsteht wenn die zufällig generierten Punkte nah aneinander liegen. Um eine gleichmäßigere Verteilung der Felder zu erreichen müssen die ursprünglich zufällig gewählten Punkte gleichmäßiger angeordnet werden. Hierfür schlägt Amit Patel verschiedene Varianten vor. Ich habe mich für eine sehr einfache entschieden, bei der ich jeden zufällig generierten Punkt in die Mitte des entstandenen Polygons verschiebe. Auf den verschobenen Punkten berechne ich dann erneut eine Triangulierung.

private void improveRandomPoints() {
    createVoronoi();
    for (Point2D point : points) {
        movePointToPolygonCenter(point);
    }
}
 
private void movePointToPolygonCenter(Point2D point) {
    Poly polygon = getClippedPolygon(point);
    Point2D polygonCenter = getPolygonCenter(polygon);
    point.setLocation(polygonCenter);
}
 
private Point2D getPolygonCenter(Poly polygon) {
    double centerX = 0.0;
    double centerY = 0.0;
    for (int i = 0; i < polygon.getNumPoints(); i++) {
        centerX += polygon.getX(i);
        centerY += polygon.getY(i);
    }
    centerX /= polygon.getNumPoints();
    centerY /= polygon.getNumPoints();
    return new Point2D.Double(centerX, centerY);
}

Die nach der Verschiebung entstehenden Polygone sind deutlich gleichmäßiger. Im Beispiel rechts sind die gleichen zufälligen Punkte zu sehen, die auch im vorhergehenden Resultat ohne die Verschiebung verwendet wurden – diesmal allerdings mit der Verschiebung und erneuter Berechnung der Triangulierung und Polygone.

Damit sind wir eigentlich auch schon am Ende. Übrig bleibt lediglich das Speichern der erzeugten Karte in einer geeigneten Datenstruktur. Sinnvoll ist es die Nachbarschaftsbeziehungen von Feldern, die aus der Triangulierung einfach zu gewinnen ist, direkt mit abzulegen.

private Map createMap() {
    Map map = new Map(width, height);
    map.addFields(createFields());
    return map;
}
 
private Collection<Field> createFields() {
    Collection<Field> result = Lists.newLinkedList();
    HashMap<Point2D, Field> mapping = Maps.newHashMap();
 
    for (Point2D point : points) {
        Poly polygon = getClippedPolygon(point);
        mapping.put(point, new Field(point, polygon));
    }
 
    for (Field field : mapping.values()) {
        Set<Point2D> neighbors = voronoi.getNeighbors(field.getCenter());
        for (Point2D neighbor : neighbors) {
            if (mapping.containsKey(neighbor)) {
                field.addNeighbor(mapping.get(neighbor));
            }
        }
        result.add(field);
    }
    return result;
}

Interessant ist hier der Aufruf voronoi.getNeighbors(…), der alle benachbarten Polygonzentren zu einem gegebenen Punkt zurückgibt. Die Implementierung dieser Methode greift dabei zunächst auf die bereits bekannte Methode findSurroundingTriangles zurück. Denn die Eckpunkte der angrenzenden Dreiecke sind die Zentren der benachbarten Polygone. Um keine Verbindungen zwischen Polygonen zu erhalten, die nach dem Clipping mit dem Spielfeld nicht mehr direkt benachbart sind, müssen Dreiecke deren Umkreismittelpunkt außerhalb des Spielfelds liegt vorab herausgefiltert werden.

public Set<Point2D> getNeighbors(Point2D point) {
    Set<Point2D> result = Sets.newHashSet();
    List<Triangle> triangles = filterTrianglesOutOfBounds(
    	findSurroundingTriangles(point));
    for (Triangle triangle : triangles) {
        for (Pnt neighbor : triangle) {
            result.add(transformPoint(neighbor));
        }
    }
    result.remove(point);
    return result;
}
 
private List<Triangle> filterTrianglesOutOfBounds(List<Triangle> triangles) {
    List<Triangle> result = Lists.newLinkedList();
    for (Triangle triangle : triangles) {
        if (triangleInBounds(triangle))
            result.add(triangle);
    }
    return result;
}
 
private boolean triangleInBounds(Triangle triangle) {
    return bounds.contains(transformPoint(triangle.getCircumcenter()));
}

Damit sind wir nun aber wirklich durch. Den Code habe ich in einem Projekt zusammengestellt und biete ihn hier zum herunterladen an. Den von mir geschriebenen Code steht unter Apache License 2.0. Zu beachten ist, dass die beiden verwendeten Implementierungen mit eigenen Lizenzbestimmungen daherkommen, die allerdings ebenfalls frei sind. Mehr dazu findet sich als Kommentar in den entsprechenden Klassen, sowie auf den Webseiten zu Delaunay und GPCJ.

Was folgt?

In meinem nächsten Post plane ich zu beschreiben, wie man die gerade erzeugten Karten mit OpenLayers im Browser darstellen und mit ihnen interagieren kann. Ich hoffe, dass ich einigen helfen konnte und freue mich auf Spiele mit interessanten Karten. Wenn ihr an einem solchen arbeitet hinterlasst bitte einen entsprechenden Kommentar. Bitte nutzt die Kommentarfunktion ebenfalls für Kritik und Anregungen.

Dieser Beitrag wurde unter Tutorials veröffentlicht. Setze ein Lesezeichen auf den Permalink.

Hinterlasse eine Antwort