I'll start with an introduction to what I have and a video showing it and then list my problems. The game is as follows, AI-controlled units come at each other from both sides of the screen, no user input, 2D auto battler practically. Component data-driven ECS, I am using Mark Daves Imaps approach. I currently have Occupational Imaps (that tell me what tiles are occupied), Proximity Imaps (that tell me the influence of each unit for both players), and I'll add a threat map as well. Units are varying sizes but mostly between 32x32 - 48x48, tiles are divided into 4x4 and Map size is 800x512. This is happening on a game server so I can't just brute force it and rely on the CPU's raw power.

You can see the gameplay here https://imgur.com/a/yugELUk

My architecture is as follows.

1) "World" class that holds the entire state of the current match inside it, calls updates that update the Grid (Imaps) and EntityManager who calls the systems and the ai and so on.

2) ECS calls AI for each unit to generate an action to perform, eg move, attack, cast a spell

3) Systems then loop through entities and do what they have to do, move it, attack...

My goals for the AI are:

1) Don't overlap with other allies ( I use some steering in the movement system to help with this)

2) Go towards the closest enemy and attack him, if there are other allies there surround him

3) If there are too many allies already just find another target

Now here are my problems. How do I use Imaps in this setup without butchering the performance? As I don't have a well enough understanding of Imaps already which makes it hard to visualize what combinations I can create.

I currently have 1 WorkingMap that I just resize (to save some memory and GC) every time AI needs it, and this is how I use it to achieve the thing in the above video.

// 1) Create working map size of interest map
proximity := 2 * int(movComp.Velocity.Magnitute()) * 5
if proximity == 0 {
 proximity = 6 * int(movComp.MovementSpeed)
}

sizeX := grid.MapWidth/ grid.TileSize -1
sizeY := grid.MapHeight/ grid.TileSize -1

wm := g.GetWorkingMap(sizeX, sizeY)

// 2) Add everything up
x, y := grid.GlobalCordToTiled(posComp.Position)
engine.AddMaps(g.GetEnemyProximityImap(entities[index].PlayerTag), wm, x, y, 1) // enemy prox map
engine.AddMaps(g.GetProximityImaps()[entities[index].PlayerTag], wm, x, y, 0.5) // allies prox map
engine.AddMaps(grid.GetProximityTemplate(movComp.MovementSpeed).Imap, wm, x,y, -1) // my prox template
wm.NormalizeAndInvert()
engine.AddMaps(g.GetInterestTemplate(proximity), wm, x, y, 1)

   // Currently I do this, but I'd like to have a check on whether or not we can attack
   //someone, surround someone and etc.
targetX, targetY := wm.GetLowestValue()
moveTowardsPoint(index, targetX, targetY, w)

Is there a way to use only 1 working map per AI iteration and to check for all of the goals I listed above (doesn't have to be necessarily 1 but something that isn't asking for a new Workingmap for every check)? I have no idea how to approach this kind of AI behavior without a bunch of if-else statements and multiple working maps. I am calling the AI once a tick for each unit as well which is probably way too much already (any advice on how to improve this as well is appreciated).

Another problem is when there are no enemies nearby, it doesn't really know where to go (it should go towards the other end of the screen or enemies center of mass). I went around this by having their working map be the entire screen, which is 200tiles * 128 tiles, but that kinda defeats the purpose of the benefits of smaller working maps.

Hopefully, I presented my problem properly, If you guys need any additional info please tell me.

• What can you share between different agents?
• What is updated at every tick, and what more rarely?
• Can you represent the “maps” more cheaply than with large arrays? For example, the closest/preferred enemy is a discrete choice between a few options, there's no need to compute a function at every point of the map.

@LorenzoGatti 1) What do you mean? I can change the system however I see fit
2) Subject to change, currently not doing anything to enchance performance

3) Well currently the cheapness isn't the problem but the fact that I cannot do anything with them :(

So, the trick here is to realize that influence maps are a helper, they don't solve all things. You need to break this down once again into the requirements and take it in smaller pieces. First and foremost, you should think of the influence map as one tool in a chest, it doesn't do everything and you should not attempt to force it to solve inappropriate items. What it is good for is global reasoning in regards to general information, it's not very good at giving you specific and individualized information. Some of your requirements need more specific entity level information that will need a different solution for best effect. So, break things down into some pseudo code:

// Behavior: MoveTowardsEnemies
Vec3f target;
if (FindNearestEnemyDensity(influenceMap, position, &target)) {
  // There is an enemy group somewhere, move that direction and return the distance to target area.
  if (MoveTowards(position, target, &velocity) < 10.0f) {
    // We are close enough to try and pick a target.
    if (SelectTarget(entityId, position, blackboard, influenceMap, &currentTarget)) {
      // We selected a target.
      SetNextState<ApproachTarget>();
    }
  }
}

That packs a lot of logic into the helpers and adds a bit of a new item in regards to the blackboard item. The blackboard is a shared data store for the group of entities. This is where you would store information about what enemy each entity has decided to attack. For the most part, you would have nothing more than a hash map of entity id's to a vector of entity id's. The keys being enemies and the value containing which attackers have chosen to attack it. So, SelectTarget helper might look something like the following:

// Helper: SelectTarget - Attempts to find the best target within a given range, or returns false.
bool SelectTarget(EntityId self, Vec3f position, Blackboard& blackboard, InfluenceMap& influenceMap, EntityId* entityId) {
  // Find enemies we can see.
  // This assumes you have a spatial query system somewhere.
  EntityVector entities;
  auto count = QueryEntities(/* center point */ position, /* range */ 10.0f, entities);
  
  EntityPriorityQueue weighted;
  for (auto i = 0; i<count; ++i) {
    // Weight the entities based on range and density.  Unlike the initial movement towards the highest
    // density, don't be stupid and rush into the middle of 10 enemies just to attack one, attack the ones
    // at the edges first.  Also, prefer entities not being attacked and ignore those with >= 5 attackers.
    weighted.emplace(WeightedEntity {
      position.DistanceTo(GetPosition(entities[i])) *
      influenceMap.QueryEnemyDensity(GetPosition(entities[i])) *
      blackboard.CountAttackers(entities[i]) > 5 ? 1000.0f : 6 - blackboard.CountAttackers(entities[i]),
      entities[i] });
  }
  
  // 'weighted' now has the entities sorted into highest priority first.
  if (weighted.size() > 0 && weighted[0].weight > 0.0f) {
    // That's the bugger I hate the most!
    *entityId = weighted[0].entity;
    blackboard.AddAttacker(*entityId, self);
    // Behaviors are required to remove themselves from the blackboard when they give up on the
    // target.
    return true;
  }
  
  // None of the entities turned out to be viable, move another tick and try again after that.
  return false;
}

The above probably won't work as written, but the general idea is there in terms that it is trying to do a weighted selection of nearby entities and figure out which to attack. It does the selection based on whatever constraints you want to program into the system, in this case it prioritizes the closest enemies in the “least” densely populated area of the influence map and with the fewest allies attacking it.

While I didn't cover it specifically, this setup does not need multiple influence maps as it uses entity specific memory (who am I attacking), group knowledge (which allies are attacking which enemy) and global knowledge in the influence map. When you get to maneuvering around to get in attack range, you might need localized influence maps to help the steering systems, but generally speaking I've rarely needed that. The more likely case of using multiple influence maps is when you start adding tactical group thinking and other items such as cover, at that point multiple influence maps becomes very useful.

Hopefully this gives you further ideas on how to move forward, the later states should be a bit easier though they have more exceptional cases such as breaking out of movement to attack something if attacked, a new target is better, the selected target died etc. If you keep breaking things down into small penny sized packets of logic, your behaviors become easier to control and understand when/why they are doing the wrong things. Of course, the above ends up with a number of fiddly bits to make it work the way you want but that tends to be a common problem with constraints based programming, more constraints more fiddly bits and more ways things can do silly stuff because you missed some edge case.

Some items in hindsight after I watched that video:

• You likely have a bug somewhere, otherwise everyone would not be moving towards the center of the screen, would they?
• Your steering system is going to need an “arrive” behavior so the units will slow down and stop when they get close to the enemy. Steering is great but you have to implement several variations to make it useful.
• You definitely need to use a state system or behavior tree or something to control the entities better.

Just a few more thoughts.

@all8up Thank you very much! I've gotten much closer to my goal with your previous advice already. Hopefully another week of research is gonna do the trick

@all8up “ When you get to maneuvering around to get in attack range, you might need localized influence maps to help the steering systems, but generally speaking I've rarely needed that.”

What do you usually use for this then? I got most of the system down, but cannot for the life of me get them to spread out and take a proper position around a unit/ on a target. I keep reading articles on starcraft movement, and they use boids for this but nowhere do they explain how their units surround a target.

sir7 said:
I keep reading articles on starcraft movement, and they use boids for this but nowhere do they explain how their units surround a target.

With boids you usually accomplish this sort of thing by combining a couple of different influences. Try having one force that acts towards the target unit, and another that repels friendly units from one another. They should converge on the target and spread out to be evenly spaced around it.

What @swiftcoder suggests is one way to do it for sure and as a starting point it is generally good enough. Basically this consists of running two steps of steering: maintain distance to target and maintain separation. Typically though, I don't like the results of that because the new boid trying to get into attack range is a pushy bastard and bumps the existing folks out of the way. So, I run a tangent field step as an addition. The idea here is that as the separation force increases to keep one boid from entering the same space as another, I also apply a force which is tangential to the boid position and the target in the direction of the separation force. So, if I'm coming up on the right side of a friendly boid, as I start getting too close the tangent field starts adding a bit more force to go “right”. This makes is such that rather than bumping into the friendly unit and pushing them to the side, the new boid will go around them a bit. There is of course a singularity in terms that if you come up right behind someone, you won't be able to figure out left or right tangent, in such a case, I just always apply right and call it a day since it is such a rare case to have “perfect” alignment.

That's one of many different ways to make boids look a bit more natural in these cases. The fun thing with steering based approaches is that with a relatively limited set of rules you can get some very natural and impressively complex behaviors. Play with variations and you can end up with very complex looking but actually very simple behaviors.

@All8Up Again me, after several days I've gotten much closer. I am mostly now stuck with this part of your solution apply a force which is tangential to the boid position and the target in the direction of the separation force.

I have the S (seperation force) basically a vector that goes from otherPos To myPos (pushes be back), but how do I get the tangential force you are talking about? I have the velocity, the seperation force, and all three positions (Green being boid, orange being the obstacle boid i want to navigate around and x being the goal).

I am having a hard time googling terms as my native language isn't english so mathematical terms of this nature are hard to digest and search for.

Hi there,

I drew up the following to help explain what I was trying to say:

Hopefully this makes more sense? It's not a perfect solution but in the case of one or two friendly units in the way, it usually looks pretty good as a very simple way to make the incoming guy not be so pushy. If there are already 3 or 4 friendlies, it doesn't do a lot since the first cross to find up/down will tend to fail due to epsilon and you just skip the rest of the calculation.

Good luck