|
Real-Time Strategy
Advanced Wall Building for RTS Games
Topics: General; Genres: RTS
Abstract: Most real-time strategy (RTS) games include walls or similar passive defensive structures that act as barriers against enemy unit movement. Having an automated wall-building algorithm increases the competitiveness of nonplayer character opponents and provides a useful addition to random map generation. The original wall-building article presented a basic algorithm and discussed a few potential improvements. In this article, we will implement all of the suggested improvements and deal with more advanced issues like walling off cities, reusing existing walls, destructible natural barriers, and walling off shorelines.
Performing Qualitative Terrain Analysis in Master of Orion 3 |  |
Topics: Strategy, Tactical, Terrain Analysis; Genres: Strategy, RTS
Abstract: One challenge for many strategy game AIs is the need to perform qualitative terrain analysis. By qualitative we mean that the analysis is based on fundamental differences between different types of locations - for instance areas that are visible to our opponents, areas that are impassible, or areas vulnerable to enemy fire. In Master of Orion 3 we identify stars that are inside or outside of our empire's borders, those that are threatened by our opponents, and those that are contested (shared with an opponent). This information is used to identify locations where we need to concentrate our defenses and to help us expand into areas that minimize our defensive needs while maximizing the territory we control.
In this article we will present the algorithms used to make the qualitative distinctions given above and the ways in which the AI uses that information. The lessons we would most like the reader to take away from this article are not the specifics of the algorithms used but rather the thought processes involved in applying qualitative reasoning to terrain analysis. The important questions to address are: what are the qualitative distinctions we should look for, how can we recognize them, and what uses can the AI make of that information. Our algorithms are but a single example of how these questions can be answered.
The Unique Challenges of Turn-Based AI
Topics: Strategy, Tactical; Genres: Strategy
Abstract: Writing a turn-based AI presents a number of unique programming and game design challenges. The common thread uniting these challenges is the user's complete control over the game's speed. Players willing to invest extreme amounts of time into micro-management and players looking to streamline their gaming experience via automated decision-making present two very different problems for the AI to handle. Further, the ability to micro-analyze turn-based games makes predictability, cheating, and competitive balance extremely important issues. This article outlines how the Civilization III development team dealt with these challenges, using specific examples to illuminate some practical solutions useful to a programmer tasked with creating an AI for a turn-based game.
Random Map Generation for Strategy Games
Topics: Strategy; Genres: Strategy, RTS
Abstract: While there are numerous articles dedicated to the generation of random maps for games, there is little published information on random maps for strategy games in particular. This subset of map generation presents distinct challenges as evident by the relatively few games that implement them. While the techniques described here can be used to create maps suitable for any type of game, this system is specifically designed to create a variety of successful random maps for real-time strategy games. This article describes the random map generation implementation as found in the RTS game Empire Earth (EE) developed by Stainless Steel Studios.
Transport Unit AI for Strategy Games
Topics: Strategy, Tactical; Genres: Strategy, RTS
Abstract: Unit AI refers to the micro-level artificial intelligence that controls a specific unit in a game and how that unit reacts to input from the player and the game world. Transports present a particular challenge for unit AI as many units must work together to achieve their common goal, all the while attempting to minimize player frustration. This article discusses the general transport unit AI challenge and a successful solution. Land, air, naval, and building transports (such as fortresses and town centers) will be discussed and a class hierarchy implementation will be suggested. Algorithms for the loading (including the calculation for rendezvous points) and unloading of transports will be presented as well as warnings for particular pitfalls.
This article assumes some sort of finite-state-machine-based unit AI system and is applicable to any game in which there are multiple units in need of transporting. This article details the transport unit AI as found in the Real-Time Strategy (RTS) game Empire Earth (EE) developed by Stainless Steel Studios.
Wall Building for RTS Games | |
Topics: Strategy, Tactical; Genres: RTS
Abstract: Most real-time strategy games include walls or similar defensive structures that act as barriers for unit movement. Having a general-purpose wall-building algorithm increases the competitiveness of computer opponents and provides a new set of options for the random mission generation. The article discusses a wall building algorithm that uses the greedy methodology to build a wall that fits the definition, protects the desired location, and meets the customizable acceptance criteria. The algorithm takes advantage of the natural barriers and map edges to minimize the cost of building a wall. The algorithm discussion focuses on importance of traversal and heuristic functions, details of implementation, and various real world problems. Advanced topics such as minimum/maximum distance requirements, placement of gates and an unusual wall configurations are elaborated on. Full source code and a demo are supplied.
Strategic Decision-Making with Neural Networks and Influence Maps | |
Topics: Strategy, Tactical; Genres: Strategy, RTS
Abstract: Influence maps provide a strategic perspective in games that allows strategic assessment and decisions to be made based on the current game state. Influence maps consist of several layers, each representing different variables in the game, layered over a geographical representation of the game map. When a decision needs to be made by the AI player, some or all of these layers are combined via a weighted sum to provide an overall idea of the suitability of each area on the map for the current decision. However, the use of a weighted sum has certain limitations.
This article explains how a neural network can be used in place of a weighted sum, to analyze the data from the influence map and make a strategic decision. First, this article will summarize influence maps, describe the current application of a weighted sum and outline the associated advantages and disadvantages. Following this, it will explain how a neural network can be used in place of a weighted sum and the benefits and drawbacks associated with this alternative. Additionally, it will go into detail about how a neural network can be implemented for this application, illustrated with diagrams.
Multi-Tiered AI Layers and Terrain Analysis for RTS Games
Topics: Strategy, Tactical, Terrain Analysis; Genres: Strategy, RTS
Abstract: RTS games tend to handle soldier AIs individually, giving each unit specific tasks from the computer player. Creating complicated, cooperative tactics are impossible for such systems without an immense effort in coding. To develop complex, large-scale plans, a mechanism is needed to reduce the planning devoted to the individual units. Some games already collect individual soldiers into squads. This reduces the planning necessary by a factor of ten, as one hundred soldiers can be collected into ten squads. However, this concept can be taken farther, with squads collected into platoons, platoons into companies, and so on. The versatility such groupings give an AI system are immense. This article will explore the implementation of a multi-tiered AI system in RTS-type games, including the various AI tiers, a set of related maps used by the AI tiers and an example to illustrate the system.
Designing a Multi-Tiered AI Framework | |
Topics: Strategy, Tactical; Genres: Strategy, RTS
Abstract: The MTAIF allows an AI to be broken up into three concrete layers, strategic, operational and a tactical layer. This allows for an AI programmer to have various AIs focus on specific tasks, while at the same time having a consistent overall focus. The MTAIF allows for the strategic layer to be focused exclusively on matters that can affect an empire on a holistic scale, while at the operational level the AI is in tune with reports from the tactical level. A differing factor from many other architectures is that the MTAIF does not allow decisions to be made on a tactical scale that would violate the overall strategic policies. This in turn forces highlevel strategic policies to be enforced in tactical situations, without the AI devolving into a reactionary based AI.
Dead Reckoning in Sports and Strategy Games
Topics: General; Genres: Sports, Strategy, RTS
Abstract: Dead reckoning is a set of techniques used to calculate the motion of objects not entirely within an agent's control. This article explores the equations required to implement dead reckoning, and shows how it can apply in a variety of game contexts, for example the calculation of the optimal trajectory for a pass or a shot in a sports simulation, as well as multiple wargame problems.
Applying Goal-Oriented Action Planning to Games
Topics: Strategy, Planning; Genres: Strategy, RTS, FPS, Action
Abstract: A number of games have implemented characters with goal directed decision-making capabilities. A goal-directed character displays some measure of intelligence by autonomously deciding to activate the behavior that will satisfy the most relevant goal at any instance. Goal-Oriented Action Planning (GOAP) is a decision-making architecture that takes the next step, and allows characters to decide not only what to do, but how to do it. A character that formulates his own plan to satisfy his goals exhibits less repetitive, predictable behavior, and can adapt his actions to custom fit his current situation. In addition, the structured nature of a GOAP architecture facilitates authoring, maintaining, and re-using behaviors. This article explores how games can benefit from the addition of a real-time planning system, using problems encountered during the development of Monolith Production's No One Lives Forever 2: A Spy in H.A.R.M.'s Way to illustrate these points.
Hierarchical Planning in Dynamic Worlds
Topics: Strategy, Planning; Genres: Strategy, RTS, FPS, Action
Abstract:
Goal Directed Behavior using Composite Tasks
Topics: Strategy, Planning; Genres: Strategy, RTS, FPS, Action
Abstract: This article will introduce the reader to goal directed behavior and offers several examples of games that have used it to increase the believability of the agents in those games. The article then goes on to discuss the implementation of the Composite Task concept that was designed and developed to provide goal directed behavior for the agents in a military tactical combat training simulator. Finally, the simulator itself is briefly discussed and references to additional information on goal directed behavior are provided.
Game Balance and AI using Payoff Matrices
John M. Olsen (Microsoft)
Massively Multiplayer Game Development, 2003.
Topics: General; Genres: RTS, RPG, MMP
Abstract: Game balance can be a very thorny issue and can require a huge investment of time to get right.
In an MMP game environment, there is little margin for error; players have an amazing ability to work
together to find and use even the smallest of advantages. In this environment, there are as many approaches
to game balance as there are games. This article will present a way to use statistical analysis and some
straightforward mathematics to simplify the job of balancing certain portions of games, and use the same
techniques to make sure your Artificial Intelligence (AI) routines are taking advantage of the opportunities
available to them.
Terrain Analysis in an RTS-The Hidden Giant
Topics: Tactical; Genres: RTS
Abstract:
Tactical Path-Finding with A* | |
Topics: A* Pathfinding, Tactical; Genres: General, FPS, RTS
Abstract: Tactical paths consider cover and stealth in addition to travel time. Although costs for cover and stealth are easily added to the A* cost function, this alone does not result in convincing tactical paths. This chapter analyzes the defects in these paths, and discusses tactical improvements: taking into account exposure time and enemy aiming behavior, and anticipating likely enemy movement. The extensions to the A* cost functions introduce additional run-time costs. This chapter discusses the costs, and provides work-arounds and optimizations to make tactical pathfinding more efficient.
Recognizing Strategic Dispositions: Engaging the Enemy
Topics: Strategy, Tactical, Movement; Genres: RTS, Strategy
Abstract:
Formations
Topics: Formations, Coordinated Movement; Genres: RPS, RTS, FPS, Action
Abstract: In games today, formations are expected for any type of cohesive group movement. From squad-based first-person shooters to sports sims to real-time strategy games, anytime that a group is moving or working together it is expected to do so in an orderly, intelligent fashion. This article will cover standard military formations, facing issues, mixed formations, spacing distance, ranks, unit mobility, group pathfindng, and dealing with obstacles.
Architecting an RTS AI
Topics: Architecture; Genres: RTS
Abstract: RTS games are one of the more thorny genres as far as AI is concerned, and a good architecture is necessary to ensure success. Most examples presented in this article are taken from the work done on Empire Earth. Issues include game components (civilization manager, build manager, unit manager, resource manager, research manager, and combat manager), difficulty levels, challenges (random maps, wall building, island hopping, resource management, stalling), and overall strategies.
An Economic Approach to Goal-Directed Reasoning in an RTS
Topics: Architecture; Genres: RTS
Abstract: In this article, we discuss one approach to creating an agent for a real-time strategy game, using the Utility Model. This approach takes Economic theories and concepts regarding consumer choice, and creates a mapping onto our game agent's decision space. We explain relevant AI terminology (goal-directed reasoning, reactive systems, planning, heuristic functions) and Economic terminology (utility, marginal utility, cost, production possibilities), and introduce a simplistic RTS example to provide a framework
for the concepts.
The Basics of Ranged Weapon Combat
Topics: Weapon Selection, Weapon Handling; Genres: RTS, RPG, FPS, Action
Abstract: This article gives a brief
introduction to the problems of firing ranged weapons. We discuss to-hit rolls, aim point selection, ray-testing, avoiding friendly fire incidents, dead reckoning, and calculating weapon trajectories for ballistic weapons.
Game Trees in Realtime Games
Marco van de Wijdeven
AI-Depot.com, July 2002.
Topics: General, Search; Genres: General, RTS
Abstract: Examines how heuristic game tree search can be used in videogames like real-time
strategy games. Written from the viewpoint of both AI programmers and gamers, the article
provides an over view of concepts as well as a description and analysis of the algorithm.
A High-Performance Tile-based Line-of-Sight and Search system
Topics: Movement, Sensory; Genres: RTS
Abstract:
An Architecture for RTS Command Queuing
Topics: Movement; Genres: RTS
Abstract: Explains the concept of Command Queuing in an RTS along with several ways to implement it. Command Queuing is the idea that the player should be able to queue up any sequence of command orders (Move, Attack, Patrol, Repair, etc) for a particular unit. Some commands that cycle, such as Patrol, present specific challanges in order to acheive the right behavior. Solutions to these difficulties are discussed along with detailed diagrams.
Influence Mapping
Topics: Tactical; Genres: RTS, Strategy
Abstract: Influence mapping is a powerful and proven AI technique for reasoning about the world on a spatial level. Although influence maps are most often used in strategy games, they have many uses in other genres as well. Among other things, an influence map allows your AI to assess the major areas of control by different factions, precisely identify the boundary of control between opposing forces, identify "choke points" in the terrain, determine which areas require further exploration, and inform the base-construction AI systems to allow you to place buildings in the most appropriate locations.
Strategic Assessment Techniques
Topics: Tactical; Genres: RTS, Strategy
Abstract: This article discusses two useful techniques for strategic decision-making. These are easiest to understand in the context of strategy game AI, but they have applications to other game genres as well. The resource allocation tree describes a data structure that allows an AI system to continuously compare its desired resource allocation to its actual current resources in order to determine what to build or purchase next. The dependency graph is a data structure that represents a game's "tech tree," and we discuss a number of ways that an AI can perform inference on the dependency graph in order to construct long-term strategic plans and perform human-like reasoning about what its opponents are attempting to accomplish.
Terrain Analysis in Realtime Strategy Games
Dave Pottinger (Ensemble Studios)
Game Developers Conference Proceedings, 2000.
Topics: Tactical; Genres: RTS
Abstract: Terrain analysis is like a black-art. Every real-time strategy (RTS) game with a decent
AI, whether it knows it or not, does some type of terrain analysis. This lecture examines various methods
for terrain analysis as they apply to RTS games. Starting with simple topics as chokepoint determination
and building placement, the class moves on to more advanced topics such as frame-based terrain representation
and integration of terrain knowledge throughout the rest of the AI. Copious examples are provided by the way
of numberous 2D/3D demos and code snippets.
Implementing Coordinated Movement
Dave Pottinger (Ensemble Studios)
Game Developer Magazine, February 1999.
Available Online at Gamasutra, 1999.
Topics: Formations, Pathfinding, Coordinated Movement; Genres: RTS, General
Abstract:
Coordinated Unit Movement
Dave Pottinger (Ensemble Studios)
Game Developer Magazine, January 1999.
Available Online at Gamasutra, 1999.
Topics: Formations, Pathfinding, Coordinated Movement; Genres: RTS, General
Abstract:
|
