树算法

Question

树算法

3

我今天早些时候在思考一个小游戏的想法，并偶然发现了如何实现它。这个想法是，玩家可以进行一系列的动作，产生一些小效果，但如果按特定的顺序执行，则会产生更大的效果。到目前为止，这个我知道怎么做。显然，我必须让它变得更加复杂（因为我们喜欢让它更加复杂），所以我认为可能有不止一条可能的路径，这些路径都会导致更大的效果，尽管是不同的效果。此外，某些序列的一部分可能是其他序列的开头，甚至整个序列也可能被包含在其他更大的序列中。现在我不确定最好的实现方式。虽然我有一些想法。

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

2）我可以实现一个状态机。然后，我不必在链表中漫游，而是具有一些巨大的嵌套开关，它将调用函数并相应地更新机器状态。看起来更容易实现，但是...嗯...看起来不太好玩...也不够优雅。对我来说，巨大的开关总是看起来很丑陋，但这样做是否更有效呢？

3）有什么建议吗？我还不错，但经验不足。编码领域的好处是，无论您的问题有多奇怪，过去都有人解决了它，但您必须知道该去哪里寻找。可能有人比我提出了更好的想法，我真的想听听建议。

- Leahn Novash

1

一般而言，开始时要简单明了，后续再逐步增加复杂度。 - Toon Krijthe

7个回答

2

您可能需要实现一个状态机，但您不必硬编码状态转换。
尝试制作一个状态图，其中状态A到状态B的链接将意味着A可以导致B。
然后您可以在运行时遍历图以找到玩家去哪里。
编辑：您可以定义图节点为：
-状态ID
-到其他状态的链接列表，其中每个链接定义为：
-状态ID
-前提条件，必须访问此状态之前的状态列表

- Sergey Volegov

可能会起作用，但状态并没有被严格定义，所以我不确定。我的意思是，A-B-C可能会导致一个效果，但B-C不会。这就是为什么我在帖子中提到可能需要复制节点来处理这种情况。不过这个想法看起来不错。能详细说明一下吗？ - Leahn Novash

我该如何轻松验证前置条件？ - Leahn Novash

你只需要在栈中跟踪已经访问过的节点，然后针对最近访问过的节点检查每个前提条件。 - Sergey Volegov

我得把栈变成循环列表以避免栈溢出，但我想我们正在接近解决方案。 - Leahn Novash

1

你所描述的听起来非常类似于游戏《文明》中的科技树。

我不知道《文明》的作者是如何构建他们的，但我倾向于使用多重图来表示可能的“移动”——有些可以从零开始，一旦进入它们，就会有多条路径通向终点。

画出游戏每个阶段可能拥有的潜在选项，然后画出从某些选项到其他选项的线。

这应该可以让你开始实现了，因为图形是[相对]容易实现和利用的概念。

- warren

文明科技树是单向的，并且有一个定义好的终点（未来科技）。我的科技树必须是循环的，没有定义好的终点。虽然你可以把直线路径看作是循环的树，但在那个科技树中，你不能重复穿过同一个节点。 - Leahn Novash

1

听起来像是一个神经网络。您可以创建一个并对其进行训练，以识别导致您寻找的各种效果的模式。

- Jason Z

但那样做不是很难添加新的模式吗？ - Leahn Novash

这比它需要的要复杂得多。 - Per Alexandersson

1

你所描述的内容听起来有点类似于依赖图或单词图。你可以研究一下这些。

- user21714

看起来依赖图是个好主意，但我找不到任何关于单词图的可靠文章。你能帮我吗？ - Leahn Novash

1

为每个所需的效果创建一个小状态机。在每个用户操作时，“广播”到所有状态机。大多数状态机不会关心，但有些会前进，或者可能倒退。当其中一个达到目标时，产生所需的效果。

为了保持代码整洁，不要硬编码状态机，而是构建一个简单的数据结构来编码状态图：每个状态都是一个节点，具有一系列有趣的事件，每个事件指向下一个状态的节点。每个机器的状态只是对适当状态节点的引用。

编辑：看起来Cowan的建议等同于这个，但他优化了他的状态机，仅表达简单的序列。这对于您的特定问题似乎足够，但更复杂的条件可能需要更通用的解决方案。

- Javier

可能会有多个“下一个状态”。有什么想法吗？ - Leahn Novash

生成新机器。 - Javier

1

@Cowan，@Javier：好主意，我能加点东西吗？

让MagicSequence对象监听用户输入的传入流，通知它们输入（广播），并让它们每个人将输入添加到内部输入流中。当输入不是期望的下一个输入时，该流会被清除，如果该模式具有MagicSequence触发其操作，则尽快完成该模式，触发该操作并清除内部输入流。

通过仅向等待它的MagicSequences提供输入来优化此过程。这可以通过两种方式实现：

您可以拥有一个对象，让所有MagicSequences与其模式中对应数字相对应的事件相连。例如，MagicSequence（1,1,7）将自己添加到got1和got7中：

UserInput.got1 += MagicSequnece[i].SendMeInput;
您可以通过在每个输入后从无效事件中注销MagicSequences并注册有效事件来优化此项技术。

- malach

太好了，这是一个更优化的通用情况，只要注册/注销的开销小于仅广播的成本。当然，你也可以让信息双向流动--'Actions'可以通过与控制器'注册'新的操作来向控制器反馈信息，以'解锁'新的操作等等。 - Cowan

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Cowan · Accepted Answer

我不完全确定我是否准确理解你的意思，但类比一下，假设有人在键盘上输入无尽的数字。 '117'是一个神奇的序列，'468'是另一个，'411799'是另一个（其中包含第一个）。所以如果用户输入：

55468411799

你想在 * 处触发“魔法事件”，就像这样：

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!
  }
}