nathansttt / hog2

Pathfinding and search testbed/visualization suite. Current code is in PDB-refactor branch.
MIT License
107 stars 54 forks source link

fix a bug where IDAStar sometimes returns sub-optimal solutions #15

Closed Shperb closed 4 years ago

Shperb commented 4 years ago

IDAStar first adds a neighboring node to the path, checks if this node is a goal and if so returns is as an optimal solution. However, IDAStar did not make sure that the solution cost is not larger than the current bound, which could lead to sub-optimal solutions; this fix address that issue by adding the missing condition.