Here is what it looks like: https://www.youtube.com/watch?v=yWNGWrZ8wec

How do they deal with the linearity of Zelda games, where you NEED a certain item to succeed in a dungeon, before you can then get access to more items later? If I need the hookshot to pass the water temple, but it gives me the floating-light-boots, how am I supposed to beat the level?

Not an expert on how they do it, but I've played a few. The logic in these things is excellent, they won't ever give you an unsolvable game (and the Zelda ones have been playtested to death at this point). I think they just specify the prerequisites for each item and then just don't assign them if they are impossible to get, not sure how exactly the algorithm works but I can think some easy ways on how solve this problem once you have that list of dependencies.

You can still get the wrong items in the temple of course, it just means it's outside the temple. Sometimes you even have to go into a temple you can't beat, get an item from a chest, which allows you to get the required item outside, which then finally allows you to beat it.

Essentially there is a couple of state machines for area access and the conditions/items that enable access.

So within each subarea the candidate items can be distributed.

Now, if they could randomize dungeon maps in the original zelda...

>Now, if they could randomize dungeon maps in the original zelda...

They do, and have for some time.

As others have noted, the logic is designed as such that it's always possible. It's a graph theory problem, although I don't know if it's coded that way or just a giant pile of if/else.

One interesting thing to note is that some of them have difficulty settings. Certain item dependency chains are more difficult than others, and the locations can be done such that it will always give you easy seeds or always give you hard seeds. Some of them are designed such that you'll always be required to do speedrun tech which are borderline exploits.

Some are graph based, some aren't. ALttP was a giant pile of if/else last time I checked the logic, which makes adding new modes a bit complex.

They program it to be winnable. There are various constraints which ensure the game can be beaten. None of them (that people actually play) are 100% random.