复杂输送能力计算（图表）- 有趣的游戏算法

Question

我正在使用Javascript开发一个游戏，让玩家可以创建传送带。想象一下邮局，包裹进来后会在传送带上运行，被处理后最终到达卡车。这些传送带可以非常复杂，可以包含循环等等。

以下是一个相当复杂（且效率低下）的传送带示例： 带有糟糕图形的传送带示例

传送带示例图： 传送带示例

圆圈中的数字表示当前情况 - 该传送“部件”上的包裹数量。

规则：

• IN 部件生成邮政包裹并放入 Belt 组件中。
• Belt 组件将邮政包裹推到 OUT 组件。OUT 组件从图中移除包裹。
• 每个组件在任何给定时刻都有最大容量限制。
• 可以有 0 到 N 个 IN 组件（如果为 0，则可能已经有包裹在传送带上）。
• 可以有 0 到 N 个 OUT 组件（如果为 0，则表示整个传送带将变满）。
• 计算是基于时间步骤进行的，这意味着“一组包裹”每次只能前进一步。
• 每次合并都会平均分配包裹。（因此，如果有两条外向线路，则每条线路都会得到 packages/2 个包裹）
• 每次连接都会平均接受包裹。（所以如果有两条输入线路，每条线路最多可以提供 max/2 个包裹）
• 包裹没有身份，它们只是总数。
• 包裹可以被分割，所以1个包裹可以成为0.5和0.5个包裹（因此为数字类型的浮点数）。

问题：

如何快速解决这样一个图表，分两步：

1. 生成必要的数据结构/图形缓存（性能：<200ms，针对1000个元素）。实际上，只有在下一次包裹旅行计算之前设置更改后才需要重新计算。

2. 计算包裹旅行。（性能：<20ms，针对1000个元素）

一些有问题的解决方案

选项A：按组件解决。（循环每个组件并根据当前情况进行解决）不起作用，因为循环、连接、合并会导致它不能像所需的那样平均移动包裹。此外，它不遵守规则，即“包裹”只能从一个组件移动到另一个组件。根据循环顺序，可能会立即将包裹送到终点）。此外，它可能只偏爱一个输入，而另一个输入将始终被阻止。

选项B：计算每个组件想要做的事情并找到冲突（例如，A和B都想向C推送10个包裹，但C总共只能接受12个。修复错误，使A和B每人仅能移动6个，这意味着他们的库存至少为下一个周期的4个。这可能会导致更多错误，因为A和B没有清空它们的内容，它们可以接受较少的内容）。现在找到更多错误并进行修复。重复操作，直到没有错误或“达到最大重复次数”，只快速修复错误=因此实际上它不按规则预期工作。 问题在于，我认为它会对某些设置卡住并可能出错。

选项C：从“OUT”元素开始并尝试将包裹移出。如果引入循环或没有“OUT”元素的区域，则会出现问题。

结论：

我陷入了困境，甚至不知道该搜索什么，因此，欢迎所有想法 :) 我发现这是一个图形问题，但也许还有其他方法。

- Oliver Leisalu

---

如果您有一个2路合并输入到一个2路分流的情况，其中一个分支返回到合并中，会发生什么？将会在循环中捕获指数衰减的软件包碎片。您是否想要表示任意小的软件包碎片？ - user2357112

真的，对于这些非常小的包裹，我会添加硬编码的IF语句，例如如果包裹大小小于0.1，它将被丢弃并忘记。很好的发现！ - Oliver Leisalu

Answer 1

只要您不需要问题的最佳解决方案，我认为您可以这样做：

1. At the beginning, use a topological sort order of the graph, and "tag"
   each node with its position in that order so you have a criteria as to
    which node is better than others. The final node has the maximum "tag"
   (check link to learn more about topological sort, not hard)

2. Mark all nodes as not visited

3. Get the *node A* with max(tag) still not visited:

3.a. Get each *node B* that is a target from *node A* 
     (i.e. at the end of the arrow) starting from the one with maximum tag
     and finishing with the one with minimum tag:

3.a.a. push all packages from *node A* to *node B* until it is filled or 
       *node A* is empty.

你可以在https://en.wikipedia.org/wiki/Topological_sorting找到拓扑排序的定义和一些算法。

祝好运 :)

- Roberto