[PATCH] Stop-gap optimizations in the Vertex Pathfinder

[fsincos]

This ticket contains stop-gap measures to improve the performance of the Vertex Pathfinder before the impending rewrite (see #1942) since that will take some time to be done and tested. This can also be considered as a sub-ticket of #3588.

Currently implemented improvements:

• Clip out vertexes that are in obstructions and thus always not visible. This removes quite a lot of visibility checks in some situations (e.g. huge combat demo). The check itself is rather cheap.
• Only partially sort the edgeSquares since a full sort would be wasteful. This improves the performance in crowded scenarios by ~5%; in my testing it also miraculously improved the performance of ComputeShortPath as well (which might be due to the distance heuristic for "probability to block rays" being worse than "just use the previous order" for squares that are further away). There is some opportunity for tuning in the form of branching / length of the partial sort since I just used some reasonable threshold.

Further improvements:

• Memory: Many vectors of edges and vertexes get thrown around in the code, it could be worthwhile to reduce this memory churn.
• Handle the case where the goal is unreachable in a sane way instead of exhausting the search space (in search of wormholes?).
• Currently, the search space is a square around the start point. This could be changed to a more reasonable search space, reducing the bugs from too small search spaces (like units running circles around a blob of other units as they only "see" the ones on their side) and improving performance (less "wasted" vertexes and edges).
• "Lazy A*": Because of the ever-changing nature of the environment, it is not a good idea to follow long paths that only improve the distance to the goal slightly. This could be stopped by selecting the path end point as the point with minimal h + g*(some constant) instead of h.

[Itms]

Really nice, you only forgot to improve the conditionals with some newlines.

Instead of

if (longconditionnumberone && longconditionnumbertwo && longconditionnumberthree && longconditionnumberfour)

write

if (longconditionnumberone &&
    longconditionnumbertwo &&
    longconditionnumberthree && 
    longconditionnumberfour)

using tabs to indent and extra spaces if necessary.

[Itms]

Sorry I think my explanation was misleading: I meant

[tab][tab]if (foo &&
[tab][tab]    foo2)

(I was talking about the higher-level indentation)

[fsincos]

First patch of the series, containing Clip and Partial Sort.

[Itms]

In 18090:

Slight improvement to the short range pathfinder. Patch by fsincos, refs #3925

[elexis]

Don't forget to add yourself to programming.json with the next patch.

[fsincos]

AddTerrainEdges rewritten to not use the "segments" vectors.

[Stan]

Any input on the performance improvements of these patches ?

[fsincos]

Unit shapes are squares; use that to optimize the TestRayAASquare-based approach even further. (+style adjustments)

[fsincos]

Unit shapes are squares; use that to optimize the TestRayAASquare-based approach even further.

[fsincos]

The first patch mainly makes AddTerrainEdges look nicer. The "Squares" patch is not fully fleshed out: Some replays diverged from the original, the performance was overall unchanged or improved quite a bit (up to 15%) for the other replays. In longer games the reduced memory fragmentation seals the deal.

As the Square patch isn't ready yet, no review tag for now.

[sanderd17]

Looking at the TerrainEdges patch. Why did you take some type definitions outside the loops (like a, b, Edge1 and Edge2)? I don't think this would cause any performance gain (the compiler is smart enough), while it also doesn't reflect the scope of the variables anymore (they're only used in the loop).

[Imarok]

Move tickets to Simulation as UI & Simulation got some sub components.