[WIP] doc on formations

[teaalltr]

I've created this gist on units formations. As you can see from the revision log, it is still a work in progress. I'm finding a way to express the last formula in terms of integer functions only (i.e. Mod, Ceil, Floor and so on). I will make a PR with a recap of the gist as ready.
This is for you to know and discuss and (possibly, if you feel to), contribute ideas 👍

[heinezen]

This looks very good! One thing to add maybe: If units types are mixed, each type forms their own little "sub"-formation.

................
...SSSSSSSSSS...
...SSSSSSSSSS...
...SSSSSSSSSS...
...SSSSSSSSSS...
................

Above would be 40 spearman

................
...AAAAAAAA...
...AAAAAAAA...
....SSSSSS....
...SSSSSSSS...
...SSSSSSSS...
................

This is a formation of 22 Spear + 16 Archers = 38 Units. They form 5 rows instead of the predicted 4.

..............
....SSSSSS....
...SSSSSSSS...
...SSSSSSSS...
..............

............
....AAAA....
...AAAAAA...
...AAAAAA...
............

That's what the 16 archers and 22 spear would look like if they were in separate formations. Seems to be a bit more complex if several different unit types are involved.

[zuntrax]

Very nice work here and in the other issues/PRs 👍

[TheJJ]

Oh shit this is gonna be so much fun implementing that in the pathfinder/steerer 🙄

[heinezen]

Found two articles which are real gold mines. They primarily deal with the formation systems of RTS.

Coordinated Unit Movement

Implementing Coordinated Movement

both are by Dave Pottinger who worked on the AI for Age of Empires II.

He even includes some pseudo-code :)

@TheJJ

[teaalltr]

@heinezen it seems to be:

• first, arrange the first group (the leading one). Let numRow1stLine1stGroup be the number of units in its first row
• each of the remaining groups are arranged in ceil(numOfUnitsNthGroup / numRow1stLine1stGroup) rows (let's call it rowCountNthGroup - different for each group).
• the number of units in each row is then ceil(numOfUnitsNthGroup / rowCountNthGroup) for the first n-1 rows, and numOfUnitsNthGroup % (rowCountNthGroup-1) for the last one

NOTE
There is one known case where the above doesn't hold. Take a group of 15 spears and 25 archers. The spears (1st group) arrange 8-7; the other group should then arrange in 4 rows, but it doesn't. It arranges in 3 rows, 9-9-7. This is probably due to the fact that the sum of the two groups is 40, which is the limit of selectable units. Instead of adding another row, they preferred to overrun the limit by one unit. No other cases are known, anyway. I'm updating the gist (thanks for the highlight BTW) 😄

[heinezen]

@Piruzzolo Great!

Unfortunately it gets even more complicated, when cavalry is mixed with infantry.

A cavalry line on its own will group normally. However, when infantry is added, they behave a little different. Take an example of 6 cavalry and 9 infantry. The cavalry will form a single line in the front as we would expect but the infantry behind will also form 1 line, making it a 6/9 formation. 6 infantry and 9 archers would form a 6/5/4 formation with a single line of infantry in front.

I think this is caused by cavalry being "wider" than infantry and they need more space in between. The infantry behind then adapts to it. At first I thought the width for the infantry line would be (cavalry line)*1.5 but is seems to be just (cavalry line) + 3.

Now maybe one could think this happens because cavalry is always in the first group, so it "naturally" influences the units behind it. But when I tested it with infantry + rams, the infantry line also gets wider. In fact, a formation of 6 rams and 16 infantry will put all of the infantry in a single line in front. If you add 10 cavalry to this formation, they also form one single line and not two.

The more I think about it, the more I am convinced that the first group doesn't matter and instead the "widest" group dictates the number of units per line. At least in mixed formations.

[heinezen]

For reference, this shows which unit groups are placed in front:

..............
4...Support... Rams, Onagers, Bombard Connons, Monks
3...Ranged.... Archers, Skrimishers, Hand Connoners, Scorpions, Cavalry Archers
2...Infantry.. Spearman, Swordsman
1...Cavalry... Knights, Camels, Light Cavalry
..............

[teaalltr]

Oh gosh! We need a bit of rethink. I agree that the width may be the right thing to look to. If you take a look here, you can see that units are internally arranged in groups and line ids, which determines their type and behaviour. LineIDs may look promising. The archers belong to a certain lineID and group. We can have mixed lines, i.e. formed by units belonging to different groups (as an example, take 11 archers and a scorpion). This suggests that we may create a (symmetric) lookup matrix with 1 if the A-type unit can be in the same line as a B-type unit, 0 otherwise. From the suggested experiment, you can notice that the presence of even a single scorpion in a line of archers does affect the spacing between all the units of the group they belong to. So, if it holds your guess about width determining the arrangement, this would affect all the units in the selection. Your reference list of unit groups will grow 😄 Here's my proposed algorithm:

• first, go through all the units to get a set (no repetitions) with their lineID (or groupID, we'll see - there's some ambiguity in names);
• secondly, for each pair (i, j) (i != j) look up in the "affinity matrix" if they can be together, in the same {group | line}.
• on this basis, update the spacing base radius to get the max of the radii of the units in each group.
• arrange the groups separately;
• calculate the width for each group;
• take the group with maximum width;
• arrange the others accordingly (see subroutine)

subroutine (modified from my previous post):

• get the width of the group with max width (widthMax)
• for each remaining group, arrange in ceil(widthNthGroup / widthMax) rows (let's call it rowCountNthGroup - different for each group).
• the number of units in each row is then ceil(numOfUnitsNthGroup / rowCountNthGroup) for the first n-1 rows, and numOfUnitsNthGroup % (rowCountNthGroup-1) for the last one

We need to check this against some data

[heinezen]

@Piruzzolo Aah indeed these Group IDs look very promising. However, i don't think we need the affinity matrix. I propose a more radical solution that should compute faster than yours.

Every formation would always be divided into 4 "sub"-formations, one for each unit group you see in my previous post. Sub-Formation 1 would take cavalry, Sub-Formation 2 infantry and so on.. Sub-Formations can be empty (with 0 lines and 0 width). The algorithm would look like this:

• For every selected unit do
  • get GroupID and sort into the associated sub-formation;
  • get width of the unit. If width of unit is greater than minWidth of the sub-formation, set minWidth=width; (all units of the sub-formation have to respect the minimum width which would always be the width of the widest unit)

Then we can continue with the 4th step in your algorithm:

• arrange the groups separately;
• ...

There are several advantages to this method. First of all sorting the units into sub-formations has a run-time of O(n) (n is the number of units) whereas your use of an affinity matrix would have a run-time of O(n²). We don't want the game to stutter when a pro player with an average of 5 clicks/s sends his units around 😄 . Furthermore, the 4 sub-formations can each have a unique spacing and could handle the arrangement of units inside the group. The "parent"-formation container could handle things like maxSpeed and formationType (line, square, split, etc.). We could also add a 5th sub-formation that would contain units that are incompatible to formation (villagers and trade carts for example).

[teaalltr]

Nice work, better and more focused algorithm. So, to do the GroupID sorting right, we need to collect some data from the unitID table site and find the sub-formation each ID belongs to. However, note that the second part of the algorithm (namely, subroutine) is still not thoroughly tested. We also need to take units overlapping into account.

[heinezen]

I think we should focus on collecting much more data, before we try to design the subroutine. I would favour a bottom-up approach in 4 steps:

1. find out what GroupID belongs to each sub-formation
2. determine how a single sub-formation orders its units
3. explore how a single sub-formation handles different unit types, e.g. spearman and swordsman (the pattern of how they are formatted doesn't look random to me)
4. finally discover how the 4 sub-formations are influenced by each other inside their parent-formation (this is were subroutine comes into place)

With the bottom-up approach we should discover all variables the formation system depends on in the process rather than just "guessing" how the subroutine might work. I would volunteer to do some research on the 1st step and which GroupIDs belong to which sub-formation. I'll report back when I tested it.

What do you think about it?

[teaalltr]

That's the right approach, I agree. Systematic analysis is definitely better than random guessing. It's going to be a big work, surely I would land you a hand 👍
Here's some information you may find useful:

1. Cavalry: Elephants, all the cavalry except those in the ranged sub-formation
2. Ranged: add Mangudai, Elite Mangudai

The following overlap with each other, in single type formation:
Elephants, Rams, Trade carts (maybe others)

Trade carts seem to arrange as they were in line formation.

My guess is a correlation between (lineIDs and groupIDs) and the actual ordering (like a comparison, greater than or so... why the negative numbers, otherwise?). May worth check

[yani]

Just wanted to add that there are 4 types of formations:
http://aok.heavengames.com/gameinfo/formations

[teaalltr]

@Yanikore Yes, we know. Since the staggered and flank one are very similar to the line formation, we could easily adapt our findings to those. The staggered formation is just the line one, more spaced; the flank formation is the line one, someway splitted in two. The box formation is a bit different

[TheJJ]

Another thought: assuming we had a working pathfinder, how would we add that formation support?
At narrow passthroughs, the formation may need to split up, squeeze together.

And if we have a random bunch of units at some battlefield, if we select those and command them somewhere, they may not have space and time to form their formation.

In other words: How do we express the request that units should form the formation?

Our coming flow-field-pathfinding-approach can handle each unit independently. Additionally, we have the choice:

• We could recalculate the path every step to account all moving objects
• Or we could ignore all moving objects and require them do to steering/collision avoidance themselves

The first option will likely be much slower, but the second one requires more logic so that units dont constantly walk into each other. But if we combine the formation forming and the "not walking into each other", we could maybe solve both problems. The formation is just another "not walking into each other" with a certain structure.

[teaalltr]

@TheJJ It's going to depend on the actual implementation. Since the game itself won't be using GPU so much, we could even try to implement core pieces of the pathfinder as GPU kernels. There are some implementations of A* on Github and many academic papers on the subject.

About formations, we may find some ideas here and here. Also, this overview by one of the game developers may be useful.

[heinezen]

@Piruzzolo Would be awesome if you can figure out if LineID is used for the ordering of units inside the sub-formations!

Since it's the weekend now, I will hopefully figure out in which sub-formation every GroupID belongs. I also want to test ship formations because they seem to have their own formation grouping going on. It's definitely worth to check what happens if sea and land units are selected simultaneously by the player.

BTW: Do you mean "overlapping" in the sense that their selection circles overlap?

@TheJJ I highly recommend you to read this as Piruzzolo already pointed out:

Coordinated Unit Movement

because it explains some basic principles that the devs at Ensemble used or the formation system. One interesting thing that Pottinger describes in this article is that a formation should have a leading unit (presumably one in the first line) and other units in the formation will just follow it. This could lead to a great performance increase, since pathfinding would only have to calculate the path for the leading unit. For now we are trying to figure out how the formation is ordering its units, so implementing formation pathfinding still sounds like rocket science 😄.

[TheJJ]

Yes, will read that :)
For the ideas about our pathfinder in general, see #366.

[heinezen]

It seems that GroupID is the deciding factor for delegating units to a sub-formation. Here are the GroupIDs for every sub-formation:

.............
1..Cavalry... 912, 947
2..Infantry.. 906
3..Ranged.... 900, 923, 936, 944, 955
4..Support... 902, 913, 918, 919, 920, 935, 943, 951, 959
5..Else...... 904, 921, 958, 961

The only exception is the Battle Ship Group. Battle ships use the same 4-sub-formations-system but the deciding factor is the ``LineID`. When land and sea units are mixed (this can be seen in shallow water), the cavalry sub formation will mix with demolition ships, the infantry one with fire ships, the ranged one with galleys, longboats and turtle ships and cannon galeons with the support group.

WARNING: These are LineIDs not GroupIDs
.............
1..Cavalry... -294
2..Infantry.. -293
3..Ranged.... -283, -284, -292
4..Support... -285, Saboteur (UnitID: 706)
5..Else...... Admiral Yun Shi (UnitID: 844)

Looks like putting units into a sub formation just requires a simple switch statement.

Note: Units in the 5th sub formation won't form a formation and won't be part of one. The also don't obey the rule that a formation moves as fast as the slowest unit it contains.

[teaalltr]

@heinezen Yes, I mean circle overlapping.
Good job, really! 👍
The LineID seems to be someway used for sub-formations. If you select 6 Archers (A), 6 Chu-Ko-Nu (C), 6 Longbowman (L) and 6 Skirmishers (S), you find that they will arrange like this:

................
...A|LCSA|LCS...
...A|LCSA|LCS...
...A|LCSA|LCS...
................

I put a pipe to show the pattern on horizontal rows. The LineID is -299 for Archers, -297 for Skirmishers, -280 for Chu-Ko-Nu and -277 for Longbowman (which is the order from the first pipe from right, to L).
So I tried to investigate what happens when I put in another unit with the same LineID of another. Then I tried with various cavalry units. The units with the same LineID are someway put close to each other in a repeating fashion, but patterns are not so clear. Needs further investigation

[heinezen]

@Piruzzolo Hmm..

I justed tested this and on my first try I had the same result as you. However after I commanded them around and selected them again I got another result:

................
...S|LCAS|LCA...
...S|LCAS|LCA...
...S|LCAS|LCA...
................

Which would be LineID -297, then -277, then -280 and finally -299?? This doesn't make sense.

From a quick test I got the idea that it might has to do with the order the units are selected. In this example I selected the units in this order: archers, longbowman, skirmishers, cho ko nu

................
...C|SLAC|SLA...
...C|SLAC|SLA...
...C|SLAC|SLA...
................

As you see, it's the selection in reverse order, repeated in every line. Maybe you were just lucky enough to select your units in the right order to support our theory 😄.

[teaalltr]

I'd say very lucky, since I've done it 3-4 times without noting! :) I'll do some tests with other configurations

[mic-e]

This (selection order) behavior seems sort of silly; should we really attempt to clone it? (would it harm the user experience not to?)

[heinezen]

@mic-e Well, we don't know until we have figured it out. Right now it could just be a side-effect of the implementation or it could even be the fastest method to order units. When we eventually figure out how it works, we can worry about improvements.

@Piruzzolo I did some more testing with units that have the same LineID: 8 militia (M) and 6 swordsmen (S). Militia was selected first.

.............
...MSMSMSM...
...MSMSMSM...
.............

If ordering depends solely on LineID they should be randomly ordered. I selected them multiple times in random order for verification. Maybe UnitID is used too.
Also, if I select the swordsmen first, I get this formation:

.............
...MMMMSMS...
...SMSMSMS...
.............

[teaalltr]

@heinezen I just found some interesting hints about LineIDs here. Here's an extract:

If you look at the rule that trains the military unit, you'll notice that instead of "militiaman" or "man-at-arms", it trains a "militiaman-line". This wild-card parameter trains any of the unit-types that can be upgraded from a militiaman. This kind of parameter helps save rules by allowing you to not have to add redundant rules for training militiamen, men-at-arms, long-swordsmen, etc.

So, "*-line" strings would be just wildcards to group unit types for AI scripting in Lisp, not a "line" meaning a "row" in a formation (or not necessarily). However, the LineID may serve multiple roles. Your guess on selection order may be right. It may be the good starting point

[teaalltr]

So, maybe the point is that units are arranged in a way that they form vertical rows of units of the same type, taking in account the initial selection order.
For instance, take a Paladin (P), 2 Elite Mameluke (EM), 2 Scouts (S) and a Mameluke (M) selected in the following order: {S, P, EM, S, P, EM, M}. The arrangement will be:

....................
... EM | P | S .....
.. M | EM | P | S ..
....................

If we enumerate the types in the list above left-right and the positions in the formation right-left from bottom, we see that the first in the formation is S (as in the order list), the second is P (as in the list), the third is EM (as in list), but then the fourth is M, which is not the fourth in the list. This can be explained by guessing that units already positioned make the turn of their type skip in favour of still non-positioned types.
Now take 2 S, 2 EM, 1 P and 1 M in the order {S, S, EM, P, M, EM}. The arrangement will be EM, S, M, P, ME, S. Same behaviour as before, it seems.

[heinezen]

@Piruzzolo If thats the case, then we could achieve this ordering by a very simple algorithm

• When a unit is added to a sub formation, check its UnitID
• If units with UnitID haven't been added yet, create a stack (or list, queue) and put it on there
• Else check which stack corresponds to UnitID and put the unit on it

This should seperate all the different unit types that get added to the sub formation. Ordering would be done in the following steps

• Get a unit from the first stack and add it to the formation line
• Switch to the next stack and do the same
• Keep iterating over the different stacks until the formation line is full
• Repeat for the next formation line until the stacks are empty

Example: Archers (A), Shirmishers (S) , Longbowman (L) selected in this order
{A, A, A, S, A, L, S, A, L, L, L, A}

Stack 1:...AAAAAA...
Stack 2:...SS...
Stack 3:...LLLL...

12 Units should form 2 line á 6 units so the lines should look like this. The arrow points in the direction the formation is oriented.

..............^......
1st line:...ASLASL...
2nd line:...ALALAA...

Which is exactly how it turns out ingame. Can you double check that? 😄

[teaalltr]

The first line ALSALS for me. The second line is the same as yours. Maybe a mistake? 😉

[heinezen]

Ooops I typed the selection order wrong. Should be fixed now and example is working correctly!

Same example for my previous "wrong" selection order:
{A, A, A, L, A, S, S, A, L, L, L, A}

Stack 1:...AAAAAA...
Stack 2:...LLLL...
Stack 3:...SS...

12 Units should form 2 line á 6 units so the lines should look like this. The arrow points in the direction the formation is oriented.

..............^......
1st line:...ALSALS...
2nd line:...ALALAA...

[heinezen]

Furthermore, @mic-e will be happy because the selection order behavior is only a side-effect of the algorithm. So there's no overhead produced :)

[teaalltr]

The resource constraints were very strict at the time 😄 Great job, man!

So, we now need to know how the width of a sub-formation is calculated. Units overlap the base circle with each other, seemingly differently depending on the unit. A rough estimate is 30% for cavalry (maybe 33.33%? Maybe)

The algorithm of above could maybe be re-used with the box formation, maybe.

For a box formation of all Archers, here's the result for 2, 3, 4, 5, 6, 7, 8, 9:

                                                                             o o
                                                    o   o       o o o      o     o
o        o        o o       o   o       o o o       o   o       o   o      o     o
o       o o       o o       o o o       o o o       o o o       o o o       o o o

[heinezen]

So, we now need to know how the width of a sub-formation is calculated. Units overlap the base circle with each other, seemingly differently depending on the unit. A rough estimate is 30% for cavalry (maybe 33.33%? Maybe)

From my observation a line of 5 Archers/Infantry is roughly 2 tiles, 5 Cavalry about 3 tiles, and 5 siege units 5 tiles wide. This means cavalry takes usually 50 % more space than infantry and siege 150 %.
But there are some exceptions: 6 siege rams allow 16 infantry in front of them but 6 siege onagers only allow 15 for whatever reason. It seems to vary depending on the unit.

Maybe @TheJJ can tell us if there is anything in the gamedata that can be used to determine the width or at least the radius of a unit? Should be used for other things such as collision.

The algorithm of above could maybe be re-used with the box formation, maybe.

For a box formation of all Archers, here's the result for 2, 3, 4, 5, 6, 7, 8, 9:

Great start! Oh this box formation gives me troubles 😄. With mixed units in a sub formation it seems to order them randomly and changes the order on every movement command. It's also hard to keep track of where the front side is.

[TheJJ]

Yes, each unit has a radius, in fact they even have three. For now we thought those are used for the selection circle size and hp bar position.
There's also clearance size, which may help.

[heinezen]

@TheJJ Thats awesome, thank you. radius_x and radius_y should be the values we need.

@Piruzzolo Our width between the units in a line would be approx. 2 * radius_x. 2 * radius_y could be used to determine how far the individual lines in a subformation have to be apart.

[teaalltr]

Maybe the y positioning it's a bit more complicated: take a Ram, its circle is aligned with that of others, but since it has a bigger radius, it has to be positioned a bit behind. It's not the center of the circle to be aligned, it's the front point of the circle, at least for a Ram. So we begin calculating a line through all the circle front points of the other units (the tangent line) and align the Ram accordingly. Need to check if it's true for all the units

[heinezen]

I'm pretty sure it's the center of the unit they align to. In a mixed sub formation of Rams and Kings, the units align to the center points both on the X and on the Y axis. There could be a hidden offset that we don't know about though. Or am I misunderstanding you?

[teaalltr]

Ok, I just realized I was wrong, I simply didn't give them enough time to align properly. The Rams seem to align to the center, my mistake

[heinezen]

@Piruzzolo No problem! :) It's better for us to double-check it than doing it wrong.

Btw i did test some box formations and the ordering of the sub formations looks like this, with 1 being cavalry, 2 infantry and so on.

...............
.1.1.1.1.1.1.1.
.1.2.2.2.2.2.1.
.1.2.3.3.3.2.1.
.1.2.3.4.3.2.1.
.1.2.3.3.3.2.1.
.1.2.2.2.2.2.1.
.1.1.1.1.1.1.1.
.........

How far the units in a sub formation (maybe "layer" is more appropiate for this one) stay apart depends on

1. the units in the sub formation itself (as before in line, staggered, flank)
2. the spacing of inner layers

Take for example a box formation of 2 onagers and 10 archers. The spacing between the archers will be the same as between the onagers. Or to put it simple: Outer layers inherit the minWidth of inner layers. Adding more archers to the formation does not make them stand closer together, instead their sub formation box just gets bigger. Also, each sub formation seems to order its units like your described in you previous post.

Still can't wrap my head around how ordering with mixed units inside sub formations works 😄

[TheJJ]

http://www0.cs.ucl.ac.uk/staff/D.Silver/web/Publications_files/coop-path-AIWisdom.pdf

[teaalltr]

Hi, I've just updated my gist on formations with a cleaner formula, much simpler than the old one. Please take a look 😄 here

[heinezen]

@Piruzzolo Hey, welcome back :)

Looks good to me and should be fast enough for practical use ingame. You totally should create a PR for it now, since it's the last thing about formations that's not in the repository (see #783).

[teaalltr]

Hi guys! Sorry, I haven't pinged in a long time :S Anyway, good news! There's a function in the AoK alpha which assigns each unit to their formation group, just like the pseudocode at the end of our nice discussion, here

@heinezen Your code looks pretty correct! 😄
Note that the function from an alpha build of AOK HD, so they may have done some changes from the original game.
I'll create a PR as soon as I can :)
(p.s. there is another function which converts the Group ID to an attack category which look almost the same... ;) )

[heinezen]

Hey @Piruzzolo ! Glad to hear back from you. I had to remove some content in your comment because we don't allow reversed code from the original games here for legal reasons. It's not worth the trouble that it could cause 😄

[simonsan]

Formation Idea: Triangle/Spear formation (example)
..............
5...Heroes... Monks, Heroes
4...Support... Rams, Onagers, Bombard Cannons
3...Ranged.... Archers, Skrimishers, Hand Connoners, Scorpions, Cavalry Archers
2...Infantry.. Spearman, Swordsman
1...Cavalry... Knights, Camels, Light Cavalry
..............

      2 2
    4 2 2 4
   4 2 2 2 4
  4 1 1 1 1 4
 4 3 3 3 3 3 4
4 3 3 3 3 3 3 4
4 5 5 5 5 5 5 4