Modern computer games tend to provide complex narratives, ensuring both extended and interesting game play. Narratives are important not only in traditional adventure games and role playing games, but also in first person shooting games and strategy games. Even so, many narratives contain defects that reduce the quality of games, and so it is important to develop analysis or verification techniques. Unfortunately, formal verification attempts are few, and in practice primarily done by manual inspection and test-playing. Our research is based on a framework, named Programmable Narrative Flow Graph (PNFG) that provides a high-level language to represent narratives. Our approach is to apply high-level, formal analysis to narratives to find out their winning paths, as a first step forward deeper verification. We extend the PNFG framework by developing a generic dataflow analysis module, and implement several analyzers to gather high-level data on narrative behaviors. To improve the performance of our approach, we also designed several optimizations that reduce the size of the search space. Not all individual optimizations are effective on all narratives, but our final, fully-optimized strategy is able to analyze large narratives in relatively little time—an improvement of several orders of magnitude over the state-of-the-art in narrative analysis. This represents a practical and effective design for analyzing narratives that we hope can be the basic of real improvements in game development. / Les jeux modernes pour ordinateurs ont tendance `a apporter les structures narratives complexes, en affirmant un jeu `a la fois entendu et int´eressant. Les structures narratives sont importantes non seulement dans le jeu d'aventure et le jeu de rˆole, mais aussi dans le jeu de tir `a la premi`ere personne et le jeu de strat´egie. Malgr´e tout, beaucoup de structures narratives poss`edent des d´efauts qui r´eduisent la qualit´e des jeux, ainsi c'est important de d´evelopper la technique de analyse ou de v´erification. Malheureusement, des tentatives de v´erification formelle sont limit´ees, et dans la pratique effectu´ee avant tout par l'inspection manuelle et l'essai du jeu. Notre recherche est bas´ee sur une structure applicative nomm´ee Programmable Narrative Flow Graph (PNFG) (Plan de Flux Narratif Programmable) qui offre un langage de haut niveau `a repr´esenter des structures narratives. En tant que premier pas vers la v´erification plue profonde, notre approche est `a appliquer l'analyse formelle de haut niveau sur les structures narratives afin de trouver leurs winning paths (chemins de la victoire). Nous prolongeons la structure applicative PNFG par l'´elaboration d'un module d'analyse de flux de donn´ees g´en´eriques, mais aussi mettons en oeuvre plusieurs analyseurs `a recueillir des donn´ees de haut niveau sur les comportements narratifs. Pour am´eliorer la performance de notre approche, nous avons ´egalement conc¸u plusieurs optimisations qui r´eduisent la taille de l'espace de recherche. Non toutes les diff´erentes optimisations sont efficaces sur les structures narratives, mais notre strat´egie finale et totalement optimis´ee$
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.32549 |
| Date | January 2009 |
| Creators | Zhang, Peng |
| Contributors | Clark Verbrugge (Internal/Supervisor) |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Master of Science (School of Computer Science) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | Electronically-submitted theses. |
Page generated in 0.0021 seconds