Arknights Endfield SAT Place and Route

Technologies:

Minizinc
OR-Tools CP-SAT (Python)
Matplotlib

Code: https://github.com/puct9/endfield-placement

About the game

Arknights Endfield is a gacha game released not so long ago and features all the usual cute looking characters and loot box mechanics you would expect. However, it’s unique in also having a factory building element! I’ve since stopped playing because I found myself being stretched needing to simultaneously feed my Genshin Impact addiction, but the puzzle of figuring out how to lay out your factory in a space efficient manner was something I wasn’t going to let go as quickly.

Placement rules

The way factory building works in the various regions in the game vary slightly, but they follow similar rules. The important rules which affect how factory elements are allowed to be placed are that

Factory buildings cannot overlap with each other or with conveyor belts
Conveyor belts can overlap with other conveyor belts only when they are travelling in perpendicular directions

Modelling approach

Prior to this experiment, I had no knowledge of anything to do with place and route (PnR). Apparently, people in the real world tend to use simulated annealing and now reinforcement learning. Being naive, I opted to use constraint programming as the means to an end for this optimisation problem.

That said, there are still more important decisions to be made on how the constraints are expressed to the solver. Being able to create an effective model in constraint programming can mean the difference between finding a solution quickly and finding no solution in days. The use of global constraints often facilitates effective constraint modelling in such scenarios. There is a fairly extensive catalogue of global constraints which vary by solver, some of the common ones include

All different, assert that all of the provided values are unique
No overlap 2d, given an array of values (x, y, width, height), interpret them as rectangles and assert that they do not overlap
Network flow, given a graph $G(V, E)$, solve for the network flow that satisfies a net flow for each vertex $v$, subject to capacities for each edge $e$

You get the idea.

I ended up exploring two fairly orthogonal approaches.

Treat conveyors as a stuck-together rectangles and primarily use No overlap 2d to enforce no collisions between factory buildings and conveyors. This approach worked better.
Treat conveyors as edges in a graph and primarily use Network flow to solve for a flavour of the multi-commodity flow problem. This approach worked terribly.

Going with the first option, we need to make a make a minor concession which is to assume a maximum number of turns a conveyor can take. If we do not cap this number (or let it be very large), then we end up with a large number of rectangles that we need to model, which increases the model complexity and makes it hard to solve. Here, we cap it to 3 segments (2 turns).

Due to practical reasons in the game, we want to have a fixed size in the $Y$ axis we want avoid exceeding, so we are primarily optimising to minimise the width of the design. While it may be alluring to set the solver objective as the maximum $X$ coordinate of any factory element, a related proxy objective of the sum of all conveyor lengths proved to be a far more effective constraint. This was unintuitive, but I believe the reason to be that the latter constraint facilitated more aggressive pruning of the search. In some sense, the former objective is also more sparse, so there is less “signal” from the objective being propagated to the variables that the solver is trying to make decisions on, leading to less efficient search.

Results

HC Valley Battery¹

The HC Valley Battery is an item that can be created using factories. In my experimentation, it was the largest design that the solver was willing to produce a solution for. Smaller designs were largely trivial.

However, despite thousands of CPU hours and tens of dollars in compute credits being spent, there was no definitive optimal design that was generated, though that’s not to say we didn’t get some very space efficient designs in the end.

Efforts were also made to simplify the model to improve solvability. Such efforts included assuming that the first column of factory buildings would only be in that position (i.e., the 10 buildings on the left can only permute amongst themselves and not move off that column).

In this example, we can see that the objective to minimise the length of the conveyors could possibly be doing us a disservice when it comes to minimising floor space. Adjusting the model to be more stringent on the dimensions in the first place, we manage to push the dimensions of the design down even further.

In the floor plans, the electric pylons were omitted to help simplify the model. Shuffling buildings around and fitting them back in likely costs little to no extra space. ↩