Codechange: Don't store tree counter in the map array

[ldpl]

Motivation / Problem

Trees add a lot of entropy to the map array drastically increasing the size of the save file.
According to my estimations, this change decreases the size by 10-15%.

Description

The tree counter is just used to determine each 8th or 16th call to the TileLoop_Trees and that can easily be done without storing it in the map array. I plan to do some follow-up tree patches but this one is so free I decided to PR it separately.

Limitations

It does change the order in which tiles are processed in the tile loop so it's not a perfect replica but it's ok as the rate is still the same. Regression tests had to be updated though as the random state blew up.

Checklist for review

Some things are not automated, and forgotten often. This list is a reminder for the reviewers.

• The bug fix is important enough to be backported? (label: 'backport requested')
• This PR touches english.txt or translations? Check the guidelines
• This PR affects the save game format? (label 'savegame upgrade')
• This PR affects the GS/AI API? (label 'needs review: Script API')
  • ai_changelog.hpp, gs_changelog.hpp need updating.
  • The compatibility wrappers (compat_*.nut) need updating.
• This PR affects the NewGRF API? (label 'needs review: NewGRF')
  • newgrf_debug_data.h may need updating.
  • PR must be added to API tracker

[2TallTyler]

If I understand this correctly: Instead of keeping track of when each tree should grow based on a random initial counter, we randomly pick trees to grow and assume that the result is approximately the same? Trees also have a growth/density state, which is not affected.

Is that correct?

[2TallTyler]

From a discussion on Discord:

@2TallTyler:

JGR It looks like you cherry-picked #10018 for your patchpack — does it do what the tin says? Any oddities to report? 🙂

@JGRennison:

It does what it says on the tin, there's nothing wrong with it that i can see
I haven't made any actual measurements of savegame sizes, however
There isn't any observable change in tree behaviour

...

@ldpl:

tbh randomization in 10018 is kinda temporary and can be improved but I doubt anyone would notice that anyway

@PeterN:

I would :p

@ldpl:

only if you're looking for it on fast forward :p
just don't say it changed in the changelog xDD
or, whoever has fast pc can can try to find some decent looking primes for lcg :p

@PeterN:

I find it odd to consider changing behaviour purely to decrease savegame size. 🤷

@ldpl:

I find it odd to store random values in the savegame :p

...

Based on my understanding of how trees currently work and how this changes that, I think this PR is a worthwhile change. If we can get the same results without bloating the savegame with unnecessary noise, we should. I imagine it would most benefit people joining network games with large maps, which is a known issue. Most network games don't have trees for this very reason.

That said, if the current randomization is "kinda temporary and can be improved" let's wait for that before we merge. 😄

[ldpl]

It was temporary in a sense that I planned more entropy reduction patches for trees that would need a better random/hash anyway. Unfortunately, circumstances changed so I probably won't return to that work for a while.

In any case, this is a fine (and simple) change on its own. Also, I improved hash a little bit so now I can't see any pattern whatsoever even on fast forward. Btw, keep in mind that tile loop adds its own randomization on top of this.

[2TallTyler]

Sure, fine by me. Except it doesn't build now. 😉

[PeterN]

It isn't (and cannot be) the same result, but it might be close enough.

As the usage of the map array has changed, it might be desirable to bump the savegame version and clear the existing data on existing maps, and ensure those bits are cleared when creating tree tiles, otherwise the benefits only appear for new maps.

[rubidium42]

There's an interesting behavioural question to answer here. Should the grass grow or not?
With this setting on 'no growth and no spread', it previously disabled it for about 87.5% of the tree tiles, and it introduced an 8x speed up for the remaining 12.5% of the tiles. Since either the treeCounter & 7 is actually 7 and it triggers every time because the tree counter does not get updated, or it never triggers as (again) the tree counter does not get updated.

As it stands now the grass is now allowed to grow for 100% of the tiles. If grass should not grow like on 87.5% of the tiles previously, then this check needs to be moved up to just after AmbientSoundEffect(tile);.

[ldpl]

I'd say it was introduced in #8415 accidentally so this fixes it. Even though non-growing grass is an interesting feature to have doing that only under the trees is a bug. Also, idk what 87.5% you're talking about, I just tested and no grass grows under trees in 13.0.

[michicc]

Sure you want this savegame version? Last is (since not long) now SLV_LINKGRAPH_EDGES (with a wrong comment).

[rubidium42]

Technically it should indeed have been SLV_LINKGRAPH_EDGES, but given the speed the two savegame versions after SLV_MULTITRACK_LEVEL_CROSSINGS got added to master, I doubt there are many (if any) savegames that are made between NewGRF road stops got added and this was merged. So, in the grand scheme of things it does not really matter.
I fixed the comment with #10471 by just squashing that tiny change into the same savegame version. Similarly, technically not the right thing to do, but essentially harmless.