[PATCH] Long range pathfinder performance improvements

[kanetaka]

What I did are:

• Improving heuristic cost calculation. The original uses Euclidean distance, so I replaced it by the combination of sqrt(2) and sqrt(5).
• Modifying cost calculation, which seems inaccurate.
• Skipping back-step. The original expands 4 directions for search tiles, but it is obvious　that one direction is back-step thus the cost calculation is unnecessary.

To check my improvements, I added some profiling code in both the original and my patch and I have both codes run with replay mode. The commands.txt is from 1 human vs. 1 AI player's match. The result is:

HRT: using name=TSC freq=1796000000.000000
HRT: counter=TSC freq=1.796e+009 res=5.56793e-010 bits=64

Original
tc_OpenPath: 1093.98 Mc (770194x)
tc_CalculateCostDelta: 191.323 Mc (2863173x)
tc_CalculateHeuristic: 446.927 Mc (863035x)

My patch
tc_OpenPath: 759.306 Mc (819498x)
tc_CalculateCostDelta: 122.711 Mc (2251315x)
tc_CalculateHeuristic: 46.2818 Mc (914242x)

tc_OpenPath is the section in CalculatePath. All modified parts are called within that section. Over 300Mc performance improvement is measured. Although this change is less than a second for the replay, at least it doesn't worsen performance.

The number of invoking CalculateCostDelta is about 3/4 times fewer by eliminating back-step.

The performance of CalculateHeuristic is about 10 times faster.

[kanetaka]

First patch doesn't have proper path so I remake it.

[Niek]

I think that the devs rather want to wait for the redesigned pathfinder (on which wriatti is working)

[kanetaka]

Replying to niektb:

I think that the devs rather want to wait for the redesigned pathfinder (on which wriatti is working)

Oh good news! Will that new pathfinder be coming soon? I am looking forward to see that.

[leper]

Also you are using floats in simulation code. That will not work as floating point calculations can yield different results on different machines (or even the same machine with different compiler settings). (Same for #2725).