Möglichen Pfad überprüfen

P

Plauzi92

Aktives Mitglied
Hi zusammen,

ich sitze gerade an einem kleineren Projekt und hätte dazu eine Frage.
Ein Labyrinth hat einen Start- und einen Zielpunkt und natürlich Wände. Die Wände können vom Spieler gesetzt werden. Vor dem Platzieren muss allerdings geprüft werden, ob danach noch ein Pfad zum Ziel vorhanden ist. Zuerst dachte ich an A* oder Djikstra, aber da mir der kürzeste Weg egal ist, wollte ich es etwas simpler halten.
Ich hab das ganze mal auf einem Blatt Papier versucht und bin auf eine Lösung gekommen. Ich denke die entspricht der Breitensuche wenn mich nicht alles täuscht :D
Die Frage ist, ob das ganze noch einfacher geht bzw. würde mich mal interessieren wie ihr das lösen würdet.

Setze den Startpunkt in die geschlossene Liste
Setze alle Nachbarn in die offene Liste
Solange der Endpunkt nicht in der geschlossenen Liste ist: (Hier könnte man eigentlich auch die offene Liste prüfen denke ich)
Solange die offene Liste nicht leer ist:
Entferne das erste Element der offenen Liste und setze es in die geschlossene Liste
Für alle Nachbarn
Nachbar frei und nicht in geschlossener Liste? -> offene Liste


Danke im Voraus :)
 
O

Oneixee5

Aktives Mitglied
Wenn der kürzeste Weg sowieso egal ist: Es gibt eine alte Labyrinth-Regel, einfach immer rechts abbiegen und du kommst ganz sicher ans Ziel.
 
L

LimDul

Top Contributor
Hi zusammen,

ich sitze gerade an einem kleineren Projekt und hätte dazu eine Frage.
Ein Labyrinth hat einen Start- und einen Zielpunkt und natürlich Wände. Die Wände können vom Spieler gesetzt werden. Vor dem Platzieren muss allerdings geprüft werden, ob danach noch ein Pfad zum Ziel vorhanden ist. Zuerst dachte ich an A* oder Djikstra, aber da mir der kürzeste Weg egal ist, wollte ich es etwas simpler halten.
Ich hab das ganze mal auf einem Blatt Papier versucht und bin auf eine Lösung gekommen. Ich denke die entspricht der Breitensuche wenn mich nicht alles täuscht :D
Die Frage ist, ob das ganze noch einfacher geht bzw. würde mich mal interessieren wie ihr das lösen würdet.




Danke im Voraus :)
Jepp das entspricht Breiten bzw. Tiefensuche und sollte für das passend sein.
Wenn der kürzeste Weg sowieso egal ist: Es gibt eine alte Labyrinth-Regel, einfach immer rechts abbiegen und du kommst ganz sicher ans Ziel.
Die ist aber deutlich schwieriger umzusetzen, den dieses Verfahren hat ein Problem in der Programmierung:

* Das Ziel muss eine Lücke in der Wand sein Beispiel wo es nicht klappt:

Code:
XXXXX
X...X
X.o.X
X...X
XXXXX
An den Mittelpunkt, das Ziel (=o) komme ich nie, wenn ich mich nur an der Wand entlagebwege

* Ich darf an einer inneren Wand starten, so dass ich innen im Kreis laufen.

Beispiel:
Code:
XXoXX
X...X
X.X.X
X...X
XXXXX
Wenn ich nicht aufpasse laufe ich nur um die Säule in der Mitte rum.
 
P

Plauzi92

Aktives Mitglied
mihe7

mihe7

Top Contributor
Ja, so ähnlich, nur dass beim Flood-Fill einfach mit Markierung ("Farbe") gearbeitet wird. Das spart die Listen.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
Kirby_Sike Alle möglichen Error Möglichkeiten abfangen Java Basics - Anfänger-Themen 33
J Erste Schritte Alle möglichen ausgaben von 5 Zahlen als Vector Java Basics - Anfänger-Themen 7
D Alle möglichen Kombinationen in einem Array ausgeben Java Basics - Anfänger-Themen 2
M Alle möglichen Strings Java Basics - Anfänger-Themen 5
S Liste von möglichen Operationen Java Basics - Anfänger-Themen 2
H auslesen der möglichen Auflösungen Java Basics - Anfänger-Themen 2
L Datentypen eine Methode mit zwei möglichen Rückgabewerten Java Basics - Anfänger-Themen 20
alderwaran überladene methoden mit allen möglichen typen aufrufen Java Basics - Anfänger-Themen 3
D Alle möglichen Stringkombinationen aus bestimmtem Alphabet erzeugen Java Basics - Anfänger-Themen 6
E Ein Objekt von zwei möglichen Klassen in einer Variable Java Basics - Anfänger-Themen 5
Guybrush Threepwood String in alle möglichen Fragmente teilen Java Basics - Anfänger-Themen 2
C array alle möglichen Reihenfolgen Java Basics - Anfänger-Themen 6
C alle möglichen Datumseingaben im Textfeld abfangen Java Basics - Anfänger-Themen 12
C Alle Möglichen Kombinationen eines Arrays Java Basics - Anfänger-Themen 5
M Java GUI explorer aufrufen um Pfad zu bekommen Java Basics - Anfänger-Themen 3
R FXMLLoader Pfad falsch`? Java Basics - Anfänger-Themen 4
S Alternativer Pfad Java Basics - Anfänger-Themen 5
R speicherort Mac pfad angeben Java Basics - Anfänger-Themen 3
L Breadth-First Search statt einem Pfad, alle Pfade herausfinden Java Basics - Anfänger-Themen 4
O Best Practice Datei-Pfad zerlegen Java Basics - Anfänger-Themen 4
T relativer Pfad in einem Runnable JAR file Java Basics - Anfänger-Themen 12
H pfad finden Java Basics - Anfänger-Themen 12
H Pfad Program Files\Common Files\Oracle\Java\javapath Java Basics - Anfänger-Themen 3
L Pfad zum Jar Java Basics - Anfänger-Themen 7
it_is_all Bild-Pfad wird gefunden, nicht aber Textdatei-Pfad Java Basics - Anfänger-Themen 8
J Leerzeichen im Pfad automatisch erkennen Java Basics - Anfänger-Themen 30
B Log4J Pfad des Logfiles definieren Java Basics - Anfänger-Themen 6
D Umgebungsvariable Pfad javaw.exe für Programmstart auf Windows Java Basics - Anfänger-Themen 1
D Pfad Java Basics - Anfänger-Themen 15
H nio Pfad aus Dateinamen extrahieren Java Basics - Anfänger-Themen 4
R Pfad angeben Java Basics - Anfänger-Themen 7
S Pfad für Dateisystem?? Java Basics - Anfänger-Themen 13
P JSON-Konfigurationsdatei verwenden: Probleme mit Pfad Java Basics - Anfänger-Themen 1
T Classpath Problem mit dem auslesen von Text-Dateien (Pfad) Java Basics - Anfänger-Themen 3
M Pfad zu einer Datei in einer exportierten Jar-Datei Java Basics - Anfänger-Themen 5
S ungültiger Pfad bei der Installation von API documentation Java Basics - Anfänger-Themen 0
N .propertiesdatei über Relativen Pfad einlesen lassen Java Basics - Anfänger-Themen 5
I ZIP Archive erstellen - ich möchte aber nur den jeweiligen Ordner zippen, bekomme ganzen Pfad Java Basics - Anfänger-Themen 1
I Bei Umlauten und Leerzeichen im Pfad, wird Datei nicht gefunden Java Basics - Anfänger-Themen 5
O JFileChooser Verhalten -Pfad Java Basics - Anfänger-Themen 15
V java Pfad javac Java Basics - Anfänger-Themen 8
D Ein Icon ohne Pfad sondern mit Package. Java Basics - Anfänger-Themen 4
P Leerzeichen in Pfad... Java Basics - Anfänger-Themen 17
P Datei auf Pfad speichern Java Basics - Anfänger-Themen 7
B Relativer Pfad zwischen zwei Files Java Basics - Anfänger-Themen 2
H Programm zur Ausgabe von Datei und Pfad Java Basics - Anfänger-Themen 7
C Pfad für Bilder angeben Java Basics - Anfänger-Themen 11
L Pfad "zuschneiden" Java Basics - Anfänger-Themen 3
B In welchem (Default) Pfad erstellt Java Dateien? Java Basics - Anfänger-Themen 4
V relativer Pfad geht nicht, absolut schon? Java Basics - Anfänger-Themen 3
J Input/Output Datei auslesen, Pfad eingeben Java Basics - Anfänger-Themen 4
S PATH und Pfad auslesen.... Java Basics - Anfänger-Themen 3
X JDK installieren Pfad wird nicht gefunden Java Basics - Anfänger-Themen 5
B Classpath cmd java mit absolutem Pfad Java Basics - Anfänger-Themen 15
B eingene Klasse in eigenem Prozess starten mit relativem Pfad Java Basics - Anfänger-Themen 5
J FileOutputStream aktuelle Speicher Pfad ausgeben Java Basics - Anfänger-Themen 13
T Erkennen ob ein Pfad lokal oder im Netzwerk ist Java Basics - Anfänger-Themen 13
F Zugriff auf Pfad des gerade ausgeführten Programms? Java Basics - Anfänger-Themen 14
S Pfad auslesen Java Basics - Anfänger-Themen 3
B Externe Libraries fuer Applet ... Pfad eingeben? Java Basics - Anfänger-Themen 23
Helgon Pfad richtig angeben Java Basics - Anfänger-Themen 7
E Input/Output Relativer Bild-Pfad für InputStream Java Basics - Anfänger-Themen 5
M Existiert der gegebene Pfad? Java Basics - Anfänger-Themen 5
G aktueller Pfad Java Basics - Anfänger-Themen 4
F Relativer Pfad auf Datei im Projektordner Java Basics - Anfänger-Themen 11
B Pfad einer .jar im Programm ermitteln Java Basics - Anfänger-Themen 13
T Pfad für Datei neben Jar Java Basics - Anfänger-Themen 9
S File Kopieren Path Pfad Problem Java Basics - Anfänger-Themen 3
I Java-Programmm starten/ Pfad hsql DB Java Basics - Anfänger-Themen 7
D Input/Output Pfad richtig ermitteln Java Basics - Anfänger-Themen 12
T Pfad gültig oder ungültig? Java Basics - Anfänger-Themen 17
T brauche den pfad Name! Java Basics - Anfänger-Themen 2
Z css pfad falsch Java Basics - Anfänger-Themen 7
P ImageIcon/Pfad Java Basics - Anfänger-Themen 3
M externen Pfad in Jar verwenden Java Basics - Anfänger-Themen 3
V pfad.exists() gilt nicht für "//server/a/xyz.jpg"? Java Basics - Anfänger-Themen 12
C Relativer Pfad - Statische Methode Java Basics - Anfänger-Themen 6
C exec Aufruf mit Leerzeilen im Pfad Java Basics - Anfänger-Themen 3
J Pfad bzw. Namen einer Datei auslesen Java Basics - Anfänger-Themen 6
D Pfad zu "Eigenen Dateien" ermitteln Java Basics - Anfänger-Themen 8
A Relativer Pfad zu einem File ermitteln Java Basics - Anfänger-Themen 2
M createImage ungültiger Pfad registrieren Java Basics - Anfänger-Themen 2
S Pfad für Datei falsch - wie richtig angeben? Java Basics - Anfänger-Themen 7
H Wie Projekt-Ordner-Pfad ermitteln? Java Basics - Anfänger-Themen 11
A Aktueller Pfad des Programms (.jar) ermitteln Java Basics - Anfänger-Themen 10
M Problem mit relativen Pfad unter Linux Java Basics - Anfänger-Themen 5
L relativer Pfad Java Basics - Anfänger-Themen 2
S In Eclipse relativen Pfad fuer Tomcat Server erstellen..? Java Basics - Anfänger-Themen 3
E Pfad zu einem gif-Bild wird zur Laufzeit nicht gefunden Java Basics - Anfänger-Themen 5
megachucky FileInputStream findet nur absoluten Pfad, keinen Relativen ?! Java Basics - Anfänger-Themen 7
M Pfad angabe bei getRescource und ImageIO.write Java Basics - Anfänger-Themen 4
E new File macht den Pfad kaputt Java Basics - Anfänger-Themen 15
0 Den Pfad für das Bild angeben Java Basics - Anfänger-Themen 9
D Pfad zum Konfigurationsfile von Servletanwendung "dynamisieren" Java Basics - Anfänger-Themen 27
H Wie mache ich aus pfad\\unterpfad pfad\unterpfad? Java Basics - Anfänger-Themen 3
L datei speichern untervorgegebenen pfad Java Basics - Anfänger-Themen 3
A relativer Pfad Java Basics - Anfänger-Themen 6
R Properties über statischen Pfad laden Java Basics - Anfänger-Themen 2
L Pfad von Webprojekt auslesen Java Basics - Anfänger-Themen 10
F Datei suchen --> Pfad als String speichern Java Basics - Anfänger-Themen 8

Ähnliche Java Themen

Anzeige

Neue Themen


Oben