Towards developing an intelligent graph restructuring algorithm for graph based stories using Google Maps

Show full item record

Please use this identifier to cite or link to this item: http://hdl.handle.net/1853/33470

Title: Towards developing an intelligent graph restructuring algorithm for graph based stories using Google Maps
Author: Hajarnis, Sanjeet Uday
Abstract: Location-based games are gaining popularity because of their unique feature of having the players move in their environment. This feature serves dual purpose (i) of allowing the players to stay fit by walking outside while playing their location based game and (ii) of separating them from their routine desk work usually sedentary work. Unfortunately, scalability becomes a huge concern for location based games because a particular (location-specific) game involves various landmarks and checkpoints in the vicinity of the current location. Thus, in order to cater to a sizeable audience and variety of locals, location based mobile games must be available for all or most playable locations. Having a database of games for all possible locations that players would wish to play in seems extremely infeasible and unreasonable. To overcome the above mentioned problem, this thesis proposes a solution that would attempt to eliminate pre-storing all the location specific games. The solution intelligently translates stories from their original locations into new locations by finding similarities between the locations. Thus, every time a user requests a game for a new location, restructure one of the previously written games for different locations to match and map to the new location the users intends to play in via a web-based authoring tool. The translation algorithm restructures original story into new story using analogical reasoning, heuristic hill-climbing and dynamic programming. Analogical reasoning is performed with the location-specific information obtained from Google Maps. This thesis uses heuristic hill-climbing algorithm to obtain the optimal mapping between the original and new location by searching through the space of similar checkpoints/landmarks between the two locations and dynamic programming and memorization optimizes the algorithm s performance by avoiding excessive re-computation. This thesis attempts to analyze the effects and success of using analogical reasoning with hill-climbing and dynamic programming in restructuring stories from original location to new location.
Type: Undergraduate Thesis
URI: http://hdl.handle.net/1853/33470
Date: 2010-05-12
Publisher: Georgia Institute of Technology
Subject: Google maps
Location based gaming
Health gaming
Mobile gaming
Intelligent story generation
Analogical reasoning
Dynamic programming
Department: Computer Science
Advisor: Faculty Mentor: Riedl, Mark

All materials in SMARTech are protected under U.S. Copyright Law and all rights are reserved, unless otherwise specifically indicated on or in the materials.

Files in this item

Files Size Format View
hajarnis_sanjeet_p_201005_ro.pdf 3.267Mb PDF View/ Open

This item appears in the following Collection(s)

Show full item record