In this paper, we present the first results obtained with an interactive storytelling prototype. Our main objective is to develop flexible character-based systems, which nevertheless rely on narrative formalisms and representations. Characters’ behaviours are generated from plan-based representations, whose content is derived from narrative formalisms. We suggest that search based planning can satisfy the real-time requirements of interactive storytelling, while still being compatible with the narrative formalisation we are pursuing. We then describe into greater detail a short episode generated by the system, which illustrates both high-level results and technical aspects, such as re-planning and user intervention. Further work will be dedicated to developing more complex narrative representations and investigating the relations between natural language semantics and narrative structures in the context of interactive storytelling.