Aスターアルゴリズムの実装手順のJavaバージョン

スターアルゴリズムの手順:

1. 最初に、オープンリストに開始点を追加します。

2. オープンリストにノードがある場合は、F 値が最小のノードである最初のノードを取り出します。

このノードが目標点であるかどうかを判断し、見つかった場合は飛び出し、

このノードに従って、8 方向のノードを取得し、G、H、F の値を見つけることができます。

マップ内の各ノードを通過できるかどうかを判断します。通過できない場合は、閉じたリストに追加してジャンプします。各ノードが閉じたリスト内にあるかどうかを判断します。ある場合は、ジャンプします。

各ノードがオープンリスト内にあるかどうかを判断します。ある場合は、G 値、F 値、およびその親ノードを更新します。ない場合は、オープンリストに追加し、G 値、H 値、および F 値を計算して、そのノードを追加します。

3. このノードをオープンリストから削除し、クローズドリストに追加します。

4. 開いたリスト内のノードを最小の F 値に従って並べ替え、最小の F 値を最初のノードにします。

5. 手順 2、3、4 を繰り返します。

ターゲットポイントがオープンリスト内にある場合は、そのポイントが見つかります。ターゲットポイントがオープンリスト内になく、オープンリストが空の場合は、そのポイントは見つかりません。

 //A* アルゴリズム public class AStar {   
    プライベート  int [][] map; //map（1は通過可能、0は通過不可）  
     private List<Node> openList; //リストを開く 
     private List<Node> closeList; // リストを閉じる 
    プライベート ファイナル  int COST_STRAIGHT = 10 ; //垂直または水平移動のパススコア 
    プライベート ファイナル  int COST_DIAGONAL = 14 ; //斜め移動のパススコア 
    プライベート  int行; //行 
    プライベート  int column; //列 
        パブリックAStar( int [][] マップ、 int行、 int列){ 
        この.map = map; 
         this .row=行; 
         this .column = 列;
        openList =新しいArrayList<Node>();
        closeList =新しいArrayList<Node>();
    } 
         //座標を検索 (-1: エラー、0: 見つからない、1: 見つかった)  
    公共  int検索( int x1, int y1, int x2, int y2){ 
         (x1< 0 ||x1>=行||x2< 0 ||x2>=行||y1< 0 ||y1>=列||y2< 0 ||y2>=列)の場合{ 
              
戻り値- 1 ;
        } 
         map[x1][y1]== 0 ||map[x2][y2]== 0の場合、 -1を返します。
        }
        ノード sNode = new Node(x1,y1, null );
        ノード eNode = new Node(x2,y2, null ); openList.add(sNode);
        リスト<Node> resultList=search(sNode, eNode); 
        結果リストのサイズが0の場合
            戻る  0 ;
        } 
         (ノード node:resultList)の場合{
            マップ[node.getX()][node.getY()]=- 1 ;
        } 
        戻る  1 ;
    } 
         //コアアルゴリズムを見つける 
    プライベートリスト<Node> search(Node sNode,Node eNode){
        List<Node> resultList =新しいArrayList<Node>(); 
        ブール値isFind = false ;
        ノード node = null ; 
         openList.size() > 0の場合
             // オープンリスト内の ***F 値、つまり *** に格納されている値の ***F 値を取り出します 
            ノード = openList.get( 0 ); 
             // ターゲットポイントが見つかったかどうかを判断します 
             (node.getX()==eNode.getX()&&node.getY()==eNode.getY()) の場合{
                isFind = true ; 
                壊す;
            } 
             //優れた 
             if ((node.getY()- 1 )>= 0 ){ checkPath(node.getX(),node.getY()- 1 ,node, eNode, COST_STRAIGHT);
            } 
             //下 
             if ((node.getY()+ 1 )<列){
                checkPath(node.getX(),node.getY()+ 1 ,node, eNode, COST_STRAIGHT);
            } 
             //左 
             ((node.getX()- 1 )>= 0 )の場合{
                checkPath(node.getX()- 1 、node.getY()、node、eNode、COST_STRAIGHT);
            } 
             //右 
             ((node.getX()+ 1 )<行)の場合{
                checkPath(node.getX()+ 1 、node.getY()、node、eNode、COST_STRAIGHT);
            } 
             //左上 
             ((node.getX()- 1 )>= 0 &&(node.getY()- 1 )>= 0 ){の場合
                checkPath(node.getX()- 1 、node.getY()- 1 、node、eNode、COST_DIAGONAL);
            } 
             //左下 
             ((node.getX()- 1 )>= 0 &&(node.getY()+ 1 )<列)の場合{
                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);
            } 
             //右下 
             ((node.getX()+ 1 )<行&&(node.getY()+ 1 )<列)の場合{
                checkPath(node.getX()+ 1 、node.getY()+ 1 、node、eNode、COST_DIAGONAL);
            } 
             // オープンリストから削除 
             //閉じたリストに追加 
            closeList.add(openList.remove( 0 )); 
             // リストのソートを開始し、最も高い F 値を持つものを最下端に配置します。Collections.sort(openList, new NodeFComparator());  
        } 
         if (isFind){
            getPath(結果リスト、ノード);
        } 
        結果リストを返します。
    } 
         // この道路が通行可能かどうか確認する 
    プライベート ブール値checkPath( int x, int y,Node parentNode,Node eNode, int cost){
        ノード node = new Node(x, y, parentNode); 
         // マップが渡せるかどうか確認する 
         (map[x][y]== 0 )の場合{
            リストを閉じます。ノードを追加します。 
            戻る 間違い;
        } 
         // 閉じたリストに存在するかどうかを確認します 
         (isListContains(closeList, x, y)!=- 1 )の場合{ 
            戻る 間違い;
        } 
         // オープンリストに存在するかどうかを確認します 
         intインデックス = - 1 ; 
         if ((index=isListContains(openList, x, y))!=- 1 ){ 
             //G値が小さいかどうか、つまりG値とF値を更新するかどうか 
             ((parentNode.getG()+コスト)<openList.get(index).getG())の場合{
                ノードを親ノードに設定します。
                countG(ノード、eNode、コスト);
                countF(ノード);
                openList.set(インデックス、ノード);
            }
        }それ以外{ 
             //オープンリストに追加 
            node.setParentNode(parentNode); count(node, eNode, cost);
            ノードをリストに追加します。
        } 
        戻る 真実;
    } 
         //コレクションに要素が含まれているかどうか (-1: 見つからない、それ以外の場合はインデックスを返す)  
    プライベート  int isListContains(List<Node> リスト、 int x、 int y){ 
         ( int i = 0 ;i<list.size();i++) {
            ノード node=list.get(i); 
             (node.getX()==x&&node.getY()==y)の場合{ 
                 iを返します。
            }
        } 
        戻り値- 1 ;
    } 
         // 終点から始点までを往復する 
    プライベート  void getPath(List<Node> resultList,Node ノード){ 
         node.getParentNode() がnullの場合、 getPath(resultList, node.getParentNode());
        }
        結果リストにノードを追加します。
    } 
         //G、H、Fの値を計算する 
    プライベート  void count(ノード node,ノード eNode, int cost){
        countG(ノード、eNode、コスト);
        countH(ノード、eNode);
        countF(eNode);
    } 
     //G値を計算 
    プライベート  void countG(ノードノード、ノードeNode、 intコスト){ 
         （node.getParentNode() == nullの場合）{
            ノード.setG(コスト);
        }それ以外{
            node.setG(node.getParentNode().getG()+コスト);
        }
    } 
     //H値を計算 
    プライベート  void countH(ノードノード、ノードeNode){
        node.setF(Math.abs(node.getX()-eNode.getX())+Math.abs(node.getY()-eNode.getY()));
    } 
     //F値を計算する 
    プライベート  void countF(ノードノード){
        node.setF(node.getG()+node.getF());
    }
    } //ノードクラス クラス Node {  
    プライベート  int x; //X座標 
    プライベート  int y; //Y座標 
     private Node parentNode; //親クラスノード 
    プライベート  int g; //現在の地点から出発地点までの移動コスト 
    プライベート  int h; //現在のポイントから終点までの移動コスト、つまりマンハッタン距離 |x1-x2|+|y1-y2| (障害物を無視)  
    プライベート  int f; //f=g+h  
        パブリックNode( int x, int y,Node parentNode){ this .x=x; 
        これ.y=y; 
        これは.parentNode=parentNode;
    } 
        公共 整数getX() { 
         xを返します。
    } 
    公共  void setX( int x) { 
        これは.x = x;
    } 
    公共 整数getY() { 
         yを返します。
    } 
    公共  void setY( int y) { 
        これは.y = y;
    } 
    パブリックノード getParentNode() { 
        親ノードを返します。
    } 
    公共  void setParentNode(ノードの親ノード) { 
         .parentNode = parentNode;です。
    } 
    公共 整数getG() { 
         gを返します。
    } 
    公共  void setG( int g) { 
        これは.g = g;
    } 
    公共 整数getH() { 
         hを返します。
    } 
    公共  void setH( int h) { 
        これは.h = h;
    } 
    公共 整数getF() { 
         fを返します。
    } 
    公共  void setF( int f) { 
        これは.f = f;
    }} //ノード比較クラスクラスNodeFComparatorはComparator<Node>{を実装します 
     @オーバーライド 
    公共  int比較(ノードo1、ノードo2) { 
         o1.getF()-o2.getF()を返します。
    }
    }

テストクラス:

公共 クラステスト{ 
        公共 静的  void main(String[] args){ 
         int [][] マップ =新規 整数[][]{
 // マップ配列
                {1,1,1,1,1,1,1,1,1,1,1},
                {1,1,1,1,0,1,1,1,1,1},
                {1,1,1,1,0,1,1,1,1,1},
                {1,1,1,1,0,1,1,1,1,1},
                {1,1,1,1,0,1,1,1,1,1},
                {1,1,1,1,0,1,1,1,1,1}  
        };
        AStar aStar = new AStar(map, 6 , 10 ); 
         intフラグ = aStar.search( 4 , 0 , 3 , 8 ); 
         if (フラグ == - 1 ) {
            System.out.println( "データ転送中にエラーが発生しました!" );
        }それ以外 フラグが0の場合
            System.out.println( "見つかりません!" );
        }それ以外{ 
             ( int x = 0 ; x < 6 ; x++) { 
                 ( int y = 0 ; y < 10 ; y++ ) { 
                     (map[x][y]== 1 )の場合{
                        システム出力を印刷します( " " );
                    }それ以外  (map[x][y]== 0 )の場合{
                        System.out.print( "〓" );
                    }それ以外  (map[x][y]==- 1 )の場合{
                        System.out.print( "※" );
                    }
                }
                システム出力のprintln();
            }
        }
    }}