Algorithm for finding the best routes for food distribution in game

Question

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

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.

Answer 1

You want to look into the Max-flow problem. Seems like in this case it is a bipartite graph, which should make things easier to visualize.

Answer 2

This is a Multi-source Multi-sink Maximum Flow Problem which can easily be converted into a simple Maximum Flow Problem by creating a super source and a super sink as described in the link. There are many efficient solutions to Maximum Flow Problems.

Answer 3

One thing you could do, which would address the incremental update problem discussed in another answer and which might also be cheaper to computer, is forget about a globally optimal solution. Let each villager participate in something like ant colony optimization.

Consider preventing the people on the bottom-right-hand yellow node in your example from squeezing out those on the far-right-hand yellow node by allowing the people at the far-right-hand yellow node to bid up the "price" of buying resources from the right-hand blue node, which would encourage some of those from the bottom-right-hand yellow node to take the slightly longer walk to the left-hand blue node.

Answer 4

I agree with Larry and mathmike, it certainly seems like this problem is a specialization of network flow.

On another note, the problem may get easier if your final algorithm finds a spanning tree for each market to its resources (granaries), consumes those resources greedily based on shortest path first, then moves onto the next resource pile.

It may help to think about it in terms of using a road to max capacity first (maximizing road efficiency), rather than trying to minimize congestion.

This goes to the root of the problem - in general, it's easier to find close to optimal solutions in graph problems and in terms of game dev, close to optimal is probably good enough.

Edit: Wanted to also point out that mathmike's link to Wikipedia also talks about Maximum Flow Problem with Vertex Capacities where each of your granaries can be thought of as vertices with finite capacity.

Answer 5

Something you have to note, is that your game is continuous. If you have a solution X at time t, and some small change occurs (e.g: the player builds another road, or one of the cities gain more population), the solution that the Max Flow algorithms give you may change drastically, but you'd probably want the solution at t+1 to be similar to X. A totally different solution at each time step is unrealistic (1 new road is built at the southern end of the map, and all routes are automatically re-calculated).

I would use some algorithm to calculate initial solution (or when a major change happens, like an earthquake destroys 25% of the roads), but most of the time only update it incrementally: meaning, define some form of valid transformation on a solution (e.g. 1 city tries to get 1 food unit from a different granary than it does now) - you try the update (simulate the expected congestion), and keep the updated solution if its better than the existing solution. Run this step N times after each game turn or some unit of time.

Its both efficient computationally (don't need to run full Max Flow every second) and will get you more realistic, smooth changes in behavior.

Answer 6

It might be more fun to have a dynamic that models a behavior resulting in a good reasonable solution, rather than finding an ideal solution to drive the behavior. Suppose you plan each trip individually. If you're a driver and you need to get from point A to point B, how would you get there? You might consider a few things:

1. I know about typical traffic conditions at this hour and I'll try to find ways around roads that are usually busy. You might model this as an averaged traffic value at different times, as the motorists don't necessarily have perfect information about the current traffic, but may learn and identify trends over time.

2. I don't like long, confusing routes with a lot of turns. When planning a trip, you might penalize those with many edges.

3. If speed limits and traffic lights are included in your model, I'd want to avoid long stretches with low speed limits and/or a lot of traffic lights. I'd prefer freeways or highways for longer trips, even if they have more traffic.

There may be other interesting dynamics that evolve from considering the problem behaviorally rather than as a pure optimization. In real life, traffic rarely converges on optimal solutions, so a big part of the challenge in transportation engineering is coming up with incentives, penalties and designs that encourage a better solution from the natural dynamics playing out in the drivers' decisions.