View Research-Project-Group-Movement on GitHub

Personal Research: Group Movement

The web page and the GitHub repository where it is created from are dedicated to how to generate Group Movement for an RTS game.

Who am I?

I am Tomás Carreras (GitHub username tomascarreras1000), student of the Bachelor’s Degree in Video Games by UPC at CITM-TTC. This content is generated for the second year’s subject Project 2, under supervision of lecturer Ramon Santamaria.

What is included in this research?

What should you know about Group Movement before starting?

Introduction

In games you usually have to control a unit, being a single character or multiple units, which means they have to move from point A to point B. In the case of RTS games, you have to move one or more units, which may be the same or different ones, across the map. Every unit has to react to other units, buildings, enemies, resources, etc. in order to move coherently and at the same time follow the player’s orders. However, there may be some problems we have to be aware of, like units overlapping or pathfinding algorithms. These problems can have different approaches, which will be dealt with later in this research, what methods are popular in different games and we will genereate our own code so we can develop a group movement which can be applied to an RTS game.

Objective

The objetive of this research is to implement group pathfinding. To reach this we’ll analyse different group movement implented in RTS games and decide which one would work best for us and work around it.

Have you seen it in games?

Age of Empires II

Age_of_Empires

In Age of Empires II, troops move to the position where the player has sent them by using A* algorithm. However, this movement depends of various factors, such as the number of units, the type of units, and (for some of them) the formation selected. The moving function isn’t exactly alike for all units: military units form up in a group in the formation the player specifies and, once in formation, they will move to their destination, unlike the villagers who just go to where they were sent to. The speed of the group is also something that can vary depending on the speed of the individual units on the group (a group will move slower if it contains an elephant due to this unit’s slow movement speed). Units avoid buildings and other obstacles but they can collide with other units, at least during a movement, not at the end of it.

StarCraft and StarCraft II

StarCraft

In StarCraft, units constantly check whether they can advance through their path, if at some point they can’t, after a while it will recalculate a new path having in mind the where it got stuck last time and avoiding that.

StarCraft_II

In StarCraft II, the units will collide with each other preventing overlapping and will each go to the specified location.

What is the approach to this problem in this research?

First Idea

As we implied in the introduction, moving troops in groups can be a real challenge challenge, and many games have to deal with it, specially in RTS, where there are many units that may have the same destination or that have to re-calculate this destination midways. Then, how do we make units cooperate with each other so they move coherently? The answer, of course, is pathfinding. Pathfinding is the technique of finding the best path from point A to point B. If we implement it correctly, together with individual unit movement and their behaviours related with the other entities, we can achive a good, coordinated group movement.

Movement

First we need to get a unit from A to B when ordered to do so. Pathfinding, as said before, enables us to calculate it. We will use a tile-based greedy algorithm: A*. We will use a basic implementation of it.

A* gives us a path from A to B, but it takes a good amount of time for it to retrieve this path. When dealing with only one unit is not a problem, but as we icrease the number of entities, it becomes more complex, and it may take too much time. Therefore, we would need some optimizations to reduce the CPU load. However, due to the scope of this research and it is not the main topic, I will not go into detail. Just be aware that this is a problem you may have.

Group Movement

When we move a single unit, we just have to give this entity the order of moving from point A to point B. However, when we have move more than one, this complicates a little bit, since only one of the units will be moving from A to B, the others will start from a different point of origin and should end in a position around B, but not exactly it to avoid overlapping. Nevertheless, bear in mind that all of them will be receiving the same instruction!

So a simple approach to group momevemnt is to select all the entities and then calculate how to get from A to B for the first one in the list. The others, however, will take into account that this spot has already been taken and will get as their destiny a surrounding tile, if walkable. And like this from this unit onwards. This will be done using pathfinding. This will keep the group together, with the same destination, but without overlaps in the end so the player can continue treating them as individuals.

Approach

Now that we have a basic idea of the most important concepts, we are going to look deeply into the matter of discussion.

In group movement we could have 3 different approaches:

  • Flow-based: The crowd as a whole is the main focus, not each unit. Individuals are equal and behavioural factors are heavily reduced.
  • Entity-based: Every movement is determined by some global laws, which are enforced to the individuals of the group.
  • Agent-based: Autonomous intelligent individuals. Action-reaction is local to each individual based on a set of rules.

However, all of them refer to the same concept: Steering behaviour. In 1986 a computer model was developed to simulate coordinated animal motion, such as the movement of bird flocks.

Steering

First, it is important to give credit to the developer of this idea, Craig Reynolds, a software engineer,expert in artificial life and computer graphics. You can check his web page here.

When talking about steering, it is important to also introduce the concept of Boids, which is this artificial life program that simulates the flocking behaviour of birds and is the short version of “bord-oid object”. The rules applied in the simplest Boids world are as follows:

  • Separation: steer to avoid crowding local flockmates.

Rule_separation

  • Aalignment: steer towards the average heading of local flockmates.

Rule_alignment

  • Cohesion: steer to move towards the average position (center of mass) of local flockmates.

Rule_cohesion

More complex rules can be added, such as obstacle avoidance and goal seeking.

The boids also have a region on which they are influenced by neighboring boids, this region is defined by an angle and distance, building a spherical field around each boid.

boid

To summarize, this concept could be defined as a set of rules that regulate the relationship between individuals of a group.

Behaviours

As said by Craig Reynolds himself, we can set mmany differen rules to keep our units moving in a structured way:

  • Simple behaviors for individuals and pairs:
    • Seek and Flee
    • Pursue and Evade
    • Wander
    • Arrival
    • Obstacle Avoidance
    • Containment
    • Wall Following
    • Path Following
    • Flow Field Following
  • Combined behaviors and groups:
    • Crowd Path Following
    • Leader Following
    • Unaligned Collision Avoidance
    • Queuing (at a doorway)
    • Flocking (combining: separation, alignment, cohesion)

However, as you can see, this by itself could be a single topic, so I won’t spend a lot of time on it: explaining each behaviour would be too much information for the scope of this project. But I recommend checking out the following link on the topic.

Pathfinding

A*

Many games use as a baseline for pathfinding implementations A*, a tile-based algorithm. These games did not have to deal with as many individuals as later sequels and new ips, so it was not much of a problem.

Flow Field

Flow Fields are an alternate way of doing pathfinding which works better for larger groups of units. A Flow Field is a grid where each grid square has a directional vector. This vector should be pointed in the direction of the most efficient way to get to the destination, while avoiding static obstacles.

Pathfinding algorithms work with graphs. If you have a graph of an immense number of small tiles and you issue an A* path you will have some serious performance problems. A key to most pathfinding implementations is to use a customized Navigation Mesh, which means a custom graph. Instead of having the regular tiles defined by the map, you can divide the map in zones, polygons or bigger tiles. Then, when issuing an A* request, the algorithm only navigates a few tiles instead of thousands, significantly improving performance. SC2 uses a navigation mesh and has a hierarchical division of the graph: it runs A* through the highest level (less nodes), traveling through tile “portals” and then issues a flow field request for the ones needed.

Performance

CPU is not affected by moving a single unit, but the movement of multiple units needs to be extremely conservative in its CPU usage. This is why, before making any decision that may affect the performance of the system, we need to prioritize. What is more important, minimize CPU usage or maximize the intelligence behind the movement? So, for example, when a unit needs to find a new, valid tile to move to, the possible, valid tiles are checked taking in account its priority. We could calculate this priority as the number of waypoints that the new path would have (maximize the accuracy behind the movement: the new tile would be the accurest tile that could have been found) or as the distance from the new tile to the goal tile (minimize CPU usage: since the unwalkable tiles are ignored, the new tile could be the closest to the goal tile, but not the best option when creating the new path). This would depend on the requirements your game and target device is.

Can it be improved?

One of the ways to improve the code is to change A* for a more modern pathfinder. A* is very basic, and has a high impact on performance. Flow Fields is a modern pathfinding tech for large groups of units, used in SC2 for example. So we implementing a solution in this direction would make the code more optimized. Making our pathfinding efficient is key in order to have groups in movement, A* is only to do basic code.

Also, since I have talked about steering behaviours, they would improve the code a lot. If no steering behaviours are used, the movement could be heavily improved when implementing some of them, both in terms of life-like feeling and performance. What if the way we move our groups enables us to only make a single path request? And on the contrary, what if our pathfinding tech enables us to move any number of units with the behaviours we want? As you can see, we can improve on A to improve B, and the other way too.

How can YOU do it?

UNDER CONSTRUCTION

How can you continue improving?

UNDER CONSTRUCTION

Here are the links and references where I got all the information I used to create this research.

Other Researches: