Towards developing an intelligent graph restructuring algorithm for graph based stories using Google Maps
Hajarnis, Sanjeet Uday
MetadataShow full item record
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.