Android A* path finding looping infinitely?

I took a bold step in trying to learn this algorithm and implementing it in my game and "understanding" it was the easy part. In trying to implement it, I keep getting an infinite loop that does not quit. I've been through my code over and over again but I must be missing something or not understanding a part of it. Any help would be appreciated.

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 += curren开发者_Go百科tNode.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;
}

}

The sx, sy, dx, and dy are starting position and goal position in a 2d array. I passed int fixed numbers for testing purposes sx = 1, sy = 1, dx = 5, dy = 5. In other words, character is at (1, 1) and the touch point is at (5, 5).

one thing you're missing is having your openList ordered by costF.

Also, you're comparing 2 Node objects with ==, when you should be comparing with equals. Maybe thats why you never reach the goal point ...

This looks like a pretty good tutorial and it's in java, maybe compare you implementation and see if anything pops out Pathfinding for games

This looks like a bug to me: you are adding the costG to the neighbournode twice Once when you first create the node and once in the 'if' statement ?

                neighborNode.costG += currentNode.costG;

Not really sure if that would cause your infinite loop, but it does look like a bug

Solved with much effort: after setting the currentNode, clear the openList.

namespace Intraweb.Dentry { public class SQLDentry : Dentry, IDentry { private string 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



}

}