-
Notifications
You must be signed in to change notification settings - Fork 259
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
[Refactoring]: Visibility calculation improvements #4506
Labels
code-maintenance
Adding/editing javadocs, unit tests, formatting.
performance
A performance or quality of life improvement
Comments
kwvanderlinde
added
performance
A performance or quality of life improvement
code-maintenance
Adding/editing javadocs, unit tests, formatting.
labels
Nov 29, 2023
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. |
This was referenced Jan 11, 2024
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Labels
code-maintenance
Adding/editing javadocs, unit tests, formatting.
performance
A performance or quality of life improvement
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.:
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 AWTArea
or a JTSLinearRing
.FogUtil
as a bunch ofstatic
methods.There's also a lot of performance being left on the table when topology stops being trivial. E.g.:
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.Geometry
(includingLineString
andLinearRing
) 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 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 forAreaTree
will be defined onAreaTree
rather than its node type.AreaMeta
will also be simplified to represent its region solely as a ring ofCoordinate
(avoiding both AWTArea
and JTSGeometry
), 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:
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.The text was updated successfully, but these errors were encountered: