Immersive computer-based training environments and computer games share many similarities; both require an interactive environment populated with believable characters where users' decisions affect the outcome of future events. The main problem in constructing these complex environments is that any sufficiently complex environment that offers users choices has to allow the users to pursue varied paths through the system and provide guidance for all these paths. Managing the multitude of paths is known as the branching storyline problem. Currently, this is addressed by hand-coding and testing all paths which increases production costs and artificially limiting user choices which damages believability and user experience. This project explores an alternative approach, using characters that rely on case-based reasoning for decision-making to provide flexibility in interacting with player, coupled with a story manager to manage and coordinate the characters by observing all user interactions to achieve the intended outcomes. The techniques developed are applicable for training environments as well as next-generation computer games.