What algorithm to use to compute the fastest order to build buildings?

Question

For a game I'm playing I would like to know the fastest order to build a number of buildings. The game in question is OGame, if you're familiar with it, then that is a plus, but obviously I will explain the basics of the game:

• The player has a number of differences resources available.
• The player can build buildings, maximum one building at a time.
• Buildings have different levels, for example Building A level 1, Building A level 2, etc.
• The resource cost to build buildings increases per level.
• Buildings cost time to build too, this also increases per level.
• Some of the buildings produce the different resources, this also increases per level.
• Some of the buildings change the calculations such that buildings get built faster.

I have explicitly chosen to not show the equations as they are not straight-forward and should not be needed to suggest an algorithm.

I have chosen to model this with the following actions:

• StartUpgradeBuildingAction: This action starts the upgrade process by subtracting the cost from the available resources.
• FinishUpgradeBuildingAction: This action finishes the upgrade process by going forward in time. This also produces resources.
• WaitAction: This action forwards the time by X seconds and meanwhile produces the resources according to the resource production.

It should be noted that the state space is infinite and can be characterized by the fact that there are multiple paths to the final configuration (where all requested buildings have been built), each possibly having a different time it takes and a different amount of resources you end up with in the end. Now I am most interested in the path (the order) that is the fastest, and if there are multiple equal paths, then the path that costs the least should be preferred.

I have already tried the following approaches:

• Breadth-First Search
• Depth-First Search
• Iterative Deepening Depth-First Search
• Iterative Deepening A* Search
• A* Search

Unfortunately all of these algorithms either take too long, or use too much memory.

As googling has not given me any further leads, I ask the following questions here:

• Is there an already existing model that matches my problem? I would think that Business Information Systems for example would have encountered this type of problem already.
• Does an algorithm exist that gives the best solution? If so, which one?
• Is there an algorithm that gives a solution that is close to the best solution? If so, which one?

Any help is appreciated.

Answer 1

There is not the one algorithm that gives you the best solution for your problem. The approaches you tried are all reasonable. However, having tried A* search doesn't mean a lot since A* search depends on a heuristic that evaluates a certain configuration (i.e. it assigns a value to the combination of the amount of time passed, number and selection of buildings built, available resources, etc.). With a good heuristic, A* search might lead you to a very good solution quickly. Finding this heuristic requires good knowledge of the parameters (costs of buildings, benefits of upgrades etc.)

However, my feeling is that your problem is structured in such a way that a series of build decisions can clearly outperform another series of decisions after a small number of steps. Lets say you build buildings A, B and C in this order. You build each one as soon as the required resources are available. Then you try the order C, A, B. You will probably find that one alternative dominates the other insofar that you have the same buildings but in one alternative you have more resources than in the other. Of course this is less likely if you have many different resources. You might have more of resource X but less of Y which makes the situations harder to compare. If it is possible, the good thing is you don't need a heuristic but you clearly see which path you should follow and which to cut off.

Anyway, I would explore how many steps it takes until you find paths that you can dismiss based on such a consideration. If you find them quick, it makes sense to follow a breadth-first strategy and prune branches as soon as possible. A depth first search bears the risk that you spend a lot of time exploring inferior paths.