论文标题
塞尔达传说：力学的复杂性
The Legend of Zelda: The Complexity of Mechanics
论文作者
论文摘要
我们分析了Zelda系列视频游戏的经典传奇人物中可用的众多游戏机制中的一些。在每种情况下，我们都证明具有该机械师的广义游戏是多项式，NP-Complete，NP-HARD和PSPACE或PSPACE-COMPLETE。在此过程中，我们概述了过去十年为视频游戏开发的许多硬度证明技术：运动规划 - 直通框架框架，平面门框架，门和按钮框架，“ Nintendo”平台游戏 /卫星框架，以及收藏的代币和收藏的代币和Toll Roads / Hamiltonicity框架。
We analyze some of the many game mechanics available to Link in the classic Legend of Zelda series of video games. In each case, we prove that the generalized game with that mechanic is polynomial, NP-complete, NP-hard and in PSPACE, or PSPACE-complete. In the process we give an overview of many of the hardness proof techniques developed for video games over the past decade: the motion-planning-through-gadgets framework, the planar doors framework, the doors-and-buttons framework, the "Nintendo" platform game / SAT framework, and the collectible tokens and toll roads / Hamiltonicity framework.
