import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
/**
* A星算法
* @author Micheal Hong
* @email babala_234@163.com
* @version 2010-9-26 下午03:14:42
*
*/
public class AStar {
private List<Node> open;
private List<Node> close;
private Node start;//起点
private Node end;//终点
private boolean[][] grid;//地图数据
private int gridWidth,gridHeight;//地图宽高
public AStar(){
open=new LinkedList<Node>();
close=new LinkedList<Node>();
}
/**
* 初始化
* @param grid
*/
public void init(boolean[][] grid){
this.grid=grid;
this.gridWidth=grid[0].length;
this.gridHeight=grid.length;
}
/**
* 寻找路径,如果找到则返回路径,否则返回null
* @param startX
* @param startY
* @param endX
* @param endY
* @return
*/
public int[][] search(int startX,int startY,int endX,int endY){
open.clear();
close.clear();
start=new Node(startX,startY,null);
end=new Node(endX,endY,null);
open.add(start);
evaluate(start);
Node node=null;
Node[] neighbour=new Node[8];//从上顺时针走向以0到8元素表示
while(open.isEmpty()==false)
{
/* 在开启表中寻找f值最小的结点*/
node=open.remove(0);
/*将node添加到close表中*/
close.add(node);
/*
* 获取node的相邻节点并做如下处理:
* ①如果它不可通过或者已经在关闭列表中,略过它。反之如下。
* ②如果它不在开启列表中,把它添加进去。把当前格作为这一格的父节点。记录这一格的F,G,和H值。
* ③如果它已经在开启列表中,用G值为参考检查新的路径是否更好。更低的G值意味着更好的路径。如果是这样,就把这一格的父节点改成当前格,并且重新计算这一格的G和F值。如果你保持你的开启列表按F值排序,改变之后你可能需要重新对开启列表排序。
*/
getNeighbour(node, neighbour);
int index;
for(int i=0;i<neighbour.length;i++)
{
if(neighbour[i]==null)
continue;
if((index=contain(open, neighbour[i].x, neighbour[i].y))!=-1)
{
if(open.get(index).gn>neighbour[i].gn)
open.set(index,neighbour[i]);
}
else
open.add(neighbour[i]);
}
/*判断是否到达目标*/
if((index=contain(open, end.x,end.y))!=-1)
{
int count=1;
Node d=open.get(index);
while(d.father!=null)
{
d=d.father;
count++;
}
d=open.get(index);
int[][] path=new int[count][];
for(int i=count-1;i>=0;i--)
{
path[i]=new int[2];
path[i][0]=d.x;
path[i][1]=d.y;
d=d.father;
}
return path;
}
/*对open表进行排序(按fn由小到大)*/
Collections.sort(open);
}
return null;
}
private void getNeighbour(Node node,Node[] neighbour)
{
int x=node.x;
int y=node.y;
for(int i=0;i<neighbour.length;i++)
neighbour[i]=null;
neighbour[0]=getNode(x, y-1,node);
neighbour[1]=getNode(x+1,y-1,node);
neighbour[2]=getNode(x+1,y,node);
neighbour[3]=getNode(x+1,y+1,node);
neighbour[4]=getNode(x, y+1,node);
neighbour[5]=getNode(x-1,y+1,node);
neighbour[6]=getNode(x-1,y,node);
neighbour[7]=getNode(x-1,y-1,node);
}
/*
* 对相邻的8格中的每一个,如果它不可通过或者已经在关闭列表中,略过它。
* 并计算它的评估值
*/
private Node getNode(int x,int y,Node father)
{
if(x>=0&&x<gridWidth&&y>=0&&y<gridHeight&&isPassable(x, y)&&contain(close,x,y)==-1)
{
Node node=new Node(x,y,father);
evaluate(node);
return node;
}
return null;
}
/*
* 如果包含则返回索引,否则返回-1
*/
private int contain(List<Node> nodes,int x,int y)
{
Node node=null;
for(int i=0;i<nodes.size();i++)
{
node=nodes.get(i);
if(node.x==x&&node.y==y)
return i;
}
return -1;
}
/*
* 是否可通行
*/
private boolean isPassable(int x,int y)
{
return grid[y][x];
}
/*
* 路径评分
*/
private void evaluate(Node node){
if(node.father!=null)
{
node.gn=node.father.gn+heuristic(node.father,node);
node.fn=node.gn+heuristic(node, end);
}
else
{
node.gn=0;
node.fn=heuristic(node, end);
}
}
/*
* 启发式评估函数,使用曼哈顿距离
*/
private int heuristic(Node n1,Node n2)
{
return Math.abs(n1.x-n2.x)+Math.abs(n1.y-n2.y);
}
/*
* 选择路径中经过哪个方格的关键是下面这个等式:
* F = G + H
* 这里:
* G = 从起点A,沿着产生的路径,移动到网格上指定方格的移动耗费。
* H = 从网格上那个方格移动到终点B的预估移动耗费。
*/
class Node implements Comparable<Node>{
int x,y;
int fn;
int gn;
Node father;
public Node(int x,int y,Node father){
this.x=x;
this.y=y;
this.father=father;
}
public int compareTo(Node node) {
return fn-node.fn;
}
}
public static void main(String[] args){
Calculagraph.getInstance("AStar").mark(null);
boolean[][] grid={
{true,true,true,false,true,true,true,true,true,true,true},
{true,true,false,true,true,false,true,false,true,true,true},
{true,true,false,false,false,false,false,false,true,true,true},
{true,false,false,true,false,false,true,true,true,true,true},
{true,true,true,false,true,false,true,false,true,false,true},
{true,true,true,false,true,true,false,true,true,false,true},
{true,true,true,true,false,false,false,true,true,true,true},
{true,true,true,false,true,false,true,false,true,false,true},
{true,true,true,false,true,true,false,false,true,false,true},
{true,true,true,false,true,true,false,true,false,false,false},
{true,true,true,false,true,true,false,true,true,true,true}
};
AStar a=new AStar();
a.init(grid);
int[][] path=a.search(0, 0, 10, 10);
Calculagraph.getInstance("AStar").mark("finish");
if(path!=null)
{
for(int i=0;i<path.length;i++)
{
if(i>0)
System.out.print("-->");
System.out.print(path[i][0]+","+path[i][1]);
}
}
System.out.println();
Calculagraph.getInstance("AStar").mark("print");
System.out.println(Calculagraph.remove("AStar").getInfo());
}
}
分享到:
相关推荐
A星算法 用c语言实现 用到了队列 a*算法 A星算法 用c语言实现 用到了队列 a*算法
通过指定的栅格地图,运用A星算法得出最短路径
使用python实现2D的A星算法, 效果程序使用终端打印形式 使用python实现2D的A星算法, 效果程序使用终端打印形式
A星算法的核心,地形网格的构建以及评估函数的算法,其它都是可以复用的。其实代码是次要的东西,要理解A星算法,建议先去看数学证明,否则看代码一点意义没有,因为看懂了证明,代码会变得非常简单。证明里有个核心...
A星算法
a星算法,写的是一个球图上最短路径的问题,没写界面 八数码,写了界面,可以自己输入八数码,也可以随机
2.内容:基于Qlearning算法最优路径规划算法matlab仿真,同时使用A星算法进行对比+代码操作视频 3.用处:用于Qlearning算法,A星算法编程学习 4.指向人群:本硕博等教研学习使用 5.运行注意事项: 使用matlab...
分享一下A星算法及A星优化算法源码,提供大家学习使用!
易语言源码易语言A星算法源码.rar
A星算法简单的实现,分别使用C#、Python、JavaScript三种语言实现,通过界面10x10方格展示算法过程 思路参考于:https://blog.csdn.net/zhanghow/article/details/53585286
虽然A*(读作A星)算法对初学者来说是比较深奥难懂,但是一旦你找到门路了,它又会变得非常简单。网上有很多解释A*算法的文章,但是大多数是写给那些有一定基础的人看的,而您看到的这一篇呢,是真正写给菜鸟的。
动态衡量式A星算法及拐角优化的matlab文件,内部包含两个matlab文件,A_ROAD_3 为完整的动态衡量式A星算法文件,A_ROAD_4是进行拐角优化后的文件,详情请见博文----详细介绍用MATLAB实现基于A*算法的路径规划(附...
本源代码借助标准C++ STL中的vector,list和heap等已封装的数据结构,优化了A星算法搜索地图、检索开始列表过程,减小了程序的时间和空间花费。经检验,检索20000*20000的随机障碍物地图时,程序在规划路径部分的平均...
matlab实现的八方向A星算法,可以选择地图大小,起点位置、终点位置以及地图中的障碍物比例,分享一起学习。
A星算法自寻路A星算法自寻路
MFC窗口程序A星算法演示,详细的注释,帮助您彻底理解A星算法原理。
对10*10的二维高程矩阵进行插值,得到较平滑的三维山地图,使用A星算法得到起点到终点的最优路径,使用B样条插值法对路径进行平滑处理。
matlab实现的A星算法,有个性界面,直接运行就可以 matlab实现的A星算法,有个性界面,直接运行就可以
用A星算法求解旅行商问题,使用C++语言描述,配有完美注释,以及测试样例
E语言 A星算法