来自多个组的具有边界的元素的有序合并算法

Question

我正在开发一款类似于 Minecraft（红石）的 2d 游戏，其中某些操作必须在每个刻度中按照预定义的顺序执行。有多个“模块”，每个模块可以注册多个“动作”。我需要一种方法来正确地按顺序执行它们，同时又不会搞乱一切。这些模块可以由不同的开发人员制作，因此冲突应该自动解决。动作次数都是两位数，所以不需要表演。

我的想法是使用边界，您可以在其中将操作定义为执行

before

或

after

一些其他操作。

假设有一个标记为“1”的模块，如下所示，包含 3 个操作：

1.A: after START
1.B: after 1.A
1.C: after 1.B

然后你就有了另一个模块“2”，稍后添加：

2.A: after 1.B

在这种情况下，我希望订单是

• 1.A
• 1.B
• 2.A
• 1.C

这很容易理解，但是当我有两个具有相同边界的定义时，问题很快就会出现。哪一个应该优先？这实际上是这里的情况，因为

2.A

和

1.C

都有相同的界限。我考虑过在

1.B

和

1.C

的定义中添加“之前”边界，以基本上将它们“推”得更远，这将确保

2.A

位于

1.B

和

1.C

之间。

然而，这些都只是非正式的想法，我觉得类似的问题一定已经存在于某个地方，而我太笨了，找不到它。

一种完全不同的方法是以某种方式协调所有这些开发人员就预定义的顺序达成一致，这将需要对这些操作进行某种全局注册表，但我并不真正想要这样做，因为它使简单的轻量级脚本变得复杂。如果您知道如何有效地做到这一点而不使事情过于复杂，我也很高兴。

Answer 1

听起来很有趣。

我将忽略模块，因为它们似乎不会影响核心问题。它们只是一种包装机制。

您有一个操作列表，每个操作都具有“之后”和“之前”的依赖关系。这些操作必须按照不违反依赖性的顺序一一执行。为了保持通用性，我假设每个操作可以有零个或多个“之后”和零个或多个“之前”依赖项。

我还将假设一个操作不关心其依赖项或其依赖项的依赖项等中未列出的任何操作。因此，在您的示例中，是否在 2 之前运行 1.C 并不重要.A或2.A在1.C之前，只要它们都在1.B之后执行即可。

我注意到让生活变得更轻松的一件事是，如果操作 B 将 A 作为其“之前”依赖项，那么将 B 添加到 A 的“之后”依赖项也是安全的，反之亦然。因此，一旦您收集了所有开发人员列出的之后和之前的所有操作，您就可以将这些操作互连起来，以便所有之后在另一侧都有相应的之前，反之亦然。

一旦完成，您就可以使用任何没有“之后”依赖项的操作来启动输出序列。然后添加“之后”依赖项都已列出的所有操作，并继续，直到完成。

这是一些伪代码：

procedure PreprocessActions
{
  Actions is an input parameter, a set of actions to modify
  
  for each Action in Actions
  {
    for each Other in Action.Befores
    {
      add Action to Other.Afters.
    }
  }
}

procedure OrderForExecution
{
  InputActions is an input parameter, a set of actions.

  Sequenced is the return value, a list of actions.
  set Sequenced to be an empty list.

  Unprocessed is a local variable, a set of actions.
  fill Unprocessed with copies of actions in InputActions.
  execute PreprocessActions on Unprocessed.
  (If it's ok to modify the input itself, Unprocessed is not needed and
  you can execute PreprocessActions on InputActions directly.)

  Processed is a local variable, a set of actions.
  set Processed to be an empty set.

  while Unprocessed is not empty
  {
    Next is a local variable, an action.
    set Next to be any action from Unprocessed without any dependencies
      or whose dependencies are all listed in Unprocessed.
    (If none can be found, throw an exception or error or something.
      It's either a circular dependency or conflicting constraints.)

    remove Next from Unprocessed.
    add Next to Processed.
    append Next to the end of Sequenced.
  }
}

集合应该是一些可以快速插入、删除和查找的数据结构。 （例如，.Net 的 HashSet 或 C++ 的 unordered_map。）输出列表应该是有序的，并在末尾快速追加（例如，.Net 的 List 或 C++ 的向量，或者只是一个基本数组，因为大小是预先已知的） 。如果您希望即使对于不关心哪个先运行的操作也保持可预测的排序，请使用快速删除功能对一些已排序的数据集进行未处理，并按模块名称然后操作名称或类似的名称对元素进行排序（例如.Net 的 SortedSet 或 C++ 的映射） ).

算法应该以二次方的时间运行。那里可能有优化的机会，但您可能没有足够的行动值得付出努力。特别是因为我假设该列表可以预先计算一次，然后重复使用数百万次。