无法在java中实现A Star
我一直在努力让这个算法运行起来，但我不能为我的生活做准备。 我在网上阅读了很多教程，以及AS3，javascript和C ++中的源代码; 但我无法适应我所看到的自己的代码。
我创建了一个AStar类，它有一个名为Node的嵌套类。 地图是名为MAP的2Darrays。
我遇到的最大问题是在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; } } } 这是我用路径查找function得到的最远的：
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); } } }
我最近将这个A *代码放在一起以解决Project Euler问题。 您必须填写Node对象矩阵的详细信息。 使用它需要您自担风险，但我可以说它解决了问题:)
public class Node { List neighbors = new ArrayList (); Node parent; int f; int g; int h; int x; int y; int cost; } public List aStar(Node start, Node goal) { Set open = new HashSet (); Set closed = new HashSet (); 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 nodes = new ArrayList (); 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); }
我不知道你是否只想使用简单的类型，或者如果你只是没有考虑它，但你需要有一个PriorityQueue来让你的A *工作。
一种好的思考方式是将起始点放入距离为0的优先级队列中，然后启动一个仅在先前队列为空时停止的循环。
在循环中，您将最小节点取出，并检查它是否之前没有打开，或者如果它已经打开，如果您现在找到了更短的路径。 如果其中任何一个为真，则将距离添加到新节点，将边/边距添加到地图，然后将距离+启发式添加到优先级队列。
我已经写过这个用于布尔网格，以及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(); 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(); int n = convert2Dto1D(newX, newY); route.add(n); do{ n = edgeTo.get(n); route.add(n); }while(start != n); repaint(); return; } } } } } } } paintGridDist = true; repaint(); }