Android A *パスが無限にループを見つけることはありますか？

Question

私はこのアルゴリズムを学び、ゲームでそれを実装しようと大胆な一歩を踏み出しました。実装しようとして、私は終了しない無限ループを続けています。私は何度も何度も何度も何度も何度も何度も何度も何度も練習をしてきましたが、何かを見逃したり、どんな助けもありがとう。

public class PathFinder { 
private LinkedList<Node> openList; 
private LinkedList<Node> closedList; 

public PathFinder() { 
    openList = new LinkedList<Node>(); 
    closedList = new LinkedList<Node>(); 
} 

private List<Node> buildPath(Node node) { 
    LinkedList<Node> path = new LinkedList<Node>(); 
    while (node.parentNode != null) { 
     path.addFirst(node); 
     node = node.parentNode; 
    } 
    return path; 
} 

public List<Node> findPath(int sx, int sy, int dx, int dy) { 
    Node startNode = new Node(sx, sy); 
    Node endNode = new Node(dx, dy); 
    startNode.costG = 0; 
    startNode.costH = startNode.getManhattanCost(endNode); 
    startNode.parentNode = null; 
    openList.add(startNode); 

    while (!openList.isEmpty()) { 
     Node currentNode = (Node) openList.removeFirst(); 
     if (currentNode == endNode) { 
      Log.d("android", "found path"); 
      return buildPath(endNode); 
     } else { 
      currentNode.createNeighbors(); 
      List<Node> neighbors = currentNode.getNeighbors(); 
      for (int i = 0; i < neighbors.size(); i++) { 
       Node neighborNode = neighbors.get(i); 
       neighborNode.costG += currentNode.costG; 
       neighborNode.costH = neighborNode.getManhattanCost(endNode); 
       neighborNode.costF = neighborNode.costG + neighborNode.costH; 
       boolean isInOpen = openList.contains(neighborNode); 
       boolean isInClosed = closedList.contains(neighborNode); 

       if ((!isInOpen && !isInClosed) || neighborNode.costG < currentNode.costG) { 
        neighborNode.parentNode = currentNode; 
        neighborNode.costG += currentNode.costG; 
        neighborNode.costF = neighborNode.costG + neighborNode.costH; 
        if (isInClosed) { 
         closedList.remove(neighborNode); 
        } 
        if (!isInOpen) { 
         openList.add(neighborNode); 
        } 
       } 
      } 
      closedList.add(currentNode); 
     } 
    } 
    openList.clear(); 
    closedList.clear(); 
    return null; 
} 

}

public class Node { 
public Node parentNode; 
public List<Node> neighbors; 
public int x; 
public int y; 
public int costG; 
public int costH; 
public int costF; 

public Node(int x, int y) { 
    this.x = x; 
    this.y = y; 
    neighbors = new ArrayList<Node>(); 
    costG = 10; 
} 

public void createNeighbors() { 
    neighbors.add(new Node(x + 1, y)); 
    neighbors.add(new Node(x, y + 1)); 
    neighbors.add(new Node(x - 1, y)); 
    neighbors.add(new Node(x, y - 1)); 
} 

public int getManhattanCost(Node node) { 
    int i = (int) Math.abs(x - node.x); 
    int j = (int) Math.abs(y - node.y); 
    costH = i + j; 
    return costH; 
} 

public int getTotalCost() { 
    return costG + costH; 
} 

public List<Node> getNeighbors() { 
    return neighbors; 
} 

}

SX、SY、DX及びDYは、2Dアレイ内の位置と目標位置を開始しています。sx = 1、sy = 1、dx = 5、dy = 5のテスト用の固定数を渡しました。つまり、文字は（1,1）、タッチポイントは（5,5）です。

Answer 1

多くの努力で解決されました：currentNodeを設定した後、openListをクリアしてください。

Answer 2

これはかなり良いチュートリアルのように見え、それはJavaでだ、多分あなたの実装を比較して、何がPathfinding for games

Answer 3

名前空間Intraweb.Dentry { パブリッククラスSQLDentry飛び出すかどうかを確認：dentryを、IDentry { プライベート文字列をstrConnection;

# region "Functions" 

    # region "Get Single Values" 

    public object GetValue(string SQL, ValueDataType VluType) 
    { 
     SqlConnection con = new SqlConnection(strConnection); 
     SqlCommand SqlCMD = new SqlCommand(SQL, con); 

     try 
     { 
      object RtVlu; 
      con.Open(); 
      RtVlu = SqlCMD.ExecuteScalar(); 
      return Convert_Value(RtVlu, VluType); 
     } 
     catch (Exception e) 
     { 
      throw new Exception("Error occurred :-" + e.Message); 
     } 
     finally 
     { 
      SqlCMD.Dispose(); 
      con.Close(); 
      con.Dispose(); 
     } 
    } 

    public object GetValue(string SQL, ValueDataType VluType, SqlTransaction SqlTrn, SqlConnection con) 
    { 
     SqlCommand SqlCMD = new SqlCommand(SQL, con); 

     try 
     { 
      SqlCMD.Transaction = SqlTrn; 
      object RtVlu; 
      RtVlu = SqlCMD.ExecuteScalar(); 
      return Convert_Value(RtVlu, VluType); 
     } 
     catch (Exception e) 
     { 
      throw new Exception("Error occurred :-" + e.Message, e); 
     } 
     finally 
     { 
      SqlCMD.Dispose(); 
      con.Close(); 
     } 
    } 

    #endregion 

    # region "Execute Commands" 

    public bool RunCommand(string strSQL, SqlTransaction SqlTrn, SqlConnection con) 
    { 
     SqlCommand Sqlcmd = new SqlCommand(); 

     try 
     { 
      Sqlcmd.CommandType = CommandType.Text; 
      Sqlcmd.Connection = con; 
      Sqlcmd.Transaction = SqlTrn; 

      Sqlcmd.CommandText = strSQL; 
      Sqlcmd.ExecuteNonQuery(); 
      return true; 
     } 
     catch (Exception e) 
     { 
      con.Close(); 
      SqlTrn.Rollback(); 
      throw new Exception("Error Occured :-" + e.Message, e); 
     } 
     finally 
     { 
      Sqlcmd.Dispose(); 
     } 
    } 

    public bool RunCommand(string strSQL) 
    { 
     SqlCommand Sqlcmd = new SqlCommand(); 
     SqlConnection con = new SqlConnection(strConnection); 

     try 
     { 
      Sqlcmd.CommandType = CommandType.Text; 
      Sqlcmd.Connection = con; 

      Sqlcmd.CommandText = strSQL; 
      con.Open(); 
      Sqlcmd.ExecuteNonQuery(); 
      return true; 
     } 
     catch (Exception e) 
     { 
      throw new Exception("Error Occured :-" + e.Message, e); 
     } 
     finally 
     { 
      Sqlcmd.Dispose(); 
      con.Close(); 
      con.Dispose(); 
     } 
    } 

    # endregion 

    # region "Fill Tables with Normal Sql Queries" 


    public DataTable GetDataTable(string strSQL) 
    { 
     SqlConnection con = new SqlConnection(strConnection); 
     SqlCommand SqlCmd = new SqlCommand(strSQL, con); 

     try 
     { 
      DataTable dt = new DataTable(); 
      con.Open(); 
      dt.Load(SqlCmd.ExecuteReader()); 
      return dt; 
     } 
     catch (Exception e) 
     { 
      throw new Exception("Error occurred :-" + e.Message); 
     } 
     finally 
     { 
      con.Close(); 
      SqlCmd.Dispose(); 
      con.Dispose(); 
     } 
    } 

    public DataSet GetDataSet(string strSQL) 
    { 
     SqlConnection con = new SqlConnection(strConnection); 
     SqlDataAdapter da = new SqlDataAdapter(strSQL, con); 

     try 
     { 
      DataSet dt = new DataSet(); 
      con.Open(); 
      da.Fill(dt); 
      return dt; 
     } 
     catch (Exception e) 
     { 
      throw new Exception("Error occurred :-" + e.Message); 
     } 
     finally 
     { 
      con.Close(); 
      da.Dispose(); 
      con.Dispose(); 
     } 
    } 

    public SqlDataReader GetDataReader(string strSQL, SqlConnection con) 
    { 
     SqlDataReader dr = null; 
     SqlCommand SqlCmd = new SqlCommand(); 

     try 
     { 
      SqlCmd.CommandType = CommandType.Text; 
      SqlCmd.Connection = con; 
      SqlCmd.CommandText = strSQL; 
      dr = SqlCmd.ExecuteReader(); 
      return dr; 
     } 
     catch (Exception e) 
     { 
      dr.Close(); 
      con.Close(); 
      throw new Exception("Error occurred :-" + e.Message); 
     } 
     finally 
     { 
      SqlCmd.Dispose(); 
     } 
    } 

    public SqlDataReader GetDataReader(string strSQL,SqlTransaction SqlTrn, SqlConnection con) 
    { 
     SqlDataReader dr=null; 
     SqlCommand SqlCmd = new SqlCommand(); 

     try 
     { 
      SqlCmd.CommandType = CommandType.Text; 
      SqlCmd.Connection = con; 
      SqlCmd.CommandText = strSQL; 
      dr = SqlCmd.ExecuteReader(); 
      return dr; 
     } 
     catch (Exception e) 
     { 
      dr.Close(); 
      con.Close(); 
      SqlTrn.Rollback(); 
      throw new Exception("Error occurred :-" + e.Message); 
     } 
     finally 
     { 
      SqlCmd.Dispose(); 
     } 

    } 
    # endregion 

    # endregion 


    # region "Constructors" 

     public SQLDentry(string ConnectionString):base(true, ConnectionString) 
     { 
      strConnection = ConnectionString; 
     } 

    #endregion 



} 

}

Answer 4

これは私にはバグのようになります。もしあなたが 'ステートメントで一度一度ときに、最初のノードを作成して二回 neighbournodeにcostGを追加していますか？それはあなたの無限ループが発生しますが、それはあなたが不足している

Answer 5

一つのことは、あなたのopenListが、もしcostf順持っているバグのように見えない場合

   neighborNode.costG += currentNode.costG; 

本当にわかりません。

また、equalsと比較する必要がある場合は、2つのノードオブジェクトを==と比較しています。多分、あなたがゴールポイントに到達しない理由は...