Verbesserungsvorschläge zu Wegfinder Programm

N

nik.stffrs

Mitglied
Moin,
Ich bin 15 Jahre alt und lerne nun seit etwa 1/2 Jahr programmieren. Heute habe ich eine Coding Challenge im Internet gefunden. Bei der ging es darum, dass man aus einem 2d Array, welches eine Map repräsentiert, einen Weg zu einem Ziel findet. Besser verständlich:
T für Spieler (Startposition)
C für Ziel
# für Wand (man kann diese nicht überqueren)
. für Weg (hier kann man lang gehen)
Map:
##########
#T########
# . ########
# . #######
# . ########
# . ########
# . ########
# . ########
# . . . . . . . C#
##########
Das ist jetzt nur ein Beispiel. Die Mapgröße lässt sich variieren. Es kann auch mehrere Wege geben, welche zum Ziel führen, allerdings wird dann nicht der Kürzere gefunden sondern es wird ein Beliebiger gefunden (Wenn es einen Weg gibt, der rechts vom Spieler anfängt wird immer dieser gefunden). Das einzige Kriterium was gegeben sein muss ist, dass es keinen Weg gibt, welcher ins Nichts führt. Das der kürzere Weg gefunden wird und dass es auch Wege gibt die ins Nichts führen möchte ich demnächst noch implementieren.
So jetzt kommen wir jedenfalls mal zu meinem Code.
Die Main-Klasse:
Java:
public final class Main {

    private boolean wayFound;

 
private final char[][] map = {  { '#', '#', '#', '#', '#', '#', '#', '#', '#', '#' },
                                { '#', 'T', '#', '.', '.', '.', '.', '.', '.', '#' },
                                { '#', '.', '#', '#', '#', '#', '#', '#', '.', '#' },
                                { '#', '.', '#', '#', '#', '#', '#', '#', '.', '#' },
                                { '#', '.', '#', '#', '#', '#', '#', '#', '.', '#' },
                                { '#', '.', '#', '#', '#', '#', '#', '#', '.', '#' },
                                { '#', '.', '#', '#', '.', '.', '.', '#', '.', '#' },
                                { '#', '.', '#', '#', '.', '#', '.', '#', '.', '#' },
                                { '#', '.', '.', '.', '.', '#', '.', '.', 'C', '#' },
                                { '#', '#', '#', '#', '#', '#', '#', '#', '#', '#' } };
 
    private ArrayList<Coordinate> way = new ArrayList<>();

    public static void main(String[] args) {
        new Main().getWay();
    }
    private void getWay() {
        Coordinate playerPosition = null;
        Coordinate destinationPosition = null;
        ArrayList<Coordinate> walkable = new ArrayList<>();
        for(int i = 0; i < map.length; i++) {
            for(int a = 0; a < map[i].length; a++) {
                if(map[i][a] == '.')
                    walkable.add(new Coordinate(a + 1, i + 1));
                else if(map[i][a] == 'T')
                    playerPosition = new Coordinate(a + 1, i + 1);
                else if(map[i][a] == 'C')
                    destinationPosition = new Coordinate(a + 1, i + 1);
            }
        }
        walkable.sort(new CoordinateComparator());
        if(playerPosition == null || destinationPosition == null)
            throw new IllegalArgumentException("The map does not contain a player or a destination");
        way.add(playerPosition);
        //1 = up; 2 = right; 3 = down; 4 = left;
        int wayDirection = 0;
        findWay(walkable, playerPosition, destinationPosition, wayDirection);
        System.out.println(Arrays.toString(way.toArray()));
    }
    private void findWay(ArrayList<Coordinate> walkable, Coordinate playerPosition, Coordinate destinationPosition, int wayDirection) {
  
        for(int i = 0; i < walkable.size(); i++) {
            Coordinate walkableCoordinate = walkable.get(i);
            Coordinate previousWayCoordinate = way.get(way.size() - 1);
            if(way.contains(walkable.get(i)))
                continue;
            if(walkableCoordinate.getX() == previousWayCoordinate.getX() - 1 && wayDirection != 2 && walkableCoordinate.getY() == previousWayCoordinate.getY()) {
                wayDirection = 4;
                way.add(walkable.get(i));
            } else if(walkableCoordinate.getX() == previousWayCoordinate.getX() + 1 && wayDirection != 4 && walkableCoordinate.getY() == previousWayCoordinate.getY()) {
                wayDirection = 2;
                way.add(walkable.get(i));
            } else if(walkableCoordinate.getY() == previousWayCoordinate.getY() - 1 && wayDirection != 3 && walkableCoordinate.getX() == previousWayCoordinate.getX()) {
                wayDirection = 1;
                way.add(walkable.get(i));
            } else if(walkableCoordinate.getY() == previousWayCoordinate.getY() + 1 && wayDirection != 1 && walkableCoordinate.getX() == previousWayCoordinate.getX()) {
                wayDirection = 3;
                way.add(walkable.get(i));
            } else if((previousWayCoordinate.getX() == destinationPosition.getX() - 1 && previousWayCoordinate.getY() == destinationPosition.getY()) ||
                      (previousWayCoordinate.getX() == destinationPosition.getX() + 1 && previousWayCoordinate.getY() == destinationPosition.getY()) ||
                      (previousWayCoordinate.getY() == destinationPosition.getY() - 1 && previousWayCoordinate.getX() == destinationPosition.getX()) ||
                      (previousWayCoordinate.getY() == destinationPosition.getY() + 1 && previousWayCoordinate.getX() == destinationPosition.getX())) {
                wayFound = true;
                way.add(destinationPosition);
                return;
            }
            if(i == walkable.size() - 1)
                findWay(walkable, playerPosition, destinationPosition, wayDirection);
        }
    }
}
Die Coordinate Klasse:
Java:
public class Coordinate {

    private int x, y;

    public Coordinate(int x, int y) {
        this.x = x;
        this.y = y;
    }
    public int getX() {
        return x;
    }
    public void setX(int x) {
        this.x = x;
    }
    public int getY() {
        return y;
    }
    public void setY(int y) {
        this.y = y;
    }
    @Override
    public String toString() {
        return x + "," + y;
    }
}
Und als Letztes die CoordinateComparator Klasse:
Java:
public class CoordinateComparator implements Comparator<Coordinate>{

    @Override
    public int compare(Coordinate arg0, Coordinate arg1) {
        if (arg0.getY() < arg1.getY()) {
            return -1;
        } else if (arg0.getY() > arg1.getY()) {
            return 1;
        } else {
            if (arg0.getX() < arg1.getX()) {
                return -1;
            } else if (arg0.getX() > arg1.getX()) {
                return 1;
            }
            return 0;
        }

    }

}

Vielleicht hat ja jemand mal Lust sich das ganze durchzulesen und mir Verbesserungsvorschläge zu geben. Ich möchte immer möglichst sauberen Code schreiben und da meine Lösung wahrscheinlich nicht gerade optimal ist würde ich mich freuen, wenn mir jemand mit Verbesserungsvorschlägen zu einer schöneren Lösung verhelfen würde.

Danke für eure Antworten!
 
M

member42

Aktives Mitglied
Moin,
Deine Lösung gefällt mir eigentlich ziemlich gut. Ich habe auch einen Pathfinding Programm gemacht, allerdings mit dem LeeAlgorthimus ohne Rekursion.
Ich würde denken dass das Sortieren der Koordinaten überflüssig ist. Den Sinn von wayDirection verstehe auch nicht ganz. Ich habe das einmal rausgenommen und es kommt das gleiche Ergebnis.

Java:
public final class Main {

    private boolean wayFound;


private final char[][] map = {  { '#', '#', '#', '#', '#', '#', '#', '#', '#', '#' },
                                { '#', 'T', '#', '.', '.', '.', '.', '.', '.', '#' },
                                { '#', '.', '#', '#', '#', '#', '#', '#', '.', '#' },
                                { '#', '.', '#', '#', '#', '#', '#', '#', '.', '#' },
                                { '#', '.', '#', '#', '#', '#', '#', '#', '.', '#' },
                                { '#', '.', '#', '#', '#', '#', '#', '#', '.', '#' },
                                { '#', '.', '#', '#', '.', '.', '.', '#', '.', '#' },
                                { '#', '.', '#', '#', '.', '#', '.', '#', '.', '#' },
                                { '#', '.', '.', '.', '.', '#', '.', '.', 'C', '#' },
                                { '#', '#', '#', '#', '#', '#', '#', '#', '#', '#' } };

    private ArrayList<Coordinate> way = new ArrayList<>();

    public static void main(String[] args) {
        new Main().getWay();
    }
    private void getWay() {
        Coordinate playerPosition = null;
        Coordinate destinationPosition = null;
 
        ArrayList<Coordinate> walkable = new ArrayList<>();
  
        for(int i = 0; i < map.length; i++) {
            for(int a = 0; a < map[i].length; a++) {
                if(map[i][a] == '.')
                    walkable.add(new Coordinate(a + 1, i + 1));
                else if(map[i][a] == 'T')
                    playerPosition = new Coordinate(a + 1, i + 1);
                else if(map[i][a] == 'C')
                    destinationPosition = new Coordinate(a + 1, i + 1);
            }
        }
        if(playerPosition == null || destinationPosition == null)
            throw new IllegalArgumentException("The map does not contain a player or a destination");
        way.add(playerPosition);      
        findWay(walkable, playerPosition, destinationPosition);
        System.out.println(Arrays.toString(way.toArray()));
    }
    private void findWay(ArrayList<Coordinate> walkable, Coordinate playerPosition, Coordinate destinationPosition) {
 
        for(int i = 0; i < walkable.size(); i++) {
      
            Coordinate walkableCoordinate = walkable.get(i);
            Coordinate previousWayCoordinate = way.get(way.size() - 1);
      
            if(way.contains(walkable.get(i)))
                continue;
            if(walkableCoordinate.getX() == previousWayCoordinate.getX() - 1 &&   walkableCoordinate.getY() == previousWayCoordinate.getY()) {
        
                way.add(walkable.get(i));
            } else if(walkableCoordinate.getX() == previousWayCoordinate.getX() + 1  && walkableCoordinate.getY() == previousWayCoordinate.getY()) {
          
                way.add(walkable.get(i));
            } else if(walkableCoordinate.getY() == previousWayCoordinate.getY() - 1  && walkableCoordinate.getX() == previousWayCoordinate.getX()) {
          
                way.add(walkable.get(i));
            } else if(walkableCoordinate.getY() == previousWayCoordinate.getY() + 1  && walkableCoordinate.getX() == previousWayCoordinate.getX()) {
          
                way.add(walkable.get(i));
            } else if((previousWayCoordinate.getX() == destinationPosition.getX() - 1 && previousWayCoordinate.getY() == destinationPosition.getY()) ||
                      (previousWayCoordinate.getX() == destinationPosition.getX() + 1 && previousWayCoordinate.getY() == destinationPosition.getY()) ||
                      (previousWayCoordinate.getY() == destinationPosition.getY() - 1 && previousWayCoordinate.getX() == destinationPosition.getX()) ||
                      (previousWayCoordinate.getY() == destinationPosition.getY() + 1 && previousWayCoordinate.getX() == destinationPosition.getX())) {
                wayFound = true;
                way.add(destinationPosition);
                return;
            }
            if(i == walkable.size() - 1)
                findWay(walkable, playerPosition, destinationPosition);
        }
    }
}
Eigentlich soll man ja Getter und Setter verwenden, aber ich finde durch diese vielen getX() und getY() wird es ziemlich unübersichtlich. Also ich würde x,y von Coordinate public machen, ist aber nur meine Meinung.

Was ist eigentlich wenn du in eine Sackgasse gerätst? Du gehst glaube ich nirgendwo zurück.
Z.B bei so einer Map läuft das Programm in die Sackgasse und es gibt einen Stackoverflow :
Java:
private final char[][] map = {  { '#', '#', '#', '#', '#', '#', '#', '#', '#', '#' },
                                { '#', 'T', '#', '.', '.', '.', '.', '.', '.', '#' },
                                { '#', '.', '#', '#', '#', '#', '#', '#', '.', '#' },
                                { '#', '.', '#', '#', '#', '#', '#', '#', '.', '#' },
                                { '#', '.', '.', '.', '.', '#', '#', '#', '.', '#' },
                                { '#', '.', '#', '#', '#', '#', '#', '#', '.', '#' },
                                { '#', '.', '#', '#', '.', '.', '.', '#', '.', '#' },
                                { '#', '.', '#', '#', '.', '#', '.', '#', '.', '#' },
                                { '#', '.', '.', '.', '.', '#', '.', '.', 'C', '#' },
                                { '#', '#', '#', '#', '#', '#', '#', '#', '#', '#' } };
EDIT: Habe es überlesen
Das einzige Kriterium was gegeben sein muss ist, dass es keinen Weg gibt, welcher ins Nichts führt
 
Zuletzt bearbeitet:
mrBrown

mrBrown

Super-Moderator
Mitarbeiter
Zum reinen Code-Stil:


* Schmeiß die Setter aus Coordinate und mach die Felder final - Koordinaten ändern sich nicht
* den Comparator kannst du deutlich einfacher mit den statischen Methoden aus Comparator aufbauen, im Endeffekt ist das ein Zweizeiler mit „vergleiche Y und dann X“
* die ganzen if-Bedingungen kannst du in sinnvoll benannte Methoden auslagern (und wenn du dann die Direction noch rausnimmst, kannst du die meisten in einer Methode zusammenfassen, im Sinne von „Koordinate A ist neben Koordinate B“)
* wenn du die Direction drin lassen willst, mach nen Enum draus


Eigentlich soll man ja Getter und Setter verwenden, aber ich finde durch diese vielen getX() und getY() wird es ziemlich unübersichtlich. Also ich würde x,y von Coordinate public machen, ist aber nur meine Meinung.
In Verbindung mit final Feldern ist das Okay. Allerdings kann man dann die Interna von Coordinate nicht ändern, ohne allen nutzenden Code anzupassen.
 
N

nik.stffrs

Mitglied
Erstmal vielen Dank für eure Antworten.
Ich würde denken dass das Sortieren der Koordinaten überflüssig ist. Den Sinn von wayDirection verstehe auch nicht ganz.
Ja da hast du Recht. Das Sortieren habe ich eigentlich auch nur gemacht weil ich gerade in meinem Buch Comparatoren behandelt habe und einfach mal einen ausprobieren wollte. Das wayDirection gar keinen Sinn hat fällt mir jetzt erst auf. Ich dachte wenn ich z.B. dem Weg nach links folge und dann in die nächste Abfrage gehe und dann zuerst überprüft wird ob sich rechts ein Feld befindet, dann würde der Algorithmus sozusagen wieder einen Schritt zurückmachen und dadurch, dass ich prüfe aus welcher Richtung ich komme könne ich das Problem lösen. Allerdings ist das ja unnötig, weil ich eh schon überprüfe ob das Feld sich schon im Weg befindet :D.
Ich habe auch einen Pathfinding Programm gemacht, allerdings mit dem LeeAlgorthimus ohne Rekursion.
Von LeeAlgorithmus habe ich zwar noch nie etwas gehört aber ich werde mir den mal angucken und zur Übung versuchen das Programm ohne Rekursion zu schreiben.
* Schmeiß die Setter aus Coordinate und mach die Felder final - Koordinaten ändern sich nicht
* den Comparator kannst du deutlich einfacher mit den statischen Methoden aus Comparator aufbauen, im Endeffekt ist das ein Zweizeiler mit „vergleiche Y und dann X“
* die ganzen if-Bedingungen kannst du in sinnvoll benannte Methoden auslagern (und wenn du dann die Direction noch rausnimmst, kannst du die meisten in einer Methode zusammenfassen, im Sinne von „Koordinate A ist neben Koordinate B“)
* wenn du die Direction drin lassen willst, mach nen Enum draus
Auch dir erstmal Danke für die zahlreichen Tipps. Ich wird mich mal dransetzen und die übernehmen. Das mit der Direction werd ich rausnehmen, da ja schon wie von member42 erwähnt das ganze nicht notwendig ist.

Ich hab mir in der Zwischenzeit mal ein paar Gedanken gemacht, wie ich das mit Sackgassen und mit dem kürzeren Weg finden machen möchte. Bisher ist mir noch nichts besseres eingefallen, als nacheinander alle Wege auszuprobieren zu lassen und dann ggf. den bisher gefundenen Weg durch den kürzeren zu ersetzen. Dabei habe ich daran gedacht flags entlang des Weges zu setzen, also wenn ich an einem Punkt abbiege ein flag zu setzen mit der Richtung in die der Weg führt. Dann würde ich beim nächsten Weg auf die flags vom vorherigen Weg zurückgreifen und dann an den Abbiegestellen jeweils in andere Richtungen gehen. Fällt euch da was besseres ein?
 
M

member42

Aktives Mitglied
Ich hab mir in der Zwischenzeit mal ein paar Gedanken gemacht, wie ich das mit Sackgassen und mit dem kürzeren Weg finden machen möchte. Bisher ist mir noch nichts besseres eingefallen, als nacheinander alle Wege auszuprobieren zu lassen und dann ggf. den bisher gefundenen Weg durch den kürzeren zu ersetzen. Dabei habe ich daran gedacht flags entlang des Weges zu setzen, also wenn ich an einem Punkt abbiege ein flag zu setzen mit der Richtung in die der Weg führt. Dann würde ich beim nächsten Weg auf die flags vom vorherigen Weg zurückgreifen und dann an den Abbiegestellen jeweils in andere Richtungen gehen
Schaue mal nach "Backtracking". Wenn das Programm in eine Sackgasse gerät, wird der letzte Schritt zurück gemacht.Wenn du den den kürzesten Weg haben möchstest darf die Rekursion nicht nach einem gefundenen Weg abrechen, sondern muss noch weiterlaufen um von allen Wegen dann den kürzesten zu finden.
 
Zuletzt bearbeitet:
mihe7

mihe7

Top Contributor
Habe mal den Spaß mal mit A-Stern nach Wikipedia implementiert. Hoffe, dass keine größeren Schnitzer drin sind :)

Erstmal das Modell:
Java:
import java.util.Optional;
import java.util.Set;
import java.util.stream.Collectors;

public class Maze {
    private final char[][] map;

    public Maze(String[] maze) {
        map = new char[maze.length][];
        int i = 0;
        for (String row : maze) {
            map[i++] = row.toCharArray();
        }
    }

    public Optional<Coordinate> findFirst(char value) {
        for (int y = 0; y < map.length; y++) {
            for (int x = 0; x < map[y].length; x++) {
                if (map[y][x] == value) {
                    return Optional.of(new Coordinate(x,y));
                }
            }
        }
        return Optional.empty();
    }

    public char getValue(Coordinate c) {
        int x = c.getX();
        int y = c.getY();
        if (y < 0 || y >= map.length || x < 0 || x >= map[y].length) {
            return '#';
        }
        return map[y][x];
    }

    public boolean isWalkable(Coordinate c) {
        return getValue(c) != '#';
    }

    public Set<Coordinate> neighbours(Coordinate c) {
        return c.neighbours().stream()
            .filter(this::isWalkable)
            .collect(Collectors.toSet());
    }
}
Java:
import java.util.Set;
import java.util.stream.IntStream;
import java.util.stream.Collectors;

public class Coordinate {

    private final int x, y;

    public Coordinate(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

    public Set<Coordinate> neighbours() {
        return IntStream.range(0, 9)
            .filter(i -> i != 4)
            .mapToObj(i -> new Coordinate(x-1+(i%3), y-1+(i/3)))
            .collect(Collectors.toSet());
    }

    public int distance(Coordinate c) {
        return (int)(Math.sqrt((c.x-x)*(c.x-x) + (c.y-y)*(c.y-y)));
    }

    @Override
    public int hashCode() {
        return 7 + 5*x*x + 13 * y*y;
    }

    @Override
    public boolean equals(Object o) {
        if (o == null || o == this || !(o instanceof Coordinate)) {
            return o == this;
        }
        Coordinate c = (Coordinate) o;
        return x == c.x && y == c.y;
    }

    @Override
    public String toString() {
        return x + "," + y;
    }
}
Dann der Algorithmus:
Java:
import java.util.*;
import java.util.function.BiFunction;
import java.util.function.Function;

public class AStar<T> {
    private final BiFunction<T,T,Integer> cost;
    private final BiFunction<T,T,Integer> estimation;
    private final Function<T,Set<T>> successors;

    private PriorityQueue<Node<T>> open;
    private Set<T> closed;
    private Map<T, Node<T>> nodeIndex;

    public AStar(BiFunction<T,T,Integer> cost,
                 BiFunction<T,T,Integer> estimation,
                 Function<T,Set<T>> successors) {
        this.cost = cost;
        this.estimation = estimation;
        this.successors = successors;
    }

    public List<T> find(T start, T end) {
        open = new PriorityQueue<>(11, (n1, n2) -> n1.value - n2.value);
        nodeIndex = new HashMap<>();
        closed = new HashSet<>();

        open.add(new Node<T>(start, 0));
        do {
            Node<T> current = open.poll();
            if (current.data.equals(end)) {
                return path(current);
            }
            nodeIndex.remove(current.data);
            closed.add(current.data);
            expand(current, end);
        } while (!open.isEmpty());

        return new ArrayList<>();
    }

    private List<T> path(Node<T> node) {
        List<T> result = new ArrayList<T>();
        result.add(node.data);
        while (node.predecessor.isPresent()) {
            node = node.predecessor.get();
            result.add(node.data);
        }
        return result;
    }

    private void expand(Node<T> node, T end) {
        for (T successor : successors.apply(node.data)) {
            if (closed.contains(successor)) {
                continue;
            }
            Node<T> succNode = nodeIndex.getOrDefault(
                    successor, new Node<T>(successor, 0));
            int tentative = node.cost + cost.apply(node.data, successor);
            if (open.contains(succNode) && tentative >= succNode.cost) {
                continue;
            }
            succNode.predecessor = Optional.of(node);
            succNode.cost = tentative;
            succNode.value = tentative + estimation.apply(successor, end);
            open.remove(succNode);
            open.add(succNode);
            nodeIndex.computeIfAbsent(successor, s -> succNode);
        }
    }

    private static class Node<T> {
        public int value;
        public int cost;
        public final T data;
        public Optional<Node<T>> predecessor;

        public Node(T data, int value) {
            this.data = data;
            this.value = value;
            this.predecessor = Optional.empty();
        }

        @Override
        public boolean equals(Object o) {
            if (o == null || o == this || !(o instanceof Node)) {
                return o == this;
            }
            return data.equals(((Node) o).data);
        }

        @Override
        public int hashCode() { 
            return data.hashCode();
        }

        @Override
        public String toString() {
            return "N[" + value + ", " + cost + ", " + data + "]";
        }
    }
}
Und zum Schluss dann noch das Programm:
Java:
import java.util.*;
import java.util.function.BiFunction;

public final class Main {

    private final static String[] map = {
        "##########",
        "#T#......#",
        "#.######.#",
        "#.##.###.#",
        "#.##.###.#",
        "#.##.###.#",
        "#.##...#.#",
        "#.##.#.#.#",
        "#....#..C#",
        "##########"
    };
    public static void main(String[] args) {
        Maze maze = new Maze(map);
        Optional<Coordinate> start = maze.findFirst('T');
        Optional<Coordinate> dest = maze.findFirst('C');
        if (!start.isPresent() || !dest.isPresent()) {
            System.err.println("Start und Ziel müssen vorhanden sein.");
            System.exit(1);
        }

        AStar<Coordinate> pathfinder = new AStar<>(
            (f,t) -> f.distance(t),
            (f,t) -> f.distance(t),
            c -> maze.neighbours(c));

        System.out.println(pathfinder.find(dest.get(), start.get()));
    }
}
 
X

Xyz1

Gast
:mad: Erste Grafik sieht so aus als wenn es von er Quelle zur Senke nur einen möglichen Weg gibt.
Dann sind gar keine komplizierten Algorithmen benötigt.

Und allgemein, Deine Variablennamen sind zu lang, Getter() sind nicht unbedingt notwendig und if else if ist auch nicht so schön, ich versuche das immer zu vermeiden!
 
N

nik.stffrs

Mitglied
Habe malden Spaß mal mit A-Stern nach Wikipedia implementiert.
Echt erstmal vielen, vielen Dank, dass du dir so viel Zeit genommen hast gleich den ganzen Algorithmus zu implementieren :oops:. Ich werd mir den mal in Ruhe ansehen, danke für die Hilfe. Natürlich auch nochmal an alle Anderen die hier gepostet haben vielen Dank :)
 
mihe7

mihe7

Top Contributor
Der Algorithmus entspricht fast 1:1 dem aus Wikipedia. Im Unterschied dazu trenne ich jedoch strikt zwischen den Knoten im Suchbaum und den Wegpunkten, um letztere nicht mit den für den Algorithmus spezifischen Daten verunreinigen zu müssen. Daher braucht es auch den nodeIndex, um etwaig vorhandene Knoten anhand der Wegpunkte zu finden.

Wenn Du Dich mit dem Programm ein wenig spielst, wirst Du feststellen, dass es in der Form nicht immer den tatsächlich kürzesten Weg liefert. Das liegt nicht am Algorithmus sondern an der Distanzberechnung. Diese gibt die Entfernung in ganzen Punkten zurück. Um genauere Ergebnisse zu erhalten, kannst Du die Distanz z. B. auf Dezi-, Zenti- oder Millipunkte genau berechnen (d. h. vor dem Cast auf int mit 10, 100 oder 1000 Multiplizieren). Alternative wäre, von int auf double umzustellen.
 
X

Xyz1

Gast
Wie war das noch mit den geschätzten Entfernungen? Die kleinste, größtmögliche Distanz wählen?? ;)

Oder anders.... nur in extrem seltenen Fällen wird er nicht den optimalen Weg liefern.... :eek:
 
mihe7

mihe7

Top Contributor
Oder anders.... nur in extrem seltenen Fällen wird er nicht den optimalen Weg liefern....
Das geht ganz schnell. Wenn ich mich recht entsinne:
Code:
    private final static String[] map = {
        "##########",
        "#T.......#",
        "#.######.#",
        "#.##.###.#",
        "#.##.###.#",
        "#.##.###.#",
        "#.##...#.#",
        "#.##.#.#.#",
        "#....#..C#",
        "##########"
    };
Dann versucht der Code ggf. über die Ecke oben rechts zu laufen, statt diagonal, und damit hast Du am Ende einen Schritt zu viel.
 
X

Xyz1

Gast
Ja Hindernis in der Mitte und Sackgasse....

Vielleicht kommts auf die Diagonalenberechnung an, aber weiß es nicht genau :cool:
 
mrBrown

mrBrown

Super-Moderator
Mitarbeiter
Ist deine Heuristik nicht monoton? So auf die Schnelle seh ich da grad kein Gegenbeispiel...
 
mihe7

mihe7

Top Contributor
Wenn sqrt(2)=1 gilt, dann ist der Pfad in horizontaler bzw. vertikaler Richtung genauso teuer wie in diagonaler. Dann kommt es im Algorithmus auf die Reihenfolge der Nachbarn an, ob die Kurve geschnitten wird oder nicht.
 
mihe7

mihe7

Top Contributor
Vermutlich ist das Problem nicht die Schätzfunktion sondern die Kostenfunktion. Die darf nicht unterschätzen, sonst taucht o. g. Problem auf.
 
mrBrown

mrBrown

Super-Moderator
Mitarbeiter
Naja, die Kostenfunktion kann ja nicht unterschätzen, fürs unterschätzen müsste sie ja kleiner sein, als die Kostenfunktion :p


Aber ich glaub, wir werfen grad unterschiedliche Dinge durcheinander: "algorithmisch" korrekt im Sinne von "Diagonal kostet genausoviel wie horizontal/vertikal und damit arbeitet der A* völlig korrekt" und "Für den Menschen ist Diagonal kürzer"?
 
mihe7

mihe7

Top Contributor
Jein, ich habe schon auf der vorherigen Seite mal geschrieben, dass das nicht am Algorithmus liegt, sondern an der Distanzfunktion.

Die 8 Nachbarn werden in der Reihenfolge links oben nach rechts unten ausgegeben. Wenn Du jetzt
Code:
####
.*r#
##u#
an der Position des Sterns bist, ist der erste relevante Nachbar r. Die Kosten (*,r)=1, d. h. der Knoten r wird mit Kosten (start,*)+1 eingetragen.

Als nächstes kommt u als relevanter Nachbar dran. Die Kosten (*,u)=1, die Gesamtkosten also (start,*)+1 und damit genauso hoch wie die Kosten von r. Da bereits ein Knoten mit diesen Kosten für den Besuch vorgemerkt ist (nämlich r), wird u nicht weiter betrachtet. D. h. der Pfad (*,u) fällt weg.

Nachtrag: das wichtigste fehlt ja noch :)
Code:
##o#
.*r#
####
Jetzt ist o zuerst an der Reihe, d. h. (*,r) fällt weg und die Kurve wird geschnitten.
 
mrBrown

mrBrown

Super-Moderator
Mitarbeiter
Die 8 Nachbarn werden in der Reihenfolge links oben nach rechts unten ausgegeben. Wenn Du jetzt
Code:
####
.*r#
##u#
an der Position des Sterns bist, ist der erste relevante Nachbar r. Die Kosten (*,r)=1, d. h. der Knoten r wird mit Kosten (start,*)+1 eingetragen.

Als nächstes kommt u als relevanter Nachbar dran. Die Kosten (*,u)=1, die Gesamtkosten also (start,*)+1 und damit genauso hoch wie die Kosten von r. Da bereits ein Knoten mit diesen Kosten für den Besuch vorgemerkt ist (nämlich r), wird u nicht weiter betrachtet. D. h. der Pfad (*,u) fällt weg.

Nachtrag: das wichtigste fehlt ja noch :)
Code:
##o#
.*r#
####
Jetzt ist o zuerst an der Reihe, d. h. (*,r) fällt weg und die Kurve wird geschnitten.

Also OpenList würde in dem Fall erstmal nur * mit Kosten n enthalten.
Von * aus sind r und u erreichbar, beide Landen also auf der OpenList, mit jeweils Kosten n+1. Weggefallen ist da noch nichts?


Welcher von beiden dann als nächstes betrachtet wird, hängt dann nur von der Heuristik ab (die in diesem Fall den genauen Kosten entspricht), und dabei kommt es drauf an, ob o oder r näher ist. Wenn die bei beiden gleich ist, haben beide auch genau die gleichen echten Kosten - im Kontext dieses "Mazes", wo Diagonal einfach nicht kürzer als Grade ist.
 
mihe7

mihe7

Top Contributor
Von * aus sind r und u erreichbar, beide Landen also auf der OpenList, mit jeweils Kosten n+1.
Du hast Recht. Aber warum hatte ich dann dieses Nicht-Kurvenschneiden beobachtet?!? :confused: Ich versuche, das nochmal zu reproduzieren.

Nachtrag: dann müsste es an der Schätzung liegen, da diese die Reihenfolge für die Bearbeitung der Open-List vorgibt.

Nachtrag zum Nachtrag: das kann eigentlich auch nicht sein... Ich glaub, ich spinne.
 
Zuletzt bearbeitet:
Ähnliche Java Themen
  Titel Forum Antworten Datum
S verbesserungsvorschläge? Java Basics - Anfänger-Themen 19
fLooojava first project - Verbesserungsvorschläge am Code Java Basics - Anfänger-Themen 8
Z Zahl Pi probabilistisch berechnen (Kritik/Verbesserungsvorschläge) Java Basics - Anfänger-Themen 4
B Erste Schritte Wechselgeld berechen. Verbesserungsvorschläge Java Basics - Anfänger-Themen 10
D Verbesserungsvorschläge zum Quellcode Java Basics - Anfänger-Themen 15
M Bitte um Verbesserungsvorschläge Java Basics - Anfänger-Themen 14
L Suche Verbesserungsvorschläge für mein erstes Programm Java Basics - Anfänger-Themen 34
Chucky Einfacher Taschenrechner Verbesserungsvorschläge Java Basics - Anfänger-Themen 13
Gaudimagspam Assertions im Programm hinzufügen Java Basics - Anfänger-Themen 4
G Weiß jemand wie man dieses Programm schreibt? Java Basics - Anfänger-Themen 84
C Programm ausführen ohne JRE? Java Basics - Anfänger-Themen 3
justemii Gehalt berechnen - Aufgabe Java-Programm Java Basics - Anfänger-Themen 9
N Best Practice How can I creat a programm with java under windows 10 in order to open an spreadsheet in libreoffice calc format Java Basics - Anfänger-Themen 11
W Programm dass Palindrome erkennt Java Basics - Anfänger-Themen 6
K Erste Schritte Programm geht aus Schleife, warum? Java Basics - Anfänger-Themen 2
P Wie für EIN Java Programm von 64bit Java (=Standard) auf 32bit Java Installation (Windows) umschalten? Java Basics - Anfänger-Themen 6
K Programm stoppt einfach ohne Grund Java Basics - Anfänger-Themen 4
M Rekursives Programm zum Anzeigen von Primzahlen Java Basics - Anfänger-Themen 3
X Kurzes Java-Programm, das sich komisch verhält Java Basics - Anfänger-Themen 6
Zrebna Programm kann aus der Konsole nicht gestartet werden (in der IDE läuft es) Java Basics - Anfänger-Themen 2
K Error bei meinem Programm - Hilfe Java Basics - Anfänger-Themen 8
J Programm schreiben Java Basics - Anfänger-Themen 5
T Kann jemand kurz das Programm testen? Java Basics - Anfänger-Themen 13
T Programm Schleife/if Java Basics - Anfänger-Themen 2
T Mein Programm hat Fehler Java Basics - Anfänger-Themen 4
G While/If Programm Java Basics - Anfänger-Themen 2
G Java-Programm Terminal Java Basics - Anfänger-Themen 2
Dimax Java Programm mit exec starten Java Basics - Anfänger-Themen 5
I Java Programm sieht wie exe aus. Java Basics - Anfänger-Themen 3
J Programm vereinfachen Java Basics - Anfänger-Themen 5
G Java-Programm weitergeben Java Basics - Anfänger-Themen 14
Kirby_Sike Programm startet nachdem es compiled wurde nicht Java Basics - Anfänger-Themen 17
T Programm effizienter gestalten Java Basics - Anfänger-Themen 17
M Ein Programm erweitern, wie? Java Basics - Anfänger-Themen 3
J Fehler in Programm: Index -1 out of bounds for length 0 Java Basics - Anfänger-Themen 5
M Programm per Nutzereingabe ändern Java Basics - Anfänger-Themen 3
G Programm mit Schleife funktioniert nicht Java Basics - Anfänger-Themen 5
G If / While Programm (Datei auslesen) Java Basics - Anfänger-Themen 6
G Dezimal zu Binärcode Programm Java Basics - Anfänger-Themen 9
G Programm schreiben: Zahl (n) eingeben, 1+1/n+2/n+3/n+....+n/n Java Basics - Anfänger-Themen 8
M Problem mit meinem Programm Java Basics - Anfänger-Themen 6
L Wie teilt man ein Programm in vernünftige Klassen ein? Java Basics - Anfänger-Themen 10
R Compiler-Fehler HalloWelt-Programm korrekt abgeschrieben, trotzdem Fehlermeldungen Java Basics - Anfänger-Themen 2
W Hilfe beim Chat Programm Java Basics - Anfänger-Themen 14
A Java-Programm läuft bei installierter JDK aber nicht mit JRE? Java Basics - Anfänger-Themen 5
J Mein Programm beendet sich ohne mein Zutun Java Basics - Anfänger-Themen 9
I Datei in Programm speichern Java Basics - Anfänger-Themen 3
H Programm compilieren Java Basics - Anfänger-Themen 10
W Java Programm mit API Anbindung Java Basics - Anfänger-Themen 2
D Java Programm mit JavaScript einbinden Java Basics - Anfänger-Themen 8
O Erstes Programm: Matrizen Multiplikation Java Basics - Anfänger-Themen 10
K Programm ausführen Java Basics - Anfänger-Themen 2
X Java Programm MacOS Java Basics - Anfänger-Themen 1
O Programm verstehen :D Java Basics - Anfänger-Themen 4
A Programm in Konsole Java Basics - Anfänger-Themen 4
S Programm als Daemon ausfuehren - wie rufe ich es auf..? Java Basics - Anfänger-Themen 3
A Wie gebe ich bei android eine string im programm aus? Java Basics - Anfänger-Themen 4
A Erklärung Programm zur Kreisberechnung Java Basics - Anfänger-Themen 43
L Fehler im Programm bei Ausgabe Java Basics - Anfänger-Themen 21
F Array-Programm Java Basics - Anfänger-Themen 10
Koookie Kleines Frage - Antwort Programm (Anfänger) Java Basics - Anfänger-Themen 5
V Vererbung Eclipse startet das Programm nicht und rechnet nicht Java Basics - Anfänger-Themen 6
R Primzahlen Zähler Programm / Benachbarte Primzahlen Java Basics - Anfänger-Themen 30
D Warum gibt mir das Programm nicht den Array invertiert an ? Java Basics - Anfänger-Themen 1
J Zugriff auf Variable in anderem Programm Java Basics - Anfänger-Themen 5
L Programm lässt sich nicht starten! Java Basics - Anfänger-Themen 1
Z Montageberechnungs programm, finde leider den Fehler nicht Java Basics - Anfänger-Themen 13
J Mehrere paintComponenten in einem Programm Java Basics - Anfänger-Themen 0
K Probleme beim Programm schreiben - Lesen von Dateiinhalten -zaehlen von Wörtern/ Buchstaben Java Basics - Anfänger-Themen 4
B Tic Tac Toe - Programm Java Basics - Anfänger-Themen 2
N BitFlags Programm (switch on/off , swap und isSet) Java Basics - Anfänger-Themen 7
T Woher nimmt das Programm die Variablenwerte???? Java Basics - Anfänger-Themen 2
Hanschyo Programm schließt sich einfach Java Basics - Anfänger-Themen 2
A Shopping Cart Programm. Verstehe einige Zusammenhänge nicht Java Basics - Anfänger-Themen 1
T Brauche Hilfe um ein Programm zu verstehe Java Basics - Anfänger-Themen 4
L Programm zur Codieren nach Rotx Java Basics - Anfänger-Themen 1
x-tshainge Mein Programm lässt sich nicht Starten Java Basics - Anfänger-Themen 8
A Erste Schritte Bitte helfen sie mir diese Programm zu schreiben Java Basics - Anfänger-Themen 12
M Programm, das ein Wort einliest Java Basics - Anfänger-Themen 3
W Warum läuft mein Programm nicht? Java Basics - Anfänger-Themen 14
D Auswahl und Ausgabe erstes Programm Java Basics - Anfänger-Themen 8
x-tshainge Schleife für ein Würfel Programm Java Basics - Anfänger-Themen 2
N Passwort Anfrage vor Programm start Java Basics - Anfänger-Themen 1
W Dezimalzahl in Binär umwandeln - Was sollte ich an meinem Programm verbessern? Java Basics - Anfänger-Themen 5
I Programm tut nicht was es soll :) Java Basics - Anfänger-Themen 5
B Programm erwartungswert Java Basics - Anfänger-Themen 16
F Java Programm schließen Java Basics - Anfänger-Themen 1
M Java Methode editierbar machen im Programm Java Basics - Anfänger-Themen 62
W Warum funktioniert mein Programm nicht ? Java Basics - Anfänger-Themen 12
B Mit Java anderes Java Programm starten Java Basics - Anfänger-Themen 3
A Kann mir jemand dieses Programm erklären? Java Basics - Anfänger-Themen 1
J Java Programm Java Basics - Anfänger-Themen 29
C Programm dreht extra Schleife, warum? Java Basics - Anfänger-Themen 6
K Armstrong Programm geht nur bis 1000, aber nicht weiter Java Basics - Anfänger-Themen 2
B Java Eclipse Programm in einer Batch ausführen Java Basics - Anfänger-Themen 3
W Warum funktioniert mein Programm nicht ? Java Basics - Anfänger-Themen 6
P SystemTray: Programm sol im Hintergrund weiter laufen Java Basics - Anfänger-Themen 30
P Sägezahn Muster Programm Java Basics - Anfänger-Themen 2
L Java Programm zum Auswerten von Daten Java Basics - Anfänger-Themen 11
W Erste Schritte Warum funktioniert mein Programm nicht ? ~if Anweisung~ Java Basics - Anfänger-Themen 4

Ähnliche Java Themen

Anzeige

Neue Themen


Oben