Go语言视频零基础入门到精通

javalearner

抱着学习的态度，偶先复习了一下以前学数据结构的时候用栈+遍历的方法实现了一个迷宫寻路问题，然后用A*算法来做同样的事~~简单起见，只用了一个比较简单的迷宫~反正思路是一样的嘛~~

A*算法的思想请看蓝色月光的贴子：
http://www.blueidea.com/tech/multimedia/2005/3121_3.asp

A*算法搜索过程中设置两个表：OPEN和CLOSED。

     OPEN表保存了所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。

    算法中有一步是根据估价函数重排OPEN表。这样循环中的每一步只考虑OPEN表中状态最好的节点。

A*算法伪码描述如下：
   
  
   
   
     
   

     
   
  




  Astar_Search()
  
{
  
Open = [起始节点];
  
Closed = [];
  
while (Open表非空)
  
{
  
从Open中取得一个节点X，并从OPEN表中删除。
  
if (X是目标节点)
  
{
  
求得路径PATH；
  
返回路径PATH；
  
}
  
for (每一个X的子节点Y)
  
{
  
if (Y不在OPEN表和CLOSE表中)
  
{
  
求Y的估价值；
  
并将Y插入OPEN表中；
  
}
  
//还没有排序
  
else if (Y在OPEN表中)
  
{
  
if (Y的估价值小于OPEN表的估价值)
  
更新OPEN表中的估价值；
  
}
  
else //Y在CLOSE表中
  
{
  
if (Y的估价值小于CLOSE表的估价值)
  
{
  
更新CLOSE表中的估价值；
  
从CLOSE表中移出节点，并放入OPEN表中；
  
}
  
}
  
将X节点插入CLOSE表中；
  
按照估价值将OPEN表中的节点排序；
  
}//end for
  
}//end while
  
}//end func
  

上面的伪码可以说是一个模板了~呵呵~~偶用java实现的A*算法也大概就是用这个模板做的~~ FLASH AS也差不多吧~~


下面是JAVA源码：




  //一个很简单的迷宫问题算法
  
import java.util.*;
  

  
class Node{
  
     
  
     boolean attainability; //节点是否可达到
  
     int x,y; //节点的位置信息
  
     int direction = 1;
  
     int score;
  
     String id = " ";
  
     //Node leftNode,rightNode,upNode,downNode;   
  
     //Node fatherNode;   
  
}
  

  
public class Puzzle {   
  
     Node[][] maze = null; //迷宫数组
  
     Node startNode,endNode; //起始点，结束点
  
     
  
     public Puzzle(){
  
         //初始化迷宫数组~并指定起始点和结束点
  
         maze = new Node[7][9];
  
         
  
         for(int i=0;i<7;i++)
  
             for(int j=0;j<9;j++){
  
                 maze[j] = new Node();
  
                 
  
                 maze[j].attainability = true;
  
                 maze[j].x = i;
  
                 maze[j].y = j;
  
         }
  
         startNode = maze[3][2];
  
         startNode.id = "&";
  
         endNode = maze[3][6];
  
         endNode.id = "@";
  
         for(int i=0;i<7;i++){
  
             maze[0].attainability = false;
  
             maze[8].attainability = false;
  
         }
  
         for(int j=0;j<9;j++){
  
             maze[0][j].attainability = false;
  
             maze[6][j].attainability = false;
  
         }
  
         maze[4][3].attainability = false;
  
         maze[2][4].attainability = false;
  
         maze[3][4].attainability = false;
  
         maze[4][4].attainability = false;
  
     }
  
     
  
     private void printMaze(){
  
         
  
         for(int i=0;i<7;i++){
  
             for(int j=0;j<9;j++){
  
                 
  
                 if(maze[j].attainability)
  
                     if(maze[j] == startNode)
  
                         System.out.print("& ");
  
                     else if(maze[j] == endNode)
  
                         System.out.print("@ ");
  
                     else System.out.print(maze[j].id + " ");
  
                 
  
                 else
  
                     if(i==0 || i==6 || j==0 ||j==8 || (i==4&&j==3) ||(i==2&&j==4) ||(i==3&&j==4) ||(i==4&&j==4))
  
                         System.out.print("# ");
  
                     else System.out.print(maze[j].id + " ");
  
             }
  
             System.out.println();
  
         }
  
     }
  
     
  
     public void getPath(){
  
         Stack s = new Stack();
  
         Node curpos = startNode;
  
         //int curstep = 1;
  
         do{
  
             if(curpos.attainability){
  
                 curpos.attainability = false;
  
                 if(curpos!=startNode && curpos!=endNode)
  
                     curpos.id = "%";
  
                 s.push(curpos);
  
                 if(curpos == endNode) printMaze();
  
                 Node tmp = nextPos(curpos,1);
  
                 curpos = maze[tmp.x][tmp.y];
  
             //    curpos.id++;
  
             //    curstep++;
  
             }
  
             else{
  
                 Node e = (Node)s.pop();
  
                 while(e.direction == 4 && !s.empty()){
  
                     e.attainability = false;
  
                     e = (Node)s.pop();
  
                 }
  
                 if(e.direction < 4){
  
                     e.direction++;
  
                     s.push(e);
  
                     Node tmp = nextPos(e,e.direction);                    
  
                     curpos = maze[tmp.x][tmp.y];
  
                 }
  
             }
  
         }while(!s.empty());
  
     }
  
     
  
     private Node nextPos(Node pos, int i){
  
         //按东南西北的顺序
  
         Node tmp = new Node();
  
         tmp.direction = pos.direction;
  
         tmp.attainability = pos.attainability;
  
         int x = pos.x;
  
         int y = pos.y;
  
         if(i == 2 && x<maze.length-1){     //南
  
             x = x+1;                        
  
             tmp.y = pos.y;
  
             tmp.x = x;            
  
         }
  
         else if(i == 4 && x != 0){     //北
  
             x = x-1;
  
             tmp.y = pos.y;
  
             tmp.x = x;
  
         }
  
         else if(i == 1 && y<maze[0].length-1){    //东
  
             y = y+1;
  
             tmp.x = pos.x;
  
             tmp.y = y;
  
         }
  
         else if(i == 3 && y != 0){    //西
  
             y = y - 1;
  
             tmp.x = pos.x;
  
             tmp.y = y;
  
         }
  
         return tmp;
  
     }
  
     
  
     public void Astar(){
  
         getScore();
  
         
  
         Stack open = new Stack(); //初始开启列表
  
         open.push(startNode);
  
         
  
         Stack close = new Stack(); //初始关闭列表
  
         while(open.size()!=0){
  
             Node x = (Node)open.pop();
  
             if(x == endNode)
  
                 break;
  
             Node[] t = null;
  
             if(x.attainability){
  
                 t = getNear(x);
  
            
  
                 for(int i=0;i<t.length;i++){
  
                     if(t != null){
  
                         if(open.search(t) == -1 && close.search(t) == -1)
  
                             open.push(t);
  
                         else if(open.search(t) != -1){
  
                             sort(open);
  
                         }
  
                         else{
  
                             if(t.score < ((Node)close.peek()).score){
  
                                 sort(close);
  
                                 open.push(close.pop());
  
                             }
  
                         }                    
  
                     }
  
                 }
  
                 close.push(x);
  
                 sort(open);
  
             }
  
         }
  
         int a = close.size();
  
         for(int i=0;i<a;i++){
  
             Node tmp = (Node)close.pop();
  
             tmp.id = "%";
  
             maze[tmp.x][tmp.y] = tmp;
  
         }
  
         printMaze();
  
     }
  
     
  
     
  
     private void sort(Stack s) {
  
         // 对一个栈里的元素按score排序，值最少的放在最上面。
  
         Node[] t = new Node[s.size()];
  
         Node tmp = null;
  
         int x = s.size();
  
         for(int i=0;i<x;i++){
  
             t = (Node)s.pop();
  
         }
  
         for(int i=0;i<t.length-1;i++)
  
             for(int j=i+1;j<t.length;j++){
  
                 if(t.score < t[j].score){
  
                     tmp = t;
  
                     t = t[j];
  
                     t[j] = tmp;
  
                 }
  
             }
  
         for(int i=0;i<t.length;i++)
  
             s.push(t);
  
     }
  

  
     private void getScore(){
  
         for(int i=0;i<maze.length;i++)
  
             for(int j=0;j<maze.length;j++){
  
                 maze[j].score = Math.abs(endNode.x - maze[j].x) + Math.abs(endNode.y - maze[j].y);
  
             }
  
     }
  
     private Node[] getNear(Node e){
  
         
  
         Node leftNode = (e.y!=0 ? maze[e.x][e.y-1] : null);
  
         Node rightNode = (e.y!=maze[0].length-1 ? maze[e.x][e.y+1] : null);
  
         Node upNode = (e.x!=0 ? maze[e.x-1][e.y] : null);
  
         Node downNode = (e.x!=maze.length-1 ? maze[e.x+1][e.y] : null);
  
         Node[] t =  {leftNode,rightNode,upNode,downNode};
  
         
  
         return t;
  
     }
  
     
  
     public static void main(String[] args){
  
         Puzzle p = new Puzzle();
  
         System.out.println("初始的迷宫如下：（其中&代表起点，@代表终点，#代表障碍）");
  
         p.printMaze();    //输出初始化的迷宫
  
         System.out.println();
  
         System.out.println("简单的一条寻路路径如下：（按东南西北的顺序遍历寻路）");
  
         p.getPath();        //输出搜寻从起始点到结束点的路径
  
         
  
         p = new Puzzle();
  
         System.out.println();
  
         System.out.println("用A*算法寻路路径如下：");
  
         p.Astar();
  
         
  
         
  
     }
  
}
  

  
运行
  

  

  
  

复制代码

源码下载：http://file.javaxxz.com/2014/11/7/000342203.zip