SFTtech
[WIP] doc on formations
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 👍
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.
Oh shit this is gonna be so much fun implementing that in the pathfinder/steerer 🙄
Found two articles which are real gold mines. They primarily deal with the formation systems of RTS.
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
@heinezen it seems to be:
- first, arrange the first group (the leading one). Let
numRow1stLine1stGroupbe the number of units in its first row - each of the remaining groups are arranged in
ceil(numOfUnitsNthGroup / numRow1stLine1stGroup)rows (let's call itrowCountNthGroup- different for each group). - the number of units in each row is then
ceil(numOfUnitsNthGroup / rowCountNthGroup)for the first n-1 rows, andnumOfUnitsNthGroup % (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) 😄
@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.
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
..............
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 :smile: 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 itrowCountNthGroup- different for each group). - the number of units in each row is then
ceil(numOfUnitsNthGroup / rowCountNthGroup)for the first n-1 rows, andnumOfUnitsNthGroup % (rowCountNthGroup-1)for the last one
We need to check this against some data
@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
GroupIDand sort into the associated sub-formation; - get
widthof the unit. Ifwidthof unit is greater thanminWidthof the sub-formation, setminWidth=width; (all units of the sub-formation have to respect the minimum width which would always be the width of the widest unit)
- get
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 :smile: . 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).
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.
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:
- find out what
GroupIDbelongs to each sub-formation - determine how a single sub-formation orders its units
- explore how a single sub-formation handles different unit types, e.g.
spearmanandswordsman(the pattern of how they are formatted doesn't look random to me) - finally discover how the 4 sub-formations are influenced by each other inside their parent-formation (this is were
subroutinecomes 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?
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:
- Cavalry: Elephants, all the cavalry except those in the ranged sub-formation
- 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
Just wanted to add that there are 4 types of formations: http://aok.heavengames.com/gameinfo/formations
@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
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.
@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.
@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:
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 :smile:.
Yes, will read that :) For the ideas about our pathfinder in general, see #366.
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.
@heinezen Yes, I mean circle overlapping.
Good job, really! :+1:
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
@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 😄.
I'd say very lucky, since I've done it 3-4 times without noting! :) I'll do some tests with other configurations
This (selection order) behavior seems sort of silly; should we really attempt to clone it? (would it harm the user experience not to?)
@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...
.............
@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
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.
@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
UnitIDhaven't been added yet, create a stack (or list, queue) and put it on there - Else check which stack corresponds to
UnitIDand 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 lineuntil 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? 😄
The first line ALSALS for me. The second line is the same as yours. Maybe a mistake? 😉
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...
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 :)