Bug: Non-deterministic generation when combining SMZ3 and The Legend of Zelda

[Mysteryem]

What happened?

Generating a multiworld with a fixed seed containing both an SMZ3 world and a The Legend of Zelda world results in non-deterministic generation. Sometimes multiple generations will produce very similar results, but other times the results are very different.

Generating either world on its own appears to be deterministic, it is only when both are together. I could not get the same non-deterministic behaviour to occur with other combinations of games with either of these two worlds (including 2x SMZ3 or 2x The Legend of Zelda), only both together.

I've tested on v0.5.0 (both from source and from the Windows installation) and on what was the HEAD of the main branch at the time (925e02dca72420d94971db28c2c15c4ddd3092c2)

For each generation, I generated with template SMZ3 and The Legend of Zelda yamls, but with a meta.yaml used to disable progression balancing, they are attached as Players.zip. Players.zip

Attached are the spoiler logs for two generations ran from v0.5.0 on source with python -O Generate.py --seed 1. I'm not too familiar with what is important in these games, however, looking at the playthrough, in gen1's Sphere 2, it picks up Missile (green Brinstar pipe) (Player1): Red Candle (Player2), but in gen2 (also in Sphere 2), this is , Missile (green Brinstar pipe) (Player1): Heart Container (Player2) instead, and if it's in the playthrough, then I'm expecting it to be progression. gen1_AP_14089154938208861744_Spoiler.txt gen2_AP_14089154938208861744_Spoiler.txt

Since I can only get this non-deterministic behaviour to occur when both worlds are present, I'm not sure where to even begin looking for the cause of the issue in these worlds, so I've made this report.

What were the expected results?

Given the same seed, generation should be the same each time (progression items at least, I don't know if filler is also supposed to be deterministic).

Software

Local generation

[PoryGone]

@lordlou @Rosalie-A @t3hf1gm3nt

[t3hf1gm3nt]

I have determined at the very least that there is an issue of non-deterministic behavior in TLOZ's level 9 junk fill. Specifically with the use of random.choice here: https://github.com/ArchipelagoMW/Archipelago/blob/main/worlds/tloz/ItemPool.py#L139 as it will grab a different group of filler items even with the same seed. I will need to do a bit more testing to determine that this is the only issue, but my preliminary testing is showing that this might be the solely an issue with TLOZ and not with SMZ3, and will also come up with and PR a solution this weekend.

[ScipioWright]

I have determined at the very least that there is an issue of non-deterministic behavior in TLOZ's level 9 junk fill. Specifically with the use of random.choice here: https://github.com/ArchipelagoMW/Archipelago/blob/main/worlds/tloz/ItemPool.py#L139 as it will grab a different group of filler items even with the same seed. I will need to do a bit more testing to determine that this is the only issue, but my preliminary testing is showing that this might be the solely an issue with TLOZ and not with SMZ3, and will also come up with and PR a solution this weekend.

Instead of doing random = world.multiworld.random, do random = world.random -- that should fix it

Definitely doesn't help that SMZ3 also uses multiworld.random all over the place -- that's probably contributing to this in some fashion

[Mysteryem]

The way I identified this issue was to compare the location of all progression items between generations, so I paid no attention to filler items if that's something that's been identified as an issue.

I modified the end of the generator to output the location of every progression item and what that item is into a line in a file whose filename is unique to the combination of the seed and the worlds in the multiworld.

If the file already exists when preparing to output to it, the progression items from the current generation are compared against each line in the file and if none of the lines match the current generation, then a new line is written for the current generation.

With this setup, I could put a unique combination of template yamls in the Players folder and spin up generation with the same seed a bunch of times. If the debug output file for that combination ever had more than one line in it, then that combination of yamls had non-deterministic generation.

I used this to bisect, starting with generation that included every template yaml, until I could find which worlds were causing the generation to be non-deterministic.

[t3hf1gm3nt]

Did what I could on TLOZ's end with #3670. lordlou will still need to look into whats going on for SMZ3