Path Lag Partial Fix

[yeerk]

Hey,

I profiled 0ad with Very Sleepy and the following code path was causing the majority of my lag:

CCmpPathfinder::ProcessSameTurnMoves

CCmpPathfinder::ProcessLongRequests

CCmpPathfinder::ComputePath

ProcessNeighbour

(CalculateHeuristic, but it is not in the stack, as it is inlined)

isqrt64

The following patch basically eliminates this whole path from my profiles: https://gist.github.com/yeerkkiller1/b02d32c09e7f6c2685d9 .

Basically the CFixedVector2D is unnecessary, as is using any sort of sqrt. I changed it to just return the distance squared, which still appears to satisfy the constraints of the function (it is still a heuristic). I played with this a few times online with someone else that has the same change applied, and I didn't run into any issues with this change.

Lag will still occur with enough units, and the time is still spent in path finding, but the new bottleneck is inside ProcessShortRequests, ComputeShortPath, instead of ProcessLongRequests, ComputePath.

Is there a place (other than this forum) I can submit this patch for review?

Thanks!

--

yeerk

[niektb]

Trac.wildfiregames.com would normally the place to be for tickets and patches, but unfortunately you profiled the old pathfinder where there already is being worked on a new one. (https://github.com/na-Itms/0ad/tree/pathfinding?files=1)

I think it would be a better idea to contribute to that one

Edited April 5, 2015 by niektb

[Itms]

Thanks for having anwsered niektb

Indeed the new pathfinder is there on GitHub, pull requests and comments are welcome!

Thanks for your will to contribute.

[Lion.Kanzen]

Thanks for having anwsered niektb ;)Indeed the new pathfinder is there on GitHub, pull requests and comments are welcome!Thanks for your will to contribute.

forget it I see them

Edited April 5, 2015 by Lion.Kanzen

[historic_bruno]

This and similar things have been proposed many times before. The problem is you are now using doubles, which aren't safe in the simulation, it must have identical behavior on all platforms. Fixed and sqrts only appear to be a bottleneck in profilers because the overall algorithm is quite flawed. (As far as using sqrt, I can't remember off the top of my head, but I seem to recall there is a good reason for it, you should discuss it with Philip on IRC, or maybe it's buried in a forum topic around here)

[WhiteTreePaladin]

This and similar things have been proposed many times before. The problem is you are now using doubles, which aren't safe in the simulation, it must have identical behavior on all platforms. Fixed and sqrts only appear to be a bottleneck in profilers because the overall algorithm is quite flawed. (As far as using sqrt, I can't remember off the top of my head, but I seem to recall there is a good reason for it, you should discuss it with Philip on IRC, or maybe it's buried in a forum topic around here)

I also seem to remember Philip finding issues with floating point. I think Redfox tried something along these lines as well?

Edited April 9, 2015 by WhiteTreePaladin