[PATCH] Inconsistencies in the hierarchical pathfinder

[mimo]

There are several problems in the RegionNearestNavcellInGoal function of HierarchicalPathfinder.cpp. Here are three points which should be improved, the first one preferably before A19.

1 - i0 and j0 are arguments of the function, used to compute the distance. But lines 239 and 241 redefines them, and it is these modified values which are used to compute the distance in the block containing line 250. This could lead to wrong paths.

2 - i do not know exactly how this function is supposed to work, but the code is really weird: a) either each case is supposed to apply only for each goal, and then some break statements are missing. b) or it is a wanted behaviour, but then the case CIRCLE/SQUARE is completely useless as fully contained in the following case and it then only results in additional useless calls to NavcellContainsGoal.

3 - performance improvment: this function is currently one of the most time consuming functions because it calls really a lot goal.NavcellContainsGoal. Understanding the point 2 should already improve it, but still the test on dist2 is certainly much faster than the call to NavcellContainsGoal. Interverting the order of these tests i.e. calling NavcellContainsGoal only if (dist2 < dist2Best) should improve the timing (note that testing on the distance first may make the case CIRCLE/SQUARE of case 2-b useful for performance reasons).

To understand point 2, we need some input from somebody knowing this code and will have to wait for after a19, but points 1 and 3 are fixed in the attached patch which i propose to commit now. With only the part of the fix concerning point 3 so without any change on the hash, and testing on a 4 Ai non visual replay with 2000 turns, the RegionNearestNavcellInGoal goes from 8% to 5% of the time (the original one called 80 millions time NavcellContainsGoal while the new one calls it 38 millions time).

[mimo]

after discussion with wraitii on irc, it happens that option 2-a is the intended one. Adding the missing break, the number of calls to NavcellContainsGoal drop to 1.2 millions and RegionNearestNavcellInGoal now represents only 1% of the replay time. I will commit this full patch then.

[mimo]

In 17284:

fixes and performance improvements in hierarchical pathfinder, fixes #3621