{"comment":{"position":null,"created_at":"2011-10-10T08:47:40Z","body":">The open list was implemented a binary heap and it doesn't have to be sorted. The way nodes were added and removed made sure that the smallest item is always on top. So the best node is ALWAYS chosen. \r\n\r\nExcept it isn't. I Checked out a631aca69748a8d8ac88aaecf9d13144cc33db43, and added the following patch\r\n\r\n    diff --git a/pathfinder.c b/pathfinder.c\r\n    index 09c54a6..7fb50c3 100644\r\n    --- a/pathfinder.c\r\n    +++ b/pathfinder.c\r\n    @@ -44,6 +44,15 @@ PF_TILE *pf_get_next_open_tile()\r\n     \t}\r\n     \r\n     \tret = pf_open.tiles[1];\r\n    +for (i = 2; i <= pf_open.count; i++)\r\n    +{\r\n    +\tif (pf_open.tiles[i]->f < ret->f)\r\n    +\t{\r\n    +\t\tfprintf(stderr, \"Oops! pf_open.tiles[%d]->f = %d < ret->f = %d!\\n\",\r\n    +\t\t\ti, pf_open.tiles[i]->f, ret->f);\r\n    +\t\tbreak;\r\n    +\t}\r\n    +}\r\n     \r\n     \tret->state = PF_STATE_CLOSED;\r\n     \r\n    \r\n\r\nApply the patch, click the map, and see what happens.\r\n\r\n>Strange paths may be caused by the FUZZY_PATH randomness.\r\n\r\nOf course, but that was turned off in testing.\r\n\r\n>The heuristic should be simple, it's an heuristic after all and doesn't have to be accurate.\r\n\r\nWell, technically, the Manhattan heuristic used does not guarantee an optimal path, since it overestimates the cost. It may be faster, though, I should do some measurements. And perhaps I should also bring some form of binary search back, since the current implementation is rather slow on large maps.\r\n\r\n","line":null,"commit_id":"44e088623ed44711aa3f67e0fe2dad471d4ae6d0","updated_at":"2011-10-10T08:47:40Z","url":"https://api.github.com/repos/raduprv/Eternal-Lands/comments/640787","id":640787,"path":null,"user":{"avatar_url":"https://secure.gravatar.com/avatar/c6b360d7b33316e467a691a7d93ff36d?d=https://a248.e.akamai.net/assets.github.com%2Fimages%2Fgravatars%2Fgravatar-140.png","url":"https://api.github.com/users/gvissers","id":1096355,"login":"gvissers"}},"legacy":{"commit":"44e088623ed44711aa3f67e0fe2dad471d4ae6d0","comment_id":640787}}