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.массив.Для проверки я передал int фиксированные числа sx = 1, sy = 1, dx = 5, dy = 5. Другими словами, символ находится в точке (1, 1), а точка касания - в точке (5, 5).

Answer 1

единственное, чего вам не хватает, так это того, чтобы ваш openList заказывал costF.

Кроме того, вы сравниваете 2 объекта Node с ==, когда вы должны сравнивать с равными.Может быть, поэтому вы никогда не достигнете цели ...

Answer 2

Решено с большим трудом: после установки currentNode очистить openList.

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

Для меня это похоже на ошибку: вы добавляете costG в соседний узел дважды Один раз, когда вы впервые создаете узел, и один раз в операторе 'if'?

                neighborNode.costG += currentNode.costG;

Не совсем уверен, что этовызовет ваш бесконечный цикл, но это похоже на ошибку

Answer 5

Это похоже на довольно хороший учебник, и он написан на Java, может быть, сравните вашу реализацию и посмотрите, появится ли что-нибудь Поиск пути для игр