Grid representations offer many advantages for path planning. Lookups in grids are fast, due to the uniform memory layout, and it is easy to modify grids. But, grids often have significant memory requirements, they cannot directly represent more complex surfaces, and path planning is slower due to their high granularity representation of the world. The speed of path planning on grids has been addressed using abstract representations, such as has been documented in work on Dragon Age: Origins. The abstract representation used in this game was compact, preventing permanent changes to the grid. In this paper we introduce a sparse grid representation, where grid cells are only stored where necessary. From this sparse representation we incrementally build an abstract graph which represents possible movement in the world at a high-level of granularity. This sparse representation also allows the representation of three-dimensional worlds. This representation allows the world to be incrementally changed in under a millisecond, reducing the maximum memory required to store a map and abstraction from Dragon Age: Origins by nearly one megabyte. Fundamentally, the representation allows previously allocated but unused memory to be used in ways that result in higher-quality planning and more intelligent agents.

The task of keyhole (unobtrusive) plan recognition is central to adaptive game AI. “Tech trees” or “build trees” are the core of real-time strategy (RTS) game strategic (long term) planning. This paper presents a generic and simple Bayesian model for RTS build tree prediction from noisy observations, which parameters are learned from replays (game logs). This unsupervised machine learning approach involves minimal work for the game developers as it leverage players’ data (com- mon in RTS). We applied it to StarCraft1 and showed that it yields high quality and robust predictions, that can feed an adaptive AI.

In recent years, real-time strategy (RTS) games have gained interest in the AI research community for their multitude of challenging subproblems — such as collaborative pathfinding, effective resource allocation and unit targeting, to name a few. In this paper we consider the build order problem in RTS games in which we need to find concurrent action sequences that, constrained by unit dependencies and resource availability, create a certain number of units and structures in the shortest possible time span. We present abstractions and heuristics that speed up the search for approximative solutions considerably in the game of StarCraft, and show the efficacy of our method by comparing its real-time performance with that of professional StarCraft players.

Character intention revision is an essential component of stories, but it has yet to be incorporated into story generation systems. However, intentionality, one component of intention revision, has been explored in both narrative generation and logical formalisms. The IRIS system adopts the belief/desire/intention framework of intentionality from logical formalisms and combines it with preexisting concepts of intentionality in narrative. IRIS also introduces the crucial concept of intention revision for characters in the story. The intent of this synthesis is to create stories with dynamic and believable characters that update their beliefs, replan, and revise their intentions over the course of the story.

In this paper we focus on proactive behavior for non-player characters (NPCs) in the first-person shooter (FPS) genre of video games based on goal-oriented planning. Some recent approaches for applying real-time planning in commercial video games show that the existing hardware is starting to follow up on the computing resources needed for such techniques to work well. Nonetheless, it is not clear under which conditions real-time efficiency can be guaranteed. In this paper we give a precise specification of SimpleFPS, a STRIPS planning domain expressed in PDDL that captures some basic planning tasks that may be useful in a first person shooter video game. This is intended to work as a first step towards quantifying the performance of different planning techniques that may be used in real-time to guide the behavior of NPCs. We present a simple tool we developed for generating random planning problem instances in PDDL with user defined properties, and show some preliminary results based on SimpleFPS instances that vary in the size of the domain and two well-known planners from the planning community.

Conflict is an essential element of interesting stories, but little research in computer narrative has addressed it directly. We present a model of narrative conflict inspired by narratology research and based on Partial Order Causal Link (POCL) planning. This model informs an algorithm called CPOCL which extends previous research in story generation. Rather than eliminate all threatened causal links, CPOCL marks certain steps in a plan as non-executed in order to preserve the conflicting subplans of all characters without damaging the causal soundness of the overall story.

Path planning is a critical part of modern computer games; rare is the game where nothing moves and path planning is unneeded. A* is the workhorse for most path planning applications. Block A* is a state-of-the-art algorithm that is always faster than A* in experiments using game maps. Unlike other methods that improve upon A*'s performance, Block A* is never worse than A* nor require any knowledge of the map. In our experiments, Block A* is ideal for games with randomly generated maps, large maps, or games with a highly dynamic multi-agent environment. Furthermore, in the domain of grid-based any-angle path planning, we show that Block A* is an order of magnitude faster than the previous best any-angle path planning algorithm, Theta*. We empirically show our results using maps from Dragon Age: Origins and Starcraft. Finally, we introduce ``populated game maps'' as a new test bed that is a better approximation of real game conditions than the standard test beds of this field. The main contributions of this paper is a more rigorous set of experiments for Block A*, and introducing a new test bed (populated game maps) that is a more accurate representation of actual game conditions than the standard test beds.

This paper presents a framework that facilitates communication between a planning system (“planner”) and a plan execution system (“executor”) to enable them to run concurrently, with the main emphasis on meeting the real-time requirements of the application domain. While the framework is applicable to general-purpose planning, its features are optimized for the requirements of automated story planning for games—with emphasis on monitoring player-triggered events and handling on-time (re-)generation of story assets such as characters, maps and scenarios. This framework subsumes the traditional interleaved planning-and-execution paradigm used in embedded continual planning systems and generalizes it to a non-embedded context, making the framework ideal for use with contemporary game architectures (e.g., multithreaded game engines, or games with subsystems communicating over a network).

A growing body of work in games research, both generative and analytic, seeks to characterize the relationship between a player’s understanding of an interactive narrative and her options for action within it. This paper provides several definitions that collectively serve as a basis for a model of the user’s comprehension of an unfolding story in a game. Central to this approach, we define the notion of narrative affordance. In essence, a game provides a narrative affordance for some course of action when a player can imagine that course of action as part of a story that completes their current story experience. To define narrative affordance, we draw links from cognitive models of narrative comprehension and a range of research on affordance, which we couple with planning approaches to story and discourse generation. In our approach, we view the creation of an interactive narrative that provides a high degree of agency as a discourse generation problem. We posit that an interactive narrative system must reason about the content and organization of its communication with a player in order to prompt a player’s understanding about the game’s story and her role in it. This paper ends by pointing toward a research direction intended to provide insight into a range of aspects of interactive narrative, including role, genre, choice and agency.

Multi-agent path planning is a challenging problem with numerous real-life applications. Running a centralized search such as A* in the combined state space of all units is complete and cost-optimal, but scales poorly, as the state space size is exponential in the number of mobile units. Traditional decentralized approaches, such as FAR and WHCA*, are faster and more scalable, being based on problem decomposition. However, such methods are incomplete and provide no guarantees with respect to the running time or the solution quality. They are not necessarily able to tell in a reasonable time whether they would succeed in finding a solution to a given instance. We introduce MAPP, a tractable algorithm for multi-agent path planning on undirected graphs. We present a basic version and several extensions. They have low-polynomial worst-case upper bounds for the running time, the memory requirements, and the length of solutions. Even though all algorithmic versions are incomplete in the general case, each provides formal guarantees on problems it can solve. For each version, we discuss the algorithm's completeness with respect to clearly defined subclasses of instances. Experiments were run on realistic game grid maps. MAPP solved 99.86% of all mobile units, which is 18--22% better than the percentage of FAR and WHCA*. MAPP marked 98.82% of all units as provably solvable during the first stage of plan computation. Parts of MAPP's computation can be re-used across instances on the same map. Speed-wise, MAPP is competitive or significantly faster than WHCA*, depending on whether MAPP performs all computations from scratch. When data that MAPP can re-use are preprocessed offline and readily available, MAPP is slower than the very fast FAR algorithm by a factor of 2.18 on average. MAPP's solutions are on average 20% longer than FAR's solutions and 7--31% longer than WHCA*'s solutions.