Dialogue in commercial games is largely created by teams of writers and designers who hand-author every line of dialogue and hand-specify the dialogue structure using finite state machines or branching trees. For dialogue heavy games, such as role playing games with significant NPC interactions, or emerging genres such as interactive drama, such hand specification significantly limits the player's interaction possibilities. Decades of research on the standard pipeline architecture in natural language generation has focused on how to generate text given a specification of the communicative goals; one can imagine beginning to adapt such methods for generating the lines of dialogue for characters. But little work has been done on the problem of procedurally generating dialogue structures, that is, dynamically generating dialogue FSMs or trees (more generally, discourse managers) that accomplish communicative goals. In this paper we describe a system that uses a formalization of backstory, character information, and social interactions to dynamically generate interactive dialogue structures that accomplish desired dialogue goals.