Storytelling is a pervasive part of our daily lives and culture. The task of creating stories for the purposes of entertaining, educating, and training has traditionally been the purview of humans. This sets up the conditions for a creative authoring bottleneck where the consumption of stories outpaces the production of stories by human professional creators. The automation of story creation may scale up the ability to produce and deliver novel, meaningful story artifacts. From this practical perspective, story generation systems replicate (...) the creative abilities of humans and can thus be considered instances of computational creativity. Computational systems that are purported to be creative typically utilize one of three general approaches: exploration of a space of concepts, combination of concepts, and transformation of concepts. In this article we present an approach to story generation that utilize exploration, combination, and transformation. Our approach, implemented in the Vignette Based Partial Order Causal Link story planner, is an algorithm that searches through a space of possible story solutions, guided by combinations of existing story fragments called vignettes. The vignettes are made relevant to novel story generation contexts through an automated transformation pre-process. Through these processes, we show that story generation can incorporate multiple perspectives on computational creativity. Our approach is presented at both the theoretical and technical levels. (shrink)