Decouple FoV calculation from map size.

[kevingranade]

Somewhat related to #22620 FoV calculation dominates game overhead in many circumstances, and is the primary reason that active maps size (the,"reality bubble") is limited. If FoV calculation is decoupled from active map size by being related to the current viewport instead of the current map, it yields several positive effects:

1. Active map size can be increased, scaling factors from this other than FoV calculation are not optimised, and are likely to have large amounts of low hanging fruit. In practical terms, growing the active map to double or more of its current radius should be feasible.
2. Players with slower computers should be able to utilize a smaller viewport to decrease CPU utilization by culling FoV overhead, the game could even detect slow FoV calculation and recommend this as a fix.

This is a technically simple change, but requires a large number of code edits to break the cross-dependencies between active map handling and viewport rendering.

[Dyrewulfe]

@kevingranade Point me where to start on this, and I'll do the grunt work. I have nothing but time of late.

[kevingranade]

The map class has a number of drawing methods and a number of build_*_cache methods, along with supporting members and methods. Extract these to a new class (maybe named map_viewport?) that is a member of game. There's quite a lot of cleanup that probably needs to happen around this, where random bits of the map class have dependencies on the cache data, and there needs to be a solution for the viewport refresh code reading data from the map class.

Once they're separated, we can start experimenting with enlarging the map area without enlarging the viewport.

[Dyrewulfe]

Okay... I've been looking this over, and considering the issues involved. The decoupling of the reality bubble from the player's view range is simple enough.

But, it seems to me that reducing the overhead for building FoV information is not so simple. We have UI elements in place which rely on visibility information involving the player's real view distance, like the creature compass and pixel minimap. And commands like listing the visible items/monsters('V'). That leaves us with reducing the player's actual viewing distance, or... What if we shift the responsibility for updating visibility information to the objects that affect it, and provide a map cache class with an interface to call in to? A lot more work would be involved to accomplish this, but the return on investment would be far greater.

Benefits:

1. • Static visibility cache, rather than recalculating the full FoV every turn.
2. • Potential to delay full calculation of elements outside of the player's visible range. Each point in the cache needs merely to store a list of objects to call back to if the location comes within visible range.
3. • Building from point 2, we gain support for long range sight effects, like using rifle scopes or binoculars/telescopic eyes in an active fashion.
4. • Potentially, we can allow for loading submaps on an as needed basis, outside of our reality bubble range.
5. • We can further reduce visibility calculation overhead by only updating objects on an as needed basis using the object callback list. E.G. - Upon removing a wall, update the lights that affected the location(and can further cull this by only updating the vectors the location obstructed.)
6. • In regards to Tiles, having a static cache of this nature will allow for optimizing terrain drawing and sprite memory usage in ways that would currently be ineffective.

And there may be other benefits I haven't thought of.

[Dyrewulfe]

Actually, thinking further about 6, we can optimize terrain drawing overall(console and tiles), since we'd be able to cache the drawn terrain, and redraw only changed points. Then we just pull a slice of that to draw to the terrain window.

[kevingranade]

The reason we need a precalculated cache for the drawable area is that the draw code makes these lookups in very high volumes, if we need to spot check a few things like which monsters are visible, we can just "draw a line" to just those monsters at a much lower cost than extending the cache to a larger area.

[kevingranade]

The above approach suffices for the compass, because we can just short-circuit, we only need to find one monster of a given type per quadrant then we can terminate early. As the number of monsters grows, the chance of spotting them is similarly large, so we should be able to spot them quickly and stop looking.
The V menu can operate with some combination of restricted range and terminating early when there are many monsters or items of the same kind in a given area.
The minimap has the same input requirements as the drawable area and can't terminate early, it must be limited in size, and the viewport size will be the union of the drawable and minimap areas.

As for caching, this approach has a fatal flaw, which is that the most common cause of FoV invalidation, player movement, invalidates the entire FoV. No matter how sophisticated your caching behaviour is, you still end up triggering a full invalidation and regeneration of the FoV on any turn in which the player moves.

[Dyrewulfe]

The majority of the workload involved in the FoV is from constantly rebuilding the light map. Calculating the player FoV is only a small part of that.

Cycle estimation for build_map_cache:

I'll work on some concept drawings and maybe a diagram of what I'm suggesting this evening.

[kevingranade]

You need to profile the release build, gnu_safe_iterator wrecks profiling.

[github-actions[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions. Please do not bump or comment on this issue unless you are actively working on it. Stale issues, and stale issues that are closed are still considered.