raduprv/Eternal-Lands — comment on commit 44e088623ed44711aa3f67e0fe2dad471d4ae6d0
File:  line 0
By gvissers:

>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.

Except it isn't. I Checked out a631aca69748a8d8ac88aaecf9d13144cc33db43, and added the following patch

diff --git a/pathfinder.c b/pathfinder.c
index 09c54a6..7fb50c3 100644
--- a/pathfinder.c
+++ b/pathfinder.c
@@ -44,6 +44,15 @@ PF_TILE *pf_get_next_open_tile()
}

ret = pf_open.tiles[1];
+for (i = 2; i <= pf_open.count; i++)
+{
+	if (pf_open.tiles[i]->f < ret->f)
+	{
+	fprintf(stderr, "Oops! pf_open.tiles[%d]->f = %d < ret->f = %d!\n",
+	i, pf_open.tiles[i]->f, ret->f);
+	break;
+	}
+}

ret->state = PF_STATE_CLOSED;

Apply the patch, click the map, and see what happens.

>Strange paths may be caused by the FUZZY_PATH randomness.

Of course, but that was turned off in testing.

>The heuristic should be simple, it's an heuristic after all and doesn't have to be accurate.

Well, 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.