Solvability test automation

[SmashManiac]

I was playing on v7 Casual seed C6433259 and realized that the seed was impossible only after I got stuck playing it for hours. (See issue #266 for details.) To my surprise, the spoiler log revealed that the Complexity Analysis also got stuck with the same set of items as I did.

Considering this, and considering that testing all possible randomization combinations is realistically impossible, I suggest to augment the Complexity Analysis to also be an automated test case that verifies the seed's solvability, with a failed test returning a friendly error message to the user, and potentially reporting the bad seed automatically.

This way, even if there was a bug in the randomization process, it would prevent users from playing through a bad one, and related bugs could be found and reported more quickly. It would also allow bulk seed generation to be a good sanity check before release.

I'm not sure what are the exact conditions to beat a seed, but I believe it should check if Agahnim 2 is always reachable and if necessary items to beat both him and Ganon are also always reachable.

[Radagast81]

The solvability test in the complexity analysis is fearly simple, just check if the set of unreachable locations is empty after the calculation. But I think this check is unnecessary as it uses the same checks as the randomizer itself does so normally that should not detect if a seed is beatable cause it should have the same bugs as the randomizer itself. The problem is, as I already mentioned earlier, that the association of a key can invalidate an already assocatioted item location. So distribution of the keys first would solve these kind of problems and the check with the complexity analysis will become redundant.

[SmashManiac]

I don't think it's that simple. It is possible in theory to distribute items is a way that makes some locations completely inaccessible, and yet have the game beatable. It happened to me in the past, and the idea of ensuring access to all locations was rejected in issue #164.

If the randomization code and the Complexity Analysis code is shared too closely, then I suggest instead to write a completely separate solvability algorithm for QA purposes.

On an unrelated note, I like the idea of distributing items in a way that prevents invalidating other items' placements, but I don't think distributing keys first would solve that problem as I believe it would result in another potential invalidation problem. I think you can only reliably do such a thing by placing items from start to finish or from finish to start, not selectively.

[Radagast81]

But that is exactly the way the randomizer works, it takes one item after another and puts it on a location that is accessable with the items you can get until to that point. The key problem is, that in some of the checks, that a location is accessable there is negation in the check equation. So when the accessable check for location A = location B contains NO key and you first assign a item for location A and then the randomizer puts a key in location B that results in location A is no longer accessable. And that is the thing that is just happening. So the first idea could be to permit all negations in the check equations. Which is possible but will lead to very long and unmantainable check equations. There are some equations that allready belong to this type. So i'm just saying there are better methods to get that to work. (The only parts of the check equations that are negated are the key containment checks...) And due to issue #164 that only considers that some keys are not reachable in the seed, if you would have get blocked from another item, then the logic would have been adapted cause in that location could also have been a key item that you needed to finish the seed. So as the randomizer puts all key items into location that you are supposed to get access to, all the check for the location will pass and therefore all locations are theoretically accessable. So the check for solvable is simply check if the set of unreachable locations is empty.

[SmashManiac]

Closing issue, as I'm come to realize the only proper way to do this is to have a bot perform a playthrough.