我目前正在使用A *算法学习和编程寻路（在Java中）。我碰到的一个问题是，当多个实体试图pathfind，他们都改变previousNode（在Node该Node所计算出的上是从哪里来的），搞乱了算法，并最终Node A将指向Node B和Node B将指向Node A。
如何将算法更改为
previousNode在所有A *算法中都乱七八糟的系统（我看到的就是）我试图避免让一个实体完成寻路，然后告诉下一个实体进行寻路，依此类推。就像在Java中做一个wait()-notify()对。
public Path findPath(int startX, int startY, int goalX, int goalY) {
//Path is basically just a class that contains an ArrayList,
//containing Nodes, which contains the steps to reach a goal.
if(map.getNode(goalX, goalY).isObstacle()) {
return null;
}
map.getNode(startX, startY).setDistanceFromStart(0);
closedList.clear();
openList.clear(); //A List with added getFirst() - gets the first Node in the list
openList.add(map.getNode(startX, startY));
while(openList.size() != 0) {
//Node contains a List that has all of the Nodes around this node, a
//F, G, and H value, and its row(y) and column(x)
Node current = openList.getFirst();
if(current.getX() == goalX && current.getY() == goalY) {
return backtrackPath(current);
}
openList.remove(current);
closedList.add(current);
for(Node neighbor : current.getNeighborList()) {
boolean neighborIsBetter;
//If I've already searched this neighbor/node, don't check it
if(closedList.contains(neighbor)) {
continue;
}
if(!neighbor.isObstacle()) {
float neighborDistanceFromStart = (current.getDistanceFromStart() + map.getDistanceBetween(current, neighbor));
if(!openList.contains(neighbor)) {
openList.add(neighbor);
neighborIsBetter = true;
} else if(neighborDistanceFromStart < current.getDistanceFromStart()) {
neighborIsBetter = true;
} else {
neighborIsBetter = false;
}
if(neighborIsBetter) {
neighbor.setPreviousNode(current);
neighbor.setDistanceFromStart(neighborDistanceFromStart);
neighbor.setHeuristic(getManhattanDistance(neighbor.getX(), neighbor.getY(), goalX, goalY));
}
}
}
}
return null;
}
public Path backtrackPath(Node fromNode) {
Path path = new Path();
while(fromNode.getPreviousNode() != null) {
path.prependWaypoint(fromNode);
fromNode = fromNode.getPreviousNode();
}
return path;
}
我正在专门谈论（内findPath()）
if(neighborIsBetter) {
neighbor.setPreviousNode(current); //previousNode is a value in the Node class that points to the Node that it came from
neighbor.setDistanceFromStart(neighborDistanceFromStart);
neighbor.setHeuristic(getManhattanDistance(neighbor.getX(), neighbor.getY(), goalX, goalY));
}
我认为如果不以某种方式为给定路径存储反向指针，就无法进行A *（或任何寻路算法）。这样就给您两个选择
选项1相当不言自明，可能是更好的选择。如果这仅适合您，则可能应该选择该选项（而不是尝试使A *在单个图形上完全并发）。这将需要添加map作为输入参数（并要求并发调用应使用其他映射实例，否则将引发异常或具有未指定的行为，如果未发生）。另外，您应该在每个调用中实例化新数据结构closedList并将其openList作为新数据结构，而不是共享列表。
如果那不是您喜欢的-您确实想将mutli-call用法完全封装到方法本身中，我认为您可以执行此操作的最简单方法是需要一个额外的参数id-某些唯一的字符串，保证该字符串不是与id另一个并发呼叫的相同。因此，A *的标头现在看起来像：
public Path findPath(final String ID, int startX, int startY, int goalX, int goalY) {
从那里，所有的每一个设定的路径发现场的实现改变Node到HashMap与id作为重点。从您的代码中，我将猜测您的Node类如下所示：
public class Node{
//Fields used by the A* call - no problem here
private boolean obstacle;
//Fields *edited* by the A* call
private float distanceFromStart;
private Node previous;
private int heuristic;
//other fields and stuff
public boolean isObstacle(){
return obstacle;
}
public float getDistanceFromStart(){
return distanceFromStart;
}
public void setDistanceFromStart(float f){
distanceFromStart = f;
}
public Node getPrevious(){
return previous;
}
public void setPrevious(Node p){
previous = p;
}
public int getHeuristic(){
return heuristic;
}
public void setHeuristic(int h){
heuristic = h;
}
}
我们可以编辑已编辑的字段，以便能够存储许多值，id例如：
public class Node{
//Fields used by the A* call - no problem here
private boolean obstacle;
//Fields *edited* by the A* call
private HashMap<String,Float> distanceFromStart;
private HashMap<String,Node> previous;
private HashMap<String,Integer> heuristic;
//other fields and stuff
public boolean isObstacle(){
return obstacle;
}
public float getDistanceFromStart(String id){
return distanceFromStart.get(id);
}
public void setDistanceFromStart(String id, float f){
distanceFromStart.put(id, f);
}
public Node getPrevious(String id){
return previous.get(id);
}
public void setPrevious(String id, Node p){
previous.put(id,p);
}
public int getHeuristic(String id){
return heuristic.get(id);
}
public void setHeuristic(String id,int h){
heuristic.put(id,h);
}
}
从那里，只需编辑您的A *方法，即可在需要时将方法调用的ID提供给getter和setter。只要两个并发方法调用的id值不同，它们就不会互相干扰。要使其正常工作，请记住三件事：
无论哪种方式，你还是应该openList和closedList新的地方的情况下，无论你选择什么样的并发方法。创建openList和closedList共享实例没有任何好处，只有错误可以解决。
List<Node> closedList = new LinkedList<Node>();
List<Node> openList = new LinkedList<Node>();
//Don't have to clear them anymore - they're new lists
openList.add(map.getNode(startX, startY));
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句