0

So I'm currently working on Pathfinding for my game using A*, currently it makes the path but the path is very incorrect. I will crudely draw the path it creates:

Start Node
   Second Node
        Third Node
            Fourth Node    Sixth Node
                    Fifth Node     Seventh Node
                                        Eighth Node   Tenth Node
                                             Ninth Node     Eleventh Node
                                                                    End Node

After going through with the debugger I determined that at the fifth node, the Top Right, Right and Bottom Right Nodes all shared the exact same fCost. At this point I can only assume it has to do with the result of my getH function. Here it is:

public int getH(int row, int col, Node goal)
{
    return (int)Math.sqrt((goal.row - row) * (goal.row - row) + (goal.col - col) * (goal.col - col));
}

So my question is, what am I doing wrong here?

On smaller tests (less nodes) I don't run into this issue where it only uses diagonals. Also the functionality to go around obstacles is not implemented, so that's not what is happening.

Tarupron
  • 538
  • 1
  • 7
  • 20

1 Answers1

2

You are using integers to calculate the costs. By casting the result from the square root to an int, you are basically throwing away the significance. Casting to an int is not the same as rounding. So in this case:

getH(...): 4.9 --> 4
getH(...): 4.1 --> 4

In both situations these costs will become the same value. Use doubles to compare the costs to resolve this issue.

Related: How to cast a double to an int in Java by rounding it down?

Community
  • 1
  • 1
Erwin
  • 3,298
  • 2
  • 15
  • 22
  • 1
    +1. Or at least round values if need integers: `(int)(d + 0.5)` – Alexei Levenkov Jun 20 '14 at 00:38
  • The issue I had with leaving it as a double was that it was causing errors that I couldn't seem to fix at the time. I'll try removing the cast and reworking some of the code, thanks. – Tarupron Jun 20 '14 at 00:40