I am making a small game in Java to practice programming and came across this little issue that I can't seem to solve on my own.
In this game, I want to build a virtual shop where I can buy and sell items.
Most items can only be obtained in the game by creating them out of other items by following what I called 'recipes'. A recipe is basically just a set of items needed to create a new item. An item can have multiple recipes. The result of a recipe can be more than one instance of the new amount. I will denote recipes like so [item, item, ..., item](resulting amount).
So there are base items, which can not be created but must be obtained through other means, and there are created items which can only be obtained via one of its recipes.
I want to try and simulate supply and demand, and I came up with this property I call the 'trade amount', which is initialized to 0 for each item. The trade amount represents how much of the item is being sold or bought. If I sell X amount of an item, its trade amount goes up by X, and if I buy Y amount of an item, its trade amount goes down by Y.
Now I need to determine a price for my items.
All base items get assigned a flat value. The value and trade amount then get plugged into a function f(v, t) that spits out a price. This price is always >= 0. One property of this function is if the trade amount t is 0, then the resulting price is equal to the input value v. So if one player buys a set amount of an item, the trade amount goes down by x and the price gets closer to 0. If then another player sells the same amount of the same item, the trade amount goes back to 0, and the price jumps back up to the original value.
Now that all base items have a value, I need to calculate the values of all created items to be able to calculate their price using f. I want their value to be based on the cheapest recipe needed to create them. So I have to parse all recipes, add up all items' prices used in each recipe, and determine the minimum price of a recipe. That is the value of the created item.
I can model this setup in a graph with vertices representing items that can be traded in the shop, and the directed edges connect an item to another item that can be created from the source item. So I have a directed edge ('source -> destination'), where the source is an ingredient in one of the destination's recipes. So from this premise, I create a random directed graph of some 600-ish vertices. This graph is different every time the game loads and the generator should specifically allow cycles within the graph.
Here is an example:
Items A and B are base items with a value of 10 and 2 respectively. Their trade amounts initially are 0, so their prices are equal to their values, 10 and 2.
Item C is a created item with two recipes R1 = A, A, B and R2 = B, B, B. Now I determine R1 to be priced at 22 and R2 to be priced at 6 which is the minimum recipe price. Thus item C has a value of 6 (and initially a trade amount of 0, thus the price is also 6).
In this case, the graph would look something like (A) --> (C) <-- (B)
Up to this point, it all works beautifully and perfectly fine.
Now the problem I have appears when the price-value dependencies are cyclic.
Here are 3 types of cases I need help with:
(1) - 0 vertex cycle
Simply put, item A has a fixed price, and item B can be created from the recipe [A, B]. If the price of B gets changed, then all items created by B have to get recalculated. In this case, B is made of A and B, so I have to recalculate the price of B as well. This again triggers the recalculation of B and so on and so forth... I know the premise is weird but think of it like repainting a door (B). It is made of the same door (B) plus paint (A). I call it a 0 vertex cycle because when traversing the cycle, you pass 0 vertices to get back to where you started.
(2) - 1 vertex cycle
If we take the same items A and B from the very first example, and add item C with recipes R1=A, B and R2=D, D, D and item D with recipe R3=C. So C can be "broken down" into 3 Ds, and 3 Ds can be combined into one C. If I now lower the price of C by selling lots of it, I should also lower the price of D, since D can be made of C. But since C can be made of D as well, and assuming R2 becomes cheaper than R1, then I have to lower the price of C as well, thus again triggering the lowering of price of D and so on and so forth. This will continue until the value has converged somewhere depending on the ingredients of the recipes involved. I call it a 1 vertex cycle because when traversing the cycle, you pass only one vertex.
(3) - n vertices cycle
This is the general case, and I think if I solve this, the two specific cases above will be solved as well. If item A is made of B, B of C, C of D and so on up to item Z, which is made of A, then changing the price of one will trigger a change in the price of the next, which will trigger the price of the next and so on and so forth. This chain can be practically arbitrarily long.**
I am looking for an algorithm that can solve my problem. I want to be able to calculate all values and prices of all items with the initial trade-amount of 0. When players buy and sell items, the price-changes should propagate through the graph. I have considered modifying Dijkstra's algorithm, A*, the Bellman-Ford algorithm, and the Floyd–Warshall algorithm, but could not get a satisfying result with any of them.
Can somebody point me in the right direction?