The Optimal Order to Purchase Vampire Survivors Power Ups

Posted on 2024-10-20 In CS/Math Disqus: Word count in article: 2.4k Reading time ≈ 9 mins.

The cost for Power Ups has changed since version 0.7, so this post is no longer applicable.

$\newcommand{\eps}{\varepsilon} \newcommand{\R}{\mathbb{R}}$ Vampire Survivors is a game released in early access near the end of 2021. It received 110k recommendations in one month, which is pretty amazing given its minimal aesthetics and seemingly low production costs. I also played it a lot back then, but I won't talk about its gameplay here. Instead, this post discusses the (old) Power Up mechanism and some of the math behind it.

The Power Up mechanism in Vampire Survivors is similar to Kingdom Rush's Upgrades, where you spend the gold earned during gameplay to make permanent gains (e.g., increase move speed by x%). As per the notes in Fandom, the cost for a Power Up is defined as: \[ Price = \text{InitialPrice} \cdot (1 + \text{Bought}) \cdot \left(1 + \frac{\text{TotalBought}}{10} \right), \] where $\text{InitialPrice}$ is the initial price of the Power Up, $\text{Bought}$ is the number of purchased ranks for this Power Up, and $\text{TotalBought}$ is the total number of purchased ranks among all Power Ups. What's interesting is that the order in which you buy Power Ups actually matters!

Intuitively, we should purchase expensive Power Ups first. For example, IGN recommends maxing out Power Ups with the highest initial costs first. However, this is not optimal. Suppose we have two Power Ups, A and B. A has 5 ranks with an initial price of 1, while B has only 1 rank with an initial price of 2. If we max out A first, the total price is: \[ 1 \times 1 + 1.1 \times 2 + 1.2 \times 3 + 1.3 \times 4 + 1.4 \times 5 + 1.5 \times 2 = 22, \] and if we max out B first, the total price is: \[ 1 \times 2 + 1.1 \times 1 + 1.2 \times 2 + 1.3 \times 3 + 1.4 \times 4 + 1.5 \times 5 = 22.5. \]

So, here is our central topic today:

What is the optimal order for buying all Power Ups?

A General Formulation and Its Hardness

The first attempt is to formulate the problem as a directed acyclic graph (DAG). More specifically, each rank $j$ of a certain Power Up $i$ is a node $v_{i, j}$, and it has a weight defined as \[ w(v_{i, j}) = \frac{1}{10} \text{InitialPrice}_i \cdot (1 + j), \] with edges $v_{i, j-1} \to v_{i, j}$, representing that $v_{i, j}$ depends on $v_{i, j - 1}$. A valid order of purchasing Power Ups is a topological sort of all nodes, and our goal is to find the optimal topological sort. We may notice that the graph has a special property (i.e., it only contains chains), but for now, let's focus on a general graph.

Weighted Topological Sort

An equivalent objective can also be defined in terms of completion time $c(v)$. The completion time of a specific node $v'$ in an ordering $v_{a_1}, \dots, v_{a_n}$ is the $i$ such that $v' = v_{a_i}$, so the objective can also be written as \[ \sum_{i} i w(v_{a_i}) = \sum_{v \in V} c(v) w(v). \]

One might try to solve the general problem but may struggle to make significant progress. The reason is simple: it's NP-hard! We present a proof, which is essentially a combination of Theorem 4.15 and Exercise 4.19 from Elements of Scheduling with (very) minor modifications.

Proof of NP-hardness of Weighted Topological Sort

We start with Linear Arrangement, an NP-hard problem, which will be defined below and used for reduction.

Linear Arrangement

Given an undirected graph $G = (V, E)$, find a one-to-one mapping $f: V \to [n]$ to minimize $\sum_{(u, v) \in E} |f(u) - f(v)|$.

One can easily show that Linear Arrangement is equivalent to minimizing $\sum_{(u, v) \in E} \max(f(u), f(v))$, as $|f(u) - f(v)| = 2 \max(f(u), f(v)) - f(u) - f(v)$. We now reduce the Linear Arrangement instance to a Weighted Topological Sort instance.

Let $K = |E|^2$. Construct a graph $G' = (V', E')$ from $G = (V, E)$ as follows:

For each vertex $v_i \in V$:

Add $K$ nodes $V_i'$ to $V'$: $v_i^{(j)}$ for $j \in \{1, \dots, K\}$;

Add $K - 1$ dependencies: $v_i^{(j)} \to v_i^{(j + 1)}$ for $j \in \{1, \dots, K - 1\}$.

For each edge $e = (v_i, v_j) \in E$:

Add $e$ to $V'$;

Add two dependencies: $v^{(K)}_i \to e$ and $v^{(K)}_j \to e$. We also define the vertex weight as $w(v_{i}^{(j)}) = 0$ and $w(e) = 1$ for each edge $e$.

Let $OPT$ be the optimal $\sum_{(u, v) \in E} \max(f(u), f(v))$ in the Linear Arrangement instance, and let $f^*$ be the corresponding mapping. Similarly, let $OPT'$ be the minimum total cost in the constructed instance, and let $v'^*$ be the corresponding solution.

We first show that $OPT' < K \cdot OPT + K$. We determine the order of $V'_i$ as \[\left[V'_{f^{*-1}(1)}, V'_{f^{*-1}(2)}, \dots, V'_{f^{*-1}(n)} \right]\] and then insert all edges $e \in E$ as early as possible. Since at most $|E|$ edges are inserted, the completion time for an edge $e$ is bounded by $c(e) < K \max(f^*(u), f^*(v)) + |E|$, which gives a total cost of \[ OPT' < \sum_{e = (u, v) \in E} \left(K \max(f^*(u), f^*(v)) + |E| \right) = K \cdot OPT + K. \]

Now, we construct an optimal solution $f$ from $v'^*$. We consider the subsequence $\left\{v_{a_i}^{(K)} \right\}_i$ in $v'^*$ and define $f\left(v_{a_i} \right) = i$. The completion time $c(e)$ for an edge $e = (u, v)$ has a lower bound of $c_e > K \max(f(u), f(v))$, which in turn provides an upper bound on $\sum_e \max(f(u), f(v))$: \[ OPT \leq \sum_{(u, v) \in E} \max(f(u), f(v)) < \frac{1}{K} \sum_{e \in E} c_e = \frac{1}{K} OPT' < OPT + 1. \] Note that $f$ maps nodes to integers, so the first inequality must be an equality, which means $f$ is an optimal mapping for the Linear Arrangement instance.

The Optimal Order for Buying Power Ups?

The result above is definitely frustrating. However, we might want to take a step back. Remember that our goal is only to find the optimal order to buy Power Ups? It's sufficient to consider only chains instead of a general graph.

Weighted Topological Sort for Chains

Given a directed acyclic graph $G = (V, E)$ and a node weight function $w: V \to \mathbb{N}$, find a topological ordering $v_{i_1}, \dots, v_{i_n}$ to minimize $\sum\limits_{i=1}^n i w(v_{a_i}).$ The graph $G$ contains only $k$ chains: \[ \begin{cases} V = \{v _{i, j}\} _{i \in \{1, \dots, k\}, j \in \{1, \dots, n_i\}}, \\ E = \{v _{i, j} \to v _{i, j + 1}\} _{i \in \{1, \dots, k\}, j \in \{1, \dots, n_i - 1\}}. \end{cases} \]

It turns out that there is an efficient (polynomial time) algorithm!

A polynomial algorithm for Weighted Topological Sort for Chains

Let $v^*$ be the optimal ordering. Let a segment be an interval of nodes from the same chain. Since $v^*$ is optimal, swapping adjacent segments that come from different chains won't improve the objective. This can be formulated as: let $v_{i_1, \{l_1, \dots, r_1\}}$ and $v_{i_2, \{l_2, \dots, r_2\}}$ be adjacent segments where $i_1 \neq i_2$, then: \[ \sum_{j=l_1}^{r_1} (j - l_1) w(v_{i_1, j}) + \sum_{j=l_2}^{r_2} (j - l_2 + r_1 - l_1 + 1) w(v_{i_2, j}) \leq \sum_{j=l_2}^{r_2} (j - l_2) w(v_{i_2, a}) + \sum_{j=l_1}^{r_1} (j - l_1 + r_2 - l_2 + 1) w(v_{i_1, j}), \] After simplification, it becomes: \[ \frac{\sum\limits_{a=l_2}^{r_2} w(v_{i_2, a})}{r_2 - l_2 + 1} \leq \frac{\sum\limits_{a=l_1}^{r_1} w(v_{i_1, a})}{r_1 - l_1 + 1}. \]

We define the weight of a segment $w(v_{i, \{l, \dots, r\}}) := \frac{1}{r - l + 1} \sum\limits_{j=l}^r w(v_{i, j})$, so the inequality above simply means that $w(v_{i_1, \{l_1, \dots, r_1\}}) \geq w(v_{i_2, \{l_2, \dots, r_2\}})$, and all maximal segments in $v^*$ are sorted in descending order.

Now, let us consider the chain $V_i$. We start with $n_i$ chains, each containing only one node. Now we're trying to merge adjacent nodes: If there exist two adjacent segments $v_{i, \{a, \dots, b\}}$ and $v_{i, \{b + 1, \dots, c\}}$ such that $w(v_{i, {a, , b}}) < $ $w(v_{i, \{b + 1, \dots, c\}})$, we can merge them into one segment $v_{i, \{a, \dots, c\}}$. The reason is: If there is another segment $v_{i', \{l', \dots, r'\}}$, one of the following must be true: \[w(v_{i', \{l', \dots, r'\}}) > w(v_{i, \{a, \dots, b\}}), \quad \text{or} \quad w(v_{i', \{l', \dots, r'\}}) < w(v_{i, \{b + 1, \dots, c\}}),\] which contradicts our previous observation. The process of merging can be summarized in the following pseudocode:

def merge_segments(chain):
    segments = []
    for v in chain:
        cur_seg = [v]
        while segments and w(segments[-1]) < w(cur_seg):
            cur_seg = segments.pop() + cur_seg
        segments.append(cur_seg)
    return segments

After merging segments, all segments in chain $i$ are sorted in descending order of $w$. This naturally leads to a greedy algorithm: The best candidate in each chain will be the current first segment, so we don't have any dependency issues!

def optimal_order(chains):
    segments = [seg for chain in chains for seg in merge_segments(chain)]
    segments = sorted(segment, key=w)
    return [v for seg in segments for v in seg]

The code above is inefficient in its representation of segments and can be easily optimized to $O(n \log n)$, where $n = |V|$.

How About a General Completion Time Weight Function?

We have considered the objective in the form of $\sum_{v} c(v) w(v) = \sum_{v} \mathnormal{Id}(c(v)) w(v)$, where $Id$ is the identity function. Is it possible to generalize this to a more complex completion time weight function $f: \mathbb{N} \to \R$ instead of the identity function?

Unfortunately, this is also NP-hard, even if the graph contains only chains. We will reduce the 3-Partition problem to it.

3-Partition

Let $S$ be a multiset containing $3n$ positive integers. Can we partition $S$ into $n$ multisets, each containing 3 elements with a sum $s = \frac{1}{n} \sum\limits_{e \in S} e$?

Note that 3-Partition is strongly NP-complete: it's NP-complete even when all numbers are bounded by a polynomial of $n$.

Proof of NP-hardness of General Completion Time Weighted Topological Sort

Given an instance of the 3-Partition problem (where we assume every element in $S$ is strictly greater than 1), we construct the following problem:

Instance of General Completion Time Weighted Topological Sort

The graph $G$ contains $3n$ chains, where the $i$-th chain $V_i$ has $S_i$ nodes.

The weight function $w$ and completion time weight function $f$ are: \[w(v_{i, j}) = \begin{cases} 1 & j = 1 \\ 0 & j = S_i \\ 2 & \text{otherwise} \end{cases}, \quad f(t) = \begin{cases} 1 & t \bmod s \in \{1, 2, 3\} \\ 2 & t \bmod s \in \{0, s - 1, s - 2\} \\ 0 & \text{otherwise} \end{cases}\]

From the Rearrangement Inequality, $3n$ is a lower bound of the objective, and it is only attained if $c(v_{i, 1}) \bmod s \in \{1, 2, 3\}$ and $c(v_{i, S_i}) \bmod s \in \{0, s - 1, s - 2\}$ for all chains $i$. In this case, the optimal ordering can be split into $n$ intervals evenly, each consisting of 3 complete chains, which means the 3-Partition instance is satisfiable.

Are Chains and Identity Completion Time Weight Function the Limit?

We found an efficient algorithm for Weighted Topological Sort for Chains, but it failed for two extensions:

A general graph;
A general completion time weight function,

both of which have been proven NP-hard. So what is the right problem to focus on for a successful generalization?

Section 4.3 of Elements of Scheduling shows that the following extensions still have polynomial time algorithms:

A series-parallel graph;
A cost function with a preference order on sequences.

We refer readers to the book for more details.

Notes

In fact, this post has been in draft for more than a year. The reason I didn’t post it earlier is that… I realized I was completely wrong when it was almost finished. I thought it should align with a classic problem:

A Classic Problem

Given a DAG, the task is to sort all vertices topologically, such that vertex 1 has the smallest index. Break ties by minimizing the index of vertex 2, 3, and so on, until $n$.

which can be seen as a special case ($w(i)= \eps^i$) of the Weighted Topological Sort problem. The analysis, however, is entirely different. When I realized this, the post was nearly done, except for the (wrong) proof. It was awkward to admit I couldn’t solve it anymore! I then modeled the problem as the Weighted Topological Sort problem and spent quite some time trying to solve it. Unfortunately, I made no progress in designing an efficient algorithm. Recently, I tried again and, after changing some keywords, I found a relevant paper. After checking out a few more papers and reading their Introduction and Related Work sections, I discovered the right keywords, which led me to Elements of Scheduling and a satisfying solution.

As for writing, I feel it’s better to present and solve the Weighted Topological Sort problem first and then attempt to generalize it. However, I’m too lazy to reorder the sections, as it already took me a lot of effort just to finish the post…

References

Scheduling (single machine)
Elements of Scheduling