A growing issue in the development of realistic and entertain-ing interactive games is the need for mechanisms that support ongoing natural language conversation between human players and artificial non-player characters. Unfortunately, many methods for implementing natural language generation(NLG) induce a significant burden on the author, do not scale well, or require specialized linguistic knowledge. We formalize the notion of typed-templates, an extension of standard structures employed in template-based NLG. We further provide novel algorithms that, when applied to typed-templates, ameliorate the above issues by affording computational support for authoring and increased variation in utterance and scenario generation. We demonstrate the efficacy of typed-templates and the algorithms through a user study.