I do actually think Zelda has higher <i>human</i> computational complexity than Mario (specifically, than Super Mario Bros; Mario 64 has a small degree of such complexity).  In adventure games and &quot;Metroidvania&quot; games, when you discover a new item or ability, you have to think about everything you&#x27;ve seen and what new places and areas that item or ability may open up; they&#x27;re not just non-linear in the &quot;find where to go next&quot; sense, but in the sense that you can go many places.  And that doesn&#x27;t just map to the classic &quot;colored keys open matching doors&quot;, either, because obstacles in the world don&#x27;t always seem like obvious &quot;doors&quot;, and which items will help you progress doesn&#x27;t always look obvious either when well done.  Some games make it more blatant, blocking the way with something that clearly has only one solution, but other games reward exploration and allow &quot;sequence breaking&quot;, or at least don&#x27;t prevent it.<p>Zelda&#x27;s main quest tends to have a lesser degree of this in practice; often it falls back on &quot;use the item you just got in this dungeon to progress in this dungeon&quot;.  And some games take it too far in the other direction, leading to the adventure game trope of &quot;poke everything with everything else until something happens&quot;.  But a good balance rewards players who remember huge parts of the world and reason about what could help them progress.