Bots for real-time strategy (RTS) games may be very challenging to implement. A bot controls a number of units that will have to navigate in a partially unknown environment, while at the same time avoid each other, search for enemies, and coordinate attacks to fight them down. Potential fields are a technique originating from the area of robotics where it is used in controlling the navigation of robots in dynamic environments. Although attempts have been made to transfer the technology to the gaming sector, assumed problems with efficiency and high costs for implementation have made the industry reluctant to adopt it. We present a multiagent potential field-based bot architecture that is evaluated in two different real-time strategy game settings and compare them, both in terms of performance, and in terms of softer attributes such as configurability with other state-of-the-art solutions. We show that the solution is a highly configurable bot that can match the performance standards of traditional RTS bots. Furthermore, we show that our approach deals with Fog of War (imperfect information about the opponent units) surprisingly well. We also show that a multiagent potential field-based bot is highly competitive in a resource gathering scenario.
A real-time strategy (RTS) game is a
game in which the players use resource gathering, base building, technological
development and unit control in order to defeat its opponent(s), typically in
some kind of war setting. The RTS game is not turn-based in contrast to board
games such as Risk and Diplomacy. Instead, all decisions by all players have to
be made in real time. Generally the player has a top-down perspective on the
battlefield although some 3D RTS games allow different camera angles. The
real-time aspect makes the RTS genre suitable for multiplayer games since it
allows players to interact with the game independently of each other and does
not let them wait for someone else to finish a turn.
In RTS games computer bots often “cheats,”
that is, they have complete visibility (perfect information) of the whole game
world. The purpose is to have as much information available as possible for the
artificial intillegence (AI) to reason about tactics and strategies in a certain environment. Cheating
is, according to Nareyek, “very annoying for the player if
discovered” and he predicts the game AIs to get a larger share of the
processing power in the future which in turn may open up for the possibility to
use more sophisticated AIs . The human player in most modern RTS games does not
have this luxury, instead the player only has visibility of the area populated
by the own units, and the rest of the game world is unknown until it gets
explored. This property of incomplete information is usually referred to as Fog
of War or FoW.
In 1985, Ossama Khatib introduced a new concept while
he was looking for a real-time obstacle avoidance approach for manipulators and
mobile robots. The technique which he called Artificial Potential Fields moves a manipulator in a field of forces. The position to be reached is an
attractive pole for the end effector (e.g., a robot) and obstacles are
repulsive surfaces for the manipulator parts . Later on Arkin  updated the knowledge by
creating another technique using superposition of spatial vector fields in
order to generate behaviors in his so called motor schema concept.
Many studies concerning potential fields are related
to spatial navigation and obstacle avoidance (see, e.g., [4, 5]). The technique is really
helpful for the avoidance of simple obstacles even though they are numerous.
Combined with an autonomous navigation approach, the result is even better,
being able to surpass highly complicated obstacles .
Lately some other interesting applications for
potential fields have been presented. The use of potential fields in
architectures of multi agent systems is giving quite good results defining the
way of how the agents interact. Howard et al. developed a mobile sensor network
deployment using potential fields , and potential fields have been used in robot soccer
[8, 9]. Thurau et al.  have developed a game bot
which learns reactive behaviours (or potential fields) for actions in the
first-Person Shooter game Quake II through imitation.
The article is organised as follows. First, we propose
a methodology for multiagent potential field- (MAPFs-) based solution in an RTS
game environment. We will show how the methodology can be used to create a bot
for a resource gathering scenario (Section 4) followed by a more complex
tankbattle scenario in Section 5. We will also present some preliminary results
on how to deal with imperfect information, Fog of War (Section 6). The
methodology has been presented in our previous papers [11, 12]. This article summarises the
previous work and extends it by adding new experiments and new results. Last in
this article, we have a discussion and line out some directions for future
2. A Methodology for Multiagent Potential Fields
When constructing a multiagent potential field-based
system for controlling agents in a certain domain, there are a number of issues
that we must take into consideration. It is, for example, important that each
interesting object in the game world generates some type of field, and we must
decide which objects can use static fields to decrease computation time.
To structure this, we identify six phases in the
design of an MAPF-based solution:
(1)the identification of objects;(2)the identification of the driving forces (i.e., the fields) of the game;(3)the process of assigning charges to the objects;(4)the granularity of time and space in the environment;(5)the agents of the system;(6)the architecture of the MAS.
In the first phase, we may ask us
the following questions. What are the static objects of the environment?
That is, what objects keep their attributes
throughout the lifetime of the scenario? What are the dynamic objects of
the environment? Here we may identify a number of different ways that objects
may change. They may move around, if the environment has a notion of physical
space. They may change their attractive (or repulsive) impact on the agents.
What is the modifiability of the objects? Some objects may be consumed,
created, or changed by the agents.
In the second phase, we identify the driving
forces of the game at a rather abstract level, for example, to avoid obstacles,
or to base the movements on what the opponent does. This leads us to a number
of fields. The main reason to enable multiple fields is that it is very easy to
isolate certain aspects of the computation of the potentials if we are able to
filter out a certain aspect of the overall potential, for example, the
repulsive forces generated by the terrain in a physical environment. We may
also dynamically weight fields separately, for example, in order to decrease
the importance of the navigation field when a robot stands still in a
surveillance mission (and only moves its camera). We may also have strategic
fields telling the agents in what direction their next goal is, or tactical
fields coordinating the movements with those of the teammate agents.
The third phase includes placing the objects in the different fields. Static objects
should typically be in the field of navigation. The potentials of such a
field are precalculated in order to save precious run time CPU resources.
In the fourth phase, we have to decide the resolution of
space and time. Resolution of space means how detailed the
navigation in the game world should be. Should for example
the agents be able to move to every single point in the world,
or should the game world be divided into a grid with tiles of
for example points in the world? Resolution of time means
how often the potential fields should be updated. If the agents
are able to move around in the environment, both these measures
have an impact on the lookahead. The space resolution obviously,
since it decides what points in space that we are able to
access, and the time in that it determines how far we may get
in one time frame (before it is time to make the next decision
about what to do).
The fifth phase is to decide what objects to agentify and set the repertoire of those
agents: what actions are we going to evaluate in the lookahead? As an example,
if the agent is omnidirectional in its movements, we may not want to evaluate
all possible points that the agent may move to, but rather try to filter out
the most promising ones by using some heuristic, or use some representable
In the sixth step, we design the architecture
of the MAS. Here we take the unit agents identified in the fifth phase, give
them roles, and add the supplementary agents (possibly) needed for
coordination, and special missions (not covered by the unit agents themselves).
strategy (ORTS)  is
a real-time strategy game engine developed as a tool for researchers within
artificial intelligence (AI) in general and game AI in particular. ORTS uses a
client-server architecture with a game server and players connected as clients.
Each timeframe clients receives a data structure from the server containing the
current game state. Clients can then call commands that activate and control
their units. Commands can be like “move unit A to or attack opponent unit X with unit A.” The game server executes the client
commands in random order.
Users can define different types of games in scripts
where units, structures, and their interactions are described. All types of
games from resource gathering to full real-time strategy (RTS) games are
We will begin by looking at a one-player resource
gathering scenario game called Collaborative Pathfinding, which was part
of the 2007 and 2008 ORTS competitions . In this game, the player has 20 worker units. The
goal is to use the workers to mine resources from nearby mineral patches and
return them to a base. A worker must be adjacent to a mineral object to mine,
and to a base to return resources. As many resources as possible will be
collected within 10 minutes.
This is followed by looking at the two-player games, Tankbattle,
which was part of the 2007 and 2008 ORTS competitions  as well.
In Tankbattle, each player has 50 tanks and
five bases. The goal is to destroy the bases of the opponent. Tanks are heavy
units with long fire range and devastating firepower but a long cool-down
period, that is, the time after an attack before the unit is ready to attack
again. Bases can take a lot of damage before they are destroyed, but they have
no defence mechanism of their own so it may be important to defend
our own bases with tanks. The map in a tankbattle
game has randomly generated terrain with passable lowland and impassable
Both games contain a number of neutral units (sheep).
These are small indestructible units moving randomly around the map. The
purpose of sheep is to make pathfinding and collision detection more complex.
4. Multiagent Potential Fields in ORTS
First we will
describe a bot playing the Collaborative Pathfinding game based on MAPF
following the proposed methodology. Collaborative Pathfinding is a 1-player
game where the player has one control center and 20 worker units. The aim is to
move workers to mineral patches, mine up to 10 resources (the maximum load a
worker can carry), then return to a friendly control center to drop them off.
4.1. Identifying Objects
We identify the
following objects in our application: Cliffs, Sheep, Base stations, and workers.
4.2. Identifying Fields
We identified five tasks in ORTS: avoid colliding with the terrain, avoid getting stuck at
other moving objects, avoid colliding with the bases, move to the bases to
leave resources, and move to the mineral patches to get new resources. This
leads us to three major types of potential fields: a field of navigation,
a strategic field, and a tactical field.
The field of navigation is a field generated by
repelling static terrain. This is because we would like the agents to avoid
getting too close to objects where they may get stuck, but instead smoothly
pass around them.
The strategic field is a dynamic attracting field. It
makes agents go towards the mineral patches to mine, and return to the base to
drop off resources.
Own workers, bases, and sheep generate small repelling
fields. The purpose of these fields is the same as for obstacle avoidance; we
would like our agents to avoid colliding with each other and bases as well as
avoiding the sheep. This task is managed by the tactical field.
4.3. Assigning Charges
Each worker, base, sheep, and cliffs has a set of charges which generates a potential field
around the object. These fields are weighted and summed together to form a
total potential field that is used by our agents for navigation.
example, impassable terrain, generate a repelling field for obstacle avoidance.
The field is constructed by copying pregenerated matrixes of potentials into
the field of navigation when a new game is started. The potential all cliffs
generate in a point is calculated as the lowest potential a cliff
generates in that point. The potential in a point at distance from the closest impassable terrain tile is calculated as:
Own worker units generate repelling fields for obstacle avoidance. The potential at distance from the center of another worker is
Sheep. Sheep generate a small repelling field for obstacle avoidance. The
potential at distance from the center of a sheep is calculated as
Own Bases. The own bases generate two different fields depending on the current state of a
worker. The base generates an attractive field if the worker needs to move to
the base and drop off its resources. Once it has arrived at the base, all the
resources are dropped. The potential at distance from the center of the base is calculated as
In all other states of the worker, the own base
generates a repelling field for obstacle avoidance. Below is the function for
calculating the potential at distance from the center of the base. Note that this
is, of course, the view of the worker. The base will effect some of the workers
with the attracting field while at the same time effect the rest with a
repelling field. If a point is inside the quadratic area the base occupies, the
potential in those points is always 10000 (potential used for impassable
similar to own bases, generate attractive fields for all workers that do not
carry maximum loads and a repelling field for obstacle avoidance when they do.
The potential of the attractive field is the same as the attractive field
around the own base in (4).
In the case when minerals generate a repelling field,
the potential at distance from the center of a mineral is calculated as
4.4. The Granularity of the System
Since the application is rather simple, we use full resolution of both the map and the
time frames without any problems.
4.5. The Agents
The main units
of our system are the workers. They use a simple finite state machine (FSM)
illustrated in Figure 1 to decide what state they are in (and thus what fields
to activate). No central control or explicit coordination is needed, since the
coordination is emerging through the use of the charges.
4.6. The Multiagent System Architecture
In addition to
the worker agents, we have one additional agent that is the interface between
the workers and the game server. It receives server information about the
positions of all objects and workers which it distributes to the worker agents.
They then decide what to do, and submit their proposed actions to the interface
agent which in turn sends them through to the ORTS server.
4.7. Experiments, Resource Gathering
Table 1 shows
the result from the Collaborative Pathfinding game in 2008 years' ORTS
tournament. It shows that an MAPF-based bot can compete with A*-based solutions
in a resource gathering scenario. There are however some uncertainties in these
results. Our bot has disconnected from the server (i.e., crashed) in 30 games.
The reason for this is not yet clear and must be investigated in more detail.
Another issue is that Uofa has used the same bot that they used in the 2007
years' tournament, and the bot had a lower score this year. The reason, according
to the authors, was “probably caused by a pathfinding bug we
Still we believe that with some more tuning and bug fixing our bot can probably
match the best bots in this scenario.
5. MAPF in ORTS, Tankbattle
2-player Tankbattle game, each player has a number of tanks and bases, and the
goal is to destroy the opponent bases. In  we describe the implementation of an ORTS bot playing
Tankbattle based on MAPF following the proposed methodology. This bot was
further improved in  where a number of weaknesses of the original bot were
addressed. We will now, just as in the case of the Collaborative pathfinding
scenario, present the six steps of the used methodology. However, there are
details in the implementation of several of these steps that we have improved
and shown the effect of in experiments. We will therefore, to improve the flow
of the presentation, not present all of them in chronologic order. Instead we
start by presenting the ones that we have kept untouched through the series of
5.1. Identifying Objects
We identify the following objects in our application: Cliffs, Sheep, and own (and opponent)
tanks and base stations.
5.2. Identifying Fields
four tasks in ORTS: Avoid colliding with the terrain, Avoid getting stuck at
other moving objects, Hunt down the enemy's forces, and Defend the bases.
In the resource gathering scenario we used the two major types: field of
navigation and strategic field. Here we add a new major type of
potential field: the defensive field.
The field of navigation is, as in the previous example
of Collaborative pathfinding, a field generated by repelling static terrain for
The strategic field is an attracting field. It makes units
go towards the opponents and place themselves on appropriate distances where
they can fight the enemies.
The defensive field is a repelling field. The purpose
is to make own agents retreat from enemy tanks when they are in cooldown phase.
After an agent has attacked an enemy unit or base, it has a cooldown period
when it cannot attack and it is therefore a good idea to stay outside enemy
fire range while being in this phase. The defensive
field is an improvement to deal with a weakness found in the original bot
Own units, own bases, and sheep generate small
repelling fields. The purpose is the same as for obstacle avoidance; we would
like our agents to avoid colliding with each other or bases as well as avoiding
the sheep. This is managed by the tactical field.
5.3. Assigning Charges
The upper picture in Figure 2 shows part of the map
during a tankbattle game. The screenshots are from
the 2D GUI available in the ORTS server. It shows our agents (light-grey
circles) moving in to attack an opponent unit (white circle). The area also has
some cliffs (black areas) and three sheep (small dark-grey circles). The lower
picture shows the total potential field in the same area. Dark areas have low
potential and light areas have high potential. The
light ring around the opponent unit, located at maximum shooting distance of
our tanks, is the distance from which our agents
prefer to attack opponent units. The picture also shows the small repelling
fields generated by our own agents and the sheep.