寻找游戏中食物分配最佳路线的算法
我正在设计一款城市建设游戏，但遇到了一个问题。
想象一下 Sierra 的凯撒 III 游戏机制：你有许多城区，每个城区都有一个市场。远处有几个粮仓通过有向加权图相连。区别：人（这里是汽车）是形成交通拥堵的单位（这里是图表权重）。
注：在《凯撒》游戏系列中，人们收获食物并将其储存在几个大粮仓中，而许多市场（小商店）则从粮仓中取出食物并将其运送给市民。
任务：告诉每个地区他们应该从哪里获取食物，同时花费最少的时间并最大限度地减少城市道路的拥堵。
地图示例
假设黄色区相应需要 7 个、7 个和 4 个苹果。 蓝色粮仓相应有 7 个和 11 个苹果。
假设边的权重与其长度成正比。那么，解决方案应该类似于边缘上指示的灰色数字。例如，第一个区从第一个粮仓获取 4 个苹果，从第二个粮仓获取 3 个苹果，而最后一个区仅从第二个粮仓获取 4 个苹果。
在这里，垂直道路首先被最大限度地占用，然后剩余的工人被发送到对角线路径。
问题
我应该使用什么实用且非常快速的算法？我正在查看一些描述拥塞游戏的论文（拥塞游戏：竞争中的优化等），但无法了解全局。
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
您想要研究最大流量问题。看起来在这种情况下它是一个二部图，这应该使事情更容易可视化。
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.
这是一个多源多汇最大流量问题，可以通过创建超级源和超级汇，可以轻松地将其转换为简单的最大流问题，如链接中所述。对于最大流量问题，有许多有效的解决方案。
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.
您可以做的一件事是忘记全局最优解决方案，这可以解决另一个答案中讨论的增量更新问题，并且对计算机来说也可能更便宜。让每个村民参与蚁群优化之类的事情。
考虑通过允许最右侧黄色节点的人们抬高从右侧蓝色节点购买资源，这将鼓励一些来自右下黄色节点的人采取稍长的步行到左侧蓝色节点。
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.
我同意 Larry 和 mathmike 的观点，这个问题显然是网络流的特殊化。
另一方面，如果您的最终算法为每个市场找到其资源（粮仓）的生成树，首先基于最短路径贪婪地消耗这些资源，然后移动到下一个资源堆，那么问题可能会变得更容易。
首先考虑使用道路以达到最大通行能力（最大化道路效率），而不是试图尽量减少拥堵，这可能会有所帮助。
这触及了问题的根源 - 一般来说，在图问题中更容易找到接近最优的解决方案，而就游戏开发而言，接近最优可能就足够了。
编辑：还想指出，mathmike 到维基百科的链接也讨论了 顶点容量的最大流量问题< /a> 其中每个粮仓都可以被视为容量有限的顶点。
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.
你必须注意的是，你的游戏是连续的。如果您在时间 t 有一个解决方案 X，并且发生了一些小的变化（例如：玩家修建了另一条道路，或者其中一个城市获得了更多人口），则最大流算法为您提供的解决方案可能会发生巨大变化< /strong>，但你可能希望 t+1 处的解与 X 类似。每个时间步完全不同的解是不现实的（在地图南端修建了 1 条新道路，并且所有路线都在自动重新计算）。
我会使用一些算法来计算初始解决方案（或者当发生重大变化时，例如地震摧毁了 25% 的道路），但大多数时候仅增量更新：意思是，定义某种形式解决方案的有效转换（例如，1 个城市尝试从与现在不同的粮仓获取 1 个食品单位） - 您尝试更新（模拟预期的拥堵），如果更新的解决方案比现有的解决方案更好，则保留更新的解决方案。每个游戏回合或某个时间单位后运行此步骤 N 次。
它的计算效率很高（不需要每秒运行完整的最大流），并且会让您的行为发生更现实、更平滑的变化。
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.
拥有一个对行为进行建模从而产生良好合理解决方案的动态可能比寻找驱动行为的理想解决方案更有趣。假设您单独计划每次旅行。如果您是一名司机，需要从 A 点前往 B 点，您会如何到达那里？您可能会考虑以下几点：
我了解此时的典型交通状况，并且我会尝试找到绕过通常繁忙的道路的方法。您可以将其建模为不同时间的平均交通状况，因为驾车者不一定拥有有关当前交通状况的完整信息，但可能会了解并识别一段时间内的趋势。
我不喜欢漫长、混乱且有很多转弯的路线。在计划旅行时，您可能会惩罚那些有很多边缘的路线。
如果您的模型中包含速度限制和红绿灯，我希望避免低速限制和/或大量红绿灯的长距离行驶。对于长途旅行，我更喜欢高速公路或高速公路，即使它们的交通量较多。
从行为上考虑问题而不是纯粹的优化可能会产生其他有趣的动态。在现实生活中，交通很少会收敛到最佳解决方案，因此交通工程中的很大一部分挑战是提出激励、惩罚和设计，鼓励驾驶员根据自然动态做出更好的决策。
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:
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.
I don't like long, confusing routes with a lot of turns. When planning a trip, you might penalize those with many edges.
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.