Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have the following simple game logic.

You start with G gold and 0 experience at Time = 0 minutes. There are different types of houses what you can build, each with his own properties.

House A which cost Pa gold, in every Ma minutes gives Ga gold and XPa experience

House B which cost Pb gold, in every Mb minutes gives Gb gold and XPb experience

House C which cost Pc gold, in every Mc minutes gives Gc gold and XPc experience

Could you please give me an advice on how to approach a general solution for minimizing the minutes needed for reaching an arbitrary goal of XP.

share|cite|improve this question
When can you build? Anytime you have the money? – Jan Dvorak Jan 17 '13 at 11:49
Yes. And you can build multiple houses in one minute if you have enough gold. – user58590 Jan 17 '13 at 11:55
The time and earnings are continuous or quantised to minutes? – Jan Dvorak Jan 17 '13 at 12:00
Is quantised to minutes. For example if you build a House A at Time = 0 and Ma is 3 minutes then you get Ga and XPa at Time = 3, 6, 9 ....minutes – user58590 Jan 17 '13 at 12:20
At the beginning of every new turn (minute) the income from the current buildings is calculated and is added to the gold quantity remained from previous turn to get the current gold. If current gold is enough you can buy new building at the end of turn. – user58590 Jan 17 '13 at 12:37
up vote 3 down vote accepted

You could search the state space:

The state is defined by the time it is, the amount of XP you have, the amount of money you have, and the set of houses built.

If a house does not produce money and XP continuously / each turn, then the phase of each building is also a part of the state. For the sake of simplicity, assume that houses that differ only by phase are different houses (that can only be built on certain turns).

The initial state is {time $0$, $0$ XP, $G$ gold, no houses}.

The goal is a state with $state.xp \ge goal$.

Possible state transitions are: build a house (costs no time), wait some time $t$ (costs time).

Building a house is a discrete event, so there's no problem from graph-theoretical point of view, but there if the time isn't quantised, there is an infinite number of ways you can wait some time, so define that you can only wait for something, and merge the wait with the following event.

Then the state transitions are: Build a house immediately (only possible at start), wait for the money to build a house, then build the house (results in having 0 cash in case of continuous time and income), wait for the XP (only viable if you can't build a house sooner, reaches the goal state).

Pruning: A state is weakly better (strictly better or equal) than another state if it has just as many houses of each kind, just as much gold, just as much XP and doesn't happen later.

Search: Dijkstra's algorithm or A* with pruning: do not explore a state if a strictly better state is reachable.

A* heuristic: I can't think of any non-trivial admissible heuristic right now, so stick to Dijkstra.

Unrealistic condition considerations: This algorithm will work with houses that generate zero or negative XP gain. This algorithm wil work with houses that generate zero or negative cash gain. Additionally, there's a trivial optimal heuristic for states with zero or negative cash and zero or negative income.

If there is a house with negative or zero cost and non-negative XP gain, the problem is trivial. If there is a house with negative cost and non-positive XP gain, the problem may be trivial or the house may be useless (or neither). The trivial cases should be easy to detect.

If there is a house with negative or zero cost and the problem is not trivial, this algorithm will not terminate unless you add artificial constraints or an admissible heuristic to prevent exploring the states that consider "buying" an infinite number of useless houses.

share|cite|improve this answer
All values are positive. – user58590 Jan 17 '13 at 12:57
@user58590 then ignore the last heading. – Jan Dvorak Jan 17 '13 at 13:00
When you buy a house, the result is not having 0 cash. Is Current cash minus house price. For example. T= 0, G = 2000, House A Pa = 1900. – user58590 Jan 17 '13 at 13:05
@user58590 "results in having 0 cash in case of continuous time". You don't have continuous time. Aditionally, this clause only applies if you did wait for the money - your example is handled by the first clause (initial spending) – Jan Dvorak Jan 17 '13 at 13:05
@user58590 if you wait to buy something, buy it and you still have money, then you could have bought it sooner. – Jan Dvorak Jan 17 '13 at 13:08

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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