algorithm - 树算法

Question

今天早些时候，我在想一个小游戏的想法，但偶然发现了如何实现它。这个想法是，玩家可以进行一系列 Action ，这些 Action 会产生一些影响，但如果按照特定顺序进行，则会产生更大的影响。到目前为止一切顺利，我知道该怎么做。显然，我不得不让它变得更复杂(因为我们喜欢让它更复杂)，所以我认为序列可能有不止一种可能的路径，它们都会产生更大的影响，尽管是不同的。此外，某些序列的一部分可能是其他序列的开始，甚至整​​个序列可能包含在其他更大的序列中。现在我不确定实现这个的最佳方法。不过，我有一些想法。

1) 我可以实现一个循环 n 链表。但是由于移动列表永远不会结束，我担心它可能会导致堆栈溢出™。这个想法是每个节点都有 n 个子节点，并且在收到命令后，它可能会将您带到他的一个子节点，或者如果没有子节点可用于此类命令，则会将您带回起点。到达任何 child 后，将执行一些功能，从而产生或大或小的影响。不过，这可能会导致树上出现大量重复节点，以应对以具有不同效果的特定移动结束的所有可能序列，这可能很难维护，但我不确定。我从来没有在代码上尝试过这么复杂的东西，只是在理论上。这个算法是否存在并且有名字？这是个好主意吗？

2) 我可以实现一个状态机。然后，我不会在链表中徘徊，而是有一些巨大的嵌套开关，可以调用函数并相应地更新机器状态。似乎更容易实现，但是......好吧......看起来并不有趣......也不优雅。巨型开关对我来说总是很丑陋，但这会更好用吗？

3)建议？我很好，但我经验不足。编码领域的好处是，无论你的问题有多奇怪，过去都有人解决过，但你必须知道去哪里找。有人可能有比我更好的想法，我真的很想听听建议。

Answer 1

我不是绝对完全确定我完全理解你在说什么，但作为一个类似的情况，假设有人在键盘上输入无穷无尽的数字流。 '117' 是一个魔术序列，'468' 是另一个，'411799' 是另一个(包含第一个)。

所以如果用户输入:

55468411799

您想在 *s 处触发“魔法事件”:

55468*4117*99*

或者类似的东西，对吧？如果这与您正在谈论的问题类似，那么(类似 Java 的伪代码):

MagicSequence fireworks = new MagicSequence(new FireworksAction(), 1, 1, 7);
MagicSequence playMusic = new MagicSequence(new MusicAction(), 4, 6, 8);
MagicSequence fixUserADrink = new MagicSequence(new ManhattanAction(), 4, 1, 1, 7, 9, 9);

Collection<MagicSequence> sequences = ... all of the above ...;

while (true) {
  int num = readNumberFromUser();
  for (MagicSequence seq : sequences) {
    seq.handleNumber(num);
  }
}

虽然 MagicSequence 有类似的东西:

Action action = ... populated from constructor ...;
int[] sequence = ... populated from constructor ...;
int position = 0;

public void handleNumber(int num) {
  if (num == sequence[position]) {
    // They've entered the next number in the sequence
    position++;
    if (position == sequence.length) {
       // They've got it all!
       action.fire();
       position = 0; // Or disable this Sequence from accepting more numbers if it's a once-off
    }
  } else {
    position = 0; // missed a number, start again!
  }
}