package?example;

import?java.util.ArrayList;
import?java.util.Collections;
import?java.util.List;

public?class?AStarAlgorithm?{
????private?int[][]?map;//地圖（1可通過?0不可通過）
????private?List?openList;//開啟列表
????private?List?closeList;//關閉列表
????private?final?int?COST_STRAIGHT?=?10;//垂直方向或水平方向移動的路徑評分
????private?int?row;//行
????private?int?column;//列
????
????public?AStarAlgorithm?（int[][]?mapint?rowint?column）{
????????this.map=map;
????????this.row=row;
????????this.column=column;
????????openList=new?ArrayList（）;
????????closeList=new?ArrayList（）;
????}
????
????//查找坐標（-1：錯誤，0：沒找到，1：找到了）
????public?int?search（int?x1int?y1int?x2int?y2）{
????????if（x1<0||x1>=column||x2<0||x2>=column||y1<0||y1>=row||y2<0||y2>=row）{
????????????return?-1;
????????}
????????if（map[x1][y1]==0||map[x2][y2]==0）{
????????????return?-1;
????????}
????????Node?sNode=new?Node（x1y1null）;
????????Node?eNode=new?Node（x2y2null）;
????????openList.add（sNode）;
????????List?resultList=search（sNode?eNode）;
????????if（resultList.size（）==0）{
????????????return?0;
????????}
????????for（Node?node:resultList）{
????????????map[node.getX（）][node.getY（）]=-1;
????????}
????????System.out.println（“路徑長度:“+resultList.size（））;
????????return?1;
????}
????
????//查找核心算法
????private?List?search（Node?sNodeNode?eNode）{
????????List?resultList=new?ArrayList（）;
????????boolean?isFind=false;
????????Node?node=null;
????????while（openList.size（）>0）{
????????????//取出開啟列表中最低F值，即第一個存儲的值的F為最低的
????????????node=openList.get（0）;
????????????//判斷是否找到目標點
????????????if（node.getX（）==eNode.getX（）&&node.getY（）==eNode.getY（））{
????????????????isFind=true;
????????????????break;
????????????}
????????????//上
????????????if（（node.getY（）-1）>=0）{
????????????????checkPath（node.getX（）node.getY（）-1node?eNode?COST_STRAIGHT）;
????????????}
????????????//下
????????????if（（node.getY（）+1）????????????????checkPath（node.getX（）node.getY（）+1node?eNode?COST_STRAIGHT）;
????????????}
????????????//左
????????????if（（node.getX（）-1）>=0）{
????????????????checkPath（node.getX（）-1node.getY（）node?eNode?COST_STRAIGHT）;
????????????}
????????????//右
????????????if（（node.getX（）+1）????????????????checkPath（node.getX（）+1node.getY（）node?eNode?COST_STRAIGHT）;
????????????}
????????????//從開啟列表中刪除
????????????//添加到關閉列表中
????????????closeList.add（openList.remove（0））;
????????????//開啟列表中排序，把F值最低的放到最底端
????????????Collections.sort（openList?new?NodeFComparator（））;
????????}
????????if（isFind）{
????????????getPath（resultList?node）;
????????}
????????return?resultList;
????}
????
????//查詢此路是否能走通
????private?boolean?checkPath（int?xint?yNode?parentNodeNode?eNodeint?cost）{
????????Node?node=new?Node（x?y?parentNode）;
????????//查找地圖中是否能通過
????????if（map[x][y]==0）{
????????????closeList.add（node）;
????????????return?false;
????????}
????????//查找關閉列表中是否存在
????????if（isListCo

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件???????3788??2013-01-01?12:26??Robot.java

?????文件???????6825??2013-01-02?11:30??AStarAlgorithm.java

?????文件???????1480??2013-01-02?10:41??AvoidBlock.java

?????文件???????2349??2013-01-03?14:24??MyEnv.java

?????文件???????1063??2012-12-27?11:11??Node.java

?????文件????????220??2012-12-27?11:13??NodeFComparator.java

-----------?---------??----------?-----??----

????????????????15725????????????????????6