[Refactoring]: Improvements to visibility calculation for large and complex geometry

[kwvanderlinde]

Describe the problem

The algorithm in FogUtil::calculateVisibility() has many inefficiencies that become noticeable when map topology gets complex.

• All faces (with the correct direction) are considered candidates for blocking vision. These need to be sorted and each potentially contributes a shadow. So the visibility calculation suffers when there are many of these faces.
• The algorithm relies heavily on the creation of shadow geometries, and unions them all together to produce a final complete shadow. Each shadow is fairly cheap to create, but when there are many the union operation contributes a fair amount of running time. Although the algorithm limits the number of these shadows by checking if the faces are already contained in a shadow, this is an imprecise check and fairly expensive (though still a net win).
• The algorithm manipulates our AWT-based types (such as Point2D and AreaFace) only to produce JTS geometry in the end. JTS geometry is generally more efficient, and any conversion from one to the other is also a point of inefficiency.

The improvement you'd like to see

There are a few main ways I see to improve the visibility calculation:

1. Limit the VisibleAreaSegments to only those within the token's range of vision. Also, cut out individual faces within a segment that lie outside of vision.
2. Use a different algorithm that can build the visible area without creating lots of geometry. E.g., the "Wall Tracking" algorithm can produce the visible area as a single polygon without having to union many other geometries or subtract the result from the total vision.
3. Rely more heavily on JTS. E.g., we can avoid VisibleAreaSegment/AreaFace in the algorithm and instead work on LineStrings. Then we can rely on that JTS geometry to perform the intersection checks needed for (1).

Expected Benefits

There are some significant performance gains to be had in the presence of large and complicated topology, and even with not-so-complicated topology.

E.g., an experimental implementation of improvement (1) brings the test case time down from ~21 seconds to ~13 seconds. Improvements (2) and (3) look like they may bring that down further to ~10 seconds. That sounds like a lot, but most of the remaining time is spent elsewhere, specifically in the Area unions performed to reveal all the FoW along the path.

Additional Context

Here is a test map which demonstrates a cave system (complicated topology) with a token with darkvision (limited range): 80x80 Cave.zip

A simple test case is as follows:

1. Import the test map.
   • Reset all fog when prompted.
2. Drag the Hero token way up to the marker token north of it.
   • This should make a path of length 2000.
3. Observe the time taken to move the token
   • Can verify by opening the performance log and checking the time listed for exposeLastPath-Hero.

I am getting a consistent result of ~21.2 seconds with the current develop code.

[cwisniew]

@kwvanderlinde, if you are thinking of exploring option 2 feel free to take any code you want from https://github.com/cwisniew/visionmock

I had started it as a test to see if we could implement the map in JavaFX canvas, but that was quickly abandoned due to how slow the JavaFX draw calls were at that point in time. The non-JavaFX stuff runs reasonably well for not being optimised (there was no point since the JavaFX drawing was more than 95% of the time taken). No library is used for intersection calculation, so it will introduce no dependencies (well, it does use JavaFX Point2D to store vertex information, but that is trivial to replace)

[kwvanderlinde]

Thanks @cwisniew, I'll ake a look at it.

[Phergus]

Tested. Significant improvement.

MT 1.12.0 alpha 1
Timer exposeLastPath (1 elements)
0. 8483 ms exposeLastPath-Hero

MT 1.11.5:
Timer exposeLastPath (1 elements)
0. 16147 ms exposeLastPath-Hero