无法在java中实现A Star [英] Unable to implement A Star in java

问题描述

我一直在努力让这个算法运行起来，但是我不能为我的生活做准备。我在网上阅读了很多教程，以及AS3，javascript和C ++中的源代码;但我无法适应我所看到的自己的代码。

I've been trying all day to get this algorithm up and running, but I cant for the life of me. I've read many tutorials on the net, and source code in AS3, javascript, and C++; but I cannot adapt what I am seeing to my own code.

我创建了一个AStar类，它有一个名为Node的嵌套类。地图是一个名为MAP的2D数组。

I have created an AStar class that has a nested class named Node. The map is a 2D array named MAP.

我遇到的最大问题是在pathfind函数中拉出F值。

The biggest problem that I am having is pulling the F value in the pathfind function.

我已经实现了F = G + H，我的问题是实际的AStar算法。有人可以帮忙，这是我到目前为止所取得的：

I have implemented the F = G + H, my problem is the actual AStar algorithm. Can someone please help, this is how far I've got as of yet:

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;
        }
    }
}

这是我能做到的最远使用探路者功能：

This is the furthest I can ever get with the pathfinder function:

   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);

            }
        }

    }

推荐答案

我最近把这个A *代码放在一起解决了 Project Euler 问题。您必须填写 Node 对象矩阵的详细信息。使用它需要您自担风险，但我可以说它解决了问题：）

I recently threw this A* code together to solve a Project Euler problem. You'll have to fill in the details for a matrix of Node objects. Use it at your own risk, however I can say it solved the problem :)

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);
}

这篇关于无法在java中实现A Star的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！