In an RTS game, how do I ensure that an enemy has a maximum of 3 attackers on him?

[farazk86]

I’m coding the combat system for my RTS game, and every time a unit spawns I iterate over all enemies and then attack the closest one. This is achieved using the below block of code:

void FindCurrentTarget()
    {
        //find all potential targets (enemies of this character)
        enemies = GameObject.FindGameObjectsWithTag(attackTag);

        //distance between character and its nearest enemy
        float closestDistance = Mathf.Infinity;
        GameObject potentialTarget = null;
        foreach (GameObject _enemy in enemies)
        {
            //check if there are enemies left to attack and check per enemy if its closest to this character
            if (Vector3.Distance(transform.position, _enemy.transform.position) < closestDistance && _enemy != null)
            {
                //if this enemy is closest to character, set closest distance to distance between character and enemy
                closestDistance = Vector3.Distance(transform.position, _enemy.transform.position);

                //also set current target to closest target (this enemy)
                if ((currentTarget == null) || ((currentTarget != null) && Vector3.Distance(transform.position, currentTarget.transform.position) > 2))
                {
                    potentialTarget = _enemy;
                }
            }
        }
        //set the current target at end of for loop, this is the closest enemy
        currentTarget = potentialTarget;

    }

This works as expected but the problem is that if I deploy 10 units, all 10 units will target the same closest unit and will gang up on the poor guy. These 10 units will then all move to the next guy and this way I have a murder ball of units.

I am thinking of a solution for this but cant think of any, any ideas as a solution would be greatly welcomed.

One solution I thought was to ensure that a target can have a maximum of 3 attackers, and if in the above loop, if it is seen that a target already has 3 attackers attacking it then move on to the next.

For this I added an int _attackers to the Character() script, and then when a new target is found it increments that integer, and if that integer is 3 we move on to the next enemy in the loop.

Below is the modification of the above code to take into account max attackers:

void FindCurrentTarget()
    {
        //find all potential targets (enemies of this character)
        enemies = GameObject.FindGameObjectsWithTag(attackTag);

        //distance between character and its nearest enemy
        float closestDistance = Mathf.Infinity;
        GameObject potentialTarget = null;
        foreach (GameObject _enemy in enemies)
        {
            // if the current enemy already has 3 attackers on him, then ignore and move to next
            if (_enemy.GetComponent<Character>()._attackers >= 3)
                continue;

            //check if there are enemies left to attack and check per enemy if its closest to this character
            if (Vector3.Distance(transform.position, _enemy.transform.position) < closestDistance && _enemy != null)
            {
                //if this enemy is closest to character, set closest distance to distance between character and enemy
                closestDistance = Vector3.Distance(transform.position, _enemy.transform.position);

                //also set current target to closest target (this enemy)
                if ((currentTarget == null) || ((currentTarget != null) && Vector3.Distance(transform.position, currentTarget.transform.position) > 2))
                {
                    potentialTarget = _enemy;
                }
            }
        }
        // in case we have a different target than the one we are changing to then decrement attacker before changing target
        if (currentTarget != null && potentialTarget != null && potentialTarget != currentTarget)
        {
            potentialTarget.GetComponent<Character>()._attackers--;
        }
        // increment the attacker after targetting it
        if (potentialTarget != null)
        {
            potentialTarget.GetComponent<Character>()._attackers++;
        }

        //set the current target at end of for loop, this is the closest enemy
        currentTarget = potentialTarget;


    }

I am of course also ensuring that the int is decremented when the attacker dies and and am also clamping the value of _attackers between 0 and 4.

But this modification is not working, the nearest enemies are ignored, the targeting which used to be nearest first is now random, sometimes targets are ignored entirely.

When I check in the inspector the targets that are ignored, it shows that the _attackers variable is already at 3. When I debug which of my deployed units is these 3 units, its just a random selection, no longer is the nearest principle respected.

Ive tried all day trying to fix this and I just end up fixing one thing and breaking two. It should be a simple enough concept to implement, but its apparently not

[Sluggy1]

The usual solution to this is called Request Tokens. In this case specifically Attack Request Tokens.

Essentially, each target has a fixed set of these and when someone wants to attack them they ‘ask permission’ from that target first. Usually the target has a first-come-first serve policy so it hands out tokens to the requesters in the order they requested. Only if the attacker receives one of these tokens are they then allowed to attack. In most cases you’d provide some backup logic if their request gets denied: such as retreating, looking for a new target, standing there and looking dumb while constantly asking for the token, etc…

Typically the attacker will return their token once they have reason to pause or stop their attack. Such reasons might include death, being stunned or disabled, running out of stamina, etc. At this point the target will now have that token to hand out to the very next attacker that makes a request for it.

Overall a very simple system but with a surprising elegance which can help give the illusion of complexity. The next time you play a beat em up style game see how the enemies act. Usually one or two attack the player and the rest back off and wait their turn. Once the first attackers die or get knocked down a new one will come in and start to fight while the previous backs off to supposedly lick their wounds. You can even make use of ‘token slots’ where specific tokens represent attacking from a specific angle. Then the attackers can request the angle closest to their position but if it’s taken they get the next closest. This way they don’t all bunch up on a single side but appear to try to surround their target.

[orionsyndrome]

Here’s another, more deterministic solution, by making a manager object whose job is to oversee the situation and ease the target assignment.

The high-level specs of this object and its interface should be as such so that

1. you have an easily-accessible single instance of it
2. it knows about all targets at all times
3. it can be called ad-hoc and will return the one target that has the least attackers
4. if there are several candidates it should pick one at random
5. if there are none it should return null

(1) is easily solved by making a singleton pattern.
(2) and (3) are potential resource hogs and bottlenecks in the overall design, so we want to use the least amount of memory, but also try to make a solution that scales well with the amount of total targets.
(4) and (5) can be handled however you seem fit. You can introduce more clever tie-breakers, or introduce some other type of favoritism. I’m sticking with random.

To solve (2) and (3) efficiently you want a data structure that can keep track of two things:
a list of targets correlated with the amount of attackers assigned to them.

This smells like a dictionary, where targets are introduced as keys, and values are simple integers, denoting how many attackers are assigned. However, this won’t work actually, because the search is very problematic, so you are right: this problem is not trivial.

After some thinking, I’ve come to a conclusion that what we want is a reverse model, the one where the amount of attackers is the key, from which dangles a set of targets who all have that many attackers assigned to them. This simplifies a lot the search algorithm, because you can exhaustively and progressively check for 0 attackers (best case), 1, 2, and so on, until you hit something. As soon as you hit a list, you’ve got your candidates with the least amount of attackers on them!

But! At the same time, you really want the forward mapping as well, because you want to quickly correlate a target with how many attackers are assigned to it.

So this should be a two-way street, really, and this is what makes this particular problem actually complicated.

To make this as abstract as possible, I’m calling the target’s type T, you can switch that to whatever you’re using, and I’ll show you how after the code.

using System.Collections.Generic;
using UnityEngine;

public class TargetOverseer<T> where T : class {

  static TargetOverseer _instance;
  public static TargetOverseer GetInstance()
    => _instance??= new TargetOverseer();

  Dictionary<T, int> _ts;           // target -> attackers #
  Dictionary<int, HashSet<T>> _grp; // attackers # -> set of targets

  private TargetOverseer() {
    _ts = new Dictionary<T, int>();
    _grp = new Dictionary<int, HashSet<T>>();
  }

  // this will report true if a target is known
  public bool Contains(T target) => _ts.ContainsKey(target);

  // this will either report an amount of attackers,
  // or will return null if the target is unknown
  public int? this[T target] => Contains(target)? _ts[target] : null;
 
  // internally used, to simplify adding objects to sets
  void addToGrp(int index, T obj) {
    if(_grp.TryGetValue(index, out var hset)) {
      hset.Add(obj);
      return;
    }

    _grp[index] = new HashSet<T>() { obj };
  }

  // internally used, to simplify removing objects in sets
  void removeFromGrp(int index, T obj) {
    if(_grp.TryGetValue(index, out var hset)) {
      if(hset.Contains(obj)) hset.Remove(obj);
      if(hset.Count == 0) _grp.Remove(index);
    }
  }

  // this method is used to increase the amount of attackers
  public void IncreaseAttacksFor(T target) {
    var atk = this[target];
    if(!atk.HasValue) atk = 0; else removeFromGrp(atk.Value, target);
    _ts[target] = atk.Value + 1;
    addToGrp(atk.Value + 1, target);
  }

  // this method is used to decrease the amount of attackers
  public void DecreaseAttacksFor(T target) {
    var atk = this[target];
    if(!atk.HasValue || atk.Value == 0) return;
 
    removeFromGrp(atk.Value, target);
    _ts[target] = atk.Value - 1;
    addToGrp(atk.Value - 1, target);
  }

  // adds new target to the system
  public void Register(T target) {
    if(Contains(target)) return;
    _ts[target] = 0;
    addToGrp(0, target);
  }

  // reduces the target to 0
  public void Cancel(T target) {
    var atk = this[target];
    if(!atk.HasValue || atk.Value == 0) return;
    removeFromGrp(atk.Value, target);
    _ts[target] = 0;
    addToGrp(0, target);
  }

  // finds a single suitable target with less attackers than specified
  // you're supposed to then register an attack with IncreaseAttacksFor(target)
  // returns null if:
  //   1) there are no targets in the system at all
  //   2) there are no targets with less attackers than specified
  public T GetTargetWithLessAttackersThan(int attackers) {
    if(_ts.Count == 0) return null;

    HashSet<T> candidates = null;
    int index = 0;

    do {
      if(_grp.TryGetValue(index, out var hset)) {
        candidates = hset;
      } else {
        index++;
      }
    } while(candidates is null && index < attackers);

    if(candidates is not null) {
      int random = Random.Range(0, candidates.Count);

      int i = 0;
      foreach(var selected in candidates) {
        if(i++ == random) return selected;
      }
    }

    return null;
  }

  // clears the internal collections
  public void Clear() {
    _ts.Clear();
    _grp.Clear();
  }

  // useful if you want to inspect all targets in the system
  public IEnumerable<KeyValuePair<T, int>> Targets {
    get {
      foreach(var kv in _ts) yield return kv;
    }
  }

}

I wrote this here directly, so if it doesn’t work it’s probably because I’m lazy to actually test it. Tell me if that’s the case, and I’ll fix it.

You can now use this like this. I’m using ITarget interface as a way to tell what’s target, you can just as well use GameObject if you want.

// declaration
TargetOverseer<ITarget> _overseer;

...

// initialization (you'll always get that one instance)
_overseer = TargetOverseer<ITarget>.GetInstance();

...

// register all targets with the system
for(int i = 0; i < whatever; i++) {
  _overseer.Register(target[i]);
}

...

// attacker requests a target
var target = _overseer.GetTargetWithLessAttackersThan(3);
_overseer.IncreaseAttacksFor(target);

...

// attacker cancels a target
_overseer.DecreaseAttacksFor(target);

...

// target dies or all attackers cancel this target for some reason
_overseer.Cancel(target);

...

// inspection
foreach(var kv in _overseer.Targets) {
  Debug.Log($"target '{kv.Key}' has {kv.Value} attackers");
}

Obviously each attacker is supposed to keep a reference to its target and reuse that. You should hook your logic onto these methods appropriately. Make sure that all increases and decreases cancel each other out, or else you’ll introduce leaks.

edit: fixed some obvious nonsense
edit2: corrected the main search slightly

[Sluggy1]

@orionsyndrome Heh, I just had a quick look at the system I used in a beat em up style game a made a few years ago. Indeed it looks like like what you suggested. Double dictionary with links going both ways. I’d forgotten that little detail but it certainly makes sense once you start looking into it. Though in my case I only had a possibility of one or two targets depending on the number of players so I just attached this component directly to each player. In that sense I think your idea of a coordinator makes a lot more sense since it can more quickly seek out the best-fit case for targets.

public class AttackTokenSource : MonoBehaviour
    {
    [Tooltip("An id presenting this token source.")]
    public HashedString SourceId;

    [Tooltip("A table of token ids and how many of each are stored by this entity.")]
    public Dictionary<string, int> Tokens;
    Dictionary<int, Stack<AttackToken>> CurrentTokens;

    public class AttackToken
    {
            public AttackTokenSource Source;
            public int HashId;
            public bool Temporary { get; private set; }


            public AttackToken(bool temporary = false)
            {
                Temporary = temporary;
            }

            public AttackToken(AttackTokenSource src, int hashId, bool temporary = false)
            {
                Source = src;
                HashId = hashId;
                Temporary = temporary;
            }
    }

...
Methods to request and return tokens
...

[Kurt-Dekker]

Good stuff… I’d just like to add I prefer to engineer these token systems as “dead man safe.”

What this means is that when an attacker gets a token from you, he must periodically reassert that token.

He reasserts it periodically and asks “Is this still valid?”

Asking will both tell him “yes it is valid” and reset the timer.

If a token isn’t asked about for one second then it gets invalidated and becomes re-available.

That way if you come up with some crazy new way to kill the attackers in the future, such as turn to stone, or ray of command (take control of him), and forget to release your attacking tokens, they automatically expire in a second or so.

Plus nobody has to explicitly give these back. They just stop caring and renewing them, which could come from dying, turning to stone, getting bored of attacking you, getting scared of almost being dead and running away, being eaten by a volcano, etc.

I feel the slight extra computation to keep verifying these things irregularly ( a random 0.25f to 0.75f second interval is nice) is well worth the weird bugs of “After I cast earthquake to kill all the little guys on me, nobody attacks me!”

EDIT: and things like “freeze” also work properly: a frozen enemy is obviously no longer attacking you and when he fails to renew his token, someone else will step in and start smacking you.

[farazk86]

This is great stuff… Thanks a lot guys, this gives me much to think about and also indicates that I will have to rewrite my character targeting system from scratch