1
$\begingroup$

I am trying to optimize a building layout in a game, and it seems like the problem could be solved by a computer much quicker than by my own trial and error. However, I only have a cursory understanding of programming (mostly JavaScript), so I'm hoping some software exists which can do most of the work for me, or some open-source code is available that does something similar enough to be adapted to my purpose without too much difficulty.

I tried searching for programs/code related to graph theory, as the node-and-link nature of the game's building layout seems connected to graph theory, but I wasn't able to find anything. Most results were about drawing graphs or analyzing the properties of known graphs, rather than finding a graph with the desired properties. I also tried more general searches with no luck.

The Problem To Which I Want To Find An Optimal Solution

We have a finite square lattice of 248 nodes, each of which can only be linked to its immediate neighbors (up to four Links total per node, fewer at the boundaries of the grid). Each node can contain a Workshop, contain a Module, or be empty. There is an additional special blocked node at the center of the grid which cannot contain a Workshop or Module, and to which all non-empty nodes must be connected by a path of Links through other nodes. A picture of the grid of nodes and possible Links is included below.

There are finite numbers of Workshops (12), Modules (48), and Links (120) available. There are five different types of Workshops (the total of 12 can consist of any combination of the 5 types) and six different types of Modules (the total of 48 can consist of any combination of the 6 types).

The challenge is to get all Workshops up to maximum efficiency given the limited numbers of Modules, Links, and nodes. I want to be able to input any desired mix of Workshop types (for anywhere between 1 and 12 Workshops in total) and have the computer calculate the layout of Workshops, Modules, and Links that satisfies all requirements using the minimum possible number of Modules and Links, OR, if such a layout is impossible, calculate the layout that comes closest to satisfying all requirements.

Layout Requirements

Each type of Workshop requires three types of Modules nearby, with varying strength depending on Workshop type, for full productivity. The strength of a Module's effect decreases linearly with distance: at a distance of one Link the strength is 5 Module-strength-points (MSP), at two Links it is 4 MSP, at three Links it is 3 MSP, at four Links it is 2 MSP, at five Links it is 1 MSP, and at six Links or farther it is 0 MSP. The required minimum MSP from each Module varies with the type of Workshop; values are given below.

Workshops and Modules both produce heat (except the Radiator Module, which produces cooling or "negative heat"), and Workshops must be in a specific temperature range to function; values are given below. The magnitude of the temperature effect of a Workshop or Module decreases by 2° per Link from one to five Links, then drops to zero at six Links or farther. For example, the Solar Cells Module increases a Workshop's temperature by 10° at a distance of one Link, 8° at a distance of two Links, 6° at a distance of three Links, 4° at a distance of five Links, and 0° for any greater distance.

The effects (including temperature) of Workshops and Modules only travel across empty nodes to which they are linked. A node with a Workshop or Module on it will block the effects of any Workshops or Modules beyond it. The central node also blocks effects, but has no effect or heat itself. A Workshop always spreads only its base heat level to other linked Workshops, even if nearby Modules/Workshops are raising or lowering its effective heat level. The requirement that all non-empty nodes be connected to the central node is not blocked by other Modules/Workshops, so the connection can pass through occupied nodes.

Module effects and heat travel along the shortest available path of Links through empty nodes to each separate Workshop, so if a direct path is blocked but a less-direct path is available, the less-direct path will be used. If more than one free path to the same Workshop is available, the shortest one is used for calculations. Even if more than one free path of the same length is available, only one counts (buildings only affect each Workshop once). One Module can affect many Workshops, so for maximum efficiency, Modules should be shared by multiple Workshops when possible. Effects/heat from multiple Modules/Workshops can travel down a single Link, so branching Link paths allow many more than four buildings to affect a single Workshop despite each individual node only allowing up to four Links.

How a Layout is Graded

A Workshop on its own, with no Modules and within its required temperature range, has a productivity of 10. With all Module-strength-point requirements fully satisfied, a Workshop has a productivity of 80, or the base 10 productivity-points plus 70 bonus productivity-points. Each Workshop requires a total of 21 Module-strength-points, receiving 10/3 ≈ 3.33 productivity-points for each Module-strength-point up to the maximum for that Module type. There is no penalty or bonus for having higher-than-required Module-strength-points.

Workshops that are outside their required temperature range drop by levels to 75%, 50%, and finally 25% productivity as their temperature goes farther above or below the required range. I haven't figured out the exact calculation behind the penalty yet, but even 1° of deviation outside the desired range leads to a 25% loss in productivity, so maintaining the desired temperature is critical.

An optimum layout will have all temperature requirements met, and all Module-strength-point requirements met (or exceeded), for all Workshops. If meeting all the Module-strength-point requirements is impossible, the most-optimal layout will have the greatest total number of Module-strength-points (ignoring any that go over the requirement for that Module type) per Workshop.

The Construction Grid

Grid of points with potential links shown as dashed lines.

Workshop Stats

  • Workshop-Agriculture

    • Base Temp: 20°
    • Min Temp: 20°
    • Max Temp: 39°
    • Module Requirements
      • Module-Artificial-G: 6
      • Module-Solar: 3
      • Module-Greenhouse: 12
  • Workshop-Biotech

    • Base Temp: 5°
    • Min Temp: 30°
    • Max Temp: 39°
    • Module Requirements
      • Module-Artificial-G: 9
      • Module-Solar: 6
      • Module-Greenhouse: 6
  • Workshop-Electronics

    • Base Temp: 5°
    • Min Temp: 0°
    • Max Temp: 9°
    • Module Requirements
      • Module-Solar: 6
      • Module-Stowage: 6
      • Module-Recycling: 9
  • Workshop-Energy

    • Base Temp: 30°
    • Min Temp: 20°
    • Max Temp: 29°
    • Module Requirements
      • Module-Artificial-G: 3
      • Module-Solar: 15
      • Module-Stowage: 3
  • Workshop-Heavy-Industry

    • Base Temp: 30°
    • Min Temp: 20°
    • Max Temp: 29°
    • Module Requirements
      • Module-Solar: 6
      • Module-Stowage: 9
      • Module-Recycling: 6

Module Heat

  • Module-Radiator: −20°
  • Module-Solar: +10°
  • Module-Greenhouse: +2°
  • Module-Artificial-G: +6°
  • Module-Stowage: +6°
  • Module-Recycling: +8°
$\endgroup$
9
  • $\begingroup$ What is a workshop efficiency exactly? And when you want to "get all 12 Workshops up to maximum efficiency", do you mean something like the sum of their individual efficiency must be maximal? Or the sum of their efficiency squared? Or the lowest efficiency of them all must be maximalized, then the second lowest must too? Or the highest efficiency of them all must be maximalized, then the second highest must too, and so on? $\endgroup$ Commented Apr 14, 2023 at 14:50
  • $\begingroup$ @ClaudeChaunier I added more information about how efficiency is graded. $\endgroup$
    – Lawton
    Commented Apr 14, 2023 at 16:09
  • $\begingroup$ Cool. Can a module contribute to several workshops if they are at equal link-distance to it? Would the contribution be divided into equal parts? May the heat contribute to several sites too? $\endgroup$ Commented Apr 14, 2023 at 16:12
  • 1
    $\begingroup$ As an easy first solution you may try millions of random layouts in a fast enough general-purpose compiled langage and pick the most sastifying layout. Then you may add some elementary heuristics to improve on a layout. $\endgroup$ Commented Apr 14, 2023 at 16:21
  • $\begingroup$ About the requirement that every workshop and module must be linked to the central node, is it okay if the required linking paths go through non-empty nodes, unlike effects and heat that would be blocked? $\endgroup$ Commented Apr 14, 2023 at 16:56

1 Answer 1

1
$\begingroup$

That's a complex set of requirements, and I don't think I understand them all, so I'll suggest a few general approaches for this sort of problem:

One standard approach is to formulate this as an instance of integer linear programming, and use an off-the-shelf ILP solver. There are a range of techniques to map such constraints to ILP, used widely in operations research. For instance, you can introduce zero-or-one boolean variables $x_i$, one for each candidate location, indicating whether it has a link or workshop or module there, and other variables to indicate the flow of heat/module effects.

A very simple approach is to use random search.

Another somewhat better approach is to use local search, where you start with one configuration and then iteratively improve it. For instance, you could use hill climbing starting from a random configuration and repeat many times, or use simulated annealing. You'll need to define a set of simple moves to make a small change to a configuration: e.g., move a Workshop by one square (and update the links), insert a Workshop (creating Links as needed), remove a Workshop, etc.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.