-
-
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: Non-rectangular sparse station catchment area #7235
Conversation
This sparse catchment area is how many players believe it already works, e.g. #7198. |
So the big issue with this is performance due to the I tested with the same savegame as with the above screenshots, using variable/modified catchment (not sparse) and world ticks jumped from 0.62ms to 1.47ms |
this is again one of those cases where we should ask "why do we even bother keeping the original version around"? also, nobody is going to understand what is meant by "sparse catchment area". |
I have to agree with Eddi: making this an option does not sound like a good idea - even when it somewhat breaks ancient savegames. Making a change for catchment area towards what is actually expected by players (and maybe making the catchment area for gathering resources the same as distributing cargo) is a desirable change. |
The option is already there, this just adds another variant. Yeah, sparse was the best word I could think of this morning :p |
I think it is a significant improvement to make catchment areas more intuitive, so keep on with this PR. I also wrote some patches for this concept of precise catchment area long ago. My code can be much better written, of course. I wrote it when I had little experience with coding. Let me explain how I got to my current implementation of precise catchment areas. The first approach I used was saving the tiles caught by a station, as I understand PeterN has done. But in the code I wrote, that lead to performance issues. In a second approach I used a bool array, and later I used a bitmap, as more experienced developers pointed out. TESTING: I have a big savegame where world ticks need 3.25 ms on original algorithm, 10ms on the PR proposed by PeterN and 3.5 ms on my branch. Anyway, my proposal may be slightly faster than those 3.5 ms, because the "bitmap" struct I use probably isn't a good one. Moreover, I think my proposal differs with PeterN's one, as it is much more restrictive trying to make catchment and delivery areas equal (see that in TriggerWatchedCargoCallbacks on houses is dealt with in my branch). So... glad someone has brought something like this to a PR. I will review it when I can. |
Urgh, turns out in improving it I ended up changing quite a few existing algorithms, so I need to figure out how to chop it up. |
b5a5871
to
b34b720
Compare
Using the Wentbourne save, the original commit suffers badly. World ticks jumped from around 2ms to 40ms, which is clearly unacceptable. The second commit adds nearby stations caching to industries and towns. This involves quite a bit of extra code, as the cache needs to be maintained, however the performance benefit over the first iteration is vast, as world ticks is around the same as in this save. |
Following our discussion in IRC I thought a bit about your station patch, but can't really suggest any good structure or algorithm here as I don't know how frequent each operation is. Have some random thoughts though:
|
On second thought, I probably shouldn't use citymania account for commenting. Even if my personal one sucks xD |
|
|
|
I think a bitset would make things easier. I have checked your PR and my branch. For big savegames, memory usage drops from 228 MB to 214 MB or from 323 MB to 311 MB. Comparing times with those savegames, PeterN PR/JJ Branch, 3.02/3.08 and 1.60/1.80. My branch although is far from efficient, as I kept the original catchment algorithms and modified catchments, and I didn't optimize it as much as PeterN current PR. So, I think a generic bitmap/bitset could be used. This is the one I used, but for sure it can be improved. |
I don't know whether this is out of scope, but I will ask anyway. On this function: |
Probably should be under the catchment tiles only. Same with the subsidy tests. |
7fe7ede
to
de284e3
Compare
Performance improvement on the Wentbourne savegame: Unmodified master: World tick is 1.9ms per game tick. |
Okay, there's an issue with station catchment somewhere, got some spurious tiles :-) |
786ea76
to
f09d2e7
Compare
I think a new building finding a new nearby station is rare enough that that the Town::stations_near.Sort() on addition will not be a performance issue. |
I haven't checked which sorting algorithm is used here (probably qsort?), but some sorting algorithms handle "nearly-sorted" lists more gracefully than others |
It's just a simple QSort. The list is already sorted before the addition. We do have Gnome sort available if that would be better. The list is generally in the order of low tens of entries, not hundreds. |
I'm actually surprised how well this patch handles a stress-test. Memory consumption is only about 2% more than master. Though it's mostly due to master itself gobbling a ridiculous amount of memory xD UPD: crash log: https://paste.openttdcoop.org/pwbjmocxr |
|
Ok, so FindStationsAroundTiles has reverted back to doing a map-scan rather than a station-scan, albeit using iterators instead of nested for-loops. It is significantly faster on games with lots of stations, and is pretty much constant speed, unless there are overlapping stations. In that case, station-scan doesn't win anything anyway. Big reason not to use station scan is we limited the area by max station spread, however this can be reduced in game after the fact, and thus we'll end up with incorrect information. |
74df881
to
42f2aee
Compare
42f2aee
to
bf1e3f9
Compare
659ba3a
to
3daef4e
Compare
I think it's time to squash most of this together, except for the first 3 commits. Yay/nay? |
Yep probably time to squash and final review. |
3daef4e
to
91ae810
Compare
4k x 4k map, high towns 100% 10x cities, very fast town growth, but no vehicles: Master world ticks: 16.91ms/t This suggests the the performance benefit of generating cargo not having to do a tile search seems to outweigh the extra cost of expanding towns doing it instead. |
91ae810
to
4d598d1
Compare
4d598d1
to
1983def
Compare
Awkwardly, this rebase effectively reimplements the neutral station handling changes in a different way. |
This also actually fixed #5661 |
This patch changes station catchment from a single rectangle covering the largest catchment radius of the station, to individual tiles based on the catchment radius of the station tiles near them.
The non-saved calculated set of catchment tiles is stored off-map within the station class. This set is then tested against when cargo is delivered to and from industries and towns.
Adds a third station catchment area option:Original fixed-size catchment area:
![catchment0](https://user-images.githubusercontent.com/639850/52896588-30950600-31c2-11e9-86f9-837d4bdb1319.png)
Modified variable-size catchment area:
![catchment1](https://user-images.githubusercontent.com/639850/52896591-32f76000-31c2-11e9-9061-72fdcb09b24b.png)
New non-rectangular sparse catchment area:
![catchment2](https://user-images.githubusercontent.com/639850/52896594-3559ba00-31c2-11e9-8b03-a23b1ce6f77a.png)