1，把起始格添加到开启列表。

   2，重复如下的工作：

      a) 寻找开启列表中F值最低的格子。我们称它为当前格。

      b) 把它切换到关闭列表。

      c) 对相邻的格中的每一个？

          * 如果它不可通过或者已经在关闭列表中，略过它。反之如下。

          * 如果它不在开启列表中，把它添加进去。把当前格作为这一格的父节点。记录这一格的F,G,和H值。

          * 如果它已经在开启列表中，用G值为参考检查新的路径是否更好。更低的G值意味着更好的路径。如果是这样，就把这一格的父节点改成当前格，并且重新计算这一格的G和F值。如果你保持你的开启列表按F值排序，改变之后你可能需要重新对开启列表排序。

      d) 停止，当你

          * 把目标格添加进了关闭列表(注解)，这时候路径被找到，或者

          * 没有找到目标格，开启列表已经空了。这时候，路径不存在。

   3.保存路径。从目标格开始，沿着每一格的父节点移动直到回到起始格。这就是你的路径。

* G = 从起点A，沿着产生的路径，移动到网格上指定方格的移动耗费。

* H = 从网格上那个方格移动到终点B的预估移动耗费。

  1 public class Move extends Thread{
  2     private int x,y,ed,pots,st;
  3     private Map ma;
  4     private Node[] node=new Node[1000];
  5     private boolean moving=true;
  6     private Queue<Node> forward=new LinkedList<Node>();;
  7     public Move(int x,int y,int xend,int yend,Map ma) {
  8         this.x=x;
  9         this.y=y;
 10         this.ma=ma;
 11         pots=0;
 12         for(int i=0;i<ma.getrows();i++)
 13             for(int j=0;j<ma.getcols();j++)
 14                 if(!ma.boxes[i][j].isColorBox()){
 15                     node[pots]=new Node(i,j);
 16                     pots++;
 17             }
 18         for(int j=0;j<pots;j++){
 19             int x1=node[j].x;
 20             int y1=node[j].y;
 21             for(int i=0;i<pots;i++){
 22                 int x2=node[i].x;
 23                 int y2=node[i].y;
 24                 int t1=x1-x2;
 25                 int t2=y1-y2;
 26                 if(((t1==1||t1==-1)&&t2==0)||((t2==1||t2==-1)&&t1==0)){
 27 //                if(t1<2&&t2<2){
 28                     node[j].neighbors.add(node[i]);
 29                 }
 30             }
 31         }
 32 
 33         ed=getnode(xend, yend);
 34     }
 35     public void run(){
 36         while(moving){
 37             try{
 38                 sleep(500);
 39             }
 40             catch(InterruptedException ie){
 41                 ie.printStackTrace();
 42             }
 43             if(ma.xstart==ma.xgoal&&ma.ystart==ma.ygoal){
 44                 moving=false;
 45                 break;
 46             }
 47             Random random = new Random();
 48             int tmp=Math.abs(random.nextInt())%7;
 49             if(tmp<2)
 50                 rand();
 51             else
 52                 mov();
 53         }
 54     }
 55     public void mov(){
 56         st=getnode(x, y);;
 57         List<Node> lit=search(node[st],node[ed]);
 58         forward.clear();
 59         for(int i=0;i<lit.size();i++)
 60             forward.offer(lit.get(i));
 61         if(!forward.isEmpty())
 62         {
 63             Node x=forward.poll();
 64             move(x.x,x.y);
 65         }
 66     }
 67     public void gostep(){
 68         if(!steps.isEmpty())
 69         {
 70             int x=steps.poll();
 71             move(sear.node[x].x,sear.node[x].y);
 72         }
 73     }
 74     public int getnode(int x,int y){
 75         for(int i=0;i<pots;i++){
 76             if(node[i].x==x&&node[i].y==y)
 77                 return i;
 78         }
 79         return 0;
 80     }
 81     public void rand(){
 82         Random random = new Random();
 83         int tmp=Math.abs(random.nextInt())%8;
 84         if(tmp==0){
 85             moveup();
 86         }
 87         else if(tmp==1){
 88             movedown();
 89         }
 90         else if(tmp==2){
 91             moveleft();
 92         }
 93         else if(tmp==3){
 94             moveright();
 95         }
 96         else if(tmp==4){
 97             moveupleft();
 98         }
 99         else if(tmp==5){
100             movedownleft();
101         }
102         else if(tmp==6){
103             moveupright();
104         }
105         else if(tmp==7){
106             movedownright();
107         }
108     }
109     public boolean Movable(int x,int y){
110         if(x>=0&&y>=0&&x<ma.getrows()&&y<ma.getcols())
111             if(!ma.getBox(x, y).isColorBox())
112                 return true;
113         if(x==ma.xgoal&&y==ma.ygoal){
114             moving=false;
115         }
116         return false;
117     }
118     public boolean move(int xn,int yn){
119         if(!Movable(xn, yn))
120             return false;
121         Box b=ma.getBox(xn, yn);
122         if(b!=null){
123             ma.xstart=xn;
124             ma.ystart=yn;
125         }
126         y=yn;
127         x=xn;
128         ma.repaint();
129         return true;
130     }
131     public void moveup(){
132         move(x-1,y);
133     }
134     public void movedown(){
135         move(x+1,y);
136     }
137     public void moveleft(){
138         move(x,y-1);
139     }
140     public void moveright(){
141         move(x,y+1);
142     }
143     public void moveupleft(){
144         move(x-1, y-1);
145     }
146     public void moveupright(){
147         move(x-1, y+1);
148     }
149     public void movedownleft(){
150         move(x+1, y-1);
151     }
152     public void movedownright(){
153         move(x+1, y+1);
154     }//以下为核心部分
155     public int getscore(Node node,Node goalNode){
156         return (node.x-goalNode.x)*(node.x-goalNode.x)
157                 +(node.y-goalNode.y)*(node.y-goalNode.y);
158     }
159     public List<Node> constructPath(Node node) {
160         LinkedList<Node> path = new LinkedList<Node>();
161         while (node.pathParent != null) {
162             path.addFirst(node);
163             node = node.pathParent;
164         }
165         return path;
166     }
167     public List<Node> search(Node startNode, Node goalNode) {
168         LinkedList<Node> closedList = new LinkedList<Node>();//存放已经访问过的节点,是(FIFO)表
169         LinkedList<Node> openList = new LinkedList<Node>(); 
170         startNode.score=0;//存放已经即将访的节点
171         openList.add(startNode);
172         startNode.pathParent = null;
173         while (!openList.isEmpty()) {
174             Node node=(Node)openList.removeFirst();
175             if (node==goalNode) {
176                 return constructPath(goalNode);
177             }
178             else {
179                 closedList.add(node);
180                 Iterator<Node> i=node.neighbors.iterator();
181                 while (i.hasNext()) {
182                     Node neighborNode=(Node)i.next();
183                     if (!closedList.contains(neighborNode)&&
184                         !openList.contains(neighborNode))
185                     {
186                         neighborNode.score=node.score+getscore(neighborNode, goalNode);
187                         neighborNode.pathParent=node;
188                         openList.add(neighborNode);
189                     }
190                 }
191             }
192             Collections.sort(openList,new Comparator<Node>(){
193                 public int compare(Node o1, Node o2){
194                     return o1.score>o2.score?1:0;
195                 }
196             }); 
197         }
198         return null;
199     }
200     public class Node {
201         public List<Node> neighbors;
202         public Node pathParent;  
203         int x,y;
204         int score=0;
205         public Node(int x,int y) {
206             this.x=x;
207             this.y=y;
208             score=0;
209             neighbors = new LinkedList<Node>();
210         }
211     }
212 }