This paper investigates a range of challenges faced in the design of a serious game aimed at teaching history in situ, through the use of an immersive, open virtual environment. In the context of this paper, such an environment is described as an exploratory, expansive virtual world within which a user may interact in a non-linear and situated fashion with the virtual characters that populate it. The main contribution of this paper consists of the introduction of the Levels of Interaction (LoI) framework, designed to assist in the creation of multiple forms of interaction between a user-driven avatar and synthetic characters. The LoI approach addresses the necessity for balancing computational efficiency with the need to provide believable and interactive virtual characters, allowing varying degrees of visual, interactive and behavioural fidelity. The Roma Nova project demonstrates a first implementation of the concept, showing in practice how the LoI are likely to foster more natural interactions between the player and the non-playing characters.