No announcement yet.

New troop AI explained

  • Filter
  • Time
  • Show
Clear All
new posts

  • New troop AI explained

    When a unit has no target, it picks the "nearest" (see below) target, and picks the route to it, and then starts following the route it stored. Units will bash through walls if they need to, but this is counted the same as walking quite a long way - so they'll prefer to attack without going through walls unless it's a lot further. The unobvious bit is that there are 2 stages to the target selection:

    Step 1: the unit picks the 5 closest, relevant targets as the crow flies, ignoring walls. This is the rule of 5. All other targets are discarded.
    Step 2: it works out the exact route to each of those 5, and then which is actually easiest to get to, allowing for detours around walls, or a large distance penalty if bashing through a wall.

    Rule of 5 in pictures

    Here's a simple example of the rule of 5...

    The barb is dropped where the flag indicates. And then goes on a long walk to the "closest" target - which is the bottom left builder hut. That is neither the closest building as the crow flies; nor closest as the barb walks. But step 1 of the pathing AI discarded all buildings except those 5 huts - which are the closest to the drop point. Step 2 avoids hacking through 2 or 3 walls, and the quickest target is to loop round the edge and break a single wall.

    Note that the rule of 5 only applies to relevant targets. So in this:

    the barb attacks the air sweeper as before - the mortar didn't make the cut in the first step. But for the giant the rule of 5 counts the closest 5 defences - so step 2 includes only the mortar and sweeper, and the AI spots the direct path.

    And this looks odd because the giant and barb can both target both of the mortar and sweeper, but they select different ones. And the resulting difference is that the giant was more likely to avoid the walls - because it's doing the full pathing check on buildings further away (since the nearby non-defences were ignored)

    To walk or to bash

    The actual distance a troop will walk to avoid a wall is quite large. In this picture the mortar is too much further away, and the barb prefers to punch thru the wall:

    But move the mortar 1 tile closer, and the barb goes for it:

    It will walk about 18 tiles sideways. It had to walk about 3 forwards from where it left the drop enclosure - so the mortar was about 15 or so tiles further walking, and was preferred to the wiz tower. But 16 tiles further and it'll punch through the wall.

    Golems and giants

    Although a unit will walk a long way along the outside to avoid a wall, in practice it often doesn't come to that because of the rule of 5. So with the mortar in the same place as the last screen above, but with more buildings added:

    the giant punches through the wall - even though the mortar is close enough that it is preferred to the wiz tower. But in this case the AD, first 2 mortars, WT and cannon are the 5 guns that make it through step 1 of the pathing AI. The mortar outside the wall never gets the true distance calculated in step 2. Since the WT is the closest of those 5, we have a boxing giant.

    But in the same replay, just zapping the right hand mortar with lightning changes the giant's pathing:

    Now there are only 4 guns behind the wall, so the mortar outside is included in the rule of 5, and the giant sees that as the easiest option. So the difference between the giant walking, or going in is actually the mortar on the far right.

    And this last screenshot is also the difference in the AI. Before the last update it was a rule of 3. So previously the giant would only have fully analysed the AD, WT and mortar behind the wall, and it would still have targeted the WT. It's not literally the distance that the giant is willing to look to find the mortar that's changed - but that's often the difference in practice.

    So in most cases before the last update golems weren't actually making a decision between going sideways to an exposed gun, or punching through the wall - because the old rule of 3 was typically more limiting than the distance they are willing to detour to avoid the wall.

    Once more unto the breach

    And this leads to the weird looking behaviour when troops walk round to a gap in the wall, and then walk right over the top of guns shooting them to hit something else...

    The barbs will happily trample over the cannon, ignoring it, to reach the mortar. And that looks bizarre in play. But if you apply the rule of 5 - I've numbered the closest guns as I see them - then the barbs ignore the cannon because it wasn't in the top 5 in step 1. But they don't go for the WT, because they can indeed reach the mortar faster.

    But then if I drop a giant on the same map, it does, target the cannon:

    because it's now included in the rule of 5, when counting guns only.

    And this is why the AI seems inconsistent - sometime walking all the way round the base to hit something outside, and sometimes ignoring buildings only 7 or 8 tiles away - because whether the building outside was even measured fully depends on how many buildings are behind the wall, as well as how close they are. It's not only the relative distance of the exposed target and the through-the-wall target that matters.

    Why oh why?

    I'm guessing most people are now thinking why the hell does the AI work in 2 steps like this, with the rule of 5 which causes so much counter-intuitive behaviour. The reason is in the calculation the software has to make to choose the best path for Barnie the barb to hit a particular cannon. This is something that humans just do instinctively, but computers are totally rubbish at. You can just glance at the picture above and see that the giant can go through that gap to hit the cannon (or mortar...). But the problem the devs have to solve is:
    - given a list of wall coordinates, such as (10, 11), (10, 12), (10, 13), (10, 14), (11, 12), (12,12), ... and there are 300 of these...

    - then what is formula for the shortest route for barnie standing at (5,20) to reach the cannon at (12,19). And the formula has to work for any combination of numbers, and any complexity of resulting path - it might be numerous swerves around walls and through gaps.

    This is not a trivial problem. And not only is it hard to program, I imagine it's very slow to calculate. Without the rule of 5, the game would need to calculate this for all 80 buildings on the map to decide what Barnie hits next. Worse, if you drop a jump spell it causes every unit on the map to do a re-target to see if it can now hit something closer. If there are 250 barch on the map, it would need to work out 20000 full routes to retarget them all - and I'm guessing the game would freeze totally for several seconds while it did this. And that's why the software filters down the possible targets with a quick and dirty direct line distance (which can be calculated very fast).