[Refactoring]: Visibility calculation improvements

[kwvanderlinde]

Describe the problem

There's a lot of things that are suboptimal about our visibility calculations.

On the one hand there's a lot of noise and unnecessary complexity in the code that could be improved. E.g.:

• The structure of AreaTree is split up across several types despite being quite straightforward, and its logic is mutually recursive between those types.
• AreaMeta can't decide whether to be represented as an AWT Area or a JTS LinearRing.
• The visibility sweep is not encapsulated at all, but squats in FogUtil as a bunch of static methods.

There's also a lot of performance being left on the table when topology stops being trivial. E.g.:

• Building AreaTree involves an expensive brute force approach to finding parent-child relationships between islands and oceans. This is enough to cause noticeable delay when rebuilding topology trees.
• The use of JTS Geometry (including LineString and LinearRing) when it's not necessary. Geometry is expensive to use due to its generallity, but we don't need that generality and so can avoid the overhead.
• The sweep algorithm itself does a poor job of using the right tools (expensive unions to fix already valid geometry, unsorted sets for open walls, hash tables for endpoint deduplication, expensive intersection checks). This really slows things down, and for operations like "Expose last path" it can grind everything to a halt.

The improvement you'd like to see

AreaTree will use a structure that clearly shows it is a basic n-ary tree with values (AreaMeta) at each node. A single node type will suffice, and algorithms for AreaTree will be defined on AreaTree rather than its node type. AreaMeta will also be simplified to represent its region solely as a ring of Coordinate (avoiding both AWT Area and JTS Geometry), and will directly use algorithms that can operate on that representation.

The visibility sweep algorithm will be encapsulated in its own class. It will maintain appropriate data structures (sorted open walls especially) and use logic that reflects real-world situations. E.g., that we can have lots of runs of the algorithm in short proximity ("expose last path"), and that we tend to see very few endpoint duplications, a small number of open walls at any given point, and lots of far away walls completely hiding behind nearer walls (for complex topology). The algorithm will also avoid expensive operations (e.g., line intersection calculations) where cheap and precise alternatives exist.

Expected Benefits

The code will be easier to follow (if still quite specialized), and performance will get a boost for complex topologies.

Additional Context

Here is a campaign that I use to test various edge cases and performance. The map "Performance: 80x80 Cave" is a good example of some of the problems with the current implementation, even if it might not itself be typical:

With auto-expose FOW, complex geometry, and a long path to expose along, the map consistently gives timings that look like this:

Timer exposeLastPath (17 elements)
  0.   30205 ms  exposeLastPath
  1.   30137 ms  exposeLastPath-Hero
  2.     546 ms  buildAreaTree
  3.   15388 ms  FogUtil::calculateVisibility
  4.      26 ms  get vision geometry
  5.     686 ms  accumulate blocking walls
  6.   14550 ms  calculate visible area
  7.      60 ms  add bounds
  8.    1338 ms  build network
  9.    1091 ms  initialize
 10.    3810 ms  sweep
 14.       2 ms  add visibility polygon
 16.     123 ms  combine visibility polygons with vision

Sorry about the structure of the timers, I didn't make it clear what exactly belongs to what The gist of it is that ~15s of the 30s total runtime is spent calculating visibility polygons, leaving another ~15s spent in the other parts of the exposure code (constraining lit areas to visible areas, unioning exposed Area at each step, etc). I don't know what to do about the latter 15s yet, but the first 15s can be reduced significantly (about 10x) by implementing the suggested improvements.

[kwvanderlinde]

Discovered that with a simple change for smarter unions, we can reduce the last ~15s to a mere ~300ms. That will be the next PR for this issue before reworking the larger sweep reworking.