Hallo zusammen,
ich bin ganz neu hier und hoffe, dass dieser Beitrag im richtigen Sub-Forum gelandet ist.
Ich habe ein Problem mit der Implementierung des A*-Algorithmus, mit dem ich in einem Spiel ein Labyrinth durchlaufe.
Der Code funktioniert prinzipiell, ich kann damit meine Maps durchlaufen. Aber manchmal kommt folgende Fehlermeldung (vgl. auch mein Log ganz unten):
Ich habe erkannt, dass das Problem ist, dass meine Open-Liste "leer" wird und der Algorithmus dann logischerweise nicht mehr auf das erste Element zugreifen kann. Mir ist aber nicht klar, wo der eigentliche Fehler im Code ist. Ich muss einerseits verhindern, dass die Open-Liste "leerläuft", und andererseits sicherstellen, dass der Algorithmus trotzdem tut, was er soll.
Ach ja, wichtig zu wissen: Wenn der Algorithmus einen Weg finden soll, dann habe ich vorher bereits sichergestellt, dass es einen Weg geben muss! D.h. es kann mit Sicherheit nicht sein, dass die Fehlermeldung kommt, weil es keine Lösung gibt.
Ich bin für jede Hilfe sehr, sehr dankbar!!
LG Verena
Hier mein Code:
Folgendes gibt mein Logger in der Console aus (nicht erschrecken, ist viel):
ich bin ganz neu hier und hoffe, dass dieser Beitrag im richtigen Sub-Forum gelandet ist.
Ich habe ein Problem mit der Implementierung des A*-Algorithmus, mit dem ich in einem Spiel ein Labyrinth durchlaufe.
Der Code funktioniert prinzipiell, ich kann damit meine Maps durchlaufen. Aber manchmal kommt folgende Fehlermeldung (vgl. auch mein Log ganz unten):
Java:
Exception in thread "Thread-2" java.util.NoSuchElementException
at java.util.LinkedList.getFirst(Unknown Source)
at util.NodeList.getFirst(NodeList.java:43)
at util.Map.findeWegVonNachMitAStar(Map.java:122)
at util.Map.findeWeg(Map.java:97)
at util.Map.getNearestFeld(Map.java:362)
at util.Map.getNearestFeldOfInterest(Map.java:392)
at Dehnis.erforschenUndSammeln(Dehnis.java:84)
at Dehnis.play(Dehnis.java:65)
at Dehnis.run(Dehnis.java:32)
at aup.contest.DukeRunner.run(DukeRunner.java:13)
at java.lang.Thread.run(Unknown Source)Ich habe erkannt, dass das Problem ist, dass meine Open-Liste "leer" wird und der Algorithmus dann logischerweise nicht mehr auf das erste Element zugreifen kann. Mir ist aber nicht klar, wo der eigentliche Fehler im Code ist. Ich muss einerseits verhindern, dass die Open-Liste "leerläuft", und andererseits sicherstellen, dass der Algorithmus trotzdem tut, was er soll.
Ach ja, wichtig zu wissen: Wenn der Algorithmus einen Weg finden soll, dann habe ich vorher bereits sichergestellt, dass es einen Weg geben muss! D.h. es kann mit Sicherheit nicht sein, dass die Fehlermeldung kommt, weil es keine Lösung gibt.
Ich bin für jede Hilfe sehr, sehr dankbar!!
LG Verena
Hier mein Code:
Java:
private ArrayList<Integer> findeWegVonNachMitAStar(int start, int ziel) {
// TEST
if (start == 92 && ziel == 39) {
logger.debug("Ich halte zu Testzwecken hier mal an.");
}
// TEST-Ende
// Initialisierung
NodeList open = new NodeList();
NodeList closed = new NodeList();
// den Startknoten als Node erzeugen und der open-Liste hinzufügen
Node startknoten = new Node(start, 0); // Vorgänger ist hier -1
open.addNode(startknoten);
// Algorithmus
while (open.getFirst().getId() != ziel) {
Node current = open.removeFirst();
closed.addNode(current);
System.out.println(" ");
logger.debug("Expandiere neuen Knoten: " + current.toString());
// die Nachbarn zu current finden
ArrayList<Integer> nachbarn = matrix.getAdjazenteFelder(current.getId());
logger.debug("Nachbarn: " + Printer.printArrayList(nachbarn));
// für alle nachbarn von current...
for (int i = 0; i < nachbarn.size(); i++) {
// Kosten errechnen und Node erstellen
int cost = current.getCost() + 1;
Node nachbar = new Node(nachbarn.get(i), cost, current.getId());
nachbar.setDistance(getManhattenDistance(nachbar.getId(), ziel));
// Node verwerten
int nachbarInOpen = open.getIndexOfNodeinNodeList(nachbar);
int nachbarInClosed = closed.getIndexOfNodeinNodeList(nachbar);
//
// Wenn der (neue) Nachbar bereits in OPEN ist, und seine Kosten
// geringer sind...
if (open.getSize() > 0 && nachbarInOpen != -1 && cost < open.get(nachbarInOpen).getCost()) {
// ... diesen aus derOpenliste entfernen, denn der neue Pfad
// ist besser.
Node n = open.remove(nachbarInOpen);
logger.debug("Entferne aus OPEN: " + n.toString());
}
// Wenn der (neue) Nachbar in CLOSED ist, und seine Kosten
// geringer sind...
if (closed.getSize() > 0 && nachbarInClosed != -1 && cost < closed.get(nachbarInClosed).getCost()) {
// ... diesen aus CLOSED entfernen
Node n = closed.remove(nachbarInClosed);
logger.debug("Entferne aus CLOSED: " + n.toString());
}
// Wenn der (neue) Nachbar weder in CLOSED noch in OPEN ist...
if (nachbarInOpen == -1 && nachbarInClosed == -1) {
// add Nachbar zu OPEN
logger.debug("Füge hinzu zu OPEN: " + nachbar.toString());
open.addNode(nachbar);
// die OPEN-Liste nach Prioritäten ordnen.
open.priorize();
}
}
logger.debug("OPEN-Size: "+open.getSize());
logger.debug("CLOSED-Size: "+closed.getSize());
}
// Pfad rückwärts zusammenbauen
ArrayList<Integer> wegListe = new ArrayList<Integer>();
ArrayList<Integer> weg = new ArrayList<Integer>();
Node currNode = open.getFirst();
int currId = open.getFirst().getId();
wegListe.add(currId);
do {
currId = currNode.getParent();
wegListe.add(currId);
currNode = closed.getNodeById(currId);
} while (currId != start);
// Die ArrayList umsortieren
for (int i = wegListe.size() - 1; i >= 0; i--) {
weg.add(wegListe.get(i));
}
return weg;
}Folgendes gibt mein Logger in der Console aus (nicht erschrecken, ist viel):
Code:
DEBUG - Finde Weg von: 92 nach: 39
DEBUG - Ich halte zu Testzwecken hier mal an.
### Hier habe ich etwas aus dem Log entfernt, da es sonst zu viel Text geworden wäre ###
DEBUG - Expandiere neuen Knoten: [ID: 301, Cost: 32, Distance: 32, Parent: 321]
DEBUG - Nachbarn: 300, 321,
DEBUG - Füge hinzu zu OPEN: [ID: 300, Cost: 33, Distance: 33, Parent: 301]
DEBUG - OPEN-Size: 4
DEBUG - CLOSED-Size: 243
DEBUG - Expandiere neuen Knoten: [ID: 320, Cost: 32, Distance: 34, Parent: 321]
DEBUG - Nachbarn: 300, 321, 340,
DEBUG - OPEN-Size: 3
DEBUG - CLOSED-Size: 244
DEBUG - Expandiere neuen Knoten: [ID: 300, Cost: 33, Distance: 33, Parent: 301]
DEBUG - Nachbarn: 280, 301, 320,
DEBUG - Füge hinzu zu OPEN: [ID: 280, Cost: 34, Distance: 32, Parent: 300]
DEBUG - OPEN-Size: 3
DEBUG - CLOSED-Size: 245
DEBUG - Expandiere neuen Knoten: [ID: 340, Cost: 31, Distance: 35, Parent: 341]
DEBUG - Nachbarn: 320, 341,
DEBUG - OPEN-Size: 2
DEBUG - CLOSED-Size: 246
DEBUG - Expandiere neuen Knoten: [ID: 280, Cost: 34, Distance: 32, Parent: 300]
DEBUG - Nachbarn: 300,
DEBUG - OPEN-Size: 1
DEBUG - CLOSED-Size: 247
DEBUG - Expandiere neuen Knoten: [ID: 381, Cost: 30, Distance: 36, Parent: 361]
DEBUG - Nachbarn: 361, 382,
DEBUG - OPEN-Size: 0
DEBUG - CLOSED-Size: 248
Exception in thread "Thread-2" java.util.NoSuchElementException
at java.util.LinkedList.getFirst(Unknown Source)
at util.NodeList.getFirst(NodeList.java:43)
at util.Map.findeWegVonNachMitAStar(Map.java:122)
at util.Map.findeWeg(Map.java:97)
at util.Map.getNearestFeld(Map.java:362)
at util.Map.getNearestFeldOfInterest(Map.java:392)
at Dehnis.erforschenUndSammeln(Dehnis.java:84)
at Dehnis.play(Dehnis.java:65)
at Dehnis.run(Dehnis.java:32)
at aup.contest.DukeRunner.run(DukeRunner.java:13)
at java.lang.Thread.run(Unknown Source)
