Programmed Graph Rewriting with Time for Simulation-Based Design

Abstract. The Discrete EVent system Specification (DEVS) formal-ism allows for highly modular, hierarchical modelling of timed, reactive systems. DEVS can be used to describe complex control structures for programmed graph transformation. A side-effect of this approach is the introduction of an explicit notion of time. In this paper we show how the explicit notion of time allows for the simulation-based design of reactive systems such as modern computer games. We use the well-known game of PacMan as an example and model its dynamics with programmed graph transformation based on DEVS. This also allows the modelling of player behaviour, incorporating data about human players ’ behaviour and reaction times. Thus, a model of both player and game is obtained which can be used to evaluate, through simulation, the playability of a game design. We propose a playability performance measure and vary parameters of the PacMan game. For each variant of the game thus ob-tained, simulation yields a value for the quality of the game. This allows us to choose an “optimal ” (from a playability point of view) game con-figuration. The user model is subsequently replaced by a visual interface to a real player and the game model is executed using a real-time DEVS simulator.