After going through a bunch of questions here on SO, I still have no idea what exactly is going wrong with my code and would appreciate some help.

I'm trying to implement a priority queue based on f-costs for an A* algorithm, and while the algorithm works fine for short pathfinding distances, it seems to go wrong when there's an obstacle or when the distance between start and goal points is greater than about 30 squares (although sometimes it screws up for less too).

while(!m_qOpenList.isEmpty())
    {
        m_xCurrent=m_qOpenList.poll();
        m_xCurrent.setBackground(Color.red);
        m_qClosedList.add(m_xCurrent);
        if(m_xCurrent.getStatus()==2)
        {
            System.out.println("Target Reached");
            solved=true;
            break;
        }

        iX=m_xCurrent.getXCo();
        iY=m_xCurrent.getYCo();

        for(i=iX-1;i<=iX+1;i++)
            for(j=iY-1;j<=iY+1;j++)
            {
                if(i<0||j<0||i>m_iMazeX||j>m_iMazeX||(i==iX&&j==iY)
                        || m_xNode[i][j].getStatus()==4||
                        m_qClosedList.contains(m_xNode[i][j]))
                    continue;
                m_xNode[i][j].score(m_xCurrent,m_xGoal);
                m_qOpenList.add(m_xNode[i][j]);
            }
    }

It's quite rudimentary as I'm just trying to get it to work for now. m_qOpenList is the PriorityQueue. The problem is that when I debug the program, at some point (near an obstacle), a Node with a fcost of say 84 has higher priority than a node with an fcost of 70. I am not attempting to modify the values once they're on the priority queue. You'll notice that I add at the end of the while loop (I read somewhere that the priorityqueue reorders itself when stuff is added to it), and poll right after that at the beginning.

Status of 2 means the Node is the goal, and a status of 4 means that it is unwalkable.

public int compareTo(Node o)
{
    if(m_iF<o.m_iF)
        return -1;
    if(m_iF>o.m_iF)
        return 1;
    return 0;
}

And that's the compareTo function.

Can you see a problem? =(