Calculating the fastest strategy in OGame

Question

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<Resource, Double> initialResources = new EnumMap<>(Resource.class);
        initialResources.put(METAL, 500d);
        initialResources.put(CRYSTAL, 500d);

        initialPlayerSnapshot.initializeResources(initialResources);

        //TODO currently it checks for metal mine level, later check for Small Cargo 1
        Predicate<PlayerSnapshot> successPredicate = playerSnapshot -> (playerSnapshot.getBuildingLevel(METAL_MINE) == 5);

        Planner planner = new Planner(initialPlayerSnapshot, successPredicate);
        PlayerSnapshot earliestPlayerSnapshot = planner.plan();

        System.out.println("Time elapsed: " + earliestPlayerSnapshot.getTime() + " seconds");
        System.out.println("---");
        for (Resource resource : Resource.values()) {
            System.out.println(resource + ": " + earliestPlayerSnapshot.getResourceAmount(resource));
        }
        System.out.println("---");
        earliestPlayerSnapshot.getPerformedActions().forEach(System.out::println);
    }

    public static void main(String[] args) {
        new OGamePlannerMain().run();
    }
}

---

public class Planner {
    private final PlayerSnapshot initialPlayerSnapshot;
    private Predicate<PlayerSnapshot> successPredicate;

    public Planner(PlayerSnapshot initialPlayerSnapshot, Predicate<PlayerSnapshot> successPredicate) {
        this.initialPlayerSnapshot = initialPlayerSnapshot;
        this.successPredicate = successPredicate;
    }

    public PlayerSnapshot plan() {
        PlayerSnapshot earliestMatchingPlayerSnapshot = null;

        if (successPredicate.test(initialPlayerSnapshot)) {
            return initialPlayerSnapshot;
        }

        PriorityQueue<PlayerSnapshot> queue = new PriorityQueue<>(Comparator.comparingLong(PlayerSnapshot::getTime));
        queue.add(initialPlayerSnapshot);
        while (!queue.isEmpty()) {
            PlayerSnapshot playerSnapshot = queue.poll();
            if (earliestMatchingPlayerSnapshot != null && playerSnapshot.getTime() >= earliestMatchingPlayerSnapshot.getTime()) {
                continue;
            }

            for (Action action : playerSnapshot.generateActions()) {
                if (action.isAllowed(playerSnapshot)) {
                    PlayerSnapshot resultingPlayerSnapshot = action.performAction(playerSnapshot);
                    if (successPredicate.test(resultingPlayerSnapshot)) {
                        if (earliestMatchingPlayerSnapshot == null) {
                            earliestMatchingPlayerSnapshot = resultingPlayerSnapshot;
                        } else {
                            if (resultingPlayerSnapshot.getTime() < earliestMatchingPlayerSnapshot.getTime()) {
                                earliestMatchingPlayerSnapshot = resultingPlayerSnapshot;
                            }
                        }
                    } else {
                        queue.add(resultingPlayerSnapshot);
                    }
                }
            }
        }

        return earliestMatchingPlayerSnapshot;
    }
}

---

public class PlayerSnapshot {
    private final ServerSettings serverSettings;

    private final List<Action> performedActions = new ArrayList<>();

    private long time = 0;

    private final EnumMap<Resource, Double> resources = new EnumMap<>(Resource.class);
    private final EnumMap<Building, Integer> buildings = new EnumMap<>(Building.class);
    private final EnumMap<Research, Integer> researches = new EnumMap<>(Research.class);
    private final EnumMap<Ship, Integer> ships = new EnumMap<>(Ship.class);

    private Building buildingInProgress = null;

    public PlayerSnapshot(ServerSettings serverSettings) {
        this.serverSettings = serverSettings;

        for (Resource resource : Resource.values()) {
            resources.put(resource, 0d);
        }

        for (Building building : Building.values()) {
            buildings.put(building, 0);
        }

        for (Research research : Research.values()) {
            researches.put(research, 0);
        }

        for (Ship ship : Ship.values()) {
            ships.put(ship, 0);
        }
    }

    public ServerSettings getServerSettings() {
        return serverSettings;
    }

    public List<Action> getPerformedActions() {
        return performedActions;
    }

    public long getTime() {
        return time;
    }

    public double getResourceAmount(Resource resource) {
        return resources.getOrDefault(resource, 0d);
    }

    public int getBuildingLevel(Building building) {
        return buildings.getOrDefault(building, 0);
    }

    public int getResearchLevel(Research research) {
        return researches.getOrDefault(research, 0);
    }

    public int getShipAmount(Ship ship) {
        return ships.getOrDefault(ship, 0);
    }

    public void initializeResources(Map<Resource, Double> resources) {
        this.resources.putAll(resources);
    }

    public void initializeBuildings(Map<Building, Integer> buildings) {
        this.buildings.putAll(buildings);
    }

    public void initializeResearches(Map<Research, Integer> researches) {
        this.researches.putAll(researches);
    }

    public void initializeShips(Map<Ship, Integer> ships) {
        this.ships.putAll(ships);
    }

    public List<Action> generateActions() {
        List<Action> actions = new ArrayList<>();
        addBuildingActions(actions);
        //TODO add actions for other things too
        return actions;
    }

    private void addBuildingActions(List<Action> actions) {
        if (buildingInProgress == null) {
            buildings.forEach((building, level) -> {
                if (building.satisfiesRequirements(this)) {
                    ActionCost upgradeCost = building.getUpgradeCost(this);
                    if (satisfiesResourcesCost(upgradeCost)) {
                        actions.add(new StartUpgradeBuildingAction(building));
                    }
                    else {
                        actions.add(new WaitForBuildingAction(building));
                    }
                }
            });
        }
        else {
            //TODO generate all possible actions for that building (including DM usage)
            Action finishBuildingAction = new FinishUpgradeBuildingAction(buildingInProgress);
            if (finishBuildingAction.isAllowed(this)) {
                actions.add(finishBuildingAction);
            }
        }
    }

    public PlayerSnapshot copyForNewAction(Action performedAction) {
        PlayerSnapshot playerSnapshot = new PlayerSnapshot(serverSettings);
        playerSnapshot.performedActions.addAll(performedActions);
        playerSnapshot.performedActions.add(performedAction);
        playerSnapshot.time = time; //TODO maybe related ActionCost to Action and add it at this point?
        playerSnapshot.resources.putAll(resources);
        playerSnapshot.buildings.putAll(buildings);
        playerSnapshot.researches.putAll(researches);
        playerSnapshot.ships.putAll(ships);
        return playerSnapshot;
    }

    public boolean satisfiesResourcesCost(ActionCost actionCost) {
        if ((int)Math.floor(getResourceAmount(METAL)) < actionCost.getMetal()) {
            return false;
        }
        if ((int)Math.floor(getResourceAmount(CRYSTAL)) < actionCost.getCrystal()) {
            return false;
        }
        if ((int)Math.floor(getResourceAmount(DEUTERIUM)) < actionCost.getDeuterium()) {
            return false;
        }
        if ((int)Math.floor(getResourceAmount(DARK_MATTER)) < actionCost.getDarkMatter()) {
            return false;
        }
        return true;
    }

    private void addCost(ActionCost actionCost) {
        addTimeCost(actionCost);
        addResourcesCost(actionCost);
    }

    private void addTimeCost(ActionCost actionCost) {
        time += actionCost.getTime();

        double metalProduction = METAL_MINE.getHourlyResourceProduction(this) / 3600d;
        double crystalProduction = CRYSTAL_MINE.getHourlyResourceProduction(this) / 3600d;
        double deuteriumProduction = DEUTERIUM_SYNTHESIZER.getHourlyResourceProduction(this) / 3600d;

        //TODO create better system to add resources
        resources.merge(METAL, metalProduction * actionCost.getTime(), (amount, production) -> amount + production);
        resources.merge(CRYSTAL, crystalProduction * actionCost.getTime(), (amount, production) -> amount + production);
        resources.merge(DEUTERIUM, deuteriumProduction * actionCost.getTime(), (amount, production) -> amount + production);
    }

    private void addResourcesCost(ActionCost actionCost) {
        resources.merge(METAL, actionCost.getMetal() * 1d, (amount, cost) -> amount - cost);
        resources.merge(CRYSTAL, actionCost.getCrystal() * 1d, (amount, cost) -> amount - cost);
        resources.merge(DEUTERIUM, actionCost.getDeuterium() * 1d, (amount, cost) -> amount - cost);
        resources.merge(DARK_MATTER, actionCost.getDarkMatter() * 1d, (amount, cost) -> amount - cost);
    }

    public void wait(ActionCost actionCost) {
        addTimeCost(actionCost);
    }

    public void startUpgradeBuilding(Building building) {
        addResourcesCost(building.getUpgradeCost(this));
        buildingInProgress = building;
    }

    public void finishUpgradeBuilding(Building building) {
        addTimeCost(building.getUpgradeCost(this));
        buildings.merge(building, 1, (currentLevel, newLevels) -> currentLevel + newLevels);
        buildingInProgress = null;
    }

    public boolean isCurrentlyUpgradingBuilding(Building building) {
        return (buildingInProgress == building);
    }
}

---

public class ServerSettings {
    private final int economySpeed;
    private final int fleetSpeed;

    public ServerSettings(int economySpeed, int fleetSpeed) {
        this.economySpeed = economySpeed;
        this.fleetSpeed = fleetSpeed;
    }

    public int getEconomySpeed() {
        return economySpeed;
    }

    public int getFleetSpeed() {
        return fleetSpeed;
    }
}

---

public enum Building implements GameObject {
    METAL_MINE {
        @Override
        public ActionCost getUpgradeCost(PlayerSnapshot playerSnapshot) {
            int currentLevel = playerSnapshot.getBuildingLevel(this);
            int metalCost = (int)Math.floor(60 * Math.pow(1.5d, currentLevel));
            int crystalCost = (int)Math.floor(15 * Math.pow(1.5d, currentLevel));
            long time = calculateTime(metalCost, crystalCost, playerSnapshot);
            return new ActionCost(time, metalCost, crystalCost, 0, 0);
        }

        @Override
        public int getEnergyCost(PlayerSnapshot playerSnapshot) {
            int currentLevel = playerSnapshot.getBuildingLevel(this);
            return (int)Math.ceil(10 * currentLevel * Math.pow(1.1d, currentLevel));
        }

        @Override
        public double getHourlyResourceProduction(PlayerSnapshot playerSnapshot) {
            int metalMineLevel = playerSnapshot.getBuildingLevel(METAL_MINE);
            int economySpeed = playerSnapshot.getServerSettings().getEconomySpeed();
            return (30d + (30d * metalMineLevel * Math.pow(1.1d, metalMineLevel) * calculateEnergyModifier(playerSnapshot))) * economySpeed;
        }
    },
    CRYSTAL_MINE {
        @Override
        public ActionCost getUpgradeCost(PlayerSnapshot playerSnapshot) {
            int currentLevel = playerSnapshot.getBuildingLevel(this);
            int metalCost = (int)Math.floor(48 * Math.pow(1.6d, currentLevel));
            int crystalCost = (int)Math.floor(24 * Math.pow(1.6d, currentLevel));
            long time = calculateTime(metalCost, crystalCost, playerSnapshot);
            return new ActionCost(time, metalCost, crystalCost, 0, 0);
        }

        @Override
        public int getEnergyCost(PlayerSnapshot playerSnapshot) {
            int currentLevel = playerSnapshot.getBuildingLevel(this);
            return (int)Math.ceil(10 * currentLevel * Math.pow(1.1d, currentLevel));
        }

        @Override
        public double getHourlyResourceProduction(PlayerSnapshot playerSnapshot) {
            int crystalMineLevel = playerSnapshot.getBuildingLevel(CRYSTAL_MINE);
            int economySpeed = playerSnapshot.getServerSettings().getEconomySpeed();
            return (15d + (20d * crystalMineLevel * Math.pow(1.1d, crystalMineLevel) * calculateEnergyModifier(playerSnapshot))) * economySpeed;
        }
    },
    DEUTERIUM_SYNTHESIZER {
        @Override
        public ActionCost getUpgradeCost(PlayerSnapshot playerSnapshot) {
            int currentLevel = playerSnapshot.getBuildingLevel(this);
            int metalCost = (int)Math.floor(225 * Math.pow(1.5d, currentLevel));
            int crystalCost = (int)Math.floor(75 * Math.pow(1.5d, currentLevel));
            long time = calculateTime(metalCost, crystalCost, playerSnapshot);
            return new ActionCost(time, metalCost, crystalCost, 0, 0);
        }

        @Override
        public int getEnergyCost(PlayerSnapshot playerSnapshot) {
            int currentLevel = playerSnapshot.getBuildingLevel(this);
            return (int)Math.ceil(20 * currentLevel * Math.pow(1.1d, currentLevel));
        }

        @Override
        public double getHourlyResourceProduction(PlayerSnapshot playerSnapshot) {
            return 0d;  //TODO implement this later, depends on planet temperature too
        }
    },
    SOLAR_PLANT {
        @Override
        public ActionCost getUpgradeCost(PlayerSnapshot playerSnapshot) {
            int currentLevel = playerSnapshot.getBuildingLevel(this);
            int metalCost = (int)Math.floor(75 * Math.pow(1.5d, currentLevel));
            int crystalCost = (int)Math.floor(30 * Math.pow(1.5d, currentLevel));
            long time = calculateTime(metalCost, crystalCost, playerSnapshot);
            return new ActionCost(time, metalCost, crystalCost, 0, 0);
        }

        @Override
        public int getEnergyCost(PlayerSnapshot playerSnapshot) {
            int currentLevel = playerSnapshot.getBuildingLevel(this);
            return -(int)Math.ceil(20 * currentLevel * Math.pow(1.1d, currentLevel));
        }

        @Override
        public double getHourlyResourceProduction(PlayerSnapshot playerSnapshot) {
            return 0d;
        }
    },
    ROBOTICS_FACTORY {
        @Override
        public ActionCost getUpgradeCost(PlayerSnapshot playerSnapshot) {
            int currentLevel = playerSnapshot.getBuildingLevel(this);
            int metalCost = (int)Math.floor(400 * Math.pow(2d, currentLevel));
            int crystalCost = (int)Math.floor(120 * Math.pow(2d, currentLevel));
            int deuteriumCost = (int)Math.floor(200 * Math.pow(2d, currentLevel));
            long time = calculateTime(metalCost, crystalCost, playerSnapshot);
            return new ActionCost(time, metalCost, crystalCost, deuteriumCost, 0);
        }

        @Override
        public int getEnergyCost(PlayerSnapshot playerSnapshot) {
            return 0;
        }

        @Override
        public double getHourlyResourceProduction(PlayerSnapshot playerSnapshot) {
            return 0d;
        }
    },
    SHIPYARD(new Requirement(ROBOTICS_FACTORY, 2)) {
        @Override
        public ActionCost getUpgradeCost(PlayerSnapshot playerSnapshot) {
            int currentLevel = playerSnapshot.getBuildingLevel(this);
            int metalCost = (int)Math.floor(400 * Math.pow(2d, currentLevel));
            int crystalCost = (int)Math.floor(200 * Math.pow(2d, currentLevel));
            int deuteriumCost = (int)Math.floor(100 * Math.pow(2d, currentLevel));
            long time = calculateTime(metalCost, crystalCost, playerSnapshot);
            return new ActionCost(time, metalCost, crystalCost, deuteriumCost, 0);
        }

        @Override
        public int getEnergyCost(PlayerSnapshot playerSnapshot) {
            return 0;
        }

        @Override
        public double getHourlyResourceProduction(PlayerSnapshot playerSnapshot) {
            return 0d;
        }
    },
    RESEARCH_LAB {
        @Override
        public ActionCost getUpgradeCost(PlayerSnapshot playerSnapshot) {
            int currentLevel = playerSnapshot.getBuildingLevel(this);
            int metalCost = (int)Math.floor(200 * Math.pow(2d, currentLevel));
            int crystalCost = (int)Math.floor(400 * Math.pow(2d, currentLevel));
            int deuteriumCost = (int)Math.floor(200 * Math.pow(2d, currentLevel));
            long time = calculateTime(metalCost, crystalCost, playerSnapshot);
            return new ActionCost(time, metalCost, crystalCost, deuteriumCost, 0);
        }

        @Override
        public int getEnergyCost(PlayerSnapshot playerSnapshot) {
            return 0;
        }

        @Override
        public double getHourlyResourceProduction(PlayerSnapshot playerSnapshot) {
            return 0d;
        }
    };

    private Requirement[] requirements;

    Building(Requirement... requirements) {
        this.requirements = requirements;
    }

    @Override
    public Requirement[] getRequirements() {
        return requirements;
    }

    public abstract ActionCost getUpgradeCost(PlayerSnapshot playerSnapshot);

    public abstract int getEnergyCost(PlayerSnapshot playerSnapshot);

    public abstract double getHourlyResourceProduction(PlayerSnapshot playerSnapshot);

    public ActionCost calculateWaitCost(PlayerSnapshot playerSnapshot) {
        ActionCost upgradeCost = getUpgradeCost(playerSnapshot);

        double metalWaitHours = (upgradeCost.getMetal() - playerSnapshot.getResourceAmount(METAL)) / METAL_MINE.getHourlyResourceProduction(playerSnapshot);
        double crystalWaitHours = (upgradeCost.getCrystal() - playerSnapshot.getResourceAmount(CRYSTAL)) / CRYSTAL_MINE.getHourlyResourceProduction(playerSnapshot);
        double deuteriumWaitHours = (upgradeCost.getDeuterium() - playerSnapshot.getResourceAmount(DEUTERIUM)) / DEUTERIUM_SYNTHESIZER.getHourlyResourceProduction(playerSnapshot);

        double minimumWaitHours = 0d;
        if (upgradeCost.getMetal() > 0) {
            minimumWaitHours = Math.max(minimumWaitHours, metalWaitHours);
        }
        if (upgradeCost.getCrystal() > 0) {
            minimumWaitHours = Math.max(minimumWaitHours, crystalWaitHours);
        }
        if (upgradeCost.getDeuterium() > 0) {
            minimumWaitHours = Math.max(minimumWaitHours, deuteriumWaitHours);
        }

        long minimumWaitSeconds = (long)Math.ceil(minimumWaitHours * 3600d);
        return new ActionCost(minimumWaitSeconds, 0, 0, 0, 0);
    }

    private static double calculateEnergyModifier(PlayerSnapshot playerSnapshot) {
        int metalEnergyCost = METAL_MINE.getEnergyCost(playerSnapshot);
        int crystalEnergyCost = CRYSTAL_MINE.getEnergyCost(playerSnapshot);
        int deuteriumEnergyCost = DEUTERIUM_SYNTHESIZER.getEnergyCost(playerSnapshot);
        int solarPlantEnergyCost = SOLAR_PLANT.getEnergyCost(playerSnapshot);
        if (solarPlantEnergyCost == 0) {
            return 0d;
        }
        else {
            double energyModifier = (metalEnergyCost + crystalEnergyCost + deuteriumEnergyCost) / (-solarPlantEnergyCost * 1d);
            return Math.min(Math.max(energyModifier, 0d), 1d);
        }
    }

    public static long calculateTime(int metalCost, int crystalCost, PlayerSnapshot playerSnapshot) {
        int roboticsFactoryLevel = playerSnapshot.getBuildingLevel(ROBOTICS_FACTORY);
        int economySpeed = playerSnapshot.getServerSettings().getEconomySpeed();
        int naniteFactoryLevel = 0; //TODO add this
        double timeInHours = (metalCost + crystalCost) / (2500d * (1 + roboticsFactoryLevel) * economySpeed * Math.pow(2d, naniteFactoryLevel));
        return (long)Math.ceil(timeInHours * 3600d);
    }
}

---

public class ActionCost {
    private final long time;

    private final int metal;
    private final int crystal;
    private final int deuterium;
    private final int darkMatter;

    public ActionCost(long time, int metal, int crystal, int deuterium, int darkMatter) {
        this.time = time;
        this.metal = metal;
        this.crystal = crystal;
        this.deuterium = deuterium;
        this.darkMatter = darkMatter;
    }

    public long getTime() {
        return time;
    }

    public int getMetal() {
        return metal;
    }

    public int getCrystal() {
        return crystal;
    }

    public int getDeuterium() {
        return deuterium;
    }

    public int getDarkMatter() {
        return darkMatter;
    }
}

---

public interface Action {
    boolean isAllowed(PlayerSnapshot playerSnapshot);

    PlayerSnapshot performAction(PlayerSnapshot playerSnapshot);
}

---

public class StartUpgradeBuildingAction implements Action {
    private final Building building;

    public StartUpgradeBuildingAction(Building building) {
        this.building = building;
    }

    @Override
    public boolean isAllowed(PlayerSnapshot playerSnapshot) {
        for (Requirement requirement : building.getRequirements()) {
            if (!requirement.isSatisfied(playerSnapshot)) {
                return false;
            }
        }
        //TODO save cost here?
        ActionCost actionCost = building.getUpgradeCost(playerSnapshot);
        return playerSnapshot.satisfiesResourcesCost(actionCost);
    }

    @Override
    public PlayerSnapshot performAction(PlayerSnapshot playerSnapshot) {
        PlayerSnapshot newPlayerSnapshot = playerSnapshot.copyForNewAction(this);
        newPlayerSnapshot.startUpgradeBuilding(building);
        return newPlayerSnapshot;
    }

    @Override
    public String toString() {
        return "StartUpgradeBuildingAction(" + building + ")";
    }
}

---

public class FinishUpgradeBuildingAction implements Action {
    private final Building building;

    public FinishUpgradeBuildingAction(Building building) {
        this.building = building;
    }

    @Override
    public boolean isAllowed(PlayerSnapshot playerSnapshot) {
        return playerSnapshot.isCurrentlyUpgradingBuilding(building);
    }

    @Override
    public PlayerSnapshot performAction(PlayerSnapshot playerSnapshot) {
        PlayerSnapshot newPlayerSnapshot = playerSnapshot.copyForNewAction(this);
        newPlayerSnapshot.finishUpgradeBuilding(building);
        return newPlayerSnapshot;
    }

    @Override
    public String toString() {
        return "FinishUpgradeBuildingAction(" + building + ")";
    }
}

---

public class WaitForBuildingAction implements Action {
    private final Building building;

    public WaitForBuildingAction(Building building) {
        this.building = building;
    }

    @Override
    public boolean isAllowed(PlayerSnapshot playerSnapshot) {
        double metalHourlyProduction = METAL_MINE.getHourlyResourceProduction(playerSnapshot);
        double crystalHourlyProduction = CRYSTAL_MINE.getHourlyResourceProduction(playerSnapshot);
        double deuteriumHourlyProduction = DEUTERIUM_SYNTHESIZER.getHourlyResourceProduction(playerSnapshot);

        ActionCost upgradeCost = building.getUpgradeCost(playerSnapshot);

        double metalWaitHours = (playerSnapshot.getResourceAmount(METAL) + upgradeCost.getMetal()) / metalHourlyProduction;
        double crystalWaitHours = (playerSnapshot.getResourceAmount(CRYSTAL) + upgradeCost.getCrystal()) / crystalHourlyProduction;
        double deuteriumWaitHours = (playerSnapshot.getResourceAmount(DEUTERIUM) + upgradeCost.getDeuterium()) / deuteriumHourlyProduction;

        if (Double.isInfinite(metalWaitHours) || Double.isInfinite(crystalWaitHours) || Double.isInfinite(deuteriumWaitHours)) {
            return false;
        }
        return true;
    }

    @Override
    public PlayerSnapshot performAction(PlayerSnapshot playerSnapshot) {
        PlayerSnapshot newPlayerSnapshot = playerSnapshot.copyForNewAction(this);
        newPlayerSnapshot.wait(building.calculateWaitCost(playerSnapshot));
        return newPlayerSnapshot;
    }

    @Override
    public String toString() {
        return "WaitForBuildingAction(" + building + ")";
    }
}

---

public class Requirement {
    private final GameObject gameObject;
    private final int level;

    public Requirement(GameObject gameObject, int level) {
        this.gameObject = gameObject;
        this.level = level;
    }

    public boolean isSatisfied(PlayerSnapshot playerSnapshot) {
        if (gameObject instanceof Building) {
            int snapshotLevel = playerSnapshot.getBuildingLevel((Building)gameObject);
            return (snapshotLevel >= level);
        }
        throw new UnsupportedOperationException();
    }
}

---

public interface GameObject {
    Requirement[] getRequirements();

    default boolean satisfiesRequirements(PlayerSnapshot playerSnapshot) {
        for (Requirement requirement : getRequirements()) {
            if (!requirement.isSatisfied(playerSnapshot)) {
                return false;
            }
        }
        return true;
    }
}

---

public enum Research implements GameObject {
    ENERGY_TECHNOLOGY(new Requirement(RESEARCH_LAB, 1)),
    COMBUSTION_DRIVE(new Requirement(ENERGY_TECHNOLOGY, 1));

    private Requirement[] requirements;

    Research(Requirement... requirements) {
        this.requirements = requirements;
    }

    @Override
    public Requirement[] getRequirements() {
        return requirements;
    }
}

---

public enum Ship implements GameObject {
    SMALL_CARGO(new Requirement(SHIPYARD, 2), new Requirement(COMBUSTION_DRIVE, 1));

    private Requirement[] requirements;

    Ship(Requirement... requirements) {
        this.requirements = requirements;
    }

    @Override
    public Requirement[] getRequirements() {
        return requirements;
    }
}

The code is not intended to work with the Research and Ship classes just yet, I have only included those classes such that the code is complete.

The code is also available in my GitHub project.

Answer 1

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.

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

2. calculate net required resources (required minus current)

3. calculate how much time step 2 represents for each resource

   4. 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.

   5. 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.

Answer 2

I think you can solve the problem more easily by using a genetic approach.

You can think of the PlayerSnapshot you have there as a "Specimen" of a generation. Any action you take has certain cost and changes your "Specimen". As such it's like an "evolution".

Since you have a defined target you can define a simplistic fitness function. The easiest I can think of right now is:

$$ \text{Fitness} = \Sigma_{Buildings} (\text{CurrentBuildingLevel} - \text{TargetBuildingLevel}) - \text{TimeTaken} + \text{CurrentResources} $$

The more refined that fitness function gets the more control you will have over it by adding weights.

Off the top of my head you can define a fitness functionover the following things:

• Proximity (to the "target specimen")
• Time Elapsed
• Resources "wasted"
• Resources used
• Building-Based "profits" (Robotics factory, Research Lab, Nanite Factory, ...)

Since the structure is a little more complicated than just a few independent genomes, but you have interdependent genomes the function must also take into account what you call "requirements".

Then you can run a standard genetic approach over this. It may not yield the absolutely best results, but it should come close. You could weigh evolutions under certain circumstances (e.g. less than 50 energy specimen are more likely to "evolve" a power plant).

The interesting part to find out IMO is the weights you can include there to find optimized building paths.

Some ideas:

• Weigh resources separately and differently depending on target
• Give special boni for reaching (or toward) special buildings (Nanite Factory!)
• Add excess resources necessary to keeping defenses up

Things you need to beware:

• Research (and defenses) can be "evolved" simultaneously, but take different amounts of time. Maybe a "do nothing" evolution path makes sense here?
• Targets going over your current resource storage capacity need to take that into account