Article: Real-Time Strategy High-Level Planning

Real-Time Strategy High-Level Planning

[Stefan Weijers, 2010]

In this article, the author analyzes the different elements needed for implementing AI in RTS games as well as different techniques used to achieve this. Here is a small summary:

Real-Time strategy games are computer games in which the player controls an army in real-time to destroy other players' armies, with each player requiring resources and buildings to create such army. The key to winning is to balnce the army production with the gathering of resources.

Tasks in real-time strategy games can be split in three levels of abstraction:

• Unit Control (Lowest level, players control a specific unit).
• Tactical Planning (Make plans on how to attack the enemy).
• Strategic Planning (High-Level decisions involving army creation and management).

Identified Problems in real-time strategy games:

-------------------------------------------------

Resource Management

The gathering and balancing of resources can be done with a reflex agent. The AI has all the relevant information and can simply assign more units to a certain resource when it runs low.

Decision making under uncertainty

To be able to recognize important events, the game needs some sort of pattern recognition. Even with no concrete information available, the AI should be able to plan future actions.

Spatial and temporal reasoning

Applicability of a strategy needs to be reevaluated constantly. Terrain analysis is really importante for this. An important problem encountered for this aspect is the process time, because the world might have changed while the AI is still calculating its strategy.

Collaboration

This aspect is clearly lacking in RTS. Computer players never work with human players to overcome a strong opponent. The AI should be able to recognize the allied strategy and help them in the right way.

Opponent modeling, learning

Human players can spot weaknesses in a strategy and exploit them while computer players have a hard time accomplishing this. The AI needs to learn from previous experiences and formulate aplicable counter strategies.

Reasons why current commercial RTS AI fail to challenge human players:

--------------------------------------------------------------------------

Predictability and lack of spatial reasoning.

When the AI is predictable, players will inevitably exploit it. The predictability of commercial AIs comes from the fact that all AI is scripted.

Scripting

Commercial games include a set of scripts that translate into several different strategies that the AI implements to give some diversity to games but that carries several problems:

Hard to implement

Implementation of scripts needs several expertns in the game to think of viable strategies, the game has to be near completion before the AI programmers can start implementing it and even after implementation, it needs to be tested and tweaked thoroughly.

Domain Specific

After implementing a scripted AI for a game, the implementation is not applicable for other RTS games. This forces game developers to go thorugh the implementation cycle again.

Game developers use other means to entertain players. Different scripted strategies or giving the AI more information than it should have are some examples to create diversity or add challenge.

Academic Research to solve these issues:

---------------------------------------

Dynamic Scripting

A reinforcement learning technique for scripts. This allows the AI to generate a strategy on the fly by selecting a viable tactic in the tactic database. Also, this allows the AI to overcome static challenges (players that use the same tactic over and over again).

This, however, carries some of the problems. It still needs a group of experts to create viable tactics and because most research is done with static opponents to learn from, their ability to counter other adaptive players is doubted.

Monte Carlo Planning

This type of planning generates a set of simulations for all possible actions, it then chooses the plan that corresponds with the best simulation for the player. Because in an RTS game the amount of possible actions is enormous, an abstraction of actions and states has to be found.

The problem with this technique is that it requires a lot of calculating and it doesn't learn from previous mistakes.

Case Based Planning

This technique is based on case based reasoining, which is similar to the dynamic scripting method. It is based on states and looks at past experience to calculate the best sub plan in the current state. Case Based Planning doesn't model the opponent and wont do adversarial planning. It needs a database of predefined tactics. The algorithm picks a random tactic and remembers the outcome. This technique allows an expert to play the game and teach the AI what good decisions are, simplifying the process of designing an AI.

The problem with Case Based Planning is that it needs to be trained against opponents before it can become strong. The more complex and diverse the opponents are, the longer it will take the CBP to learn how to win.

The author finally concludes that the most advanced technique is the Case Based Planning because it can adapt, change and enhance strategies, but pointing out which one of the three is the best is hard because advance scripts have been made in commercial games and the performance of the Case Based or Monte Carlo planners have yet to be proved in more complex games.

Read the full article here!

Wijers, S., 2010, Real-Time strategy high-level planning. Obtained in August 11th, 2011 from PIXEL: www.inter-actief.utwente.nl/studiereis/pixel/files/indepth/StefanWeijers.pdf

Game: Virulent

Virulent is a game where you control a virus and your goal is to infect the cells of the body you're in.

The game controls are easy to understand as they are mouse-only and movement is done by drawing a line with your mouse which will be the path your virus will follow.

It includes basic immunological system information which trasnforms into gameplay mechanics. For example, B-cells will kill the virus so you must be careful when moving around. Also, as the game progresses, antibodies will start to roam around the area so you have to maneuver your units skillfully to avoid them while multiplying your virus.

The game is short, but a good example of real-world knowledge transformed into gameplay mechanics.

PLAY THE GAME HERE!

Morgridge Institute for Research (2011). Virulent. Obtained in August 5th, 2001 from http://discovery.wisc.edu/media/MIR_images/erca/virulent_web/Virulent_2011_06.html

Article: Foundations of a Successful RTS

Foundations of a Successful RTS

[Tom Cadwell, 1999]

In this interesting article, Tom analyzes some aspects that RTS games should be considered when designing a RTS game.

Principles of RTS Balance:

1. As a general rule, if race A builds up a unit mix and attcks race B, there should exist a cost/effective counter for B that is available around the same time and requires slightly less time to build. Also, versatile units should be less powerful compared to specialist units.
2. Balane should take the form between unit mixes, not individual units. This is to avoid the "just build a large number of the same unit" problem.
3. Consider maximum firepower conentration. Many super long range units is bad.
4. As the range of the unit increases, the firepower should be reduced. This is unrealistic, but balances the game.
5. Map lag. Don't allow units, especially early units, to cross the map too quickly.
6. Combat formulae and the various values units have need to be very flexible to be able to fix balance if problems are discovered later on.
7. Every attack should have a risk. There should always be some opportunity for you opponent to counter your attack and destroy your resources cos effectively.
8. Endgame driving forces must be in place. Attrition is the way to go. Bigger isn't necesarily better. Avoid getting to the point of players having to control hundreds of units. Also, static defenses need a way of being cracked so a player who suffers from attrition will be unable to continue.
9. The more a unit can move, the less powerful it should be, but some units that break this rule can be in the game to avoid map specific imbalances.

Design principles

1. If it isn't fun, it should't be in a game. Avoid tedious tasks. Avoid lots of administative stuff unless your game is designed around them. And always avoid AI that acts stupid, this will 100% of the time annoy the player.
2. Gameplay over realism. The game needs to "make sense" but that doesn't mean hyper realistic mechanics. If you need to sacrifice one or the other, sacrifice realism.
3. The aspects of a game that appeal the most to the hardcore gamer should tend to be in the hidden features (hotkeys not visible on the screen, combat bonuses for cover, etc). Don't try to make the game "complex" by cluttering the screen with buttons.
4. Sound effects and visual effects are extremely useful and don't affect play balance. Use them extensively.
5. Straegic wealth should always be sought after. This is accomplished by complex unit interactions or simple but elegant resource system. Chess is a great example of simple but elegant game.
6. Give units a "purijavascript:void(0)ty of purpose". Consider what do race X needs to flesh out its combat abilities in a unique way and come up with units that fit that feel. Also avoid giving units more than one purpose and having more than one unit per race that does the same.
7. Never let a unit become obsolete. This confuses players and leads to more imbalances.

To read the complete article, go to StrategyGamingOnline.

Tom Cadwell, 1999. Foundations of a Successful RTS. Obtained in Jul 19th, 2011 from Strategy Gaming Online: http://www.strategy-gaming.com/editorials/sucessful_rts.shtml

Article: Using Potential Fields in a Real Time Strategy Game

Using Potential Fields in a Real-Time Strategy Game Scenario

[Johan Hagelback, 2009]

In this article/tutorial Johan explores a potential field based approach to real-time planning and navigation.

Potential fields are similar to influence maps in the fact that they are both constructed by placing numerical values on a grid map. The difference is that influence maps use player units/buildings to set the numerical values and potential fields place the numerical value in areas of interest.

An example of an influence map.

After the potenial map spreads through the map (fading its values to zero), a moving unit can easily reach it's destination by simply moving to its current more attractive adjacent tile. The idea is to use attractive fields in the destinations and repelling fields in the obsacles. This will create a potential map that will guide the unit through the terrain.

This can also have other applications, for example, when a unit ends its "attack phase" and enters a "reload phase", it can create repellant fields to flee if the enemy unit comes closer. Another application can be for long ranged units. If they place a small repellant field to enemy units to create a "ring" for the optimum firing range.

An example of a potenial field with obstacle repellant fields.

One of the advantages of using potential fields is the ability to handle dynamic game worlds. Agents only need to see one step ahead to move. They don't need to know the full path to their destination, eliminating the risk of obsolete paths due to changes in the game world. Also, it can easily create complex behaviors by just modifying the fields, for example, several unis will surround an enemy while being at shooting range and avoiding other friendly units who are also attacking the same enemy.

The main drawback from this approach would be the fact that it would need to be carefully programmed as to require an efficient amount of resources. Although the author solved this issue, it's definetely not something trivial.

For more information, including common problems and solutions, hit the link.

Hagelbäck, Johan, 2009. Using Potential Fields in a Real Time Strategy Game Scenario. Obtained in July 28th, 2011 from AiGameDev.com : http://aigamedev.com/open/tutorials/potential-fields/

Paper: Map-Adaptive Artificial Intelligence for Video Games

Map-Adaptive Artificial Intelligence for Video Games

[Laurens van der Blom, 2007]

The author of this paper explains how to implement an AI opponent in a RTS game that takes into account the properties of the map it is placed in. For example, the AI makes decisions based on the amount of resources nerby, the location of cliffs and/or narrow passages, and the overall strategy of the opponent (if the opponent is playing offensively or defensively).

To achieve this, a ID3 Decision Tree was used in combination with fuzzy logic to allow the AI to find the best course of action depending on the current state of the game.

The game in which the AI was tested was a moderately complex RTS so the following set of rules were used:

1. Construct metal extractors at near metal resources.
2. Construct metal extractors at far away metal resources.
3. Place offensive units at relatively narrow roads.
4. Place offensive units at own base.
5. Place artillery on cliffs.
6. Protect operational metal extractors.
7. Protect artillery on cliffs.

The AI was tested against a computer controlled opponent and a human opponent in five different types of maps designed to test specific attributes like amount of resources or presence of narrow paths. In most of their tests, the AI performed as they expected but when placed against a human player it lost most of the games (even if it also performed as expected).

What I liked about this approach is that the AI actually varies the strategy if the enemy is near or not and if the enemy is attacking or not and it's relatively easy to distinguish what actions are being performed by it. And while this approach works, the AI had a hard time beating human players. That may be caused because, as the author states in the article, the decision tree needed more specific cases. Maybe the use of a nerual network could remedy this issue, but it could make the implementation a little more complicated or even change it completely.

Read article, complete with experiments and results here.

Van der Blom, Laurens, 2007. Map-Adaptive Artificial Intelligence for Video Games. Obtained in July 21st, 2011. http://www.unimaas.nl/games/files/bsc/Blom_BSc-paper.pdf

RTS example project in Unity

I just stumbled across a public project in Unity that can be extremely helpful when trying to make a RTS style game in this game engine.

The project's last official update(1.1) was on august 2009, but the community has been adding little bits of stuff and posting small updates on their own (a quick search through the post's replies is enough to find all the different updates). Someone even created a SVN for the project and someone created google docs for documentation. (Open source projects with a great community are amazing!)

This project is free for personal and commercial use which is great and it always helps not having to write everything from scratch.

The project can be found here.

An example of the project running (version 1.1) can be played here.

Paper: Random Map Generation for Strategy Games

Random Map Generation for Strategy Games

[Shawn Shoemaker, 2004]

This paper explains how to generate a random map for a RTS game using clumps.

One of the most important aspects to consider when creating random maps for these games is the balance. Every player must have a balanced amount of terrain near them and a balanced amount of resources.

This can be achieved with clumps which are pieces of land that iteratively grow untill the map is filled. Initially, the map contains an empty grid with a tile for every player. This initial tiles are equally separated from each other.

Then, each tile grows iteratively by one tile, creating a clump of land untill the maximum growth size is reached or there are not enough tiles to expand again.

This leaves us with a map grid of zones for each player with roughly the same space. After each player's space has been determined, terrain height details will be generated, trying to give each clump a balanced configuration. Finally, resources can be placed inside each of the clumps, ensuring that each player can obtain the same amount of resources in one way or another.

This technique is useful as a general map creation algorithm, for either simple or complicated maps for different types of games.

A more detailed explanation of the algorithm and some examples can be found in the book AI Game Programming Wisdom 2.

Shoemaker, Shawn (2004). Random Map Generation for Strategy Games. In Steve
Rabin (Ed.) AI Game Programming Wisdom 2. United States, Charles River Media
Inc.