生活随笔
收集整理的這篇文章主要介紹了
Java版A星算法
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
A星算法步驟：
1.起點先添加到開啟列表中
2.開啟列表中有節(jié)點的話，取出第一個節(jié)點，即最小F值的節(jié)點
判斷此節(jié)點是否是目標(biāo)點，是則找到了，跳出
根據(jù)此節(jié)點取得八個方向的節(jié)點，求出G，H，F值
判斷每個節(jié)點在地圖中是否能通過，不能通過則加入關(guān)閉列表中，跳出
判斷每個節(jié)點是否在關(guān)閉列表中，在則跳出
判斷每個節(jié)點是否在開啟列表中，在則更新G值，F值，還更新其父節(jié)點；不在則將其添加到開啟列表中，計算G值，H值，F值，添加其節(jié)點
3.把此節(jié)點從開啟列表中刪除，再添加到關(guān)閉列表中
4.把開啟列表中按照F值最小的節(jié)點進(jìn)行排序，最小的F值在第一個
5.重復(fù)2，3，4步驟
直到目標(biāo)點在開啟列表中，即找到了；目標(biāo)點不在開啟列表中，開啟列表為空，即沒找到
?
?public?class?AStar?{ ?????private?int[][]?map;?????private?List<Node>?openList;?????private?List<Node>?closeList;?????private?final?int?COST_STRAIGHT?=?10;?????private?final?int?COST_DIAGONAL?=?14;?????private?int?row;?????private?int?column;????? ?????public?AStar(int[][]?map,int?row,int?column){ ?????????this.map=map; ?????????this.row=row; ?????????this.column=column; ?????????openList=new?ArrayList<Node>(); ?????????closeList=new?ArrayList<Node>(); ?????} ????? ??????????public?int?search(int?x1,int?y1,int?x2,int?y2){ ?????????if(x1<0||x1>=row||x2<0||x2>=row||y1<0||y1>=column||y2<0||y2>=column){ ?????????????return?-1; ?????????} ?????????if(map[x1][y1]==0||map[x2][y2]==0){ ?????????????return?-1; ?????????} ?????????Node?sNode=new?Node(x1,y1,null); ?????????Node?eNode=new?Node(x2,y2,null); ?????????openList.add(sNode); ?????????List<Node>?resultList=search(sNode,?eNode); ?????????if(resultList.size()==0){ ?????????????return?0; ?????????} ?????????for(Node?node:resultList){ ?????????????map[node.getX()][node.getY()]=-1; ?????????} ?????????return?1; ?????} ????? ??????????private?List<Node>?search(Node?sNode,Node?eNode){ ?????????List<Node>?resultList=new?ArrayList<Node>(); ?????????boolean?isFind=false; ?????????Node?node=null; ?????????while(openList.size()>0){ ??????????????????????????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()-1,node,?eNode,?COST_STRAIGHT); ?????????????} ??????????????????????????if((node.getY()+1)<column){ ?????????????????checkPath(node.getX(),node.getY()+1,node,?eNode,?COST_STRAIGHT); ?????????????} ??????????????????????????if((node.getX()-1)>=0){ ?????????????????checkPath(node.getX()-1,node.getY(),node,?eNode,?COST_STRAIGHT); ?????????????} ??????????????????????????if((node.getX()+1)<row){ ?????????????????checkPath(node.getX()+1,node.getY(),node,?eNode,?COST_STRAIGHT); ?????????????} ??????????????????????????if((node.getX()-1)>=0&&(node.getY()-1)>=0){ ?????????????????checkPath(node.getX()-1,node.getY()-1,node,?eNode,?COST_DIAGONAL); ?????????????} ??????????????????????????if((node.getX()-1)>=0&&(node.getY()+1)<column){ ?????????????????checkPath(node.getX()-1,node.getY()+1,node,?eNode,?COST_DIAGONAL); ?????????????} ??????????????????????????if((node.getX()+1)<row&&(node.getY()-1)>=0){ ?????????????????checkPath(node.getX()+1,node.getY()-1,node,?eNode,?COST_DIAGONAL); ?????????????} ??????????????????????????if((node.getX()+1)<row&&(node.getY()+1)<column){ ?????????????????checkPath(node.getX()+1,node.getY()+1,node,?eNode,?COST_DIAGONAL); ?????????????} ???????????????????????????????????????closeList.add(openList.remove(0)); ??????????????????????????Collections.sort(openList,?new?NodeFComparator()); ?????????} ?????????if(isFind){ ?????????????getPath(resultList,?node); ?????????} ?????????return?resultList; ?????} ????? ??????????private?boolean?checkPath(int?x,int?y,Node?parentNode,Node?eNode,int?cost){ ?????????Node?node=new?Node(x,?y,?parentNode); ??????????????????if(map[x][y]==0){ ?????????????closeList.add(node); ?????????????return?false; ?????????} ??????????????????if(isListContains(closeList,?x,?y)!=-1){ ?????????????return?false; ?????????} ??????????????????int?index=-1; ?????????if((index=isListContains(openList,?x,?y))!=-1){ ??????????????????????????if((parentNode.getG()+cost)<openList.get(index).getG()){ ?????????????????node.setParentNode(parentNode); ?????????????????countG(node,?eNode,?cost); ?????????????????countF(node); ?????????????????openList.set(index,?node); ?????????????} ?????????}else{ ??????????????????????????node.setParentNode(parentNode); ?????????????count(node,?eNode,?cost); ?????????????openList.add(node); ?????????} ?????????return?true; ?????} ????? ??????????private?int?isListContains(List<Node>?list,int?x,int?y){ ?????????for(int?i=0;i<list.size();i++){ ?????????????Node?node=list.get(i); ?????????????if(node.getX()==x&&node.getY()==y){ ?????????????????return?i; ?????????????} ?????????} ?????????return?-1; ?????} ????? ??????????private?void?getPath(List<Node>?resultList,Node?node){ ?????????if(node.getParentNode()!=null){ ?????????????getPath(resultList,?node.getParentNode()); ?????????} ?????????resultList.add(node); ?????} ????? ??????????private?void?count(Node?node,Node?eNode,int?cost){ ?????????countG(node,?eNode,?cost); ?????????countH(node,?eNode); ?????????countF(eNode); ?????} ??????????private?void?countG(Node?node,Node?eNode,int?cost){ ?????????if(node.getParentNode()==null){ ?????????????node.setG(cost); ?????????}else{ ?????????????node.setG(node.getParentNode().getG()+cost); ?????????} ?????} ??????????private?void?countH(Node?node,Node?eNode){ ?????????node.setF(Math.abs(node.getX()-eNode.getX())+Math.abs(node.getY()-eNode.getY())); ?????} ??????????private?void?countF(Node?node){ ?????????node.setF(node.getG()+node.getF()); ?????} ????? ?} ??class?Node?{ ?????private?int?x;?????private?int?y;?????private?Node?parentNode;?????private?int?g;?????private?int?h;?????private?int?f;????? ?????public?Node(int?x,int?y,Node?parentNode){ ?????????this.x=x; ?????????this.y=y; ?????????this.parentNode=parentNode; ?????} ????? ?????public?int?getX()?{ ?????????return?x; ?????} ?????public?void?setX(int?x)?{ ?????????this.x?=?x; ?????} ?????public?int?getY()?{ ?????????return?y; ?????} ?????public?void?setY(int?y)?{ ?????????this.y?=?y; ?????} ?????public?Node?getParentNode()?{ ?????????return?parentNode; ?????} ?????public?void?setParentNode(Node?parentNode)?{ ?????????this.parentNode?=?parentNode; ?????} ?????public?int?getG()?{ ?????????return?g; ?????} ?????public?void?setG(int?g)?{ ?????????this.g?=?g; ?????} ?????public?int?getH()?{ ?????????return?h; ?????} ?????public?void?setH(int?h)?{ ?????????this.h?=?h; ?????} ?????public?int?getF()?{ ?????????return?f; ?????} ?????public?void?setF(int?f)?{ ?????????this.f?=?f; ?????} ?} ??class?NodeFComparator?implements?Comparator<Node>{ ??????@Override?????public?int?compare(Node?o1,?Node?o2)?{ ?????????return?o1.getF()-o2.getF(); ?????} ????? ?}? ?
轉(zhuǎn)載于:https://blog.51cto.com/xmmdream/806053
總結(jié)
以上是生活随笔為你收集整理的Java版A星算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
