Изображение странного Z-движения ... F стоимость не имеет значения?
Я нахожу путь, но не самый короткий. Я думаю, что мой PriorityQueue не в правильном порядке или просто путь восстановления плох. Не могу понять это. Я сделал это из псевдокода вики и некоторых видео на YouTube. Я пытался отладить это. Иногда порядок приоритетной очереди неправильный. Я попытался изменить порядок, удалив и прочитав, как вы видите ниже. Он всегда находит путь, но иногда для пути выбирает более высокое значение f.
Я кое-что понял: если я запускаю метод поиска пути 10 раз, это дает отличный результат. (может быть, это зависит от количества соседей?) Я вызываю поиск пути щелчком правой кнопки мыши, и после этого я устанавливаю мышь в положение false, поэтому при нажатии она запускается 1 раз. Я удалил этот ложный переключатель, и когда мышь нажата, он дает идеальный результат, если удерживать ее правой. Теперь мне нужно 10 раз запустить поиск пути, чтобы получить идеальный результат:
//A* path finding by right click
if (handler.isMouseright()==true) {
if (selected==true) {
handler.setMouseright(false);
//A star path finding:
for (int j=0;j<10;j++) {
aStar = new AStar((int)x/Game.tilesize,(int)y/Game.tilesize,(int)MouseInput.mx/Game.tilesize,(int)MouseInput.my/Game.tilesize);
path=aStar.findPath();
}
//aStar = null;
}
}
public class AStar {
public Node[][] searchArea;
public PriorityQueue<Node> openList;
public ArrayList<Node> closedList;
public ArrayList<Node> neighbourList;
public Node startNode;
public Node endNode;
public Node currentNode;
public Node parentNode;
public AStar(int startNodeX,int startNodeY, int endNodeX,int endNodeY) {
this.searchArea=Game.Nodes.clone();
this.startNode=searchArea[startNodeX][startNodeY];
this.endNode=searchArea[endNodeX][endNodeY];
this.openList = new PriorityQueue<Node>(new Comparator<Node>() {
@Override
public int compare(Node node0, Node node1) {
return Integer.compare(node0.getF(), node1.getF());
}
});
this.closedList = new ArrayList<Node>();
this.neighbourList = new ArrayList<Node>();
}
public ArrayList<Node> findPath() {
ArrayList<Node> path = new ArrayList<Node>();
int tentativeG;
startNode.setG(0);
startNode.calculateH(endNode);
startNode.calculateF();
openList.add(startNode);
while(!openList.isEmpty()) {
currentNode=openList.poll();
closedList.add(currentNode);
if (currentNode.getX()==endNode.getX() && currentNode.getY()==endNode.getY()) {
//path found!
path=getPath(currentNode);
System.out.println("Path found!");
return path;
} else {
//search neighbours
//neighbours:
//(x-1,y-1) (x0,y-1) (x+1,y-1)
//(x-1,y0) (x0,y0) (x+1,y0)
//(x-1,y+1) (x0,y+1) (x+1,y+1)
if (neighbourList.isEmpty()==false) neighbourList.clear();
//+map bounds check
//upper row---------------------------------------------------------------------------------------------------------------------------------------
if (currentNode.getX() > 0 && currentNode.getY() > 0) neighbourList.add(searchArea[currentNode.getX()-1][currentNode.getY()-1]);
if (currentNode.getY() > 0) neighbourList.add(searchArea[currentNode.getX()][currentNode.getY()-1]);
if (currentNode.getX() < Game.tiles && currentNode.getY() > 0) neighbourList.add(searchArea[currentNode.getX()+1][currentNode.getY()-1]);
//middle row--------------------------------------------------------------------------------------------------------------------------------------
if (currentNode.getX() > 0) neighbourList.add(searchArea[currentNode.getX()-1][currentNode.getY()]);
if (currentNode.getX() < Game.tiles) neighbourList.add(searchArea[currentNode.getX()+1][currentNode.getY()]);
//lower row---------------------------------------------------------------------------------------------------------------------------------------
if (currentNode.getX() > 0 && currentNode.getY() < Game.tiles) neighbourList.add(searchArea[currentNode.getX()-1][currentNode.getY()+1]);
if (currentNode.getY() < Game.tiles) neighbourList.add(searchArea[currentNode.getX()][currentNode.getY()+1]);
if (currentNode.getX() < Game.tiles && currentNode.getY() < Game.tiles) neighbourList.add(searchArea[currentNode.getX()+1][currentNode.getY()+1]);
for (Node neighbour : neighbourList) {
if (neighbour.isBlock==true || closedList.contains(neighbour)) continue;
currentNode.calculateG(startNode);
//tentative_gScore := gScore[current] + dist_between(current, neighbor)
tentativeG=currentNode.getG()+calculateNodeDist(currentNode,neighbour);
if (tentativeG >= neighbour.getG() || openList.contains(neighbour)==false) {
neighbour.setParent(currentNode);
neighbour.setG(tentativeG);
neighbour.calculateH(endNode);
neighbour.calculateF();
if (openList.contains(neighbour)==false) {
openList.add(neighbour);
openList.remove(neighbour); //reorder array
openList.add(neighbour); //reorder array
}
}
}
}
}
return path;
}
public ArrayList<Node> getPath(Node currentNode) {
ArrayList<Node> path = new ArrayList<Node>();
path.add(currentNode);
Node parentNode;
while ((parentNode = currentNode.getParent()) != null && parentNode!=startNode) {
path.add(0, parentNode);
currentNode = parentNode;
}
return path;
}
public int calculateNodeDist(Node node1,Node node2) {
//this.g=Math.abs(startNode.yy - this.yy) + Math.abs(startNode.xx - this.xx);
int dst;
int dstX = Math.abs(node1.getX() - node2.getX());
int dstY = Math.abs(node1.getY() - node2.getY());
if (dstX > dstY) {
dst = 14*dstY + 10* (dstX-dstY);
} else {
dst = 14*dstX + 10 * (dstY-dstX);
}
return dst;
}
}
public class Node {
public int xx,yy;
public int h; //heuristic distance from endNode
public int g; //distance from startNode
public int f; //h+g
public boolean isBlock; //path blocker?
public Node parent; //the parent node. if algorithm founds a path it can trace back
public Node getParent() {
return parent;
}
public void setParent(Node parent) {
this.parent = parent;
}
public Node(int xx, int yy) {
super();
this.xx = xx;
this.yy = yy;
}
public int getX() {
return xx;
}
public void setX(int xx) {
this.xx = xx;
}
public int getY() {
return yy;
}
public void set(int yy) {
this.yy = yy;
}
public void calculateH(Node endNode) {
//this.h = Math.abs(endNode.yy - this.yy) + Math.abs(endNode.xx - this.xx);
int dstX = Math.abs(this.getX() - endNode.getX());
int dstY = Math.abs(this.getY() - endNode.getY());
if (dstX > dstY) {
this.h = 14*dstY + 10* (dstX-dstY);
} else {
this.h = 14*dstX + 10 * (dstY-dstX);
}
}
public void calculateG(Node startNode) {
//this.g=Math.abs(startNode.yy - this.yy) + Math.abs(startNode.xx - this.xx);
int dstX = Math.abs(this.getX() - startNode.getX());
int dstY = Math.abs(this.getY() - startNode.getY());
if (dstX > dstY) {
this.g = 14*dstY + 10* (dstX-dstY);
} else {
this.g = 14*dstX + 10 * (dstY-dstX);
}
}
public void calculateF() {
int finalCost = getG() + getH();
this.setF(finalCost);
}
public int getH() {
return h;
}
public void setH(int h) {
this.h = h;
}
public int getG() {
return g;
}
public void setG(int map) {
this.g = map;
}
public int getF() {
return f;
}
public void setF(int finalCost) {
this.f = finalCost;
}
public boolean isBlock() {
return isBlock;
}
public void setBlock(boolean isBlock) {
this.isBlock = isBlock;
}
}
Хорошо, я получил решение сам. оператор if неверен в конце поиска пути:
for (Node neighbour : neighbourList) {
if (neighbour.isBlock==true) continue;
currentNode.calculateG(startNode);
tentativeG=currentNode.getG()+calculateNodeDist(currentNode,neighbour);
if (!openList.contains(neighbour) && !closedList.contains(neighbour) || tentativeG < neighbour.getG()) {
neighbour.setParent(currentNode);
neighbour.setG(tentativeG);
neighbour.calculateH(endNode);
neighbour.calculateF();
if (closedList.contains(neighbour)) closedList.remove(neighbour);
if (!openList.contains(neighbour)) openList.add(neighbour);
}
}