关于

Your chocobo’s plumage can be modified by feeding it 6 possible fruits. Each fruit changes the chocobo’s RGB values according to the following table:

RGB values can never exceed or go below . If eating a fruit will cause a value to go beyond the valid range, it will be clamped. The RGB values of possible colors are known, and the problem is how to determine what sequence of fruits will get from one color to another. Unfortunately, not all RGB values are possible since the fruits always change values in increments of (ignoring clamping). The goal is to reach certain RGB values such that the closest possible color is the desired color. Distance here is measured using the Euclidean norm (assuming this is what FFXIV uses).

Greedy Algorithm

A simple algorithm is to keep picking the fruit that gets us closest to the desired color, stopping when no single fruit can get any closer.

function calculate (startColor: Color, endColor: Color): Fruit[] {
  const solution: Fruit[] = []
  let currentColor = startColor
  let currentDistance = startColor.distanceTo(endColor)

  while (true) {
    // Find the best fruit
    const fruitsSorted = fruits.sort((fruitA, fruitB) =>
      currentColor.add(fruitA).distanceTo(endColor) -
      currentColor.add(fruitB).distanceTo(endColor)
    )
    const bestFruit = fruitsSorted[0]

    // If this fruit doesn't get us closer, stop
    if (currentColor.add(bestFruit).distanceTo(endColor) >= currentDistance) {
      return fruits

    // Otherwise, add it to the list and continue
    } else {
      fruits.push(bestFruit)
      currentColor = currentColor.add(bestFruit)
      currentDistance = currentColor.distanceTo(endColor)
    }
  }
}

This algorithm has several shortcomings, but performs decently well and serves as the basis to the actual algorithm used. The biggest issue is that the algorithm tends to stop early. Suppose the target color is , and the current color is . The current distance is and eating any fruit will cause this distance to jump up to or , so the algorithm terminates. But feeding the 3 fruits 塞尔法特尔沙果, 辉鳞油梨, and 奥·哥摩罗浆果 would land exactly on the target color.

Matrix Algorithm

The next algorithm to consider involves treating the problem as a sort of matrix equation. Using the variables

and not requiring them to be integers, we must solve

where is the difference . This does not take into account clamping, which can be avoided almost always. It gives only the number of fruits required, which is then ordered to hopefully avoid clamping. I did this by repeatedly picking fruits that minimize the distance to using the uniform norm.

Since the fruits are “opposites” of the fruits, we can drop the variables by removing the nonnegativity constraints on . This transforms the problem into the standard linear equation

with a negative value of corresponding instead to a positive value of , etc. To turn the solutions into integers, I round them. (This doesn’t always give the closest color, and that problem is the closest vector problem. The lattice is “nice” enough though, and since I don’t end up using this strategy, I don’t bother optimizing it.) This algorithm can outperform the first algorithm in situations where the first algorithm would terminate early.

Lookahead

To fix the issue of early termination in the first algorithm, some amount of lookahead is introduced. Instead of considering fruits one by one, the algorithm does the following:

1. Compute all possible fruit combinations up to a length of
2. Let be the fruit combination that lands closest to the target color
3. If contains no fruits, then stop (no path gets closer)
4. Otherwise, add the first fruit in to the solution and repeat

while (true) {
  // Find the best path
  const allPaths = computePaths(lookahead)
  const pathsSorted = allPaths.sort((pathA, pathB) =>
    currentColor.addPath(pathA).distanceTo(endColor) -
    currentColor.addPath(pathB).distanceTo(endColor)
  )

  // This assumes a stable sort so that the empty path is prioritized
  const bestPath = pathsSorted[0]

  // If no paths get us closer, stop
  if (bestPath.length === 0) {
    return fruits

  // Otherwise, add the first fruit in the path to the list and continue
  } else {
    const bestFruit = bestPath[0]
    fruits.push(bestFruit)
    currentColor = currentColor.add(bestFruit)
    currentDistance = currentColor.distanceTo(endColor)
  }
}

With a big enough lookahead, the algorithm is able to momentarily step further away from the target color in order to get closer later. The algorithm implemented on the Chocobo Color page is this algorithm with a lookahead of , which specifically admits the strategy of eating 3 fruits to increase/reduce all values by 5. This performs very well.

Lookahead also allows the algorithm to utilizing clamping, considering cases where the fruits no longer commute. For example, if the current color is 素雪白 and the target color is 煤烟黑 , then we need to decrease the RGB values as much as possible. Without any clamping, this can be done in 110 fruits. With clamping, it’s possible to get as close with 97 fruits instead. It involves feeding a bunch of 塞尔法特尔沙果 first to max out the RGB’s red value so that subsequent 塞尔法特尔沙果 will lower the average RGB value quicker. Unfortunately, lookaheads with quickly become infeasible, the benefits are small, and situations that can use it are rare.

Optimality

Fortunately, a lookahead of is enough to guarantee that the algorithm terminates with a color as close to the target color as possible (ignoring clamping). By feeding 2 fruits, any individual RGB value can be adjusted by while leaving the other two values unaffected. This means that the color the algorithm ends up at cannot have coordinates that differ from the target color’s by more than . The same must be true of the optimal solution.

Let the solution the algorithm returns be . Focusing only on the red component, the optimal solution must have a red component of , , or . Now consider the 27 points:

One of these points is the optimal solution, and all the points marked as red are impossible to reach due to parity (see the Error section below). Starting at , we must show that the algorithm considers all the green points with a lookahead of . By symmetry, there are only 3 cases that need to be checked.

Thus the algorithm is optimal, in the sense that it returns the closest possible color without clamping.

Error

The algorithm can get us pretty close to the desired color, but it’s not always possible to be exact. The two closest possible colors a chocobo can be are 醋栗紫 and 葡萄紫 . These two have a distance of , so if we can guarantee an error of less than , then the desired color will always be the closest color, but this is impossible to guarantee.

Feeding a fruit will always change the parity of the RGB values, i.e. odd → even or even → odd. If the target color is with all even values, and the current color is with 1 odd value, no sequence of fruits can get closer (ignoring clamping). Thus the maximum error is bounded below by , and we cannot guarantee that the closest color is the desired color. The maximum error is actually given by the vector .

A possible solution is to instead aim for some color that is near the desired color and far from other nearby colors, maximizing the likelihood that we end up at the desired color. The hope is that our final color ends up inside the Voronoi cell of the desired color, so a sensible target would be the centroid of this region. In 2D, this may look like

This would allow more room for error, but I decided computing these targets would be too much work. It would also complicate recoloring chocobos. As long as the algorithm gets as close to the desired color as possible (ignoring clamping), it’s sufficient. There are only two color combinations where the closest color does not lead to the desired color, and those have hardcoded solutions for now.