-
-
Notifications
You must be signed in to change notification settings - Fork 945
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
Change: Cache stations and links for whole map for linkgraph GUI to eliminate delay when scrolling or zooming #7080
Conversation
91e883a
to
05970bd
Compare
60f8101
to
d6a23c6
Compare
Here's what the CI says:
The first section is hopefully self explanatory, the second is because the Linux/Make build system only uses -std=c++11... of which |
6ea6ccb
to
f015b94
Compare
@LordAro Sorry about the spaces/tabs issue; the OpenTTD CI wasn't responding when I pushed my code, and I forgotten about it after that. I have fixed this issue. Regarding the |
Also, prepare for more overloads of FindLastBit
This is in preparation for use by the new linkgraph GUI algorithm.
c763912
to
aa1c2ca
Compare
Added polyfill for |
e66a882
to
f40f6a4
Compare
… visible region This eliminates the delay when scrolling or zooming
f40f6a4
to
5b8f8d6
Compare
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
The data types implemented look really fishy to me. The trees don't enforce any invariants on data ordering, so how can they have lookup algorithms assuming something about data ordering?
I would think that for storing information about line segments, a classic BSP tree would be more appropriate. I can't visualise what this implementation is supposed to be doing.
template <typename T> | ||
class AreaQueryTree { | ||
private: | ||
SegmentTree<LinearQueryTree<T>> data; |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
A tree containing trees?
} | ||
|
||
/** | ||
* Resize the tree (may or may not preserve existing data). |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
That's a really vague guarantee, or lack of.
typedef std::vector<std::pair<StationID, uint> > StationSupplyList; | ||
//typedef std::map<StationID, LinkProperties> StationLinkMap; | ||
//typedef std::map<StationID, StationLinkMap> LinkMap; | ||
//typedef std::vector<std::pair<StationID, uint> > StationSupplyList; |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Don't leave commented out code. It can always be fetched from VCS history.
This introduces a whole load of new untested code to fix something very very minor. I'm not keen on it. |
This pull request has been automatically marked as stale because it has not had any activity in the last month. |
This is a replacement for #7005 that fully eliminates the need for the cache refresh delay after scrolling and zooming. It uses a 2D segment tree data structure to store a cache of the cargo flow legend for the whole map (previously, the cache only stored the stations and links that might be visible). The eliminates the need to rebuild the cache when the user scrolls or zooms around the map, so we don't need to add the additional LINKGRAPH_DELAY after those user actions anymore.
There does not seem to be any noticeable slowdown in the game when using my patch.
Note on algorithmic complexity:
LinkGraphOverlay::RebuildCache()
remains the same because insertion of a station or link into the data structure is still O(1) (assuming that we have O(1)FindFirstSet
which I can write in another PR).Note on existing lag (not caused by this patch):
The existing implementation (as well as this patch) gets noticeably jerky when the number of possibly-visible links is large. This is mainly due to the
Blitter::DrawLine()
function that is called to draw all those edges pixel by pixel. It could be alleviated in the future by doing a bit more math inLinkGraphOverlay::IsLinkVisible()
to prune a few more cases to determine that an edge is definitely off-screen (software solution, I can probably implement this some other time), or a fix forBlitter::DrawLine()
that utilizes the GPU to draw lines instead of drawing pixel-by-pixel (hardware solution, I don't know how to do this).To observe the lag mentioned above, go to https://wiki.openttdcoop.org/PublicServer:Archive_-_Hall_of_Fame and download Pro Zone Game 13 Final, then load it and enable the cargo flow legend for all companies and all cargo types.