by Graig Fisher

One of the most popular genres of computer games is real time strategy (RTS). RTS games have been around for quite a few years, and have grown and evolved with technology, as well as work in the field of artificial intelligence. These games borrow many standard game theories, as well as have their own unique set of theories. This is due to the nature of the game; the computer still must be programmed to react as in any other game, yet must deal with the unique element of reacting in real time. A specific problem of real time strategy games is pathfinding, and its related problems of tactical and terrain analysis. These problems have improved tremendously over the history of RTS games, but still require significant work to be perfected.

The main objective of an RTS game is to control units (workers, military, and buildings) which perform tasks (build, combat, gather resources, produce other units) to overcome the opponent’s units. Generally, an RTS involves two or more players with equal (though not always similar) abilities in developing and commanding various types of these units. Play usually involves military destruction of the other players’ units on the board. Workers (non-military units) support military units by upgrading certain capabilities of the military units (i.e. creating military unit producing units, "researching" more advanced weapons, etc.) Military units combat those of the opponent(s). Though other strategies exist, especially in later, more advanced games, military might is generally essential for most RTS games. The entire point of the game, be it military or non-military based, is that all of the gameplay occurs in real time rather than a turn basis and requires a certain amount of skill in control of units. Being able to react immediately to opponents and do several things at once are key features to the popularity of RTS games. These features, though, are also what make creating an efficient artificial intelligence for this type of game a bit different than others.

What follows is an analysis of several of the pathfinding problems and techniques involved with RTS games. Specifically, published and experimental research on a variety of RTS games will be used to show some of the strengths and weaknesses of the genre and how developers are overcoming them. The main game used for the research was Ensemble Studios’ Age of Empires 2: Age of Kings as it is one of the most advanced RTS games available. Other games included in the study are Blizzard’s Warcraft: Orcs and Humans and Warcraft 2: The Tides of Darkness, Westwood’s Command and Conquer, Bungie Software’s Myth: The Fallen Lords, and Cyberlore Studios’ Majesty. These games were studied in the contexts of pathfinding (moving units from one position on the board to another [goal] chosen by the player), strategic and tactical analysis (using pathfinding techniques applied to how certain positions would benefit a player in military advantage), and terrain analysis (deciding path advantages and disadvantages based on the type of that area of the game board). The results were compared with the documentation found online and are presented here.

Similarities of RTS games with turn based games are numerous. Specifically, the goal of the game’s artificial intelligence remains the same: to overcome the other players (human or machine). The computer must analyze the current situation (or "game state") and determine the best course of action to take. This may be based off of any one of a number of artificial intelligence algorithms, just as a standard turn based game. Newer games (of any genre) may include variable rules and algorithms. This is generally accomplished via user modifiable scripts. Some games (such as Epic Games’ Unreal Tournament) have gone as far as providing an entire scripting language for that express purpose.¹ Scripting provides variety and easy access to improvement in artificial intelligence. It also allows modification for different types of scenarios without having to touch the finished game engine. For example, modifications for different terrain types, human ability levels, or "personalities" are possible.

There are several key differences between RTS games and turn based games. For example, a favored technique to determine the computer’s best move (irrespective to the actual algorithm used) is to analyze the current state of the game and proceed from there. In a real time strategy, analyzing the game state in the traditional sense (i.e. examining the value of certain variables, including position(s), number of units, known enemy statistics) is impossible because: 1) It is extremely complex. There are simply too many variables, and they are constantly changing. 2) There isn’t enough time for real analysis; responses have to be immediate. These factors make the artificial intelligence (and the game as a whole) much more complex. Another difference between RTS and turn-based is the ability to make simultaneous moves in RTS. This poses yet another problem for machines, as they are inherently deterministic. The problem is generally overcome by the fact that by allocating enough CPU cycles to the problem, the computer’s speed can make it seem to react to several situations at once.

Pathfinding is an important element of RTS games. Because the game involves so many units doing so many things at one time, the player (be it human or machine) simply does not have the time to be concerned with getting every individual unit where it needs to go at every moment. It is up to the games built in artificial intelligence to determine how a unit should proceed to a given destination. Most games today use some variation of the A* algorithm.² This algorithm is generally the best and most efficient for finding a path to the goal. This algorithm is based on a heuristic function that ranks nodes in a possible path by the an estimate of the best path through that node.

Figure 1.³

The rank value is determined simply by adding the actual value of reaching the node to the estimated value of reaching the goal from the node.⁴ Several improvements and modifications to the algorithm have been made over the years, as well as customization for individual games. The main advantages are the ability to look ahead as well as make path choices quicker. These gains are readily apparent when comparing Warcraft (the oldest game in the pack) with Age of Empires 2 (the newest). The Age of Empires units are better able to determine a "good" route to a goal. In Warcraft, the units would not reevaluate their positions when moving around objects. They would treat each new obstacle as a separate entity and move around it until reaching the original vector of their path. This wastes time and is an obvious flaw in the pathfinding. Also, the Warcraft units are slower to react (even on the same test machine as the Age units), slower to calculate an alternative when faced with an obstacle, and less likely to take a "good" route when there is unit congestion (a clustering of units, or traffic jam). Furthermore, there is more unit congestion overall as the units are less able to detangle themselves from other units.

Factors external to methodic algorithm design have improved pathfinding (and games’ artificial intelligence overall.) First, much more powerful computers are running modern RTSs than previously possible. For example, when Warcraft was released in 1994, a state-of-the-art PC would have been a 100 MHz 80486DX (or perhaps a Pentium, if you could get around the FPU bug.) Another factor is the percent of the CPU’s computation used by artificial intelligence. If 5% of the clock cycles were devoted to artificial intelligence, that was significant. When compared with today’s games giving 25% of a 500 MHz to 1.2 GHz processor to artificial intelligence,⁵ there is a quite obvious difference in horsepower. The issue here is that there is a theoretical limit to how fast silicon can be clocked. As we approach this limit, physical improvements in speed, power, and space can not be relied upon. The key is to work smarter, not harder.

Figure 2.⁶

Though the Age units are much improved, there are parts of the game where they do not seem any more intelligent than their Warcraft counterparts. First, neither game (nor any other game studied, for that matter) implements any form of unit communication. Age of Empires 2 does implement communication on a player level, but not on a unit level. This lack makes for some very confusing situations when attempting to move large groups of units through heavily obstacled areas. A simple communication system could help alleviate the congestion problem. Or, a further extension of communication would be to have ranked units, i.e. squads of soldiers commanded by a sergeant, which in turn were organized into platoons commanded by a leutenant, etc. Each rank would have duties assigned to it. For example, it might be up to the sergeant unit to make sure all of its squad is able to stay together and deal with unit congestion.

A second area that needs improvement is tactical analysis. This refers to the ability of a unit to choose a route other than the optimal based on sight of the enemy. If the chosen path takes a unit near enemies that could destroy it, that should count as an obstacle and should be avoided. A direct and physically clear path is not best if it takes a unit to its death. This type of system could be very effective when implemented in combination with the communication system from above. For example, a scout (high mobility, long range vision, little or no defensive/offensive capability) finds an enemy outpost. Knowing it is unable to handle this situation by itself, it backs off and calls for the nearest troop of military units to mobilize. Now that’s artificial intelligence! Unfortunately, it’s only available in one of the games in this study, Majesty, and even this implementation does not have inter-unit communication. Majesty adds a new twist to the standard RTS formula: units are individuals that make decisions and advance based on their experiences, rather than by direct order of the player. Each unit can decide whether or not to participate in a fight based on its current health, armour, and skill in comparison to that of its enemy, as well as the reward for success. But, from Warcraft to Age, no "true" RTS game was able to accurately make determinations as to how units in danger should procede.

The final area in dire need of an upgrade is that of terrain analysis. Really, tactical analysis is a sub-problem of this one. Terrain analysis is examining paths not only for physical obstacles that can stop a unit, but for areas more difficult to traverse than others (hills, swamps, etc.), points of possible ambush, and defendable positions. Again, no game studied was able to do this with any sort of effectiveness. In fact, the trend seems to be that as games are becoming more complex, this area of the artificial intelligence seems to be getting worse. The reasons are that more complexity generally translates to more units (mobile and immobile) of different types, taking up more gameboard area, all while gameboards are becoming more diverse in the types of area offered. This leads to a more haphazard layout of units, which in turn are less effective in the use of the terrain. The answer here lies in the use of weighted graphs. Imagine Figure 1 from above, but with each possible path assigned an integer value. Once the unit has determined all possible paths that will allow it to arrive at its goal, these paths’ total weights are calculated in search of the optimal route. Again, no game studied exhibited this level of analysis. Age of Empires, though, does have a very limited form of this type of decision making; it was able to deal with hills only in that ranged units (archers, arrow towers) are able to fire further from atop a hill. Still, the units traversing hills (and any other type of terrain) are not able to calculate paths to avoid them.

Why are pathfinding and its related analyses so difficult for a computer? Why is it that a human, with a tiny fraction of the computing power of a standard desktop PC can build effective walls, set effective ambushes, and make effective use of defensible positions while laughing at the inability of the computer? According to most research, it is because of the way humans think vs. the way computers "think." Humans are rated at about 1,000 operations per second.⁷ An average desktop computer playing an RTS game can do several hundred million operations per second. The reason that humans win, despite this fact, is that they are great at a technique known as pattern matching. This is associating known facts, images, or other human "data structures" with their real world counterparts. This is why we can recognize people’s faces and voices, as well as why we can easily identify common objects. This type of problem is parallel, easily handled by the brain’s 100 billion or so neurons.⁸ Because its an inherently massively parallel process, this type of analysis is much more difficult for a computer. Computers excel at searching type problems: linear, "mathy" problems which rely on pure computational brute force.⁹ Unfortunately, this type of ability is ill suited to recognizing good strategic points on a game board, i.e. pathfinding. Humans, who can compare their current position not only to past game experience, but to real world experience, will always have this advantage.

To some extent, though, there is a debate about how much some of these items should actually be improved. For example, it is suggested than unit congestion (clumping) is a very "real world" type of problem, and that it should be the job of the commander (i.e. player) to fix it¹⁰ (or order units as not to create it in the first place.) These types of debates will most likely continue as computers become more powerful and better algorithms are designed. As the technology exists for better and better computer players, the duel between a "perfect" computer player and a "fun" computer player becomes very important. Which aspect should be required to submit, technology or game playability? The obvious answer lies within the goal of the project: to create the "best" game possible. How "best" is defined is up to you.