Nicht in der Lage, A Star in Java zu implementieren

Question

Ich habe den ganzen Tag damit verbracht, diesen Algorithmus zum Laufen zu bringen, aber ich kann es einfach nicht. Ich habe viele Tutorials im Netz gelesen und Quellcode in AS3, Javascript und C ++ angesehen, aber ich kann nicht anpassen, was ich sehe, um es in meinen eigenen Code einzufügen.

Ich habe eine AStar-Klasse erstellt, die eine verschachtelte Klasse namens Node hat. Die Karte ist ein 2D-Array namens MAP.

Das größte Problem, das ich habe, ist das Herausholen des F-Werts in der pathfind-Funktion.

Ich habe F = G + H implementiert, aber mein Problem ist der eigentliche AStar-Algorithmus. Kann mir bitte jemand helfen, das ist bisher mein Stand:

import java.util.ArrayList;

public class AStar
{
    int MAP[][];

    Node startNode, endNode;

    public AStar(int MAP[][], int startXNode, int startYNode,
                              int endXNode, int endYNode)
    {
        this.MAP = MAP;
        startNode = new Node(startXNode, startYNode);
        endNode = new Node(endXNode, endYNode);
    }

    public void pathfinder()
    {
        ArrayList openList = new ArrayList();
        ArrayList closedList = new ArrayList();

    }

    public int F(Node startNode, Node endNode)
    {
        return (H(startNode, endNode) + G(startNode));
    }

    //H oder Heuristik-Teil des A*-Algorithmus
    public int H(Node startNode, Node endNode)
    {
        int WEIGHT = 10;
        int distance = (Math.abs(startNode.getX() - endNode.getX()) + Math.abs(startNode.getY() - endNode.getY()));

        return (distance * WEIGHT);
    }

    public int G(Node startNode)
    {
        if(MAP[startNode.getX() - 1][startNode.getY()] != 1)
        {
            return 10;
        }

        if(MAP[startNode.getX() + 1][startNode.getY()] != 1)
        {
            return 10;
        }

        if(MAP[startNode.getX()][startNode.getY() -1] != 1)
        {
            return 10;
        }

        if(MAP[startNode.getX()][startNode.getY() + 1] != 1)
        {
            return 0;
        }

        return 0;
    }

    public class Node
    {
        private int NodeX;
        private int NodeY;

        private int gScore;
        private int hScore;
        private int fScore;

        public Node(int NodeX, int NodeY)
        {
            this.NodeX = NodeX;
            this.NodeY = NodeY;
        }

        public int getX()
        {
            return NodeX;
        }

        public int getY()
        {
            return NodeY;
        }

        public int getG()
        {
            return gScore;
        }

        public void setG(int gScore)
        {
            this.gScore = gScore;
        }

        public int getH()
        {
            return hScore;
        }

        public void setH(int hScore)
        {
            this.hScore = hScore;
        }

        public int getF()
        {
            return fScore;
        }

        public void setF(int fScore)
        {
            this.fScore = fScore;
        }
    }
}

Dies ist der letzte Stand, den ich je mit der pathfinder-Funktion erreichen kann:

public void pathfinder()
{
    LinkedList openList = new LinkedList();
    LinkedList closedList = new LinkedList();

    Node currentNode;

    openList.add(startNode);

    while(openList.size() > 0)
    {
        currentNode = (Node) openList.get(0);
        closedList.add(currentNode);

        for(int i = 0; i < openList.size(); i++)
        {
            int cost = F(currentNode, endNode);

        }
    }

}

Answer 1

Ich habe kürzlich diesen A*-Code zusammengestellt, um ein Project Euler Problem zu lösen. Sie müssen die Details für eine Matrix von Node-Objekten ausfüllen. Verwenden Sie es jedoch auf eigenes Risiko, obwohl ich sagen kann, dass das Problem gelöst wurde :)

public class Node {
    List nachbarn = new ArrayList();
    Node elternteil;
    int f;
    int g;
    int h;
    int x;
    int y;
    int kosten;
}

public List aStar(Node start, Node ziel) {
    Set offen = new HashSet();
    Set geschlossen = new HashSet();

    start.g = 0;
    start.h = schätzenEntfernung(start, ziel);
    start.f = start.h;

    offen.add(start);

    while (true) {
        Node aktuell = null;

        if (offen.size() == 0) {
            throw new RuntimeException("keine Route");
        }

        for (Node knoten : offen) {
            if (aktuell == null || knoten.f < aktuell.f) {
                aktuell = knoten;
            }
        }

        if (aktuell == ziel) {
            break;
        }

        offen.remove(aktuell);
        geschlossen.add(aktuell);

        for (Node nachbar : aktuell.nachbarn) {
            if (nachbar == null) {
                continue;
            }

            int nächstesG = aktuell.g + nachbar.kosten;

            if (nächstesG < nachbar.g) {
                offen.remove(nachbar);
                geschlossen.remove(nachbar);
            }

            if (!offen.contains(nachbar) && !geschlossen.contains(nachbar)) {
                nachbar.g = nächstesG;
                nachbar.h = schätzenEntfernung(nachbar, ziel);
                nachbar.f = nachbar.g + nachbar.h;
                nachbar.elternteil = aktuell;
                offen.add(nachbar);
            }
        }
    }

    List knoten = new ArrayList();
    Node aktuell = ziel;
    while (aktuell.elternteil != null) {
        knoten.add(aktuell);
        aktuell = aktuell.elternteil;
    }
    knoten.add(start);

    return knoten;
}

public int schätzenEntfernung(Node knoten1, Node knoten2) {
    return Math.abs(knoten1.x - knoten2.x) + Math.abs(knoten1.y - knoten2.y);
}

Answer 2

Ich weiß nicht, ob du nur versuchst, einfache Typen zu verwenden, oder ob du einfach nicht daran gedacht hast, aber du brauchst eine PriorityQueue, um dein A* zum Laufen zu bringen.

Ein guter Ansatz ist, dass du deinen Startpunkt mit Entfernung 0 in eine Prioritätswarteschlange einfügst und dann eine Schleife startest, die nur stoppt, wenn die Prioritätswarteschlange leer ist.

In der Schleife nimmst du den Min-Knoten heraus und prüfst, ob er noch nicht geöffnet wurde oder falls doch, ob du nun einen kürzeren Weg zu ihm gefunden hast. Wenn eine dieser Bedingungen zutrifft, fügst du die Entfernung zum neuen Knoten hinzu, fügst die Kante/von-Quadrat zu einer Map hinzu und fügst dann die Entfernung + Heuristik zur Prioritätswarteschlange hinzu.

Ich habe dies geschrieben, um auf einem Gitter von booleschen Werten zu arbeiten und eine konstante Umwandlung zwischen 1D- und 2D-Arrays, aber ich hoffe, es ist lesbar:

public void AStarRoute()
{
    gridDist = new double[rows][cols];
    System.out.println("Start von AStarRoute");
    MinPriorityQueue pq = new MinPriorityQueue(rows * cols);
    edgeTo = new HashMap();

    gridDist[x1Dto2D(start)][y1Dto2D(start)] = 0;
    pq.insert(start, 0);
    int from;
    while (!pq.isEmpty()) {
        from = pq.delMin();
        int x = x1Dto2D(from);
        int y = y1Dto2D(from);
        for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
                int newX = x + i;
                int newY = y + j;
                if (newX >= 0 && newY >= 0 && newX < cols && newY < rows && !(i == 0 && j == 0)) {
                    if (grid[newX][newY]) {
                        //System.out.println("NewDist: " + gridDist[newX][newY] + " - OldDist+dist: " + (gridDist[x][y] + ((Math.abs(i) == Math.abs(j)) ? 1.4 : 1.0)) + ":" + (int)(gridDist[x][y] + ((Math.abs(i) == Math.abs(j)) ? 1.4 : 1.0)));
                        if (!edgeTo.containsKey(convert2Dto1D(newX, newY)) || gridDist[newX][newY] > (gridDist[x][y] + ((Math.abs(i) == Math.abs(j)) ? 14 : 10))) {
                            gridDist[newX][newY] = (int)(gridDist[x][y] + ((Math.abs(i) == Math.abs(j)) ? 14 : 10));
                            maxDistToEnd = (int)Math.max(maxDistToEnd, gridDist[newX][newY]);
                            edgeTo.put(convert2Dto1D(newX, newY), convert2Dto1D(x, y));
                            pq.insert(convert2Dto1D(newX, newY), gridDist[newX][newY] + (int)Math.sqrt(Math.pow((newX - x1Dto2D(end))*10, 2) + Math.pow((newY - y1Dto2D(end))*10, 2)));
                            if(convert2Dto1D(newX, newY) == end){
                                System.out.println("Ende gefunden bei (" + newX + ", " + newY + ")");
                                paintGridDist = true;

                                route = new ArrayList();
                                int n = convert2Dto1D(newX, newY);
                                route.add(n);
                                do{
                                    n = edgeTo.get(n);
                                    route.add(n);
                                }while(start != n);

                                repaint();
                                return;
                            }
                        }
                    }
                }
            }
        }
    }

    paintGridDist = true;
    repaint();
}