A*算法实现

Question

我正在构建一个应用程序，它将计算出建筑物中两个房间之间的路线。这个应用程序应该显示一个平面图，然后在上面显示路线。用户进入他们当前的房间和他们想要到达的房间。通过遵循一个教程，我实现了A*算法。在这里，代码：

：

package testalgo.ut;

public class Vector1 {

    private int x;
    private int y;

    public Vector1(){

        set(0,0);
    }

    public Vector1(Vector1 vector){

        set(vector.x, vector.y);

    }
public Vector1(int x,int y ){

    this.x = x;
    this.y = y;

    }
    public void set (int x, int y){

        this.x = x;
        this.y = y;

    }


    public int getX(){

        return x;

    }

public int getY(){

        return y;

    }

public Vector1 setX(int x){

    this.x = x;
    return this;

}

public Vector1 setY(int y){

    this.y = y;
    return this;

}

public Vector1 add(Vector1 vector){


    this.x += vector.x;
    this.y += vector.y;

    return this;
}

public Vector1 subtr(Vector1 vector){


    this.x -= vector.x;
    this.y -= vector.y;

    return this;
}

public boolean equals(Object object){

    if(!(object instanceof Vector1))return false;
    Vector1 vec = (Vector1)object;
    if(vec.getX() == this.getX() && vec.getY() == this.getY())return true;
    return false;

}   

}

Node.java：

package testalgo;

import testalgo.ut.Vector1;

public class Node {

    public Vector1 t;
    public Node parent;
    public double f;
    public double g;
    public double h;


    public Node(Vector1 t,Node parent, double g,double h){

        this.t = t;
        this.parent= parent;
        this.g = g;
        this.h = h;
        this.f= this.g + this.h;

    }

}

CMain.java

package testalgo;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.function.Function;
import java.util.function.ToDoubleFunction;
import java.util.function.ToIntFunction;
import java.util.function.ToLongFunction;

import testalgo.ut.Vector1;

public class CMain {
    private Comparator<Node> sortNodes = new Comparator<Node>(){

        public int compare(Node n0, Node n1) {
            if(n1.f < n0.f)
            return +1;
            if(n1.f < n0.f)
            return -1;  

            return 0;
        }

    };
    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub

    }

    public List<Node> findPath(Vector1 start, Vector1 goal){

        List<Node> open = new ArrayList<Node>();
        List<Node> closed = new ArrayList<Node>();
        Node current = new Node( start, null, 0, getDistance(start, goal));
        open.add(current);
        while (open.size() > 0){
            Collections.sort(open, sortNodes);
            current = open.get(0);
            if(current.t.equals(goal)){
                List<Node> path = new ArrayList<Node>();
                while(current.parent != null){
                    path.add(current);
                current = current.parent;
                }
                open.clear();
                closed.clear();
                return path;
            }
            open.remove(current);
            closed.add(current);
            for (int i = 0; i <9 ; i++){
                if(i ==4)continue;
                int x = current.t.getX();
                int y = current.t.getY();
                int xi = (i%3)-1;
                int yi = (i/3) -1;
                Vector1 a = new Vector1(x + xi, y + yi);
                double g = current.g + getDistance(current.t, a);
                double h = getDistance(a, goal);
                Node node = new Node(a, current,g, h);
                if(vecInList(closed, a) && g >= node.g)continue;
                if(!vecInList(open, a) || g < node.g)open.add(node);
            }
        }
        closed.clear();
         return null;

    }

    private boolean vecInList(List<Node> list, Vector1 vector  ){

        for(Node n : list){

            if(n.t.equals(vector))
                return true;
        }
        return false;
    }

    private double getDistance(Vector1 t, Vector1 goal){

        double dx = t.getX() - goal.getX();
        double dy = t.getY() - goal.getY();

        return Math.sqrt(dx * dx + dy * dy);
    }




}

我用PlotDigitizer来获取平面图上每个房间的坐标。平面图是一张位图。这是我第一次做这样的事情，我不知道如何使坐标和算法一起工作，这样就可以计算和显示路线。任何帮助和建议都将是非常感谢的。谢谢!

Answer 1

要使A*可用，您需要从图形中操作。所以你有一系列的房间，但这并不意味着你有一个易于操作的图表。拥有一个平面图的位图意味着你没有一个图形来操作A* off。你需要一个数据结构，把房间的坐标映射到平面图上。那么你就需要在这些房间之间绘制路径图。这将构成图表的基础。见下面的平面图：

​

​

蓝色方块可能是你的平面图。绿色点是A*工作的节点/向量图上的点。粉红色的线条是房间之间的小径。这个图形表示没有显示给用户。这只是让你想象一下电脑是如何理解空间的。但是你需要用一个映射到平面图的图形数据结构来表示它。

因此，用户在其中一个房间的某个点(不一定是一个绿点)。用户单击另一个房间中的另一个点来告诉我们目的地。单击该算法将找到与用户当前位置最接近的绿色点。这是A*算法的起点。A*的终点将是离目的地最近的绿点。然后A*将使用粉红色/绿色图形数据结构来查找起点和终点之间的路径(即绿色点)。然后移动到用户从那个绿色点点击的目标点。

要绘制路径，您将有一系列绿色点，用户将在起始点和终点之间移动，添加自己的直线，从用户的当前位置到起点，以及终点到目的地点。

因此，您需要手工从Vector类构建粉红色/绿色的点，然后在数据结构的基础上非常容易地应用A*。如果您有创建平面图的人，那么您需要一个更复杂的平面图表示，并且您可以导出房间之间的路径，但是只需要一个图形的平面图就可以自动构建它。

例如，该算法可能已经解决了以下问题：

​

​

给定橙色起点和橙色目标点。用户目前处于橙色起点。用户单击目标点。从起始点开始，该算法将计算出起点绿点是最近的，然后使用A*沿着粉红路径走到终点，然后从终点走到用户单击的目标点。

所以Waypoint模拟每个绿点。邻居数组保存通过粉红边沿直接连接到此Waypoint的点。我发现从文件中读取图形及其边缘并从文件中构建数据结构是最容易的。

在这个模型中，我将展示如何使用距离公式实现g()、h()和f()函数。

public Vector {
    private int x;
    private int y;

    public double distanceFrom( Vector here ) {
        return Math.sqrt( Math.pow(x - here.x, 2) + Math.pow( y - here.y,2) );
    }
}

public class Waypoint {
    Vector position;
    List<Waypoint> neighbors;

    public Waypoint( Vector pos, List<Waypoint> neighbors ) {
        this.position = pos;
        this.neighbors = neighbors;
    }

    public List<Waypoint> getNeighbors() {
        return neighbors;
    }

    public double h( Vector goal ) {
        return goal.distanceFrom( position );
    }

    public double g( Vector current ) {
        return position.distanceFrom( current );
    }

    public double f( Version current, Vector goal ) {
        return g(current) + h(goal);
    }
}