Interactive digital storytelling (IDS) aims at generating dramatically compelling stories based on the user's input. During a quarter of a century of research, IDS has promised to change the way computer games and other interactive applications tell stories. This paper reviews the theory behind IDS as well as the current state of IDS research, and studies whether - and how - IDS can improve interactive applications in general and computer games in particular.