这是很久前另一个BLOG上的，现在不用了。转过来吧，方便查看...

?

找工作未果，?闲来无事，先学学一些感兴趣的算法和弄些小东西~~

?

参考文章：

http://blog.vckbase.com/panic/archive/2005/03/20/3778.html

写得真的非常棒，翻译得也很好，整个实现就是跟着他来的。

?

直接上代码，效率问题没有仔细研究过，我是每次寻路完毕都进行一次资源释放，进一步的优化可以继续参考以上连接作者BLOG的其他关于A*的文章。

?

/***
?* A*寻路
?* @author univasity
?* 2008-10-01 0:19
?* QQ:595920004
?*/
public class PF_A_Start {
?
?/**构造函数*/
?public PF_A_Start(byte[][] map, byte[] blocks) {
??this.map = map;
??this.blocks = blocks;
?}

?/**
? * 根据指定的起始位置和目标寻路
? * @param sx 起始点X坐标
? * @param sy 起始点Y坐标
? * @param tx 目标点X坐标
? * @param ty 目标点Y坐标
? * @return 可行的路径，如果没有则返回空
? */
?public int[][] findPath(int sx, int sy, int tx, int ty){
??
??init();
??
??setFatherNode(sx, sy, sx, sy); // 起始点的父节点设置为自身
??value_G[sy][sx] = 0;
??value_H[sy][sx] = CalculationValueH(sx, sy, tx, ty);
??addToOpenList(sx, sy); // 把起始点加入开放列表
??
??while(num_open>0 && !(sucess = isInCloseList(tx, ty))){
???
???// 获取具有最小F值的节点，作为下一个移动目标
???int node1 = openList[0];
???int nx = node1%10;
???int ny = node1/10;
???for(int i=1; i<num_open-1; i++){
????int node2 = openList[i+1];
????int x2 = node2%10;
????int y2 = node2/10;
????if(ValueF(x2, y2)<ValueF(nx, ny)){
?????nx = x2;
?????ny = y2;
????}
???}
???
???// 把四周可到的节点加入开放列表，以待检测
???for(int i=0; i<8; i++){
????if(isBlock(nx+px[i], ny+py[i])) // 如果是障碍，跳过
?????continue;
????if(isInCloseList(nx+px[i], ny+py[i])) // 如果已存在关闭列表中，跳过
?????continue;
????if(isInOpenList(nx+px[i], ny+py[i])){ // 如果已存在开放列表中
?????int fatherNode = FatherNode(nx+px[i], ny+py[i]);
?????// 判断以当前节点为父节点，G值是否比原来小
?????setFatherNode(nx+px[i], ny+py[i], nx, ny);
?????if(CalculationValueG(nx+px[i], ny+py[i])<value_G[ny+py[i]][nx+px[i]]){ // 如果只是
??????value_G[ny+py[i]][nx+px[i]] = CalculationValueG(nx+px[i], ny+py[i]); // 更新G值，令父节点为当前节点
?????}else{ // 否则
??????setFatherNode(nx+px[i], ny+py[i], fatherNode%10, fatherNode/10); // 恢复父节点为初始值
?????}
????}else{ // 未被添加到开放列表
?????// 设置父节点为当前节点，计算G值和H值，并添加到开放列表中
?????setFatherNode(nx+px[i], ny+py[i], nx, ny);
?????value_G[ny+py[i]][nx+px[i]] = CalculationValueG(nx+px[i], ny+py[i]);
?????value_H[ny+py[i]][nx+px[i]] = CalculationValueH(nx+px[i], ny+py[i], tx, ty);
?????addToOpenList(nx+px[i], ny+py[i]);
????}
???}
???// 从开放列表删除该节点
???deleteFromOpenList(nx, ny);
???// 添加到关闭列表
???addToCloseList(nx, ny);
??} // 搜索结束
??
??// 读取路径
??int[][] path = null;
??if(sucess){
???int[][] temp = new int[num_open][2];
???int index = num_open-1;
???int nx = tx;
???int ny = ty;
???while(nx!=sx || ny!=sy){
????int node = FatherNode(nx, ny);
????nx = node%10;
????ny = node/10;
????temp[index][0] = nx;
????temp[index][1] = ny;
????index--;
???}
???path = new int[num_open-index-1][2];
???System.arraycopy(temp, index+1, path, 0, path.length);
??}
??
??release();
??
??return path;
?}
?
?/**资源初始化*/
?private void init() {
??num_open = num_close = 0;
??openList = new int[map.length*map[0].length]; // 开放列表
??closeList = new int[map.length*map[0].length]; // 关闭列表
??fatherNode = new int[map.length][map[0].length]; // 父节点列表
??value_G = new int[map.length][map[0].length]; // G值表
??value_H = new int[map.length][map[0].length]; // H值表
?}
?
?/**释放资源*/
?private void release() {
??openList = null;
??closeList = null;
??for(int i=0; i<fatherNode.length; i++){
???fatherNode[i] = null;
??}
??fatherNode = null;
??for(int i=0; i<value_G.length; i++){
???value_G[i] = null;
??}
??value_G = null;
??for(int i=0; i<value_H.length; i++){
???value_H[i] = null;
??}
??value_H = null;
??System.gc();
?}

?/**添加到开放列表*/
?private int addToOpenList(int x, int y){
??return (openList[num_open++] = y*10+x);
?}
?
?/**添加到关闭列表*/
?private int addToCloseList(int x, int y){
??return (closeList[num_close++] = y*10+x);
?}
?
?/**从开放列表中删除*/
?private void deleteFromOpenList(int x, int y){
??if(num_open<=0)
???return;
??int i;
??for(i=0; i<num_open; i++){
???if(openList[i]==y*10+x){
????openList[i] = 0;
????break;
???}
??}
??for(; i<num_open-1; i++){
???openList[i] = openList[i+1];
??}
??num_open--;
?}
?
?/**获取F值*/
?private int ValueF(int x, int y){
??return value_G[y][x]+value_H[y][x];
?}
?
?/**获取父节点*/
?private int FatherNode(int x, int y){
??return fatherNode[y][x];
?}
?
?private void setFatherNode(int x, int y, int fx, int fy){
??fatherNode[y][x] = fy*10+fx;
?}
?
?/**是否已存在于开放列表*/
?private boolean isInOpenList(int x, int y){
??for(int i=0; i<num_open; i++){
???if(openList[i]==y*10+x)
????return true;
??}
??return false;
?}
?
?/**是否已存在于关闭列表*/
?private boolean isInCloseList(int x, int y){
??for(int i=0; i<num_close; i++){
???if(closeList[i]==y*10+x)
????return true;
??}
??return false;
?}
?
?/**计算G值*/
?private int CalculationValueG(int x, int y){
??int node = FatherNode(x, y);
??int fx = node%10;
??int fy = node/10;
??for(int i=0; i<4; i++){
???if(fx+px[4+i]==x && fy+py[4+i]==y)
????return value_G[fy][fx] + 14;
??}
??return value_G[fy][fx] + 10;
?}
?
?/**计算H值*/
?private int CalculationValueH(int x, int y, int tx, int ty){
??return (Math.abs(y-ty)+Math.abs(x-tx))*10;
?}
?
?/**判断是否是障碍*/
?private boolean isBlock(int x, int y){
??if(x<0 || x>=map[0].length || y<0 || y>=map.length)
???return true;
??if(blocks==null)
???return false;
??for(int i=0; i<blocks.length; i++){
???if(map[y][x]==blocks[i])
????return true;
??}
??return false;
?}
?
?// 四周8个方位的位置偏移量
?private static final byte[] px = {-1,1,0,0,-1,-1,1,1};
?private static final byte[] py = {0,0,-1,1,-1,1,-1,1};
?
?private byte[][] map; // 地图数据
?private byte[] blocks; // 障碍ID
?
?private int[] openList;// 开放列表
?private int[] closeList; // 关闭列表
?private int num_open, num_close; // 数量标记
?
?private int[][] fatherNode; // 父节点列表
?private int[][] value_G; // G值表
?private int[][] value_H; // H值表
?
?private boolean sucess;
}