[1.0.12.9] Possible cause of MP descync: RNG from table.sort() in map generation

[Scrum Lord]

Based on code inspection (and some unexpected results while debugging a map script) I found what looks like a possible root cause of multiplayer desyncs: map generator calls to table.sort() on lists that have ties combined with RNG in the sorting algorithm itself.

For context, here is an earlier discussion on why any RNG other than official Civ-seeded RNG is bad for multiplayer games:
https://forums.civfanatics.com/thre...-scripts-in-multiplayer.626600/#post-14981091

Now to explain how table.sort() relates to this and could potentially cause problems:

1. Lua's built-in table.sort() algorithm is quicksort (lua.org) (not sure if 5.3.x is the exact lua version that Civ 6 uses, but it seems close)
2. The quicksort alrgorithm requires arbitrary pivot values, and the Lua 5.3.6 implementation mentioned above may use RNG to choose pivots for sufficiently large arrays.
3. Any table that contains ties, as in two or more elements that are equal to each other, can be sorted into multiple valid outputs.
4. Therefore calling table.sort() with a large enough array that has ties results in a table that is at least partially randomized, since the result may be one of multiple valid outputs determined by RNG.

Tying this back to map-generator code (looking at latest GS code from Apr 2021 Game Update / 1.0.12.9): ResourceGenerator.lua alone has seven calls to table.sort(), four of which pass in a list of locations on a map and a comparator that allows ties. I also found similar calls in NaturalWonderGenerator and AssignStartingPlots (just search for "table.sort").

For example, one call at function ResourceGenerator:__PlaceStrategicResources(eContinent) at L621 sorts through all valid locations for each strategic resource type and sorts them by score :

table.sort (self.aaPossibleStratLocs[row.ResourceIndex], function(a, b) return a.Score > b.Score; end);

If there is a tie then the order of the strategic resource locations list (self.aaPossibleStratLocs[row.ResourceIndex]) is no longer deterministic. And since not all locations in the list are chosen, then the locations of resources on the map become non-determinstic too. This means that players in a MP game running the exact same map settings and seed could potentially get maps with resources in different places.

Has anyone else noticed any inconsistencies in things like natural wonder placement, resource placement, and starting locations? This seems like a bug that could exist in many places in the base game Lua as well as map mods and map scripts.

Suggested fix: pass-in a comparator that uses a unique field such as an ID or database index to break ties so that only one valid outcome is possible for table.sort().

EDIT: I forgot to mention that I also found calls to table.sort in CoastalLowlands.lua (L110, choosing which tiles to mark for inland flooding) and MapUtilities.lua (L867, placing ley lines for Secret Societies).

 

[Gedemon]

interesting find.

I had some desyncs when testing my overhaul in MP, but then I'm surprised I just had a few, I would have expected more, using sort on relatively large tables multiple times each turn. Or maybe they were still under the limit, IDK.

just a side note, Civ6 use Havok Script, for which I never found any documentation, except for marketing the tool, I would have loved to be able to use the debugging tools they mention there.

 

[Scrum Lord]

I had some desyncs when testing my overhaul in MP, but then I'm surprised I just had a few, I would have expected more, using sort on relatively large tables multiple times each turn. Or maybe they were still under the limit, IDK.

Whether you get a desync also depends on what you do with the sorted tables. In the case of the resource generator example that I mentioned above, you would only see a desync if the cut-off for placing "enough" copies of the resource happened between two equal elements in the locations list. Not sure what the exact probability of that happening would be.