The Travelling Apothecary. A discrete optimization approach to… | by Nathan Pratt | Dec, 2020


A discrete optimization approach to Skyrim’s alchemy device.

Nathan Pratt

Whether you’re replaying the sport for the fifth time or to your 15th personality (not able to keep in mind what you have been doing with the opposite 14 saves while you ultimate had unfastened time), Skyrim nonetheless holds a heat spot within the hearts of many avid gamers. For me, this replayability does no longer prolong to the alchemy device inside Skyrim. Nearly a 12 months in the past, I had some unfastened time over the vacations and was once beginning up any other personality. I used to be looking for a strategy to keep away from the grind of unlocking aspect results once I known this may well be represented as an optimization drawback.

I want to percentage with you the idea in the back of this drawback and the approach with explanations (written in R).

Skyrim is a role-playing recreation set in a medieval myth international. There are a number of mechanics the participant can grasp throughout the recreation. These come with archery, swordsmanship, blacksmithing, magic, and alchemy amongst others. Alchemy, particularly, comes to gathering 111 other components (from the wild, buying from retail outlets, or sometimes discovering them as loot from fallen foes).

  • In Skyrim’s alchemy device, a potion is created the usage of 2–Three components and has the entire results which are shared between any 2 of the components.
  • Each aspect has Four results.
  • The results are all unknown except published by growing potions with the ones results or consuming the aspect can disclose results 1–Four relying at the degree of your Experimenter perk (calls for degree 90 in Alchemy earlier than you’ll be able to absolutely release this perk).

A participant on his first playthrough will start by randomly checking out masses of aspect mixtures that can continuously fail to provide viable potions. By the tip in their playthrough, maximum will sooner or later cross to a wiki website and glance up the consequences of unknown components. Others will make investments some issues into the Experimenter perk and consume any aspect they see with unknown results.

On next playthroughs, many avid gamers will open up the console and cheat within the Experimenter perk early or cross to on-line boards for an optimum path to unlocking results. This forum post is essentially the most smartly carried out of those posts that I’ve noticed, however sadly, it simplest incorporates components from the bottom recreation (none from the additions to the sport). For reference, the suggestions by the avid gamers in this board include 74 potions to release the consequences for the 90 components within the base recreation. The slower of the 2 algorithms discussed on this article can release a lot of these results the usage of simplest 67 potions. Unfortunately, the speedier of the algorithms makes use of 82 potions because of it lately leaving remoted wallet of unknown results (This shall be mentioned within the Testing phase of the item).

When results are recognized, you’ll be able to simply filter out by which results you need and select components accordingly inside Skyrim’s personal crafting device (on the alchemy desk). For this reason why, revealing the consequences the primary time will due to this fact supply quite a lot of comfort for avid gamers.

Since I’m really not prepared to degree as much as 90 in Alchemy earlier than unlocking those aspect results, we can try to release results by growing potions the usage of the fewest choice of components.

We shall be putting in this knowledge in a directed graph the place each and every aspect connects to its related results.

I will be able to think you will have some familiarity with R and the libraries I will be able to be the usage of. I will be able to supply explanations/feedback that are supposed to supply enough context should you aren’t aware of any specific library.

The following libraries shall be used (hyperlinks result in cran for each and every)

  1. stringr: provide for your base set up of R for string manipulation
  2. rvest: for internet scraping
  3. igraph: supplies a graph knowledge construction and related purposes
  4. dplyr and tidyr: for knowledge body manipulations

We shall be scraping the information from a fan-based wiki the usage of the next code:

This knowledge body will have to appear to be the next:

We now will have to make a decision methods to constitute this knowledge to maximum successfully use it for this optimization drawback. I’ve selected a reasonably easy graph illustration the place the nodes include the components and results and the perimeters constitute connections from components to their results. (One essential level to notice, I’m including in a assets rely which we can speak about later)

The following code will arrange this knowledge in an igraph object to be used in our purposes:

Notice that this creates a graph the place each node has the next houses:

  • Name: Accessed by way of V(alchemyGraph)$title Note that igraph ignores the primary column and references it by way of the lowercase title
  • Type: signifies whether or not the node represents an aspect or an impact. Referenced by way of V(alchemyGraph)$Type
  • Count: A placeholder to signify the person’s present stock of the aspect (at all times NA for an impact). V(alchemyGraph)$Count
  • Comments: Comments from the scraped knowledge. We received’t be the usage of this box on this workout

Also, each edge incorporates a boolean assets Known, which represents whether or not or no longer that ingredient-effect courting is unlocked by the participant. Accessed by way of E(alchemyGraph)$Known

The ensuing graph incorporates 111 components, 55 results, and 444 edges. For a way of scale, it may be visualized the usage of the next:

vertex.label = NA,
vertex.dimension = 4)
Light blue nodes are results and the pink nodes are components

Below we can outline a number of application purposes. Error dealing with is integrated for some. My apologies for the duration of this phase and congrats if you’ll be able to observe all of them. Feel unfastened to make use of the desk of contents if you want to skip this phase.

First, we can outline a couple of purposes that can get components and their results again out of the graph.

Next, we can outline purposes to set/get the aspect rely in addition to set the Known assets of ingredient-effect edges.

Next shall be purposes for calculating the consequences found in a potion given the components used and any other to calculate the choice of ingredient-effects unlocked if the equipped components have been used. We can even upload a serve as to simulate making a potion the usage of a given graph in addition to one to guage the choice of components a chain of potions unearths.

Now a few purposes which are somewhat extra summary and shall be used to get all conceivable mixtures of a given set of components to be used in the primary serve as. (The make bigger grid serve as is a amendment of 1 discovered on stack overflow. The unique serve as is connected within the feedback)

I went via five selection variations of the set of rules to try to achieve processing potency with out sacrificing effects. One of which pre-loaded the graph with all doable potion mixtures and attached the ones potions to a unmarried root node for looking (root > potion > components > results). The following two algorithms stay the similar graph construction outlined above and display minor tradeoffs when it comes to velocity and potency. In a Gremlin graph database, there are a couple of traversal methods that would make this more uncomplicated than when carried out in R.

I discussed I might provide an explanation for the desire for the Count assets. The most simple approach would think that we have got the entire components and I wish to know the fewest potions I will have to make to release all aspect results (With this set of rules that solution is 78). With the Count assets, we will use subgraphs to just calculate for the ones components we lately have in our stock. This makes the answer a lot more dynamic and helpful to the adventurer who needs to be an apothecary however hasn’t discovered the rarest of components but.

The serve as recommendPotionForEffectReveal() will function the main good judgment for the optimization. This serve as will take a graph within the type of alchemyGraph above, and go back a vector (duration 2 or 3) of the components to make use of to make the following potion. This really helpful potion will have to be the person who will disclose the very best choice of unknown ingredient-effect edges with a secondary precedence of fewest components. Other components shall we additionally prioritize are price/rarity of aspect (no longer integrated on this set of rules) and amount of components (appearing a desire for unlocking extra results for the aspect now we have fewer of)

We will quilt this serve as step by step. Before we commence, let’s take a look at a easy subgraph consisting of simplest Four components

structure = coords,
vertex.label.colour = V(sampleGraph)$colour,
vertex.dimension = 0)
Ingredients in Red

Next, we’ll show off recognized/unknown edges by the usage of a dotted line for unknown aspect results. Also, you’ll observe that this graph has results with just one edge. This would no longer occur within the unique graph. For now, we can mark the ones edges as recognized to forget about them.

Dotted Lines point out unknown ingredient-effect relationships (from the participant viewpoint)

In the primary segment of the set of rules we can create the next subgraphs:

  • sg: A subgraph appearing components with a rely > Zero and results that connect with a couple of provide aspect.
  • sgUnknown: A subgraph of sg the place we delete all Known edges.


Please enter your comment!
Please enter your name here