5

私は一日中このアルゴリズムを稼働させようとしてきましたが、一生できません。ネット上の多くのチュートリアルと、AS3、javascript、および C++ のソース コードを読みました。しかし、私が見ているものを自分のコードに適応させることはできません。

Node.js という名前のネストされたクラスを持つ AStar クラスを作成しました。マップは、MAP という名前の 2D 配列です。

私が抱えている最大の問題は、pathfind 関数で F 値を取得することです。

私は F = G + H を実装しました。私の問題は実際の AStar アルゴリズムです。誰か助けてください。

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 or Heuristic part of A* algorithm
    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;
        }
    }
}

これは、パスファインダー機能を使用して取得できる最も遠いものです。

   public void pathfinder()
    {
        LinkedList<Node> openList = new LinkedList();
        LinkedList<Node> 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);

            }
        }

    }
4

2 に答える 2

6

私は最近、プロジェクトオイラーの問題を解決するためにこのA*コードを一緒に投げました。オブジェクトのマトリックスの詳細を入力する必要がありNodeます。ご自身の責任で使用してください、しかし私はそれが問題を解決したと言うことができます:)

public class Node {
    List<Node> neighbors = new ArrayList<Node>();
    Node parent;
    int f;
    int g;
    int h;
    int x;
    int y;
    int cost;
}

public List<Node> aStar(Node start, Node goal) {
    Set<Node> open = new HashSet<Node>();
    Set<Node> closed = new HashSet<Node>();

    start.g = 0;
    start.h = estimateDistance(start, goal);
    start.f = start.h;

    open.add(start);

    while (true) {
        Node current = null;

        if (open.size() == 0) {
            throw new RuntimeException("no route");
        }

        for (Node node : open) {
            if (current == null || node.f < current.f) {
                current = node;
            }
        }

        if (current == goal) {
            break;
        }

        open.remove(current);
        closed.add(current);

        for (Node neighbor : current.neighbors) {
            if (neighbor == null) {
                continue;
            }

            int nextG = current.g + neighbor.cost;

            if (nextG < neighbor.g) {
                open.remove(neighbor);
                closed.remove(neighbor);
            }

            if (!open.contains(neighbor) && !closed.contains(neighbor)) {
                neighbor.g = nextG;
                neighbor.h = estimateDistance(neighbor, goal);
                neighbor.f = neighbor.g + neighbor.h;
                neighbor.parent = current;
                open.add(neighbor);
            }
        }
    }

    List<Node> nodes = new ArrayList<Node>();
    Node current = goal;
    while (current.parent != null) {
        nodes.add(current);
        current = current.parent;
    }
    nodes.add(start);

    return nodes;
}

public int estimateDistance(Node node1, Node node2) {
    return Math.abs(node1.x - node2.x) + Math.abs(node1.y - node2.y);
}
于 2011-04-09T00:28:49.763 に答える
0

単純な型のみを使用しようとしているのか、それとも考えていなかったのかはわかりませんが、A* を機能させるには PriorityQueue が必要です。

考える良い方法は、開始点を距離 0 の優先キューに入れ、優先キューが空になったときにのみ停止するループを開始することです。

ループ内で最小ノードを取り出し、それが以前に開かれていないかどうか、または開いているかどうか、さらに短い方法を見つけたかどうかを確認します。これらのいずれかが true の場合、距離を新しいノードに追加し、エッジ/正方形からマップに追加してから、距離 + ヒューリスティックを優先度キューに追加します。

ブール値のグリッドと、1D 配列と 2D 配列の間の一定の変換で動作するようにこれを書きましたが、読みやすいと思います。

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

    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("End found at (" + newX + ", " + newY + ")");
                                paintGridDist = true;

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

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

    paintGridDist = true;
    repaint();
}
于 2011-04-29T12:47:30.003 に答える