Skip to content
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

Closed
wants to merge 7 commits into from

Conversation

btzy
Copy link
Contributor

@btzy btzy commented Jan 22, 2019

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:

  • The cost of 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).
  • The cost of enumerating visible edges and stations is O(N+RC) where N is the number of possibly-visible stations/links (it is around 2x of the old implementation and the difference is not noticeable), and R*C is a small constant depending on the size of the visible region of the map (this is quite small, less than 100 even when fully zoomed out).

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 in LinkGraphOverlay::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 for Blitter::DrawLine() that utilizes the GPU to draw lines instead of drawing pixel-by-pixel (hardware solution, I don't know how to do this).

image

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.

@btzy btzy changed the title Change: Cache stations and links in 2D segment tree for linkgraph GUI, to eliminate need for LINKGRAPH_DELAY when scrolling or zooming Change: Cache stations and links in 2D segment tree for linkgraph GUI to eliminate need for LINKGRAPH_DELAY when scrolling or zooming Jan 22, 2019
@btzy btzy changed the title Change: Cache stations and links in 2D segment tree for linkgraph GUI to eliminate need for LINKGRAPH_DELAY when scrolling or zooming Change: Cache stations and links for whole map for linkgraph GUI to eliminate need for LINKGRAPH_DELAY when scrolling or zooming Jan 22, 2019
@btzy btzy changed the title Change: Cache stations and links for whole map for linkgraph GUI to eliminate need for LINKGRAPH_DELAY when scrolling or zooming Change: Cache stations and links for whole map for linkgraph GUI to eliminate delay when scrolling or zooming Jan 22, 2019
@btzy btzy force-pushed the better-linkgraph-redraw branch 2 times, most recently from 60f8101 to d6a23c6 Compare January 22, 2019 13:32
@LordAro
Copy link
Member

LordAro commented Jan 24, 2019

Here's what the CI says:

2019-01-22T19:04:57.4474968Z ##[error]*** b/src/core/linearquery_type.hpp:96: Use tabs for indentation: '     * @return The desired index into the data array.'
2019-01-22T19:04:57.4475810Z ##[error]*** b/src/core/linearquery_type.hpp:119: Use tabs for indentation: '     * @return A reference to the element at that particular index.'
2019-01-22T19:04:57.4476680Z ##[error]*** b/src/core/linearquery_type.hpp:133: Use tabs for indentation: '     * @return A reference to the element at that particular index.'
2019-01-22T19:05:32.0921071Z In file included from /home/vsts/work/1/s/src/linkgraph/../core/areaquery_type.hpp:15:
2019-01-22T19:05:32.0921875Z /home/vsts/work/1/s/src/core/linearquery_type.hpp:60:21: error: no member named 'make_unique' in namespace 'std'
2019-01-22T19:05:32.0922245Z                 this->data = std::make_unique<T[]>(static_cast<std::size_t>(1) << (size + 1));
2019-01-22T19:05:32.0922304Z                              ~~~~~^
2019-01-22T19:05:32.0922593Z /home/vsts/work/1/s/src/core/linearquery_type.hpp:60:33: error: 'T' does not refer to a value
2019-01-22T19:05:32.0922862Z                 this->data = std::make_unique<T[]>(static_cast<std::size_t>(1) << (size + 1));
2019-01-22T19:05:32.0922916Z                                               ^
2019-01-22T19:05:32.0922986Z /home/vsts/work/1/s/src/core/linearquery_type.hpp:27:20: note: declared here
2019-01-22T19:05:32.0923232Z template <typename T>
2019-01-22T19:05:32.0923280Z                    ^
2019-01-22T19:05:32.0923331Z /home/vsts/work/1/s/src/core/linearquery_type.hpp:60:35: error: expected expression
2019-01-22T19:05:32.0923781Z                 this->data = std::make_unique<T[]>(static_cast<std::size_t>(1) << (size + 1));
2019-01-22T19:05:32.0923825Z                                                 ^
2019-01-22T19:05:32.1027273Z /home/vsts/work/1/s/src/core/linearquery_type.hpp:72:22: error: no member named 'make_unique' in namespace 'std'
2019-01-22T19:05:32.1027552Z                         this->data = std::make_unique<T[]>(static_cast<std::size_t>(1) << (size + 1));
2019-01-22T19:05:32.1027626Z                                      ~~~~~^
2019-01-22T19:05:32.1027839Z /home/vsts/work/1/s/src/core/linearquery_type.hpp:72:34: error: 'T' does not refer to a value
2019-01-22T19:05:32.1028051Z                         this->data = std::make_unique<T[]>(static_cast<std::size_t>(1) << (size + 1));
2019-01-22T19:05:32.1028124Z                                                       ^
2019-01-22T19:05:32.1028166Z /home/vsts/work/1/s/src/core/linearquery_type.hpp:27:20: note: declared here
2019-01-22T19:05:32.1028205Z template <typename T>
2019-01-22T19:05:32.1028255Z                    ^
2019-01-22T19:05:32.1028295Z /home/vsts/work/1/s/src/core/linearquery_type.hpp:72:36: error: expected expression
2019-01-22T19:05:32.1028711Z                         this->data = std::make_unique<T[]>(static_cast<std::size_t>(1) << (size + 1));
2019-01-22T19:05:32.1028775Z                                                         ^
2019-01-22T19:05:32.3009423Z 6 errors generated.

The first section is hopefully self explanatory, the second is because the Linux/Make build system only uses -std=c++11... of which std::make_unique is not part of. Not sure what the proper solution there is. I have no issues with using C++14...

@btzy btzy force-pushed the better-linkgraph-redraw branch 2 times, most recently from 6ea6ccb to f015b94 Compare January 24, 2019 06:25
@btzy
Copy link
Contributor Author

btzy commented Jan 24, 2019

@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 std::make_unique, I could roll my own make_unique if C++14 is not allowed here.

@btzy btzy force-pushed the better-linkgraph-redraw branch 2 times, most recently from c763912 to aa1c2ca Compare January 26, 2019 07:29
@btzy
Copy link
Contributor Author

btzy commented Jan 26, 2019

Added polyfill for std::make_unique so it will also work on C++11 compilers that do not have C++14.

@btzy btzy force-pushed the better-linkgraph-redraw branch 4 times, most recently from e66a882 to f40f6a4 Compare January 26, 2019 07:53
Copy link
Contributor

@nielsmh nielsmh left a 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;
Copy link
Contributor

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).
Copy link
Contributor

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;
Copy link
Contributor

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.

@PeterN
Copy link
Member

PeterN commented Feb 23, 2019

This introduces a whole load of new untested code to fix something very very minor. I'm not keen on it.

@stale
Copy link

stale bot commented Mar 25, 2019

This pull request has been automatically marked as stale because it has not had any activity in the last month.
Please feel free to give a status update now, ping for review, or re-open when it's ready.
It will be closed if no further activity occurs within 7 days.
Thank you for your contributions.

@stale stale bot added the stale Stale issues label Mar 25, 2019
@stale stale bot closed this Apr 1, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
stale Stale issues
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

4 participants