我有这个路径查找代码,它只需走一个方 block 即可完成查找的第一部分
public class PathFinding {
static Vector2 start;
static Vector2 end;
static Cell[][] cells;
static Node currentNode;
static Arena arena;
public static void calcPAth(Vector2 from, Vector2 to,
Cell[][] mapCells, Arena a) {
start = from;
end = to;
cells = mapCells;
arena = a;
List<Node> openList = new ArrayList<Node>();
List<Node> closedList = new ArrayList<Node>();
Gdx.app.log(PArena.LOG, "Lists Created");
currentNode = new Node(null, start);
openList.add(currentNode);
Gdx.app.log(PArena.LOG, "Added start to openList");
// check squares around this and add
int startPX = (int) currentNode.parentV.x / 32;
Gdx.app.log(PArena.LOG, "Start X" + startPX);
int startPY = (int) currentNode.parentV.y / 32;
Gdx.app.log(PArena.LOG, "Start Y" + startPY);
Gdx.app.log("", "");
//
int MIN_X = startPX - 1;
int MIN_Y = startPY - 1;
int MAX_X = startPX + 1;
int MAX_Y = startPY + 1;
int startPosX = (startPX - 1 < MIN_X) ? startPX : startPX - 1;
int startPosY = (startPY - 1 < MIN_Y) ? startPY : startPY - 1;
int endPosX = (startPX + 1 > MAX_X) ? startPX : startPX + 1;
int endPosY = (startPY + 1 > MAX_Y) ? startPY : startPY + 1;
// Check boundaries on start cell
for (int rowNum = startPosX; rowNum <= endPosX; rowNum++) {
for (int colNum = startPosY; colNum <= endPosY; colNum++) {
// All the neighbors will be grid[rowNum][colNum]
if (!cells[rowNum][colNum].getTile().getProperties()
.containsKey("blocked")) {
Node node = new Node(currentNode, new Vector2(
rowNum, colNum));
if (rowNum != startPX && colNum != startPY) {
node.setMovementCost(14);
} else
node.setMovementCost(10);
openList.add(node);
System.out.print(node.getFValue() + "|");
} else
System.out.print("B");
}
System.out.println("");
}
openList.remove(currentNode);
closedList.add(currentNode);
int n = openList.get(0).getFValue();
int index = 0;
for (Node temp : openList) {
if (temp.getFValue() < n) {
n = temp.getFValue();
index = openList.lastIndexOf(temp);
Gdx.app.log("n", "n = " + n);
}
}
currentNode = openList.get(index);
arena.colorSquare(currentNode.getVectorPos());
// need to calc move cost;
//
Gdx.app.log("", "");
openList.clear();
closedList.clear();
}
这是我的 Node 类
public static class Node {
int hVal;
int gVal;
int fVal;
Node parentNode;
Vector2 parentV;
private Node(Node node, Vector2 p) {
setParent(node);
this.parentV = p;
calcHValue();
}
public void setMovementCost(int c) {
this.gVal = c;
calcFVal();
}
private void calcFVal() {
fVal = gVal + hVal;
// Gdx.app.log("Node", "HVal = " + hVal);
// Gdx.app.log("Node", "GVal = " + gVal);
// Gdx.app.log("Node", "FVal = " + fVal);
}
private void calcHValue() {
int x = (int) (parentV.x - end.x);
if (x < 0)
x *= -1;
int y = (int) (parentV.y - end.y);
if (y < 0)
y *= -1;
hVal = (int) (x + y) / 32;
// Gdx.app.log(PArena.LOG, "Heuristic Value" + hVal);
}
private void setParent(Node node) {
this.parentNode = node;
}
public int getFValue() {
return fVal;
}
public Vector2 getVectorPos() {
return parentV;
}
}
我的问题是我的调试输出是这样的
15|11|15|
11|11|11|
15|11|15|
所以基本上它并没有实际计算总值(value)。它只是添加移动成本,而不是启发式。
这是什么问题?我是不是少了一步?
最佳答案
我认为您缺少继任者列表。 A* 确实有一个后继列表,当打开列表不为空时,您可以执行以下操作:
while (openList.size() != 0) {
successor.clear();
q = openList.remove(); //first element of the prio queue
// generate your neighbornodes of q and add them to the successorlist
//after this you iterate over the successor and check if its your goalnode.
//If so you do return it else you add it to the openlist. (still inside of the while!)
//Dont forget to check if the neighbor is inside of the close list!
//if so you do not need to add it to the successorlist
//Here is how it does look at mine A*. It also contains a check if there is a betterone
// calc
for (Node suc : successor) {
if (suc.x == (int) this.screen.character.mapPos.x
&& suc.y == (int) this.screen.character.mapPos.y)
return suc; //return the goalnode
boolean add = true;
if (betterIn(suc, openList))
add = false;
if (betterIn(suc, closeList))
add = false;
if (add)
openList.add(suc);
}
最后但并非最不重要的一点是,您需要从 openlist 中删除 q note 并将其添加到 close list 中。
}
closeList.add(q);
}//end of while
一些更小的改进是您确实向节点添加了一个比较对象..
@Override
public int compareTo(Node o) {
if ((this.g + this.h) < (o.g + o.h))
return -1;
else if ((this.g + this.h) >= (o.g + o.h))
return 1;
else
return 0;
}
还覆盖它的 equals 和 hashCode 方法,例如如下所示:
@Override
public boolean equals(Object o) {
// override for a different compare
return ((Node) o).x == this.x && ((Node) o).y == this.y;
}
@Override
public int hashCode() {
return x + y;
}
之后你的openList
可以是PriorityQueue<Node>
并且您从 得到的第一个对象始终是 h 最小的对象。
不要忘记返回最终的 Node 来迭代 getparent 方法来获取路径。
<小时/>private boolean betterIn(Node n, Collection<Node> l) {
for (Node no : l) {
if (no.x == n.x && no.y == n.y && (no.g + no.h) <= (n.g + n.h))
return true;
}
return false;
}
关于java - 修复寻路代码,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18709081/