This program is a simple implementation of an algorithm for finding optimal gizmos for perk combinations, for RuneScape's Invention skill. The data used for components and perks, and the perk generation algorithm the search focuses around, can be found on the RuneScape Wiki.
You will need CMake 3.5+, and a compiler supporting C++17. After that, the application can be built by:
mkdir build
cd build
cmake ..
make
After building, the tool can be run with:
./gizmo-search <arguments>
The arguments you can specify are:
- Gizmo Type -
-stdfor Standard or-ancfor Ancient. Defaults to-std. - Equipment Type -
-wfor Weapon,-tfor Tool,-afor Armour. This must be specified. - Invention Level -
-l levelwherelevelis your invention level. E.g.-l 137. Defaults to level 120. - Target Perks -
-p perk and rank. This must be specified, and only up to two targets can be specified. E.g.-p Precise 4. - Excluded Components -
-x component. You can specify any number of these, and these components will not be considered when searching for Gizmos. E.g. to exclude Noxious and Subtle:-x Noxious -x Subtle. - Number of Results -
-n number. Defaults to 1. - Number of Threads -
-j number. Defaults to 1.
If we wanted to find an Ancient Armour Gizmo containing Biting 4 and Mobile, at Invention level 137, we would run the tool as follows:
./gizmo-search -anc -a -l 137 -p Biting 4 -p Mobile
Or suppose we wanted to do the same, but excluding any Gizmos using Subtle Components. We can run:
./gizmo-search -anc -a -l 137 -p Biting 4 -p Mobile -x Subtle
The algorithm used here focuses on looking for opportunities to reduce the search space required when looking for optimal gizmos, and reducing the amount of duplicate work done.
One of the quirks associated with the perk generation algorithm is the fact that the position of materials within a gizmo can significantly affect the generated perks in some cases, due to the way the generated combinations are iterated over and the sorting algorithm used.
If we examine the algorithm in detail, specifically step 2, we see what matters in the breaking of ties is the order in which unique possible perks are inserted from those available, from the gizmo's components. Therefore, if two components do not add any new perks, their order can be changed without affecting the probabilities of the perks generated.
We can exploit this by defining a 'Gizmo Normal Form', which will have the special property that for any two gizmos A and B, GNF(A) = GNF(B) implies that perks(A) = perks(B), where GNF(G) represents the normal form of gizmo G and perks(G) the perks and probabilities generated by G.
In gizmo normal form, if we iterate over the components in their insertion order (middle -> top -> left -> right -> bottom), if we find that a component does not add any new possible perks, then the remaining components are guaranteed to not add any new perks too. Furthermore, we sort the components in the gizmo from this point onwards by their ID to ensure uniqueness.
Consider a weapon gizmo containing Armadyl Components, Precise Components, Evasive Components, Evasive Components, and Subtle Components. In this order, the gizmo is not in normal form:
- Armadyl Components provide Precise (not seen before).
- Precise Components provide Cautious, Blunted, Equilibrium, and Flanking. (Precise too, but we've seen that already).
- Evasive Components do not provide any new perks (they provide Cautious and Blunted, but we've seen both before).
- The second Evasive Component once again does not provide any new perks. But:
- The Subtle Component provides Looting, Demon Bait, and Mobile.
As the Subtle component appearing last provides new perks, after the previous Evasive components do not, this is not in normal form. We can swap the Subtle and first Evasive component to bring the gizmo into normal form, and this is guaranteed to not affect the probabilities of perks generated by the gizmo, as the insertion order of possible perks will remain the same.
Therefore, the normal form of this gizmo is Armadyl, Precise, Subtle, Evasive, Evasive.
Now, we know that if two gizmos share the same normal form, they generate the same perks with the same probabilities, and since they use the same components we can safely discard all but one for the purposes of searching. This significantly reduces the number of gizmos we have to calculate perks for.
As described in step 3 of the perk generation algorithm described on the Wiki, in order for a perk with a given rank to be generated, the sum of the perk values from each component must reach it's threshold.
If we reach a point where the maximum total potential contribution, defined as the maximum over all components of the sum of each component's base and roll values for a given perk, multiplied by the remaining slots in the gizmo, becomes less than the perk's rank threshold minus the current contribution from existing components in the gizmo, then it is impossible to generate the desired perk from that point onwards.
This can, in some cases particularly for high rank perks, remove thousands of gizmos from needing to be tested.
For Enhanced Devoted 3, we require a threshold of 230.
The maximum sum of base and roll for all components for this perk is Faceted Components, with 53.
Now consider in our search we are currently at a situation looking at gizmos starting Crystal Parts, Crystal Parts, x, x, x. The total maximum contribution from the crystal parts is (5 + 15) * 2 = 40. Therefore at this stage we need 230 - 40 = 190 extra contribution to reach Enhanced Devoted 3. But, we have only 3 remaining slots, and 3 * 53 = 159 < 190, so from this point we know it is impossible to generate Enhanced Devoted 3, and we can completely skip all possibilities for those remaining 3 components.
These two optimisations together are enough to speed up the search to workable times on their own in most cases - for lower rank perks there are still problems.
The final optimisation is the only one which may affect the correctness of the algorithm, but such cases should hopefully be rare and so far none have been found.
We can make the assumption that an optimal gizmo will only ever contain components which have a chance to generate at least one of the two target perks. Now, with the way ties are broken, it is theoretically possible this might not be true, but so far it appears to be a relatively safe assumption. If you happen to find a counterexample, we can investigate and perhaps add some logic to handle it.
With this optimisation alone, the search space is reduced in most cases to at most around 50,000 potential gizmos, a very large number of which will be further filtered using the previous two optimisations, leading to on-the-fly searches being possible very quickly.
There is definitely scope to include more optimisation here, for example by excluding gizmos containing components unavailable for the input level, and finding a better way to generate all possible normal form gizmos from a given set of components, but for now this appears to be enough to get the search times low enough to be usable.
Of course, it is trivially easy to cache identical requests too to avoid multiple searches for the same level/perks/type combinations, as these should not change.