Earlier quoted context omitted.
Zelda is not simply a single instance of a static puzzle with a well-defined solution, it has code creating things dynamically. The title implies that the NP-complete problems are part of the actual gameplay. If you're only looking at mechanics you can pick nearly any game with movement and pull out traveling salesman.
A straight up implementation of TSP (I assume you mean the decision variant) needs some kind of door that shuts with a timer. How do you plan to encode arbitrary graphs? This poses a challenge for 2d platformers. In case of any 2d game, how do you encode non-planar graphs? You would need some kind of teleportation device. A graph with few edges and large edge values will also be problematic if you plan on keeping you…
Re: Classic Nintendo Games are NP-Hard
#21Those features are nice but unnecessary. Just use planar graphs. Then you don't have to enforce single-visiting either. Limited scrolling will bound the longest edges but you don't need arbitrary edges. Only problems of a limited size will be able to fit in the limited memory of the game but that's still NP-complete over what does fit.