Calculating the fastest strategy in OGame

For a game I am playing, OGame, I am trying to calculate the fastest strategy to reach a certain state in the game, relevant parts of the game for this question are:

• You can build different types of buildings.

• Buildings take time to be built.

• In particular the Metal Mine, Crystal Mine and Deuterium Synthesizer buildings grant respectively Metal, Crystal and Deuterium resources every second.

• Buildings can be upgraded.

• At higher level the mines (Metal/Crystal/Deuterium) produce more resources, but also cost more to get upgraded.

• There is a very small base Metal and Crystal production if you do not have any buildings.

• You start the game with 500 Metal and 500 Crystal.

• Metal Mine, Crystal Mine and Deuterium Synthesizer cost energy to operate, the Solar Plant building provides that energy. If your consumption is higher than your production, then your mines are less efficient.

Please note that this is a rough prototype, but by all means do write critique on it as creating rough prototypes as good as possible is also a valuable skill.

My main concern with this program is the performance, if I query it to calculate the fastest strategy for for example Metal Mine 1, or 2, or 3 or 4 then it is fast, but for Metal Mine 5 it takes forever. The problem lies in RAM usage as for Metal Mine 5 it takes at least 6 GB of RAM and this is obviously a big issue. On the other hand, I am restricted to doing a Brute-Force search as I cannot think of any good heuristic which would let me allow a more efficient algorithm.

```
public class OGamePlannerMain {
public void run() {
ServerSettings serverSettings = new ServerSettings(1, 1);
PlayerSnapshot initialPlayerSnapshot = new PlayerSnapshot(serverSettings);

EnumMap initialResources = new EnumMap<>(Resource.class);
initialResources.put(METAL, 500d);
initialResources.put(CRYSTAL, 500d);

initialPlayerSnapshot.initializeResources(initialResources);

//TODO cu

Brute force (as you have found) is never going to scale beyond very small cases.

If I were going to compute the most efficient path to a certain build state, it would go something like this:

You have a snapshot of your current position.

-
calculate total cost to get to build state (sum the difference between build costs of target versus current state).

-
calculate net required resources (required minus current)

-
calculate how much time step 2 represents for each resource

-
a. take whichever resource will take longest. Simulate building an extra production level for that resource (+1 to building level, - costs from current resources). Re calculate time. If it shortens the time required, set this as your new baseline, add the building to a list of "order to build things in", go to (1). Else, return the final "order to build things in" list.

-
b. If 4.a. resulted in energy going negative, simulate with an extra solar level. Judge the combined result.

It occurs to me that this is almost exactly how performance optimisation works. Analyse code, find the bottleneck, improve the bottleneck, repeat until satisfied with the final result.

since this is a simple greedy algorithm, it can only see 1 move ahead. You may want to look at chaining this 2,3,4 etc. moves out and picking the best of all of them to get closest to an optimal solution.

StackExchange Code Review Q#118382, answer score: 5