✔ Labyrinthgenerator, Performanceprobleme

hi schnuffie,
schön wenn es Dir weiter half. Allerdings würde ich an Deiner Stelle wirklich nur die Koordinaten, die als Wege dienen merken, um auch auf sehr große Flächen Labyrinthe erstellen zu können. Noch rafinierter wäre es nur die Wegpunkte zu merken, jedoch bedeutet dies ein bissle lineare Algebra. Davon ausgehend, dass die Wege nur unendliche Steigung (vertikaler Weg) oder Steigung = 0 (horizontaler Weg) haben mag da vielleicht die Sache vereinfachen eine Routine zu entwickeln, die aus Wegpunkten wieder Wege gestaltet. Das ganze wäre sehr sehr Speicher optimierend.

Takidoso
 
Hi Takidoso,

hatte gestern Deinen Vorschlag in die Tat umgesetzt, mußte allerdings feststellen, daß der Zufall oft seltsame Wege geht, d.h. "zufällig" im Kreis geht und somit keine Folge-Positionen mehr findet. Stets wieder zu beginnen, bis es endlich klappt, bringt enorme Performance-Einbußen. :(

Schlußendlich hatte ich mich auch darauf geeinigt (tolles Deutsch...), daß ich zuerst den Weg mit seinen Zufalls-Positionen erstelle, solange, bis das Ziel erreicht ist, oder falls keine weitere Position möglich ist, anschließend wieder irgendwo starte und den Weg wiederfinde. Sobald der Weg erstellt ist (und eine gewisse Länge hat), ist es ein gültiges Labyrinth. Durch die mehrfach vorkommenden "Sackgassen", wo ich wieder mit einer neuen Position beginnen muß, werden von ganz allein Irrwege erstellt. Ich spare mir also die Irrweg-Schritte. :)

Das sich der Zufall bekanntlich nicht steuern läßt, passiert es in seltenen Fällen, daß sich in bestimmten Bereichen manches Labyrinths keine Weg-Positionen befinden.
In einem solchen Labyrinth ist der Lösungsweg natürlich einfacher zu finden, als in einem gut "gemischten" Labyrinth. Diesen Nachteil nehme ich in Kauf, da er bei größeren Labyrinths selten auftritt.
Das Entscheidende ist der Performance-Gewinn bei diesem Vorgehen:) :

10x10: < 2s
20x20: 5s
50x50: 40s
75x75: 2,5min

Ich denke, mit diesen Zeiten "kann ich leben" *freu*

Nun bin ich noch drauf und dran, Struktur in meinen Source-Code zu bringen und kann den dann auch gern für alle Interessierten hier bei Bedarf veröffentlichen.
 
Hallo Schnuffie,
die einzelnen Punkte habe ich zwar jetzt noch nicht ganz verstanden, die Du anführst, aber schön dass es nun nach Deinen Vorstellungen klappt.
Vielleicht verstehe ich es ja, wenn Du Deinen Code veröffentlichst.

schnuffie hat gesagt.:
Nun bin ich noch drauf und dran, Struktur in meinen Source-Code zu bringen und kann den dann auch gern für alle Interessierten hier bei Bedarf veröffentlichen.
Zum Vergrößern anklicken....

hihi, das scheint uns beide etwas zu unterscheiden, meist bringe ich erst Struktur und bei bestimmter Komplexität, die mir zu sonst unübersichtlich erscheint, fange ich mit Kommentaren an, und schreibe dann erst den eitgentlichen Sourcecode.

Takidoso
 
...manchmal dauert's länger als erwartet. ;-)

@taktdoso Schön, daß es auch Interesse für fertigen Code gibt...

Mein inneres Klassencaos habe ich nun bereinigt und kann den vorerst fertigen Code (ohne den Schnickschnack außenrum) mal darstellen:

Code: 
package com.webnobis.labyrinth.elements;

/**
 * Title: Labyrinth<br>
 * Description: Labyrinth<br>
 * Copyright: Copyright (c) 2006<br>
 * <br>
 * 
 * @author Steffen<br>
 * @version 1.00 (15.01.2006)<br>
 */
public interface Labyrinth {

    /**
     * Liefert die Breite.<br>
     * 
     * @return Breite
     */
    public int getWidth();

    /**
     * Liefert die Höhe.<br>
     * 
     * @return Höhe
     */
    public int getHeight();

    /**
     * Liefert alle Segmente dieses Labyrinths.<br>
     * Die Einträge sind sortiert von oben links nach unten rechts.<br>
     * 
     * @return Array aller Segmente
     * @see com.webnobis.labyrinth.elements.Segment
     */
    public Segment[] getSegmentArray();

}

Code: 
package com.webnobis.labyrinth.elements;

import java.util.Arrays;

/**
 * 
 * Title: AbstractLabyrinth<br>
 * Description: Abstraktes Basis-Labyrinth<br>
 * Copyright: Copyright (c) 2006<br>
 * <br>
 * 
 * @author Steffen<br>
 * @version 1.00 (21.02.2006)<br>
 */
public abstract class AbstractLabyrinth implements Labyrinth {

    private int width;

    private int height;

    /**
     * Konstruktor, der die Maße erwartet.<br>
     * 
     * @param width
     *            Breite
     * @param height
     *            Höhe
     */
    public AbstractLabyrinth(int width, int height) {
        if (width > 3) {
            this.width = width;
        } else {
            this.width = 3;
        }
        if (height > 3) {
            this.height = height;
        } else {
            this.height = 3;
        }
    }

    /**
     * 
     * @see com.webnobis.labyrinth.elements.Labyrinth#getWidth()
     */
    public int getWidth() {
        return width;
    }

    /**
     * 
     * @see com.webnobis.labyrinth.elements.Labyrinth#getHeight()
     */
    public int getHeight() {
        return height;
    }

    /**
     * Vergleicht mit dem Vergleichs-Objekt.<br>
     * Verglichen werden die Maße und Segmente (falls vorhanden).<br>
     * 
     * @param other
     *            Vergleichs-Objekt
     * @return true, bei Gleichheit
     */
    public boolean equals(Object other) {
        if (other == null) {
            return false;
        } else if (other == this) {
            return true;
        } else if (other instanceof AbstractLabyrinth) {
            return Arrays.equals(this.getSegmentArray(), ((AbstractLabyrinth) other).getSegmentArray());
        } else {
            return false;
        }
    }

    /**
     * Liefert den Hash-Code.<br>
     * 
     * @return Hash-Code
     */
    public int hashCode() {
        return this.width ^ this.height;
    }

    /**
     * Liefert die String-Repräsentation.<br>
     * 
     * @return String-Repräsentation
     */
    public String toString() {
        return this.getClass().getName() + " (" + this.width + 'x' + this.height + ')';
    }

}

Code: 
package com.webnobis.labyrinth.elements;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.Random;

/**
 * 
 * Title: RandomLabyrinth<br>
 * Description: Zufälliges Labyrinth<br>
 * Copyright: Copyright (c) 2006<br>
 * <br>
 * 
 * @author Steffen<br>
 * @version 1.00 (21.02.2006)<br>
 */
public class RandomLabyrinth extends AbstractLabyrinth {

    private Random r;

    private Segment[] segmentArray;

    private int minWayPosition;

    private RelativePosition relativePosition;

    /**
     * Konstruktor, der die Maße erwartet.<br>
     * Erstellt wird ein zufällig generiertes Labyrinth mit mindestens einem Lösungsweg.<br>
     * 
     * @param width
     *            Breite
     * @param height
     *            Höhe
     */
    public RandomLabyrinth(int width, int height) {
        super(width, height);
        this.r = new Random();
        this.minWayPosition = ((width * height) - ((width * 2) + (height * 2))) / 2;
        this.init();
    }

    // Initialisierung
    private void init() {
        this.segmentArray = new Segment[super.getWidth() * super.getHeight()];
        Position entry;
        Position target;
        switch (r.nextInt(4)) {
            case 0:
                entry = new Position(0, r.nextInt(super.getHeight() - 2) + 1);
                target = new Position(super.getWidth() - 1, r.nextInt(super.getHeight() - 2) + 1);
                break;
            case 1:
                entry = new Position(super.getWidth() - 1, r.nextInt(super.getHeight() - 2) + 1);
                target = new Position(0, r.nextInt(super.getHeight() - 2) + 1);
                break;
            case 2:
                entry = new Position(r.nextInt(super.getWidth() - 2) + 1, 0);
                target = new Position(r.nextInt(super.getWidth() - 2) + 1, super.getHeight() - 1);
                break;
            default:
                entry = new Position(r.nextInt(super.getWidth() - 2) + 1, super.getHeight() - 1);
                target = new Position(r.nextInt(super.getWidth() - 2) + 1, 0);
        }
        this.relativePosition = new RelativePosition(target, super.getWidth(), super.getHeight());
        this.addSolutionWay(new ArrayList(super.getWidth() * super.getHeight()), entry, target);
    }

    // Lösungsweg hinzufügen
    private void addSolutionWay(List list, Position entry, Position target) {
        boolean isWay;
        WayFinder wf;
        Position position;
        int i, count;
        do {
            // Startposition einnehmen
            count = 0;
            list.clear();
            Arrays.fill(segmentArray, Segment.WALL); // count < minWayPosition
            position = entry;
            // Weg erstellen
            for (i = 0; i < (super.getWidth() * super.getHeight() * 10); i++) {
                isWay = false;
                position = this.nextPosition(list, position);
                if (position == null || (count < minWayPosition && position.equals(target))) {
                    position = (Position) list.remove(r.nextInt(list.size()));
                    isWay = this.canSet(position);
                } else {
                    isWay = true;
                }
                if (isWay) {
                    if (position.equals(target)) {
                        break;
                    }
                    count++;
                    segmentArray[PositionTranslator.toPosition(position.getX(), position.getY(), super.getWidth())] = Segment.WAY;
                }
            }
            segmentArray[PositionTranslator.toPosition(entry.getX(), entry.getY(), super.getWidth())] = Segment.ENTRY;
            segmentArray[PositionTranslator.toPosition(target.getX(), target.getY(), super.getWidth())] = Segment.TARGET;
            wf = new WayFinder(this);
        } while (!wf.hasWay() || (count < minWayPosition));
    }

    // liefert die nächste zufällig gefundene erlaubte Position
    private Position nextPosition(List listWay, Position position) {
        Position nextPosition;
        List list = relativePosition.getPositionList(position);
        listWay.addAll(list);
        while (!list.isEmpty()) {
            nextPosition = (Position) list.remove(r.nextInt(list.size()));
            if (this.canSet(nextPosition)) {
                return nextPosition;
            }
        }
        return null;
    }

    // true, wenn mögliche Position
    private boolean canSet(Position position) {
        int wayCount = 0;
        int pos;
        Position nextPosition;
        Iterator it = relativePosition.getPositionList(position).iterator();
        while (it.hasNext()) {
            nextPosition = (Position) it.next();
            pos = PositionTranslator.toPosition(nextPosition.getX(), nextPosition.getY(), super.getWidth());
            if (!Segment.WALL.equals(segmentArray[pos])) {
                wayCount++;
            }
        }
        return (wayCount < 2); // Anzahl bereits vorhandener Weg-Positionen prüfen
    }

    /**
     * 
     * @see com.webnobis.labyrinth.elements.Labyrinth#getSegmentArray()
     */
    public Segment[] getSegmentArray() {
        return segmentArray;
    }

}

Code: 
package com.webnobis.labyrinth.elements;

import java.io.Serializable;

/**
 * 
 * Title: Position<br>
 * Description: Koordinaten<br>
 * Copyright: Copyright (c) 2006<br>
 * <br>
 * 
 * @author Steffen<br>
 * @version 1.00 (15.01.2006)<br>
 */
public class Position implements Serializable, Comparable {

    // generiert
    private static final long serialVersionUID = 3100301197596399072L;

    private final int x;

    private final int y;

    /**
     * Konstruktor, der die Koordinaten erwartet.<br>
     * 
     * @param x
     * @param y
     */
    public Position(int x, int y) {
        super();
        this.x = x;
        this.y = y;
    }

    /**
     * Liefert x.<br>
     * 
     * @return x
     */
    public int getX() {
        return x;
    }

    /**
     * Liefert y.<br>
     * 
     * @return y
     */
    public int getY() {
        return y;
    }

    /**
     * Liefert den Hash-Code.<br>
     * 
     * @return Hash-Code
     */
    public int hashCode() {
        return x ^ y ^ 1971;
    }

    /**
     * Vergleicht mit dem Vergleichs-Objekt.<br>
     * Verglichen werden x und y.<br>
     * 
     * @param other
     *            Vergleichs-Objekt
     * @return true, bei Gleichheit
     */
    public boolean equals(Object other) {
        if (other == null) {
            return false;
        } else if (this == other) {
            return true;
        } else if (other instanceof Position) {
            Position p = (Position) other;
            return this.x == p.x && this.y == p.y;
        } else {
            return false;
        }
    }

    /**
     * Vergleicht mit dem Vergleichs-Objekt.<br>
     * Verglichen werden x und y.<br>
     * Es wird 0 bei Gleichheit zurückgegeben.<br>
     * Nur wenn y gleich ist, wird x ausgewertet.<br>
     * Sind diese Koordinaten kleiner als die Koordinaten des Vergleichs-Objekts, wird -1 zurückgegeben.<br>
     * Sind diese Koordinaten größer als die Koordinaten des Vergleichs-Objekts, wird 1 zurückgegeben.<br>
     * 
     * @param other
     *            Vergleichs-Objekt
     * @return -1, 0 oder 1
     * @throws NullPointerException,
     *             wenn das Vergleichs-Objekt null ist
     * @throws ClassCastException,
     *             wenn das Vergleichs-Objekt keine Position ist
     * 
     */
    public int compareTo(Object other) throws NullPointerException, ClassCastException {
        if (this.equals(other)) {
            return 0;
        } else {
            Position p = (Position) other;
            if (this.y < p.y) {
                return -1;
            } else if (this.y > p.y) {
                return 1;
            } else if (this.x < p.x) {
                return -1;
            } else {
                return 1;
            }
        }
    }

    /**
     * Liefert die String-Repräsentanz.<br>
     * 
     * @return String-Repräsentanz
     */
    public String toString() {
        return "Position (" + x + ':' + y + ')';
    }

}

Code: 
package com.webnobis.labyrinth.elements;

import java.io.Serializable;

/**
 * 
 * Title: Segment<br>
 * Description: Mauer, Weg, Lösungsweg, Eingang oder Ziel<br>
 * Copyright: Copyright (c) 2006<br>
 * <br>
 * 
 * @author Steffen<br>
 * @version 1.00 (15.01.2006)<br>
 */
public final class Segment implements Serializable {

    // generiert
    private static final long serialVersionUID = 8354478227560744505L;

    /**
     * Weg<br>
     */
    public static final Segment WAY = new Segment(' ');

    /**
     * Mauer<br>
     */
    public static final Segment WALL = new Segment('#');

    /**
     * Lösungsweg<br>
     */
    public static final Segment SOLUTION = new Segment('O');

    /**
     * Eingang<br>
     */
    public static final Segment ENTRY = new Segment('E');

    /**
     * Ziel<br>
     */
    public static final Segment TARGET = new Segment('T');

    private final char type;

    // unsichtbar
    private Segment(char type) {
        this.type = type;
    }

    /**
     * Liefert den Typ des Segments.<br>
     * 
     * @return Typ
     */
    public char getType() {
        return this.type;
    }

    /**
     * Vergleicht mit dem Vergleichs-Objekt.<br>
     * Verglichen wird der Typ des Segments.<br>
     * 
     * @param other
     *            Vergleichs-Objekt
     * @return true, bei Gleichheit
     */
    public boolean equals(Object other) {
        if (this == other) {
            return true;
        } else if (other == null) {
            return false;
        } else if (other instanceof Segment) {
            return ((Segment) other).type == this.type;
        } else {
            return false;
        }
    }

    /**
     * Liefert den Hash-Code.<br>
     * 
     * @return Hash-Code
     */
    public int hashCode() {
        return this.type;
    }

    /**
     * Liefert die String-Repräsentanz.<br>
     * 
     * @return String-Repräsentanz
     */
    public String toString() {
        return "Segment (" + this.type + ')';
    }

}

Code: 
package com.webnobis.labyrinth.elements;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Set;
import java.util.SortedMap;
import java.util.TreeMap;

/**
 * 
 * Title: WayFinder<br>
 * Description: Findet die Lösungswege durch das Labyrinth<br>
 * Copyright: Copyright (c) 2006<br>
 * <br>
 * 
 * @author Steffen<br>
 * @version 1.00 (15.01.2006)<br>
 */
public class WayFinder {

    private Labyrinth labyrinth;

    private Position entry;

    private Position target;

    private RelativePosition relativePosition;

    private Random r;

    private SortedMap wayMap;

    /**
     * Konstruktor, der das Labyrinth erwartet.<br>
     * 
     * @param labyrinth
     *            Labyrinth
     */
    public WayFinder(Labyrinth labyrinth) {
        this.labyrinth = labyrinth;
        this.entry = PositionTranslator.toPosition(Arrays.asList(labyrinth.getSegmentArray()).indexOf(Segment.ENTRY), labyrinth.getWidth());
        this.target = PositionTranslator.toPosition(Arrays.asList(labyrinth.getSegmentArray()).indexOf(Segment.TARGET), labyrinth.getWidth());
        this.relativePosition = new RelativePosition(target, labyrinth.getWidth(), labyrinth.getHeight());
        this.r = new Random();
    }

    /**
     * Prüft, ob es mindestens einen Lösungsweg gibt.<br>
     * 
     * @return true, wenn es mindestens einen Lösungsweg gibt
     */
    public boolean hasWay() {
        return this.getWaySize() > 0;
    }

    /**
     * Liefert die Anzahl der Lösungsweg-Segmente des kürzesten Lösungswegs.<br>
     * Wenn kein Lösungsweg gefunden wurde, wird -1 zurückgegeben, sonst wird er im Labyrinth als Lösungsweg markiert.<br>
     * 
     * @return Anzahl der Lösungsweg-Segmente oder -1
     */
    public int findShortestWay() {
        if (this.wayMap == null) {
            this.wayMap = this.findWays();
        }
        if (wayMap.isEmpty()) {
            return -1;
        }
        int pos;
        Position position;
        Set waySet = (Set) wayMap.get(wayMap.firstKey()); // kürzester Weg
        Iterator it = waySet.iterator();
        while (it.hasNext()) {
            position = (Position) it.next();
            pos = PositionTranslator.toPosition(position.getX(), position.getY(), labyrinth.getWidth());
            labyrinth.getSegmentArray()[pos] = Segment.SOLUTION;
        }
        return waySet.size();
    }

    /**
     * Liefert die Anzahl der Lösungsweg-Segmente eines zufällig gewählten Lösungswegs.<br>
     * Wenn kein Lösungsweg gefunden wurde, wird -1 zurückgegeben, sonst wird er im Labyrinth als Lösungsweg markiert.<br>
     * 
     * @return Anzahl der Lösungsweg-Segmente oder -1
     */
    public int findRandomWay() {
        if (this.wayMap == null) {
            this.wayMap = this.findWays();
        }
        if (wayMap.isEmpty()) {
            return -1;
        }
        int pos;
        Position position;
        List list = new ArrayList(wayMap.keySet());
        Set waySet = (Set) wayMap.get(list.get(r.nextInt(list.size()))); // zufälliger Weg
        Iterator it = waySet.iterator();
        while (it.hasNext()) {
            position = (Position) it.next();
            pos = PositionTranslator.toPosition(position.getX(), position.getY(), labyrinth.getWidth());
            labyrinth.getSegmentArray()[pos] = Segment.SOLUTION;
        }
        return waySet.size();
    }

    /**
     * Liefert die Anzahl der Lösungswege.<br>
     * Wenn kein Lösungsweg gefunden wurde, wird 0 zurückgegeben.<br>
     * 
     * @return Anzahl der Lösungswege
     */
    public int getWaySize() {
        if (this.wayMap == null) {
            this.wayMap = this.findWays();
        }
        return wayMap.size();
    }

    /**
     * Entfernt den markierten Lösungsweg wieder aus dem Labyrinth.<br>
     */
    public void clearFoundWays() {
        for (int i = 0; i < labyrinth.getSegmentArray().length; i++) {
            if (Segment.SOLUTION.equals(labyrinth.getSegmentArray()[i])) {
                labyrinth.getSegmentArray()[i] = Segment.WAY;
            }
        }
    }

    // findet die Lösungswege
    private SortedMap findWays() {
        SortedMap wayMap = new TreeMap();
        this.findWay(this.entry, new HashSet(), new HashSet(), wayMap);
        return wayMap;
    }

    // recursive Methode
    // true, wenn das Ziel gefunden wurde
    private boolean findWay(Position current, Set waySet, Set solutionSet, Map wayMap) {
        if (current.equals(this.target)) {
            wayMap.put(new Integer(solutionSet.size()), solutionSet);
            return true;
        }
        boolean hasNext = false;
        int pos;
        Segment segment;
        Set set;
        Position position;
        Iterator it = relativePosition.getPositionList(current).iterator();
        while (it.hasNext()) {
            position = (Position) it.next();
            pos = PositionTranslator.toPosition(position.getX(), position.getY(), labyrinth.getWidth());
            if (!waySet.contains(position)) {
                waySet.add(position);
                segment = labyrinth.getSegmentArray()[pos];
                if (Segment.WAY.equals(segment) || Segment.TARGET.equals(segment)) {
                    set = new HashSet(solutionSet);
                    if (Segment.WAY.equals(segment)) {
                        set.add(position);
                    }
                    if (this.findWay(position, new HashSet(waySet), set, wayMap)) {
                        hasNext = true;
                    }
                }
            }
        }
        return hasNext;
    }
}

Und wie sieht das Ergebnis aus? Das fertige Programm gibt's unter "Entwickler/labyrinth" auf http://www.webnobis.com .

Danke an alle, die mir engagiert geholfen haben.
 
Was mich interessieren würde .. Hast du die Javadoc Kommentare alle per Hand eingetragen oder, falls du mit Eclipse arbeitest, gibt es da irgend ein Plugin, welches schon automatisch Kommentare bspw. für Methodenparameter usw. schablonenartig anfertigt oder ist das sogar schon in Eclipse selbst integriert? :)

Danke schön,
Gruß teppi
 
Hallo!

In Eclipse kannst du die Templates fuer java Doc Kommentare ueber Window -> Preferences -> Java -> Code style -> Code templates -> Comments -> bearbeiten.

Weiterhin kannst du einer Methode die noch keinen Java Doclet Kommentar hat mittels der Tastenkombination alt + shift + j einen solchen hinzufuegen.

Alternativ dazu kann man die Methoden/ Typen auch im Outline markieren und dort die genannte Tastenkombination verwenden. Dann werden Java Doc Kommentare fuer alle selektierten Elemente generiert.

Gruss Tom
 
Preferences -> Java -> Code Style

Dort kann man einige Einstellungen vornehmen.

/*Edit
Damn ich habe die 2te Seite nicht gesehen :D
 
Tom kennt sich wie immer gut aus.

Habe meine Javadoc-Kommentare in Eclipse als Template aufgenommen und modifiziere sie nur, falls erforderlich. Bei überlagerten Methoden kopiere ich gelegentlich die Kommentare.

P.S.:

Mit "/**" werden diese Standard-Template-Kommentare vorgegeben...
 
Hallo,

ich weiß nicht, ob noch jemand an einem Algorithmus für einen Labyrinthgenerator interessiert ist? Ich habe gestern einen programmiert und danach diese Diskussion gefunden. Ihr könnt Ihn hier ausprobieren:
http://www.your-memory.de/labyrinth/

Er schafft eine 100x100 Matrix in ca. 2 Sekunden. Es gibt immer nur genau einen richtigen Weg. Alle Abzweigungen sind Sackgassen.

Falls jemand an dem Algorithmus interessiert ist, erkläre ich ihn gern. Falls Ihr noch andere Algorithmen kennt, bin ich auch sehr daran interessiert.

Viele Grüße,
Schimmel
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück