Algorithm for finding the best routes for food distribution in game
- by Tautrimas
Hello,
I'm designing a city building game and got into a problem.
Imagine Sierra's Caesar III game mechanics: you have many city districts with one market each. There are several granaries over the distance connected with a directed weighted graph. The difference: people (here cars) are units that form traffic jams (here goes the graph weights).
Note: in Ceasar game series, people harvested food and stockpiled it in several big granaries, whereas many markets (small shops) took food from the granaries and delivered it to the citizens.
The task: tell each district where they should be getting their food from while taking least time and minimizing congestions on the city's roads.
Map example
Sample diagram
Suppose that yellow districts need 7, 7 and 4 apples accordingly.
Bluish granaries have 7 and 11 apples accordingly.
Suppose edges weights to be proportional to their length. Then, the solution should be something like the gray numbers indicated on the edges. Eg, first district gets 4 apples from the 1st and 3 apples from the 2nd granary, while the last district gets 4 apples from only the 2nd granary.
Here, vertical roads are first occupied to the max, and then the remaining workers are sent to the diagonal paths.
Question
What practical and very fast algorithm should I use? I was looking at some papers (Congestion Games: Optimization in Competition etc.) describing congestion games, but could not get the big picture.
Any help is very appreciated!
P. S. I can post very little links and no images because of new user restriction.
