Resources

Introduction

I am Yessica Servin Dominguez, student of the Bachelor’s Degree in Video Games by UPC at CITM. This content is generated for the second year’s subject Project 2, under supervision of lecturer Ricard Pillosu. Especial thanks to Sandra Alvarez, she also did the same research so check out her project here

Objective

The objetive of this research is to implement group pathfinding. To reach this we'll analysis differents group movement implented in RTS games, we'll see different forms to implemantate it. This feature's something that you can do in many ways, it depends on your game characteristics.

Disclaimer: Although this implementation is based on different RTS games it could also be applied in different kind of games. AND please check out reference links I used to develop this project you could find more information

Espected Result

Pathfinding

To implement a group movement the first step is to be able to move one unit, this one needs to find the best way to point A to B, the best way to do this is by using the Jump Point Search or A* algorithm , it's generally used in most of the games cause it takes lower computation power, and if you need a lot of units to be searching for the goal that is an important thing to consider.
If you are a beginner and your game doesn't need that many units, you can also see Breadth First Search algorithm or Dijkstra’s Algorithm. These methods are more easy to understand and also to implement and a good point to start.

Goal Tile

If we try units to move to the same Tile they would get overlapping, or if we got collision system only one unit would get there and the other was will still try to move

To solve this one idea is to transfer the state of "found goal" through units, so if a unit tries to get in a tile were there is one already but both of them got the same the destination and one found it the other one will too, and stop moving. This implementation is called "transitive bumping" and it's a good idea but cause some problems like: - Units placed in line instead of a group So what we are going to do is determine an offset to the goal so every entity got its own goal. This offset is calculated with the start position of every unit. We find the middle center between entities and translate this point to the destination and place entities respecting the original distance between this one and the middle point.

If you don't see it yet here's a gif to illustrate this

GifExplenation
The blue point is the middle point and the red one is the destination, and squares are entities This is something that games like Command & Conquer: Red Alert 2 and The Maestros seems to be doing.

Command & Conquer:Red Alert 2

The Maestros

As I said before in this game units mantein the inital formaton. In this game, you could see that on the feet of every entity selected there is a circle this is used as the area that an entity take up and it is considered to determinate the position of the entities. So when an entity is going to a tile to know that this one has reached it we watch if that point was inside this area.

The transitive bumping is something that works really well when the group is small and at the start of the movement they are near each other, also it's a really simple implemantation

The problem with this is that as they started so far away from the group they end up separated, instead to join the group. To solve this problem we are going to limit the offset of the entities to the goal. In my case I made a Lider in case a unit don't have a path cause it's goal was invalid or was out of this ratio of offset units can follow.

before and after

Collition system

For preventing entities to collide to each other, we are going to not let them collide in the first place. To do this before they start moving we are going to consider all units, their state, and their move. We are going to identify which kind of collision the unity is going to have so we can prevent it.

First kind of collition

An unit try to enter in a tile where there is a unit not moving. To solve this problem you should consider de direction of the unit that is moving. To move the one that lies still in a tile that doesn't bother the unit that is moving. Or if you want to make the effect that one is pushing the other, you should do the opposite make.






This is done in the "Supreme Commander 2" in witch units move away from the path of other


Second kind of collition

Two units want to get into the same tile, in this one there is no unit.


To solve this possible collition one unit should wait the other one to move, to this tile and get out. Also consider if this tile is the goal of one of them, in which case the first unit will pass would be the one that it's not. You probably won't notice this implementation depending on the units speed.




Third kind of collition

Two agents reach the cell of each other Happens if the agents are walking towards each other (in opposite directions).










Reference information

The objetive of this research is to implement group pathfinding. To reach this we'll analysis differents group movement implented in RTS games, we'll see different forms to implemantate it. This feature's something that you can do in many ways, it depends on your game characteristics.

Disclaimer: Although this implementation is based on different RTS games it could also be applied in different kind of games. AND please check out reference links I used to develop this project you could find more information


Espected Result

Pathfinding

To implement a group movement the first step is to be able to move one unit, this one needs to find the best way to point A to B, the best way to do this is by using the A* algorithm , it's generally used in most of the games cause it takes lowe computation power, and if you need a lot of units to be searching for the goal that is an important thing to consider. If you are a beginner and your game doesn't need that many units, so you can also see Breadth First Search algorithm or Dijkstra’s Algorithm. These methods are more easy to understand and also to implement and a good point to start.

Goal Tile

If we try units to move to the same Tile they would get overlapping, or if we got collision system only one unit would get there and the other was will still try to move

To solve this one idea is to transfer the state of "found goal" through units, so if a unit tries to get in a tile were there is one already but both of them got the same the destination and one found it the other one will too, and stop moving. This implementation is called "transitive bumping" and it's a good idea but cause some problems like: - Units placed in line instead of a group So what we are going to do is determine an offset to the goal so every entity got its own goal. This offset is calculated with the start position of every unit. We find the middle center between entities and translate this point to the destination and place entities respecting the original distance between this one and the middle point.

If you don't see it yet here's a gif to illustrate this

GifExplenation
The blue point is the middle point and the red one is the destination, and squares are entities This is something that games like Command & Conquer: Red Alert 2 and The Maestros seems to be doing.

Command & Conquer:Red Alert 2

The Maestros

As I said before in this game units mantein the inital formaton. In this game, you could see that on the feet of every entity selected there is a circle this is used as the area that an entity take up and it is considered to determinate the position of the entities. So when an entity is going to a tile to know that this one has reached it we watch if that point was inside this area.

The transitive bumping is something that works really well when the group is small and at the start of the movement they are near each other, also it's a really simple implemantation

The problem with this is that as they started so far away from the group they end up separated, instead to join the group. To solve this problem we are going to limit the offset of the entities to the goal. In my case I made a Lider in case a unit don't have a path cause it's goal was invalid or was out of this ratio of offset units can follow.

before and after

Collition system

For preventing entities to collide to each other, we are going to not let them collide in the first place. To do this before they start moving we are going to consider all units, their state, and their move. We are going to identify which kind of collision the unity is going to have so we can prevent it.

First kind of collition

An unit try to enter in a tile where there is a unit not moving. To solve this problem you should consider de direction of the unit that is moving. To move the one that lies still in a tile that doesn't bother the unit that is moving. Or if you want to make the effect that one is pushing the other, you should do the opposite make.






This is done in the "Supreme Commander 2" in witch units move away from the path of other


Second kind of collition

Two units want to get into the same tile, in this one there is no unit.


To solve this possible collition one unit should wait the other one to move, to this tile and get out. Also consider if this tile is the goal of one of them, in which case the first unit will pass would be the one that it's not. You probably won't notice this implementation depending on the units speed.




Third kind of collition

Two agents reach the cell of each other Happens if the agents are walking towards each other (in opposite directions).










Reference information