Opened 19 months ago

Last modified 19 months ago

#3925 new defect

[PATCH] Stop-gap optimizations in the Vertex Pathfinder

Reported by: fsincos Owned by:
Priority: Should Have Milestone: Backlog
Component: UI & Simulation Keywords: pathfinding
Cc: Patch:

Description

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.

Attachments (4)

Clip.patch (2.3 KB) - added by fsincos 19 months ago.
First patch of the series, containing Clip and Partial Sort.
TerrainEdges.patch (6.8 KB) - added by fsincos 19 months ago.
AddTerrainEdges? rewritten to not use the "segments" vectors.
Squares.patch (13.2 KB) - added by fsincos 19 months ago.
Unit shapes are squares; use that to optimize the TestRayAASquare-based approach even further. (+style adjustments)
Squares.2.patch (7.1 KB) - added by fsincos 19 months ago.
Unit shapes are squares; use that to optimize the TestRayAASquare-based approach even further.

Download all attachments as: .zip

Change History (12)

comment:1 Changed 19 months ago by 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.

comment:2 Changed 19 months ago by 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)

Changed 19 months ago by fsincos

Attachment: Clip.patch added

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

comment:3 Changed 19 months ago by Itms

In 18090:

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

comment:4 Changed 19 months ago by Itms

Keywords: review removed

comment:5 Changed 19 months ago by elexis

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

Changed 19 months ago by fsincos

Attachment: TerrainEdges.patch added

AddTerrainEdges? rewritten to not use the "segments" vectors.

comment:6 Changed 19 months ago by stanislas69

Any input on the performance improvements of these patches ?

Changed 19 months ago by fsincos

Attachment: Squares.patch added

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

Changed 19 months ago by fsincos

Attachment: Squares.2.patch added

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

comment:7 Changed 19 months ago by 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.

comment:8 Changed 19 months ago by 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).

Also, while improving performance on a piece of code that should be ripped out is already highly questionable, making such code "look nicer" is even more questionable.

Last edited 19 months ago by sanderd17 (previous) (diff)
Note: See TracTickets for help on using tickets.