4. 代码实现

4. 代码实现

首先对整个算法我们需要整体上的认识：

1. Java的优先队列不能迭代遍历，所以在检查检点是否出现过可以通过添加一个Exist表，这个表格将收集出现

在Open表和Close表中出现过的所有结点

1. Close表使用普通的数组即可

需要一个Node类记录经过的每一个结点的信息，Node类的信息如下：

//结点的属性 //因为每个结点都需要存放在优先队列中，所以需要实现Comparable接口

class Node implements Comparable<Node> { public int x; //x坐标

public int y; //y坐标 public int F; //F属性

public int G; //G属性 public int H; //H属性

public Node Father;//此结点的上一个结点 //构造函数

public Node(int x, int y) { this.x = x;

this.y = y;

} //通过结点的坐标和目标结点的坐标可以计算出F， G， H三个属性

//需要传入这个节点的上一个节点和最终的结点 public void init_node(Node father, Node end) {

this.Father = father;

if (this.Father != null) { //走过的步数等于父节点走过的步数加一

this.G = father.G + 1;

} else { //父节点为空代表它是第一个结点 this.G = 0;

} //计算通过现在的结点的位置和最终结点的位置计算H值

this.H = Math.abs(this.x - end.x) + Math.abs(this.y - end.y);

this.F = this.G + this.H;

} // 用来进行和其他的Node类进行比较重写的方法

@Override public int compareTo(Node o) {

return Integer.compare(this.F, o.F);

} }

ps:为了方便数据的处理，所有的成员变量我都public了（这好吗？这不好！不要学我哈，还是要学会封装的。）

接下来是Solution类，所有的算法和使用到数据结构都存放在这个类中首先需要一个地图：

{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, {-1, 0, 0, 0, 0, 0, 0, 0, 0, -1},

{-1, 0, 0, 0, 0, -1, 0, 0, 0, -1}, {-1, 0, 0, 0, -1, 0, 0, 0, 0, -1},

{-1, 0, 1, 0, -1, 0, 0, 2, 0, -1}, {-1, 0, 0, 0, 0, -1, 0, 0, 0, -1},

{-1, 0, 0, 0, -1, 0, 0, 0, 0, -1}, {-1, 0, 0, 0, 0, -1, 0, 0, 0, -1},

{-1, 0, 0, 0, 0, 0, 0, 0, 0, -1}, {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}

};

这个map就是上面的地图，由于判断地图是否越界过于麻烦，添加了辅助区域，让我们对【当前结点】进行扩展操作的时候判断扩展是否越界变得简单直观，只要不等于-1就代表没有越界，而不必判断x坐标和y坐标的范围。

有了地图之后我们还需要【Open表】，【Close表】，【Exist表】对结点进行扩展添加的时候除了需要判断结点是否合法，还需要判断结点是否在【Open表】和【Close表】中出现

过但是由于【Open表】不是可以遍历的数据结构，为了方便使用【Exist表】来记录当前结点是否出现在【Open表】

中和【Close表】中

//Open表用来存放能够到达的结点 //Open表会自动把F值最小的结点放在队首

public PriorityQueue<Node> Open = new PriorityQueue<Node>();

//Close表用来存放已经到达的结点 public ArrayList<Node> Close = new ArrayList<Node>();

//Exist表用来存放两张表出现过的结点 public ArrayList<Node> Exist = new ArrayList<Node>();

判断一个结点是否出现过（is_exist方法）

public boolean is_exist(Node node)

{ for (Node exist_node : Exist) {

//如果这个结点在Exist中出现过，返回true if (node.x == existnode.x && node.y == existnode.y) {

return true;

} }

//没有出现返回false return false;

}

怎么判断一个结点是否合法（is_valid方法）

if (map[x][y] == -1) return false;

for (Node node : Exist) { //如果结点出现过，不合法

if (is_exist(new Node(x, y))) { return false;

} }

//以上情况都没有则合法 return true;

}

怎么扩展【当前结点】的【上】【下】【左】【右】四个方向的结点(extendcurrentnode方法)

public ArrayList<Node> extendcurrentnode(Node current_node) { //获取当前结点的x, y

int x = current_node.x;

int y = current_node.y;

//如果当前结点的邻结点合法，就加入到neighbour_node ArrayList<Node> neighbour_node = new ArrayList<Node>();

if (is_valid(x + 1, y)) { Node node = new Node(x + 1, y);

neighbour_node.add(node);

} if (is_valid(x - 1, y)) {

Node node = new Node(x -1, y);

neighbour_node.add(node);

} if (is_valid(x, y + 1)) {

Node node = new Node(x, y + 1);

neighbour_node.add(node);

} if (is_valid(x, y - 1)) {

Node node = new Node(x, y - 1);

neighbour_node.add(node);

} //返回合法的邻结点们

return neighbour_node;

}

Astar寻路算法具体实现(astarSearch方法)

public Node astarSearch(Node start, Node end) { //把第一个开始的结点加入到Open表中

this.Open.add(start);