SpyFeet is a mobile Android game which utilizes augmented reality, dynamic quest generation, natural language generation (NLG) and the compelling stories of traditional role playing games to encourage middle school girls to exercise. The player quickly discovers that she has the power to see and converse with animal spirits by using her phone. The spirits give the player quests which must be accomplished in the physical world, using the phone’s GPS and accelerometer. As quests are completed, the player earns the trust of the spirits and learns of the circumstances pertaining to a rash of mysterious environmental disasters. Each animal spirit had a distinct personality, realized through the NLG system Personage. When combined with our dynamic quest structure, which represented story events abstractly and allowed them to be re-ordered in response to player choices, multiple paths through the story could be followed with character-believable dialog and a minimal amount of increased authoring work. I worked with both the story team, which designed the story management system and the non-linear story to go with it, as well as the implementation team, getting the game to run on mobile devices.