Java編程實(shí)現(xiàn)A*算法完整代碼
前言
A*搜尋算法俗稱A星算法。這是一種在圖形平面上，有多個(gè)節(jié)點(diǎn)的路徑，求出最低通過成本的算法。常用于游戲中
通過二維數(shù)組構(gòu)建的一個(gè)迷宮，“%”表示墻壁，A為起點(diǎn)，B為終點(diǎn)，“#”代表障礙物，“*”代表算法計(jì)算后的路徑
本文實(shí)例代碼結(jié)構(gòu)：
% % % % % % % % o o o o o % % o o # o o % % A o # o B % % o o # o o % % o o o o o % % % % % % % % ============================= 經(jīng)過A*算法計(jì)算后 ============================= % % % % % % % % o o * o o % % o * # * o % % A o # o B % % o o # o o % % o o o o o % % % % % % % % <
算法理論
算法的核心公式為：F=G+H
把地圖上的節(jié)點(diǎn)看成一個(gè)網(wǎng)格。
G=從起點(diǎn)A,沿著產(chǎn)生的路徑，移動(dòng)到網(wǎng)格上指定節(jié)點(diǎn)的移動(dòng)消耗，在這個(gè)例子里，我們令水平或者垂直移動(dòng)的耗費(fèi)為10，對(duì)角線方向耗費(fèi)為14。我們?nèi)∵@些值是因?yàn)檠貙?duì)角線
的距離是沿水平或垂直移動(dòng)耗費(fèi)的的根號(hào)2，或者約1.414倍。為了簡(jiǎn)化，我們用10和14近似。
既然我們?cè)谟?jì)算沿特定路徑通往某個(gè)方格的G值，求值的方法就是取它父節(jié)點(diǎn)的G值，然后依照它相對(duì)父節(jié)點(diǎn)是對(duì)角線方向或者直角方向(非對(duì)角線)，分別增加14和10。例子中這
個(gè)方法的需求會(huì)變得更多，因?yàn)槲覀儚钠瘘c(diǎn)方格以外獲取了不止一個(gè)方格。
H=從當(dāng)前格移動(dòng)到終點(diǎn)B的預(yù)估移動(dòng)消耗。為什么叫”預(yù)估“呢，因?yàn)槲覀儧]有辦法事先知道路徑的長(zhǎng)度，這里我們使用曼哈頓方法，它計(jì)算從當(dāng)前格到目的格之間水平和垂直
的方格的數(shù)量總和，忽略對(duì)角線方向。然后把結(jié)果乘以10。
F的值是G和H的和，這是我們用來判斷優(yōu)先路徑的標(biāo)準(zhǔn)，F(xiàn)值最小的格，我們認(rèn)為是優(yōu)先的路徑節(jié)點(diǎn)。
實(shí)現(xiàn)步驟
算法使用java寫的，先看一看節(jié)點(diǎn)類的內(nèi)容
package a_star_search;
/**
* 節(jié)點(diǎn)類
* @author zx
*
*/
public class Node {
private int x; //x坐標(biāo)
private int y; //y坐標(biāo)
private String value; //表示節(jié)點(diǎn)的值
private double FValue = 0; //F值
private double GValue = 0; //G值
private double HValue = 0; //H值
private boolean Reachable; //是否可到達(dá)（是否為障礙物）
private Node PNode; //父節(jié)點(diǎn)
public Node(int x, int y, String value, boolean reachable) {
super();
this.x = x;
this.y = y;
this.value = value;
Reachable = reachable;
}
public Node() {
super();
}
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
public String getValue() {
return value;
}
public void setValue(String value) {
this.value = value;
}
public double getFValue() {
return FValue;
}
public void setFValue(double fValue) {
FValue = fValue;
}
public double getGValue() {
return GValue;
}
public void setGValue(double gValue) {
GValue = gValue;
}
public double getHValue() {
return HValue;
}
public void setHValue(double hValue) {
HValue = hValue;
}
public boolean isReachable() {
return Reachable;
}
public void setReachable(boolean reachable) {
Reachable = reachable;
}
public Node getPNode() {
return PNode;
}
public void setPNode(Node pNode) {
PNode = pNode;
}
}
還需要一個(gè)地圖類，在map的構(gòu)造方法中，我通過創(chuàng)建節(jié)點(diǎn)的二維數(shù)組來實(shí)現(xiàn)一個(gè)迷宮地圖，其中包括起點(diǎn)和終點(diǎn)
package a_star_search;
public class Map {
private Node[][] map;
//節(jié)點(diǎn)數(shù)組
private Node startNode;
//起點(diǎn)
private Node endNode;
//終點(diǎn)
public Map() {
map = new Node[7][7];
for (int i = 0;i<7;i++){
for (int j = 0;j<7;j++){
map[i][j] = new Node(i,j,"o",true);
}
}
for (int d = 0;d<7;d++){
map[0][d].setValue("%");
map[0][d].setReachable(false);
map[d][0].setValue("%");
map[d][0].setReachable(false);
map[6][d].setValue("%");
map[6][d].setReachable(false);
map[d][6].setValue("%");
map[d][6].setReachable(false);
}
map[3][1].setValue("A");
startNode = map[3][1];
map[3][5].setValue("B");
endNode = map[3][5];
for (int k = 1;k<=3;k++){
map[k+1][3].setValue("#");
map[k+1][3].setReachable(false);
}
}
<span style="white-space:pre"> </span>//展示地圖
public void ShowMap(){
for (int i = 0;i<7;i++){
for (int j = 0;j<7;j++){
System.out.print(map[i][j].getValue()+" ");
}
System.out.println("");
}
}
public Node[][] getMap() {
return map;
}
public void setMap(Node[][] map) {
this.map = map;
}
public Node getStartNode() {
return startNode;
}
public void setStartNode(Node startNode) {
this.startNode = startNode;
}
public Node getEndNode() {
return endNode;
}
public void setEndNode(Node endNode) {
this.endNode = endNode;
}
}
下面是最重要的AStar類
操作過程
1從起點(diǎn)A開始，并且把它作為待處理點(diǎn)存入一個(gè)“開啟列表”，這是一個(gè)待檢查方格的列表。
2尋找起點(diǎn)周圍所有可到達(dá)或者可通過的方格，跳過無法通過的方格。也把他們加入開啟列表。為所有這些方格保存點(diǎn)A作為“父方格”。當(dāng)我們想描述路徑的時(shí)候，父方格的資
料是十分重要的。后面會(huì)解釋它的具體用途。
3從開啟列表中刪除起點(diǎn)A，把它加入到一個(gè)“關(guān)閉列表”，列表中保存所有不需要再次檢查的方格。
經(jīng)過以上步驟，“開啟列表”中包含了起點(diǎn)A周圍除了障礙物的所有節(jié)點(diǎn)。他們的父節(jié)點(diǎn)都是A,通過前面講的F=G+H的公式，計(jì)算每個(gè)節(jié)點(diǎn)的G，H，F(xiàn)值，并按照F的值大小，從小
到大進(jìn)行排序。并對(duì)F值最小的那個(gè)節(jié)點(diǎn)做以下操作
4，把它從開啟列表中刪除，然后添加到關(guān)閉列表中。
5，檢查所有相鄰格子。跳過那些不可通過的(1.在”關(guān)閉列表“中，2.障礙物)，把他們添加進(jìn)開啟列表，如果他們還不在里面的話。把選中的方格作為新的方格的父節(jié)點(diǎn)。
6，如果某個(gè)相鄰格已經(jīng)在開啟列表里了，檢查現(xiàn)在的這條路徑是否更好。換句話說，檢查如果我們用新的路徑到達(dá)它的話，G值是否會(huì)更低一些。如果不是，那就什么都不
做。（這里，我的代碼中并沒有判斷）
7，我們重復(fù)這個(gè)過程，直到目標(biāo)格（終點(diǎn)“B”）被添加進(jìn)“開啟列表”，說明終點(diǎn)B已經(jīng)在上一個(gè)添加進(jìn)“關(guān)閉列表”的節(jié)點(diǎn)的周圍，只需走一步，即可到達(dá)終點(diǎn)B。
8，我們將終點(diǎn)B添加到“關(guān)閉列表”
9，最后一步，我們要將從起點(diǎn)A到終點(diǎn)B的路徑表示出來。父節(jié)點(diǎn)的作用就顯示出來了，通過“關(guān)閉列表”中的終點(diǎn)節(jié)點(diǎn)的父節(jié)點(diǎn)，改變其value值，順藤摸瓜即可以顯示出路徑。
看看代碼
package a_star_search;
import java.util.ArrayList;
public class AStar {
/**
* 使用ArrayList數(shù)組作為“開啟列表”和“關(guān)閉列表”
*/
ArrayList<Node> open = new ArrayList<Node>();
ArrayList<Node> close = new ArrayList<Node>();
/**
* 獲取H值
* @param currentNode：當(dāng)前節(jié)點(diǎn)
* @param endNode：終點(diǎn)
* @return
*/
public double getHValue(Node currentNode,Node endNode){
return (Math.abs(currentNode.getX() - endNode.getX()) + Math.abs(currentNode.getY() - endNode.getY()))*10;
}
/**
* 獲取G值
* @param currentNode：當(dāng)前節(jié)點(diǎn)
* @return
*/
public double getGValue(Node currentNode){
if(currentNode.getPNode()!=null){
if(currentNode.getX()==currentNode.getPNode().getX()||currentNode.getY()==currentNode.getPNode().getY()){
//判斷當(dāng)前節(jié)點(diǎn)與其父節(jié)點(diǎn)之間的位置關(guān)系（水平？對(duì)角線）
return currentNode.getGValue()+10;
}
return currentNode.getGValue()+14;
}
return currentNode.getGValue();
}
/**
* 獲取F值 ： G + H
* @param currentNode
* @return
*/
public double getFValue(Node currentNode){
return currentNode.getGValue()+currentNode.getHValue();
}
/**
* 將選中節(jié)點(diǎn)周圍的節(jié)點(diǎn)添加進(jìn)“開啟列表”
* @param node
* @param map
*/
public void inOpen(Node node,Map map){
int x = node.getX();
int y = node.getY();
for (int i = 0;i<3;i++){
for (int j = 0;j<3;j++){
//判斷條件為：節(jié)點(diǎn)為可到達(dá)的（即不是障礙物，不在關(guān)閉列表中），開啟列表中不包含，不是選中節(jié)點(diǎn)
if(map.getMap()[x-1+i][y-1+j].isReachable()&&!open.contains(map.getMap()[x-1+i][y-1+j])&&!(x==(x-1+i)&&y==(y-1+j))){
map.getMap()[x-1+i][y-1+j].setPNode(map.getMap()[x][y]);
//將選中節(jié)點(diǎn)作為父節(jié)點(diǎn)
map.getMap()[x-1+i][y-1+j].setGValue(getGValue(map.getMap()[x-1+i][y-1+j]));
map.getMap()[x-1+i][y-1+j].setHValue(getHValue(map.getMap()[x-1+i][y-1+j],map.getEndNode()));
map.getMap()[x-1+i][y-1+j].setFValue(getFValue(map.getMap()[x-1+i][y-1+j]));
open.add(map.getMap()[x-1+i][y-1+j]);
}
}
}
}
/**
* 使用冒泡排序?qū)㈤_啟列表中的節(jié)點(diǎn)按F值從小到大排序
* @param arr
*/
public void sort(ArrayList<Node> arr){
for (int i = 0;i<arr.size()-1;i++){
for (int j = i+1;j<arr.size();j++){
if(arr.get(i).getFValue() > arr.get(j).getFValue()){
Node tmp = new Node();
tmp = arr.get(i);
arr.set(i, arr.get(j));
arr.set(j, tmp);
}
}
}
}
/**
* 將節(jié)點(diǎn)添加進(jìn)”關(guān)閉列表“
* @param node
* @param open
*/
public void inClose(Node node,ArrayList<Node> open){
if(open.contains(node)){
node.setReachable(false);
//設(shè)置為不可達(dá)
open.remove(node);
close.add(node);
}
}
public void search(Map map){
//對(duì)起點(diǎn)即起點(diǎn)周圍的節(jié)點(diǎn)進(jìn)行操作
inOpen(map.getMap()[map.getStartNode().getX()][map.getStartNode().getY()],map);
close.add(map.getMap()[map.getStartNode().getX()][map.getStartNode().getY()]);
map.getMap()[map.getStartNode().getX()][map.getStartNode().getY()].setReachable(false);
map.getMap()[map.getStartNode().getX()][map.getStartNode().getY()].setPNode(map.getMap()[map.getStartNode().getX()][map.getStartNode().getY()]);
sort(open);
//重復(fù)步驟
do{
inOpen(open.get(0), map);
inClose(open.get(0), open);
sort(open);
}
while(!open.contains(map.getMap()[map.getEndNode().getX()][map.getEndNode().getY()]));
//知道開啟列表中包含終點(diǎn)時(shí)，循環(huán)退出
inClose(map.getMap()[map.getEndNode().getX()][map.getEndNode().getY()], open);
showPath(close,map);
}
/**
* 將路徑標(biāo)記出來
* @param arr
* @param map
*/
public void showPath(ArrayList<Node> arr,Map map) {
if(arr.size()>0){
Node node = new Node();
//<span style="white-space:pre"> </span>node = map.getMap()[map.getEndNode().getX()][map.getEndNode().getY()];
//<span style="white-space:pre"> </span>while(!(node.getX() ==map.getStartNode().getX()&&node.getY() ==map.getStartNode().getY())){
//<span style="white-space:pre"> </span>node.getPNode().setValue("*");
//<span style="white-space:pre"> </span>node = node.getPNode();
//<span style="white-space:pre"> </span>}
}
//<span style="white-space:pre"> </span>map.getMap()[map.getStartNode().getX()][map.getStartNode().getY()].setValue("A");
}
}
最后寫一個(gè)Main方法
package a_star_search;
public class MainTest {
public static void main(String[] args) {
Map map = new Map();
AStar aStar = new AStar();
map.ShowMap();
aStar.search(map);
System.out.println("=============================");
System.out.println("經(jīng)過A*算法計(jì)算后");
System.out.println("=============================");
map.ShowMap();
}
}
修改地圖再測(cè)試一下，看看效果
% % % % % % % % o o o o o % % o o # o o % % A o # o B % % o o # o o % % o o o o o % % % % % % % % ============================= 經(jīng)過A*算法計(jì)算后 ============================= % % % % % % % % o o o o o % % o o # o o % % A o # o B % % o o # o o % % o o o o o % % % % % % % %
總結(jié)
保證找到最短路徑（最優(yōu)解的）條件，關(guān)鍵在于估價(jià)函數(shù)h(n)的選?。汗纼r(jià)值h(n)<=n到目標(biāo)節(jié)點(diǎn)的距離實(shí)際值，這種情況下，搜索的點(diǎn)數(shù)多，搜索范圍大，效率低。但能得到
最優(yōu)解。如果估價(jià)值>實(shí)際值,搜索的點(diǎn)數(shù)少，搜索范圍小，效率高，但不能保證得到最優(yōu)解。
最大的感觸就是：做事最忌三天打漁，兩天曬網(wǎng)。量可以不大，但必須有連續(xù)性，貴在堅(jiān)持。
希望每一個(gè)程序員，都能開心的敲著代碼，做自己喜歡做的事。
以上就是本文關(guān)于Java編程實(shí)現(xiàn)A*算法完整代碼的全部?jī)?nèi)容，希望對(duì)大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站其他相關(guān)專題，如有不足之處，歡迎留言指出。
相關(guān)文章
有時(shí)候系統(tǒng)中需要多個(gè)jdk版本共存,我們?cè)谧鎏囟ǖ牟僮鲿r(shí)需要特定的版本,這篇文章主要給大家介紹了關(guān)于Java?JDK的多版本共存實(shí)現(xiàn)?的相關(guān)資料,需要的朋友可以參考下2023-09-09
這篇文章主要給大家介紹了關(guān)于Java利用endorsed如何覆蓋jdk提供的類的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧。2017-09-09
如何使用MyBatis框架實(shí)現(xiàn)增刪改查（CRUD）操作
本文主要介紹了如何使用MyBatis框架實(shí)現(xiàn)增刪改查（CRUD）操作。首先介紹了MyBatis框架的基本概念和使用方法，然后分別介紹了如何使用MyBatis實(shí)現(xiàn)增刪改查操作。最后，通過一個(gè)簡(jiǎn)單的示例演示了如何使用MyBatis框架實(shí)現(xiàn)CRUD操作。2023-05-05
實(shí)例解析Java設(shè)計(jì)模式編程中的適配器模式使用
適配器模式的主要作用是在新接口和老接口之間進(jìn)行適配,通過將一個(gè)類的接口轉(zhuǎn)換成客戶期望的另一個(gè)接口，讓原本不兼容的接口可以合作無間,本文以實(shí)例解析Java設(shè)計(jì)模式編程中的適配器模式使用,需要的朋友可以參考下2016-05-05
這篇文章主要介紹了java迭代器模式，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-05-05
Java數(shù)組集合的深度復(fù)制代碼實(shí)例
這篇文章主要介紹了Java數(shù)組集合的深度復(fù)制代碼實(shí)例,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-11-11
詳解PipedInputStream和PipedOutputStream_動(dòng)力節(jié)點(diǎn)Java學(xué)院整理
這篇文章主要為大家詳細(xì)介紹了管道PipedInputStream和PipedOutputStream，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-05-05
Mac安裝多個(gè)JDK并實(shí)現(xiàn)動(dòng)態(tài)切換
有時(shí)候我們有多個(gè)項(xiàng)目需要使用多個(gè)版本JDK，本文主要介紹了Mac安裝多個(gè)JDK并實(shí)現(xiàn)動(dòng)態(tài)切換，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-07-07
java編程中實(shí)現(xiàn)調(diào)用js方法分析
這篇文章主要介紹了java編程中實(shí)現(xiàn)調(diào)用js方法,結(jié)合具體實(shí)例形式較為詳細(xì)的分析了java編程中調(diào)用js方法的常用操作技巧與注意事項(xiàng),需要的朋友可以參考下2017-09-09
關(guān)于String轉(zhuǎn)Json的幾種方式
這篇文章主要介紹了關(guān)于String轉(zhuǎn)Json的幾種方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-12-12