Add formations formulas reverse engineering by teaalltr · Pull Request #1761 · SFTtech/openage · GitHub

This adds my results in clean-room reverse engineering the mechanics of choosing the number of lines in formations and so on

Add formations formulas on formations lines

I like the overall idea of this document, but you should try to make this read less like someone's math homework 😅

This should probably not be a separate file but moved into /doc/media/reverse_engineering/formations.md.

I think the readability of your whole text suffers from "too much math lingo" :D I can understand what you are saying but someone implementing this mechanic will probably not have a great time. Especially someone without a mathematical background. You can also probably fix a lot of this with formatting things differently, e.g. by making a bullet point llist for the intervals or, even better, a table.

Here's an example of what I would like to see:

Suggested change

      
            If you table the number of units in the first row, in the second row and so on accordingly to the number of units in the group, you'll find a pattern in the units number intervals for a given row count: namely, the length of the first interval `(0...6)` is `6`, the second `(7...15)` is `9 = 6+3 + 0`, the third `(16...28)` is `13 = (6+3) + 3+1`, the fourth (maybe) `(29...46)` is `18 = ((6+3) + 3+1 ) + 3+2`.
          
            Units in a line formation are grouped into several lines. The number of lines and units per line is determined by the total number of units in the group.
          
            The pattern for the number of lines is as follows:
          
            | No. of Lines | Unit Count  |
          
            |--------------|-------------|
          
            | 1            | `(0...6)`   |
          
            | 2            | `(7...15)`  |
          
            | 3            | `(16...28)` |
          
            | 4            | `(29...45)` |
          
            | 5            | `(46...60)` |

Where does the 13 = (6+3) + 3+1 come from?

The forth interval is (29...45) which you can actually check in HD Edition and DE2 since those have a selection limit of 60.

Please give your functions and variables appropriate names, I have no idea what f does. n is the unit count I presume?

I'm not sure if the second option is actually faster. In any case, I think the document should not be about coding recommendations and more about explaining the mechanic... and multiple code snippets can make this harder to understand.

I recommend you only put in one of these two code snippets. Preferrably the most readable one which for me is the second one.

Same problem as above, i.e. you're now recommending more code. This time also in a language that we don't even use in our codebase :D I appreciate what you did here, but it's not really helpful for someone who wants to learn what how to replicate the formation formulas from AoE2. Same goes for the rest of this section which gets too much into details about mathematical specifics that are hard to understand.

I think you should do 2 things to improve this section:

Rewrite it so that this section only contains the formulas and their explanation. We don't need much derivation.
Create only a small example script which contains the most readable mock implmentation for these formulas.

This should be at the start of the formulas section. We don't need the unoptimized solutions.

This whole section is interesting, but I would say it's not relevant at all in practice. Usually, any compiler or interpreter will optimize this code much better. See also our documentation on optimization, especially item no. 2

readability comes first: openage depends on outsiders being able to understand the engine code. If the code is super fast but totally incomprehensible, then nobody is going to maintain it.

avoid premature optimization: optimization without reason wastes time, reduces readability, and can sometimes lead to even worse performance. It's often better to implement a workable solution first and then use profiling to identify bottlenecks. Modern compilers are often smart enough to find small improvements during compilation anyway.

prefer architecture improvements over speeding up specific use cases: openage is a game engine, so we don't exactly know what people will use it for. We want the general case to be fast, not the edge cases.

What would this be used for?

You also need to fix the failing CI checks. Click on them to see more details.

hey @teaalltr! With a bit of polishing I'd gladly merge this into our main repo.
Would you mind improving your document with the given feedback?

How did you figure this out, by the way? 😄

teaalltr added 2 commits March 22, 2025 10:50

Add formations formulas on formations lines

36e80ef

This adds my results in clean-room reverse engineering the mechanics of choosing the number of lines in formations and so on

Merge pull request #1 from teaalltr/formations-formulas

a214dbb

Add formations formulas on formations lines

heinezen requested changes Mar 23, 2025

View reviewed changes

heinezen added nice new thing ☺ A new feature that was not there before documentation Involves the project documentation labels May 18, 2025

+              ``` python
+              def f(n):
+                  if n == 0:
+                  	return 9
+                  return f(n-1) + n + 3
+              ```

+              ``` python
+              rows[rowCount - 1] = numOfUnits - (rowCount-1)*rows[0]
+              ```
+              or, if you care about performance:
+              ``` python
+              rows[rowCount - 1] = numOfUnits % (rowCount-1)
+              ```

+              **Considerations** : for performance sake (or just out of curiosity), you may want to find a better, non recursive function for `f`. It turns out that the recurrence equation can be solved to
+                      f(n) = (18 + 7*n + n^2)/2
+              using Mathematica's
+              ``` mathematica
+                      RSolve[{f[n] == f[n-1] + n + 3, f[0] == 9}, f[n], n]
+              ```

+              The final Python code may be:
+              ``` python
+              import math
+              def findRowCount(numOfUnits):
+                  return math.ceil((math.sqrt(1 + 8*numOfUnits) - 3) / 4)
+              ```

+              ## Performance considerations
+              Turns out that the expression is equivalent to
+              ``` mathematica
+                  -Quotient[N, Quotient[3 - Sqrt[1+8*N], 4]]
+              ```
+              which contains less divisions and `Quotient` is directly mapped to the `IDIV` Intel x86 instruction.
+              More, it is equal to
+              ``` mathematica
+                  -Quotient[N, Quotient[3 - Sqrt[BitShiftLeft[N, 3]], 4]]
+              ```
+              which not contains the addition and uses a left shift to do the multiplication, thus being faster.
+              Or one may use the following
+              ``` mathematica
+                  -Quotient[N, Quotient[2 - Floor[Sqrt[BitShiftLeft[N, 3]]], 4]]
+              ```
+              where `Floor[Sqrt[n]]` is the [integer square root function](https://en.wikipedia.org/wiki/Integer_square_root) and there exist plenty of optimized algorithms to do it.


		### Line formation

		If you table the number of units in the first row, in the second row and so on accordingly to the number of units in the group, you'll find a pattern in the units number intervals for a given row count: namely, the length of the first interval `(0...6)` is `6`, the second `(7...15)` is `9 = 6+3 + 0`, the third `(16...28)` is `13 = (6+3) + 3+1`, the fourth (maybe) `(29...46)` is `18 = ((6+3) + 3+1 ) + 3+2`.

+              ## BONUS: Hackish stuff
+              The general formula is `M*i - (i-u)` with some constraints on `M` and `u`.
+              This gives us:
+              ``` mathematica
+                      Ceiling[N / Ceiling[(1-M-2*u + Sqrt[(-1+M)*(-9+M+ 8*N) + 4*(-1+M) u+4 u^2]) / (2*(-1+M))]]
+              ```
+              The constraints on N, M and u are `(N | M | u) ∈ ℤ && u ≥ 1 && M ≥ 2 && N ≥ 2`.
+              This is useful if we're not satisfied with the default game behavior :smile:

Add formations formulas reverse engineering by teaalltr · Pull Request #1761 · SFTtech/openage · GitHub

Uh oh!

Uh oh!

Add formations formulas reverse engineering - #1761

Add formations formulas reverse engineering#1761teaalltr wants to merge 2 commits intoSFTtech:masterSFTtech/openage:masterfrom teaalltr:masterteaalltr/openage:masterCopy head branch name to clipboard

Conversation

teaalltr commented Mar 22, 2025

Uh oh!

heinezen left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

heinezen Mar 23, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

heinezen commented Mar 23, 2025

Uh oh!

TheJJ commented Mar 31, 2025

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

Add formations formulas reverse engineering#1761
teaalltr wants to merge 2 commits into
SFTtech:masterfrom
teaalltr:master

heinezen Mar 23, 2025 •
edited
Loading