Crafting Planner Dev Status and Plans: Early October 2024
Hi all!
Real Life (TM) has gotten hectic for me and I haven’t been able to work on the crafting planner much for the past month, but I wanted to go over its current status and my plans (meta-plans? they’re plans for a planner after all) for future development.
First of all, in the month or so prior to Cohost going read-only, I merged a couple sets of changes. One added support for more different crafting behaviors and abilities, particularly the use of Great Strides in more roles than just an immediate prelude to Byregot's Blessing, and the inclusion of Prudent Touch and Prudent Synthesis. Including these further increases the complexity of the problem, but it's manageable, and it allows the planner to find successful rotations for the hardest master crafts using fewer steps and lower stats. You can access these with the new PROGRESS+ and QUALITY+ modes in the command line app, or with the checkboxes for “free” Great Strides and prudent actions in the web app.
The other changeset fixed some subtle bugs in the Pareto front algorithm and tweaked it to run substantially faster based on my improved understanding of its performance properties. I haven't done careful timing measurements, but based on what I vaguely remember for how long it took to run before my changes, it seems to be several times up to ten times faster in the command line app on my laptop. This more than makes up for the greater time taken with new planning modes, and suggests the possibility of making the web app more attractive to use.
Now, I created the web app as an attempt to make a more accessible version of the crafting planner, something that wouldn't require people to compile C++ or use a command line. It hasn't lived up to my expectations because for the hardest recipes -- the ones for which you most need the planner -- it's extremely slow and can easily crash by running out of memory. These are both due to the limitations of running in a browser: it's hard to do threaded parallel execution like the command line app does, and by default I'm stuck in a 32-bit address space that doesn't let the working set of crafting states grow as big as it needs to be. But I'm hopeful that my algorithmic improvements might make it fast enough to get acceptable performance even single-threaded, so if I'm interested in making the web app useful it's time to reduce its memory usage. (Note: there's been some interest in someone making a native C++ graphical interface. Irrespective of the existence of the web app, I welcome that; it'll always have better performance than the web app. I've considered working on that myself, but I also kinda hate doing GUI programming.)
Most of the memory used by the planner is filled with CraftingState objects representing all the different crafting rotations the planner is trying. Each CraftingState contains the current state of the craft (durability, progress, quality, CP, all the various status effects), plus a history of all the actions that were taken to reach that state. That history is the biggest part of the CraftingState's data -- 45 bytes out of 63 total. So now I'm looking into ways to reduce the amount of space taken up by that history. One thing I looked at was that, since I generate a lot of CraftingStates through a trial-and-error approach then winnow them down to a Pareto front of only the ones worth keeping, perhaps I could avoid storing the history of the new CraftingStates until they were proven useful, and instead just have them refer back to the previous state that they came from, plus store just the one action that was taken since then. Handling this cleanly would require changes to how I handle action combos in the planner, and I was able to prototype this before committing to the entire line of development. Unfortunately those changes substantially worsened the performance of the Pareto reduction, making the planner take about 50% longer; I wasn't willing to sacrifice that much performance, so I've shelved that idea for now.
The other thing I'm currently looking at is exploiting the fact that a lot of CraftingStates share much of their history in common. The histories of all CraftingStates can be thought of as forming a tree structure, with its root at the start of the craft, and a new branch coming off the tree whenever the histories of two different CraftingStates (which are still in the Pareto front, that is, still in consideration for leading to viable crafting rotations) diverge from each other. I did some instrumentation and it turns out that on average there are fewer than two tree nodes per CraftingState in the Pareto front, so if I can keep the size of those nodes reasonable, that's a big opportunity for memory savings. It also plays nicely with the current way I handle combo actions, so I get to keep all of my performance gains, and indeed possibly get more because by not keeping the whole history with each CraftingState I'll be transferring less data between the CPU and RAM.
So that's what I'm planning to work on next: reimplementing history storage with a tree structure to reduce memory consumption. It might still be a few weeks until I can find the time to work on it seriously, but I think it will be a good improvement.