Moving in a formation is a basic group behaviour needed in computer games. This chapter presents different methods for co-ordinating formations in real-time game environments. To compare the methods in different situations, how well the formations stay organized and how fast they are able to navigate through test courses is measured. Additionally, the authors analyse whether the methods can cope with pathological situations such as passing through a narrow canyon. The effect of different formation types and study the scalability when the formations get larger are also compared.
TopIntroduction
Computer-controlled entities often have to move in a formation. For example, a real-time strategy game can include hundreds of computer-controlled entities on a battlefield, which are not to be controlled individually but as groups. If the entities are commanded on this higher level, the player can control even larger units with less effort. Therefore, formations can improve the visual appeal and realism of a game, because the units seem to move in a natural looking way rather than in unorganized groups.
The task of co-ordinating formations can be divided into three subtasks:
- 1.
Define a control structure for the formation.
- 2.
Find a path for the whole formation.
- 3.
Steer the individual entities.
Control structure is used to model the formation, and it defines how to calculate the places of the agents (or entities) in a formation (for basic formation types, see Figure 1). To realize this we can choose from several different control structures, which can be based on following a leader or the average position of the neighbours.
Figure 1. Basic formations types: (a) column, (b) line, (c) wedge, (d) vee, (e) box, (f) right flank, (g) left flank, and (h) diamond
In path finding, we search for the shortest viable path from a start position to a goal position. For this subtask, the most commonly used path finding algorithm is A*, which has many game-dependent variants to make it faster. The path found by the algorithm can look unrealistic, but it can be improved by path realization methods to make it look more natural.
When we have found a path, the agents are guided through the game world using a steering method. It tries to keep the agents as close to their intended place in the formation as possible. Moreover, it should allow the agents to deviate if the environment does not allow them to maintain a tight formation.
In general, decision-making can be divided into three levels: strategic, tactical, operative (Smed & Hakonen, 2006). Strategic level contains long-term decisions based on large amounts of data. Tactical level handles group-level decisions aiming at fulfilling a plan made at the strategic level. Operational level focuses on short-term decisions from a limited set of alternatives. In this chapter, we will focus on operational level decision-making in the domain of co-ordinating formations. We assume that the path for the formation has already been found and we must now steer the group using a control structure. For this reason, we have implemented three different formation methods: a steering behaviour-based method, a fuzzy logic controller, and a mass-spring system. We test the performance of these methods with different metrics, measuring the level of organization of a formation and the speed at which they solve test tracks. We analyse closely pathological cases such as passing through a narrow canyon. Moreover, we compare the results for different types of formations (e.g., square, line and column) to see their effect on the methods. Finally, we present results from massive formations that can include up to 100 computer-controlled entities.
TopIn this section, we present methods for modelling and controlling formations. First we look at different approaches to model formations, which are classified according to how the point-of-reference of an agent in a formation is calculated. After that, we study obstacle avoidance and, finally, how to maintain the correct position in a formation. We do not focus on path finding but assume that the path to follow has been given (e.g., from a human player or a higher-level decision-making system).
Most of the research work on formation has been carried out in the field of robotics, whereas for computer games, the research has been scarce: Dawson (2002) gives a short introduction to the use of formations in computer games, Verth et al. (2000) present a solution used in the game Force 21, and Pottinger (1999a; 1999b) proposes ideas albeit without a deeper analysis. Heiden et al. (2008) discuss a dynamic approach on organizing formations in a real-time strategy game.