Comprehensive and Instantly Responsive Player Assistance using Binary Decision Diagrams
Open Access
- 21 May 2024
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1-11
Abstract
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.Keywords
This publication has 19 references indexed in Scilit:
- Control design for hybrid systems with TuLiP: The Temporal Logic Planning toolbox2016
- Symbolic Dynamic Programming2011
- LUDOCORE: A logical game engine for modeling videogames2010
- Using Datalog with Binary Decision Diagrams for Program Analysis2005
- OBDDs in heuristic search1998
- Disjunctive Partitioning And Partial Iterative Squaring: An Effective Approach For Symbolic Traversal Of Large Circuits1997
- Efficient implementation of a BDD package1990
- Boolean Analysis of MOS CircuitsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1987
- Graph-Based Algorithms for Boolean Function ManipulationIEEE Transactions on Computers, 1986
- Binary Decision DiagramsIEEE Transactions on Computers, 1978