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星寻路"文件可能包含实现A星算法的具体代码示例,通过读取栅格地图数据,计算各个节点之间的路径成本,使用A星算法找到从起点到终点的最短路径。理解并掌握这些知识点,将有助于你在实际项目中实现...
### A星算法简介 A*(A星)算法是一种广泛应用于路径寻找和图遍历的算法,能够在图中寻找从起始节点到目标节点的最短路径。虽然A*算法对于初学者而言较为复杂,但一旦掌握其核心原理,就会发现其实质上是非常直观且...
本压缩包“易语言源码易语言A星算法源码.rar”提供了易语言实现的A星(A*)寻路算法的源代码,这对于想要了解或学习A*算法以及易语言编程的人来说是一份宝贵的资源。 A星算法是路径搜索领域中的一种非常高效的算法,...
A星算法(A* Search Algorithm)是路径搜索领域中一种经典的启发式搜索算法,因其高效性和准确性而被广泛应用。这个名为"A星算法大全"的资源显然提供了深入学习和理解A星算法的全面教程,对于想在游戏中实现智能路径...
下面将详细介绍A星算法的基本原理、实现步骤以及在JAVA中的应用。 1. A星算法的基本原理: A*算法的核心在于评估每个节点的F值,F值是G值(从起点到当前节点的实际代价)和H值(从当前节点到目标节点的预估代价)...
1. **A星算法**:A星算法的核心在于维护一个优先级队列,其中包含当前可能的最短路径节点。每个节点有一个评估函数值`f(n) = g(n) + h(n)`,`g(n)`表示从起点到当前节点的实际代价,`h(n)`是启发式估计从当前节点到...
其次,A星算法(A*)是一种高效的路径搜索算法,用于找到起点到终点之间的最短路径。它结合了Dijkstra算法的全局最优性和宽度优先搜索的效率。A*算法的核心在于使用启发式函数来评估剩余成本估计,通常是到目标的...
A星算法的核心思想是找到从起点到目标点的最小代价路径。它使用一个开放列表和一个关闭列表来存储节点。开放列表包含待检查的节点,而关闭列表则存储已检查过的节点。算法的主要步骤如下: 1. 初始化:将起点放入...
"Astar div3_A星算法在三维栅格地图中的寻路" 这个标题明确指出了我们讨论的核心技术——A星算法(A* Algorithm),并且它被应用在一个特殊的场景,即三维栅格地图(3D Grid Map)中的路径规划。"div3"可能是指这个...
在这个MATLAB实现的项目中,我们将会深入探讨A星算法的原理、MATLAB编程技巧以及八方向的路径规划。 首先,A星算法的核心在于它的评估函数F(n),它由两部分组成:G(n) 和 H(n)。G(n) 是从起点到当前节点的实际代价...
A星算法结合了最佳优先搜索(BFS)和Dijkstra算法的优点,通过引入启发式函数来提高搜索效率。 A星算法的核心包括以下几个关键部分: 1. **开放列表(Open List)**:这是一个优先级队列,存储待检查的节点,根据F...
在优化A星算法时,我们通常关注以下几个关键点: 1. **启发式函数(Heuristic Function)**:启发式函数是A星算法的核心,用于估算从当前节点到目标节点的剩余代价。理想的启发式函数应该是admissible和consistent...
A星算法的核心在于结合了Dijkstra算法的全局最优性和最佳优先搜索的效率。它使用一个优先队列来存储待评估的节点,根据每个节点的评估函数值F进行排序。F值由两部分组成:G值(从起点到当前节点的实际成本)和H值...
在这个"A星算法演示"项目中,我们可以通过MFC(Microsoft Foundation Classes)窗口程序来直观地理解并学习A星算法。MFC是微软提供的一种C++库,用于构建Windows应用程序,它简化了窗口、菜单、控件等元素的创建和...
使用python实现2D的A星算法, 效果程序使用终端打印形式 使用python实现2D的A星算法, 效果程序使用终端打印形式
标题中的"A星算法地图编辑器"是一个专门用于地图设计与编辑的工具,它结合了A星(A*)寻路算法,使得用户能够方便地创建、编辑和优化适用于游戏或其他应用的地图。A星算法是一种在图形搜索中常用的路径查找算法,以...
A星算法的核心,地形网格的构建以及评估函数的算法,其它都是可以复用的。其实代码是次要的东西,要理解A星算法,建议先去看数学证明,否则看代码一点意义没有,因为看懂了证明,代码会变得非常简单。证明里有个核心...
2.内容:基于Qlearning算法最优路径规划算法matlab仿真,同时使用A星算法进行对比+代码操作视频 3.用处:用于Qlearning算法,A星算法编程学习 4.指向人群:本硕博等教研学习使用 5.运行注意事项: 使用matlab...
A星算法的核心在于它结合了启发式信息和实际代价,以找到从起点到目标点的最短路径。在这个"A星算法演示_原码加EXE"的压缩包中,包含的源码和可执行文件(EXE)为初学者提供了一个直观的学习和实践平台。 首先,...