Scaling games to epic proportions

ABSTRACT

We introduce scalability for computer games as the next frontier for techniques from data management. A very important aspect of computer games is the artificial intelligence (AI) of non-player characters. To create interesting AI in games today, developers or players have to create complex, dynamic behavior for a very small number of characters, but neither the game engines nor the style of AI programming enables intelligent behavior that scales to a very large number of non-player characters.

In this paper we make a first step towards truly scalable AI in computer games by modeling game AI as a data management problem. We present a highly expressive scripting language SGL that provides game designers and players with a data-driven AI scheme for customizing behavior for individual non-player characters. We use sophisticated query processing and indexing techniques to efficiently execute large numbers of SGL scripts, thus providing a framework for games with a truly epic number of non-player characters. Experiments show the efficacy of our solutions.

REFERENCES

• 1: Personal correspondence with Sims technical team, 2006.
• 2: AIAndy and Zalamander. Advanced melee AI in Warcraft III. http://www.ecs.soton.ac.uk/~lph105/AMAI/.
• 3: Entertainment Software Association. 2006 sales, demographic and usage data: Essential facts about the computer and video game industry. http://www.theesa.com/.
• 4: Jon Louis Bentley. K-d trees for semidynamic point sets. In Proc. SGC, pages 187--197, 1990.
• 5: Murray Campbell, Knowledge discovery in deep blue, Communications of the ACM, v.42 n.11, p.65-67, Nov. 1999 [doi>10.1145/319382.319396]
• 6: Bernard Chazelle and Leonidas Guibas. Fractional cascading. Technical report, Systems Research Center of Digital Equipment Corporation, 1986.
• 7: Yi-Jen Chiang and Roberto Tamassia. Dynamic algorithms in computational geometry. Technical Report CS-91-24, Brown University, 1992.
• 8: Bruce Dawson. Game scripting in Python. In Game Developers Conf., 2002.
• 9: Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer Verlag, 2nd edition, 2000.
• 10: Mark DeLoura, editor. Game Programming Gems, volume 1. Charles River Media, 2000.
• 11: Michael Dickheiser, editor. Game Programming Gems, volume 6. Charles River Media, 2006.
• 12: David Diller, William Ferguson, Alice Leung, Brett Benyo, and Dennis Foley. Behavior modeling in commercial games. In Proceedings of the Thirteenth Conference on Behavior Representation in Modeling and Simulation, 2004.
• 13: Epic Games. http://www.unrealtechnology.com/html/homefold/home.shtml. Corporate Website, 2006.
• 14: John Laird and Michael van Lent. Interactive computer games: Human-level AI's killer application. In National Conference on Artificial Intelligence (AAAI), 2000.
• 15: Iosif Lazaridis and Sharad Mehrotra. Progressive approximate aggregate queries with a multi-resolution tree structure. In SIGMOD Conference, 2001.
• 16: Jonathan Littke. Eight years after the creation, blizzard releases a new patch for starcraft. GosuGamers; http://sc.gosugamers.net/features.php?i=a&id=2195, 2006.
• 17: Michael Mateas and Andrew Stern. Natural language understanding in faade: Surface-text processing. In Technologies for Interactive Digital Storytelling and Entertainment (TIDSE), 2004.
• 18: Don Moar and Jay Watamaniuk. Introduction to the Aurora Neverwinter Toolset. Bioware, 2006.
• 19: Olga Papaemmanouil, Yanif Ahmad, Ugur Cetintemel, John Jannotti, and Yenel Yildirim. Extensible optimization in overlay dissemination trees. In Proc. SIGMOD, 2006.
• 20: Steve Rabin. Designing a general robust AI engine. In Game Programming Gems, volume 1, pages 221--236. Charles River Media, 2000.
• 21: Philip Rosedale and Cory Ondrejka. Enabling player-created online world with grid computing and streaming. Gamasutra, September 18, 2003.
• 22: Brian Schwab. AI Game Engine Programming. Charles River Media, 2004.
• 23: Sega.Rome: Total War Manual, 2004.
• 24: Jake Simpson. Scripting and Sims2: Coding the psychology of little people. In Game Developers Conf., 2005.
• 25: Mustafa Thamer. Act of mod: Building Sid Meier's Civilization IV for customization. Game Developer, August:15--18, 2005.
• 26: Paul Tozour. Using a spatial database for runtime spatial analysis. In AI Game Programming Wisdom, volume 2, pages 381--390. Charles River Media, 2004.
• 27: Wizards of the Coast. Revised (v.3.5) System Reference Document, 2006.
• 28: Will Wright. The future of content. In Game Developers Conf., 2005.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Specialized application languages

General Terms:
Languages, Performance

Keywords:
aggregates, games, indexing, scripting