Comprehensive and Instantly Responsive Player Assistance using Binary Decision Diagrams
Ross Mawhorter, Adam M. Smith · 2024
In large game worlds, players can get lost and feel overwhelmed as they try to figure out which immediate choices will make progress towards their own long-range goals in the game. This is a planning problem, but these games often have large state spaces. In this paper, we show that Binary Decision Diagrams (BDDs) can directly manipulate very large game state spaces, and this power can be leveraged to construct instantly responsive player assistance systems. We use BDDs to build a compressed representation of a game’s state-transition function, and use it to derive an action policy that makes shortest-path recommendations for any feasible state towards any achievable goal in milliseconds. We introduce the intuition behind planning with BDDs using a tiny grid world, and eventually scale to an integrated system for start-to-finish gameplay assistance in Super Metroid.