Verbesserungsvorschläge zu Wegfinder Programm

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!
 

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

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.
 

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?
 

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

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!
 

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

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:
 

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

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

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

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

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

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
N BMI Rechner Was haltet ihr von dem Code habt ihr Verbesserungsvorschläge weil design teschnisch ist das nicht das geilste würde das gerne überarbeiten Java Basics - Anfänger-Themen 12
D Verbesserungsvorschläge zur Struktur einer Client Server Desktop Chat App Java Basics - Anfänger-Themen 24
Vivien Bitte um Optimierungsvorschläge / Verbesserungsvorschläge / allgemeines Feedback Java Basics - Anfänger-Themen 8
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
J Delay erzeugen, ohne Programm zu blockieren Java Basics - Anfänger-Themen 7
Ü Dead Code im Programm? Java Basics - Anfänger-Themen 13
M Java Mail Programm Java Basics - Anfänger-Themen 4
E Java Programm zur anzeige, ob Winter- oder Sommerzeit herrscht Java Basics - Anfänger-Themen 62
M Mini Jar-Programm Java Basics - Anfänger-Themen 51
G JTable Listselectionlistener friert das Programm ein Java Basics - Anfänger-Themen 8
M Das Programm stellt nichts dar Java Basics - Anfänger-Themen 2
K Programm compilierbar aber nicht ausführbar... Java Basics - Anfänger-Themen 21
Z Programm Ideen Java Basics - Anfänger-Themen 8
P Wie kann ich in meinem Java Programm etwas dauerhaft speichern? Java Basics - Anfänger-Themen 5
P Wie kann ich beispielsweise Speicherstände eines Spiels DAUERHAFT in meinem Programm speichern? Java Basics - Anfänger-Themen 3
H Java-Programm zur Ausgabe von Zuständen Java Basics - Anfänger-Themen 80
G Kann Java-Programm nicht als jar aufrufen, auch als EXE nicht Java Basics - Anfänger-Themen 19
benny1993 Java Programm erstellen für ein Fußball-Turnier Java Basics - Anfänger-Themen 3
T Programm stürzt ab Java Basics - Anfänger-Themen 40
KeinJavaFreak Erste Schritte Programm "Java(TM) Platform SE binary " nicht vorhanden Java Basics - Anfänger-Themen 1
G Programm läuft durch, ohne Eingabe aus dem Chat abzuwarten Java Basics - Anfänger-Themen 4
N Programm Funktioniert mit .txt Datei aber nicht mit .rtf Datei Java Basics - Anfänger-Themen 2
N Interpreter-Fehler Compiler zeigt keine Fehler an, aber das Programm läuft nicht (BlueJ) Java Basics - Anfänger-Themen 2
D Java Programm mit Batch-Datei starten Java Basics - Anfänger-Themen 32
Jul1n4tor Programm mit Scanner und If-Statements Java Basics - Anfänger-Themen 2
D Wie sehe ich ein Java-Programm? Java Basics - Anfänger-Themen 27
K Ist das Programm schlecht bzw. schlampig programmiert ? Java Basics - Anfänger-Themen 9
Zrebna Kann Java Programm nicht in Konsole ausführen Java Basics - Anfänger-Themen 1
K Warum läuft das Programm nicht(bzw. nicht richtig) Java Basics - Anfänger-Themen 4
M Von Eclipse zum richtigen Programm Java Basics - Anfänger-Themen 1
nbergmann IntelliJ: Wie lade ich ein fertiges Programm aus dem Lehrbuch? Java Basics - Anfänger-Themen 26
D Anfängerfrage zu meinem Programm. Java Basics - Anfänger-Themen 15
nbergmann Eclipse: Lehrbuch-Programm startet nicht Java Basics - Anfänger-Themen 22
I Jetty starten von Programm (Main) Java Basics - Anfänger-Themen 27
Kydo Programm Beschreibung Java Basics - Anfänger-Themen 3
nbergmann Eclipse: Lehrbuch-Programm startet nicht Java Basics - Anfänger-Themen 7
T Java FXML selbes Fenster verschiedene Stellen im Programm Java Basics - Anfänger-Themen 5
frager2345 Programm erstellen ohne Autoboxing und Unboxing Java Basics - Anfänger-Themen 13
D JAVA Programm schreiben Java Basics - Anfänger-Themen 46
P exportiertes Programm funktioniert nur teilweise Java Basics - Anfänger-Themen 7
J Mein Programm läuft bei der ersten Eingabe nicht mehr weiter, woran liegt das? Java Basics - Anfänger-Themen 6
M Wo hält das Programm an? Java Basics - Anfänger-Themen 11
J Mein Java Programm lässt sich nicht mehr bearbeiten Java Basics - Anfänger-Themen 2
Fugover Programm funktioniert nicht Java Basics - Anfänger-Themen 11
Fugover Kopfrechnen-Programm Java Basics - Anfänger-Themen 6
NadimArazi Wie kann ich eine collision detection für die Paddles in meinem Pong Programm hinzufügen? Java Basics - Anfänger-Themen 4
sserio Wieso funktioniert mein Programm nicht Java Basics - Anfänger-Themen 2
sserio Größtes Palindrom-Produkt Programm funktioniert nur halb Java Basics - Anfänger-Themen 23
J selbst erstellte Datei mit Programm öffnen Java Basics - Anfänger-Themen 10
F nach Methode Programm nicht beenden Java Basics - Anfänger-Themen 9
A wie kann ich es in meinem Programm rein tun Java Basics - Anfänger-Themen 8
S Fehler beim Programm Java Basics - Anfänger-Themen 2
Jose05 Fehler im Programm feststellen Java Basics - Anfänger-Themen 2
F Kann mir jemand kurz dieses Programm erklären? Java Basics - Anfänger-Themen 22
I Programm erkennt nicht an das Array zurückgegeben wird trotz Initialisierung *einfach* Java Basics - Anfänger-Themen 9
J Nach dem Exportieren funktioniert mein Programm nicht mehr Java Basics - Anfänger-Themen 8
P Mein Programm wird zwar erfolgreich Compiliert, öffnet sich aber nicht Java Basics - Anfänger-Themen 6
J Kann ich mein Programm so schreiben? Java Basics - Anfänger-Themen 4
A Lotto Programm Java Basics - Anfänger-Themen 3
S Programm erstellen Java Basics - Anfänger-Themen 3
A Verarbeiten einer Excel Datei durch das java-Programm Java Basics - Anfänger-Themen 3
S MinMax Programm erstellen Java Basics - Anfänger-Themen 4
J Interpreter-Fehler Programm gibt nicht gewünschtes Ergebnis aus Java Basics - Anfänger-Themen 11
brypa Programm mit Eingabe Java Basics - Anfänger-Themen 129
B Java Programm soll mit Python kommunizeren Java Basics - Anfänger-Themen 1
SpigBin Programm läuft nicht weiter... Java Basics - Anfänger-Themen 10
M JAVA Programm in Website einbinden Java Basics - Anfänger-Themen 19
B Programm, dass alle 3 Tage eine Webseite öffnet? Java Basics - Anfänger-Themen 20
B Programm beendet sich nicht und weiteres seltsames Verhalten Java Basics - Anfänger-Themen 9
N Eclipse Programm normal ausführen Java Basics - Anfänger-Themen 1
D Programm auf Enter warten lassen Java Basics - Anfänger-Themen 2
C Programm das feststellen kann, ob eine eingegebene Zahl einem Schaltjahr entspricht, richtig geschrieben? Java Basics - Anfänger-Themen 11
C Brauche Hilfe um ein Programm zu schreiben Java Basics - Anfänger-Themen 8
F Frage betreff Programm mit dem man C++-Code in JAVA-Code übersetzen lassen kann Java Basics - Anfänger-Themen 2
nevel Programm für die Summer der Zahlen 1- 1ß Java Basics - Anfänger-Themen 12
WAB9703-04 Programm zum automatischen Ausfüllen von Formularen programmieren Java Basics - Anfänger-Themen 3
OSchriever Jar-Programm läuft auf Windows aber nicht auf Linux(Raspberri Pi4) Java Basics - Anfänger-Themen 22
G Programm Code Java Basics - Anfänger-Themen 5
CptK Achsenskalierung in Koordinatensystem hängt Programm auf Java Basics - Anfänger-Themen 5
H Kann eine while-Schleife ein Programm blockieren? Java Basics - Anfänger-Themen 8
TimoN11 Mail Programm mit Java? Java Basics - Anfänger-Themen 1
Sajeel Chattha Dieses Programm umschreiben Java Basics - Anfänger-Themen 5
J Programm beenden ohne System.exit() oder Runtime.exit() Java Basics - Anfänger-Themen 5
F Java Programm, das kleine Buchstaben in einem String zählen soll und bei großen Buchstaben oder Sonderzeichen abbrechen soll. Java Basics - Anfänger-Themen 5
A Programm Histogram Java Basics - Anfänger-Themen 2
C Was ist nötig für ein Java-Programm auf Server für Website Java Basics - Anfänger-Themen 18
CT9288 Interaktion mit laufendem Programm -Fachbegriffe Java Basics - Anfänger-Themen 2
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

Ähnliche Java Themen

Neue Themen


Oben