树算法

Question

我今天早些时候在想一个小游戏的想法，并且偶然发现了如何实现它。这个想法是，玩家可以进行一系列引起一点效果的动作，但如果以特定的顺序完成，会产生更大的效果。到目前为止这么好，我知道该怎么做。显然，我必须使它变得更加复杂（因为我们喜欢使它更加复杂），所以我认为序列可能有多条可能的路径，这两条路径都会产生更大的影响，尽管影响不同。另外，一些序列的一部分可能是其他序列的开始，甚至整​​个序列可能被其他更大的序列所包含。现在我不确定实现这一点的最佳方式。不过，我有一些想法。

1）我可以实现一个循环的n链表。但是由于动作列表永远不会结束，所以我担心它可能导致堆栈溢出。这个想法是，每个节点将有n个孩子，并在接到命令后，可能会引导你到他的一个孩子，或者如果没有孩子可用于这样的命令，则引导你回到起点。到达任何儿童时，将会执行一些功能，从而产生小而大的效果。然而，这可能会导致树上有很多重复的节点，以应对以特定动作结束的所有可能的序列，并且具有不同的效果，这可能是一种维护的痛苦，但我不确定。我从来没有尝试过这种复杂的代码，只是在理论上。这个算法是否存在并且有一个名字？这是个好主意吗？

2）我可以实现一个状态机。然后，而不是在一个链表中漫游，我会有一个巨大的嵌套开关，可以调用函数并相应地更新机器状态。看起来实施起来更简单，但是......好吧......看起来并不有趣......也不是很美丽。巨型开关对我来说总是显得很丑，但是这样做会更好吗？

3）建议？我很好，但我很缺乏经验。编码领域的好处是，不管你的问题有多怪，有人在过去解决它，但你必须知道在哪里寻找。有人可能比我有更好的想法，我真的很想听听建议。

Answer 1

我并不完全确定，我完全理解你在说什么，但作为一个不和谐的情况，说某人在键盘上输入了无穷无尽的数字流。 '117'是一个魔法序列，'468'是另一个，'411799'是另一个（包含第一个）。

因此，如果用户输入：

你想火 '神奇事件' 在* S：

55468 * 4117 * 99 *

或类似的东西，对吧？如果这是analagous给你谈论，那么关于类似的信息（类似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! 
    } 
} 

Answer 2

您所描述的内容听起来与游戏中的科技树非常相似。

我不知道文明作者是如何构建他们的，但我倾向于用多图表示可能的“动作” - 会有一些你可以从没有“体验”开始，一旦你'他们在里面，会有多条路径到最后。

绘制出什么潜在的选择，你可以在游戏中的每一个阶段，然后画线，从一些选项给别人去。

这应该给你实现一个开始，因为图是[比较]易概念来实施和利用。

Answer 3

你可能仍要实现状态机，但你不必硬编码状态转换。
尽量让状态，其中状态A之间的状态B的链接将意味着可能导致B.
然后你就可以在运行时遍历图形寻找到的球员去的图表。

编辑：您可以定义图形节点：
-state-ID链接到其他国家
-list， 其中的每一个环节定义：
-state-ID
-precondition，状态的列表什么是必须临睡前这种状态

Answer 4

参观听起来像一个neural network。你可以创建一个并训练它来识别导致你正在寻找的各种效果的模式。

Answer 5

您所描述的内容听起来有些类似于依赖图或字图。你可以看看那些。

Answer 6

创建一个小的状态机每个你想要的效果。在每个用户动作中，将其“广播”给所有状态机。大多数人不会在乎，但有些人会前进，或者倒退。当他们中的一个达到目标时，产生期望的效果。

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

编辑：看来考恩的建议是等同于这一点，但他自己最优化状态机仅表达简单的序列。对于你的具体问题来说似乎已经足够了，但是更复杂的条件可能需要更通用的解决方案

Answer 7

@Cowan，@Javier：不错的主意，如果我加入它，介意吗？

让MagicSequence对象听的用户输入的输入流，即通知他们的输入（广播）的，并让他们每个人的输入添加到有内部输入流。当输入不是模式中预期的下一个输入时，该流将被清除，MagicSequence将触发其操作。一旦模式完成，就开始动作并清除内部输入流。仅通过供给输入到正在等待它的MagicSequences

优化此。这可以通过两种方式：

1. 你有一个对象，让所有MagicSequences与在他们的模式的数字对应的事件连接。 MagicSequence（1,1,7）将添加本身GOT1和got7，例如：

   UserInput.got1 + = MagicSequnece [i]中。SendMeInput;

2. 您可以对此进行优化，使得在每次输入MagicSequences注销无效事件并注册有效的事件之后。