SYSTEM AND METHOD FOR SCALING SIMULATIONS AND GAMES

• US 20090307671A1
• Filed: 06/08/2009
• Published: 12/10/2009
• Est. Priority Date: 06/06/2008
• Status: Active Grant

• Current Assignee: Cornell University
• Original Assignee: Cornell University
• Inventors: Demers, Alan John, White, Walker, Koch, Christoph Emanuel, Gehrke, Johannes
• Granted Patent: US 8,443,350 B2
• Time in Patent Office: Days
• US Class Current: 717/149
• CPC Class Codes: A63F 13/10 Control of the course of the game, e.g. start, progess, end
• CPC Class Codes: A63F 13/45 Controlling the progress of the video game
• CPC Class Codes: A63F 13/60 Generating or modifying game content before or while executing the game program, e.g. authoring tools specially adapted for game development or game-integrated level editor
• CPC Class Codes: A63F 2300/209 characterized by low level software layer, relating to hardware management, e.g. Operating System, Application Programming Interface
• CPC Class Codes: A63F 2300/6009 for importing or creating game content, e.g. authoring tools during game development, adapting content to different platforms, use of a scripting language to create content
• CPC Class Codes: G06F 9/445 Program loading or initiating bootstrapping G06F9/4401; security arrangements for program loading or initiating G06F21/57
• CPC Class Codes: G06N 3/004 Artificial life, i.e. computing arrangements simulating life
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound

Abstract

A system and method for modeling simulation and game artificial intelligence as a data management problem. A scripting language that provides game designers and players with a data-driven artificial intelligence scheme for customizing behavior for individual agents. Query processing and indexing techniques to efficiently execute large numbers of agent scripts, thus providing a framework for games with a large number of agents.

Claims

1. A method for computerized compilation a scripting language to perform agent-level scripting in the context of a computer simulation, said method comprising the steps of:

receiving agent scripts for each agent, wherein the agent scripts include agent script properties of each of the agents, wherein the agent script properties are separated into states and effects, and wherein the agent scripts are separated into query phases and update phases, wherein the states, in the query phase are read-only, and the effects, in the query phase, are write-only, wherein the agent scripts can only modify the states during the update phase, wherein the effects are associated with aggregation fimctions, wherein the associated aggregation functions can only modify the effects and only in the query phase; and

converting the agent scripts into a set-at-a-time query plan, said step of converting executing computer instructions to perform the steps of;

building data parallel pipelines;

identifying locations in the data parallel pipelines where an index can be generated;

identifying ways to reorder the data parallel pipelines;

using database cost metrics to identify selected ways from the ways; and

annotating the data parallel pipeline with the index and the selected ways.

2. A scripting language compiler to perform agent-level scripting in the context of a computer simulation, said compiler comprising:

an update phase processor receiving agent scripts for each agent, wherein the agent scripts include agent script properties of each of the agents, wherein the agent script properties are separated into states and effects, and wherein the agent scripts are separated into query phases and update phases, wherein the states, in the query phase are read-only, and the effects, in the query phase, are write-only, wherein the agent scripts can only modify the states during the update phase, wherein the effects are associated with aggregation functions, wherein the associated aggregation functions can only modify the effects and only in the query phase; and

a converter converting the agent scripts into a set-at-a-time query plan, said converter executing computer instructions to perform the steps of;

building data parallel pipelines;

identifying locations in the data parallel pipelines where an index can be generated;

identifying ways to reorder the data parallel pipelines, using database cost metrics to identify selected ways from the ways; and

annotating the data parallel pipeline with the index and the selected ways.

3. A method for constructing a simulation with a scripting language compiler and a scripting language runtime including the steps of:

reading the agent scripts into the scripting language compiler to produce a set-at-a-time query plan;

converting the set-at-a-time query plan to a data-parallel pipeline with indices and selected ways from the ways;

embodying each step of behavior of the agent as a single execution of the data parallel pipeline to produce results;

linking the results to the simulation;

gathering pipeline statistics about the data parallel pipeline based on the amount of time/memory available;

identifying which of the indices to create and which of the indices to eliminate at each of the steps of behavior; and

reordering the set-at-a-time query plan according to pipeline statistics.

4. A scalable system for managing computer games, each computer game containing agents, the system comprising:

an environment table for each category of agents;

a script that, at each clock tick, updates the contents of the environment table via set-at-a-time processing; and

a linker that connects the environment table to the computer game.

5. A scripting language for customizing agent behavior for agents that are part of a computer simulation comprising:

a script analyzer to analyze agent scripts defining agent behavior; and

produce an agent database;

a script compiler to convert the agent behavior into a database query plan; and

a scripting language runtime for applying the database query plan to the agent database and linking the results to the simulation.

6. A method for indexing and code reordering to execute agent scripts to achieve scalability in the number of agents in a computer game comprising the steps of:

pre-computing results of expensive functions in the computer game;

indexing the results of said step of pre-computing to access the results within the agent scripts;

in a single clock tick, encoding effects generated by the agent script into an environment table;

combining the effects into the environment table to produce a set-at-a-time table with a single value of the effects for each of the agents; and

applying the single value of the effects using a post-processing step specific to the computer game.