What algorithm to use to calculate the fastest order for the construction of buildings?

Question

For the game I play, I would like to know the fastest order for the construction of a number of buildings. The game in question is OGame, if you are familiar with it, then this is a plus, but obviously I will explain the basics of the game:

• The player has several differences resources available.
• A player can build buildings, with a maximum of one building at a time.
• Buildings have different levels, for example, Building A level 1, Building A level 2, etc.
• The cost of resources for the construction of buildings is increasing by a level.
• Buildings save time on assembly, it also increases by level.
• Some buildings create different resources, this also increases by level.
• Some buildings change their calculations so that buildings are built faster.

I clearly decided not to display the equations, since they are not straightforward and are not needed to propose an algorithm.

I decided to simulate this with the following steps:

• StartUpgradeBuildingAction . This action starts the update process by subtracting the cost from the available resources.
• FinishUpgradeBuildingAction . This action completes the update process, moving forward in time. It also creates resources.
• WaitAction . This action sends the time by X seconds and in the meantime creates resources in accordance with the production of resources.

It should be noted that the state space is infinite and can be characterized by the fact that there are several paths to the final configuration (where all the requested buildings are built), each of which may have a different time that is required and a different amount of resources that you will finish in the end. Now I'm most interested in the path (order), which is the fastest, and if there are several equal paths, then the preferred path, which costs the least.

I have already tried the following approaches:

• Width and Width Search
• Depth Search
• Iterative in-depth depth-first search
• Iterative recess A * Search
• A * Search

Unfortunately, all of these algorithms are too long or too much memory.

Since googling did not give me further guidance, I ask the following questions here:

• Is there an existing model that fits my problem? I would have thought that Business Information Systems, for example, would have already faced this type of problem.
• Is there an algorithm that gives a better solution? If so, which one?
• Is there an algorithm that gives a solution close to a better solution? If so, which one?

Any help is appreciated.

Answer 1

There is more than one algorithm that gives you the best solution for your problem. The approaches you tried are all reasonable. However, having tried A * search does not mean much, since A * search depends on a heuristic that evaluates a specific configuration (that is, it assigns a value to a combination of the amount of time passed, the number and choice of buildings built, available resources, etc.). Thanks to good heuristics, searching for A * can quickly lead you to a very good solution. The search for this heuristic requires a good knowledge of the parameters (building costs, benefits of upgrades, etc.).

However, I feel that your problem is structured in such a way that a number of build decisions can clearly outperform another series of solutions after a few steps. Let's say you build buildings A, B, and C in that order. You build each as soon as the necessary resources are available. Then you try ordering C, A, B. You will probably find that one alternative dominates the other, since 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 may have more X resources but less Y, making it difficult to compare situations. If possible, it’s good that you do not need heuristics, but you clearly see which path you should follow and which to cut off.

In any case, I would study how many steps are required until you find ways that you can reject based on this consideration. If you find them fast, it makes sense to follow the first line strategy as soon as possible and prune the branches. The first search for depth carries the risk that you will spend a lot of time exploring the lower paths.