Fix for desync related to trees

[ceeac]

This patch fixes a desync which may occur when processing a tile that contains a tree that is about to die and a tree that is about to spawn new trees. The order in which both trees are processed is essentially random so it is possible for one tree to be deleted on the server while it is still present on the client. To reproduce the desync:

• set max_no_of_trees_on_square=5 in simuconf.tab
• Start a paused server with the yoshi test map
• Connect to server with a client

If the desync does not occur after a few seconds, restart the server and reconnect the client to the server.

I think the only way to fix this is by storing tree offsets in the save again, even though this makes server saves significantly larger.
I tried to counter this increase by pooling desc names of trees - the names of tree descs are stored separately instead of with each tree. However, server saves with this patch are still ~20% larger on average compared to before.

The patch also increases the save game version.

[Dwachs]

Good catch!

Two questions:

1) Why did you move tree loading to baum.cc? Leaving it in boden.cc would save one byte per tree for obj-id for saving/loading in obj_list. If because of private member variables, then a new method rwdr_lean in baum.cc could do the trick.
2) Also why these computations with xoff/yoff? It think saving these two bytes and restoring them after call to constructor would be enough.

[prissi]

Server and client always have the same pak, otherwise they desync anyway. So the id to names exercie is not needed; in the worst case just another type of tree would appear in loading an old server game in a newer pak server or an offline client. For a server with "legal" client, the tree ids should be identical.

Since the only problem is the offset, how about using the id and the current age instead of the pointer? Those two are deterministic and should always give similar offsets. Furthermore, the age is already random. So replace Line 264 in baum.cc by

Code Select Expand

const sint16 random = (sint16)( get_pos().x + get_pos().y + get_pos().z + slope + geburt + tree_id );

With this all desync seems gone. Now identical trees born in the same month gets similar offsets; but that probably rather happens very rarely.

EDIT:
To be precise: Out of 310384 trees in the yoshi map it concerns only 95 trees. SO one can ignore this entirely and keep the savegame size as it is now.

EDIT 2:
I commited the above line as r9954. It would appreaciate, if you could test that I was not just lucky for my 15 tries.

[Mariculous]

How does this affect the tool_plant_tree_t?
In that case there will be many trees generated in the same mmonth.

[prissi]

Unless there is a default parameter, yes, indeed. Although random trees are spawned, and thus these will has different offets. But I think there should be a random age for this tool anyway without a default parameter..

[Mariculous]

There are some paksets out there with a rather low variety of trees (per climate).
Although not exactly correct, slightly randomising the age seems fair to me.

Another consideration: Why is the hang/slope involved in this? Shouldn't the coords be enough to have different patterns on different tiles?

[prissi]

The slope does not hurt, but is not really needed. (Ok, it is needed to calculate the actual offset down in the function.) Actually one could have a better pseudorandom function which could involve the slope.

[ceeac]

Hm, if tree offsets can be recalculated from the remaining tree properties, I think we can avoid having to save the offsets in the save game also for clients. In addition to reducing the save size this would be one step closer to byte-equal client and server saves which would help with checking for desyncs.

[prissi]

Indeed, this is possible.

[ceeac]

Here is a patch with the changes for r10078. I have included the id <-> desc name mapping because it is required if you want to open the save with a new pakset version. For the same reason this is also enabled for servers (i.e. from now on you can load old server games with new paksets and trees will be migrated automatically via compat.tab).

Results for the yoshi save (in kB):

	trunk	new	change
binary	23112	18240	-21%
xml	202892	157948	-22%
zipped	4608	3344	-27%
bzip2	3120	2604	-16%
zstd	4244	3116	-27%

[prissi]

Thank you very much. I think you can submit yourself. But please defer to bumping the actual savegame version yet, this is usually done shortly before a release only. (You can bump the server savegame version though, since this is only used on autosave and servers.)

[ceeac]

Okay, submitted as r10080.