游戏中的撤销/重做功能的栈实现

Question

我正在制作一个游戏，玩家可以在棋盘/网格上移动。它有moveLeft()、moveRight()、moveUp()和moveDown()方法，每次移动玩家1个空格。

我试图规划所需的撤销/重做功能的方法，以便在玩家移动时进行操作（例如，如果玩家向左移动了一个空格，并调用了Undo，则玩家将向右移动一个空格）。我是一名学生，正在研究栈。

然而，在编程之前，当我在纸上规划逻辑时（我发现这有助于我的作业），我不知道基于以下问题，是否应该使用栈。

每次调用每个移动方法时，都会将字符串“Up”、“Down”、“Left”、“Right”添加到Stack 1中，具体取决于调用的方法。这跟踪玩家在棋盘上的移动。

如果调用undo()，则从Stack 1的顶部删除字符串，并添加到一个新的堆栈“Stack 2”中。这用于跟踪“撤消”的移动，以便redo()有一个路径可以遵循。

如果调用redo()，则从Stack 2中删除字符串，并重新添加到Stack 1中。

这个方法完美地工作，但只有当您调用Redo()的次数与Undo()相同并直接在其后时才有效。

例如：

1. 玩家进行4次移动：（Stack 1现在有4个字符串） 2. 调用Undo()一次：（Stack 1现在有3个字符串，Stack 2有1个字符串） 3. 玩家再进行4次移动：（Stack 1现在有7个字符串，Stack 2仍有1个字符串） 4. 再次调用Undo()：（Stack 1现在有6个字符串，Stack 2有2个字符串） 5. 调用Redo()：（这里是问题）这可以被调用两次，因为Stack 2有2个字符串，但实际上玩家在棋盘上只能调用Redo()一次。

我已经试图孤立地解决这个逻辑问题了4个小时！任何建议都将不胜感激。即基于以上内容，是否仍然可能使用栈来实现我需要的功能，或者应该放弃，因为这是不可能的。

- javapalava

---

你必须使用 Stack 吗？还是可以使用其他东西（例如 List）？ - Dan W

看起来是个不错的方法，但也许你想在进行移动时清除重做栈，因为这样最后一次操作就不再是撤销了，这使得重做变得毫无意义。 - Kenney

@Kenney 我考虑过这个问题，但我无法找到任何逻辑来确定何时应该清除堆栈。Undo() 方法调用其中一个移动方法，因为它必须将玩家带回一个空间，所以当它们被调用时我不能清除它... - javapalava

@javapalava 1) 栈继承自Vector，它有一个clear方法。2) 只需在执行非撤销或重做操作时清除重做栈。 - Mage Xy

那么你可能需要重新考虑一下你的设计。在我看来，执行 undo() / redo 也会将该移动推入撤销堆栈中？ - Kenney

Answer 1

如果您不想使用Stacks，因为您不确定何时清除撤消Stack，则可以使用List来实现此目的。然后，您的逻辑可以以类似的方式维护：

• 保持移动的索引（从0开始，每次新移动增加1）
• 如果执行了撤消操作，则将索引减1（除非您在列表的开头）
• 如果执行了重做操作，则将索引加1（除非您在列表的末尾）
• 如果执行了新移动，则将索引增加并清除所有大于或等于索引的移动（从而清除您的撤消/重做移动）

然后，您的示例是：

1. 玩家进行了4次移动（索引为3，列表有4个项目）
2. 调用Undo()一次（索引为2，列表有4个项目）
3. 玩家再进行了4次移动（索引为6，列表有7个项目，并且所有撤消/重做项目都已清除）
4. 调用Undo()一次（索引为5，列表有7个项目）
5. 调用Redo一次（索引为6，列表有7个项目）
6. 再次调用Redo（因为没有可用的重做操作而被拒绝）

- Dan W

---

感谢@Dan - 唯一的问题是，Undo()，Redo()必须调用移动方法以移动玩家，因此每次玩家移动时所有移动都将被清除，并且索引永远无法增加到0之上。没有办法确定一个“新”的移动。 - javapalava

你可以将 MoveType 的枚举传递到你的移动方法中。它可以有 Undo，Redo 和 New 选项。然后，你的注释 move 方法可以根据你的 MoveType 采取相应的操作。 - Dan W

好的，现在我会查一下枚举是什么！ :) - javapalava

Answer 2

这样想吧.. 撤销和重做的整个概念都围绕着应用程序（程序）的状态。撤销意味着您想回到应用程序的上一个状态；同样，重做也是如此。是的，堆栈是保留先前状态的最佳解决方案。对于撤销操作，您可以执行弹出并将其推送到另一个堆栈中。使用另一个堆栈进行重做操作。 您可能希望为撤销和重做设置限制。 如何保存应用程序状态取决于您。

- Jor El

---

谢谢Jor，但这并不能帮助我解决上述问题，即Redo()重新跟踪错误的步骤...... - javapalava

Answer 3

在第三步中。

Player makes 4 more moves: (Stack 1 now has 7 strings, Stack 2 still has 1 string) 

你必须清空第二个栈。

- Pablo

---

所以，我考虑过这个问题，但是...... a) 我找不到清除堆栈的方法，更重要的是 b) 我找不到可以应用于确定何时应该清除堆栈的逻辑。Undo() 方法调用其中一个移动方法，因为它必须使玩家回到之前的空间，所以当它们被调用时我无法清除它... - javapalava

当玩家撤销三次时，将会撤回三步。如果他从这个点开始做新的移动，那么重做就没有意义了。重做移动只有在撤销后立即进行才有意义。 - Pablo

是的，但是程序无法告诉何时清空第二个堆栈 - 它无法知道。撤消（和重做）调用相同的移动方法，因此如果每次调用移动方法时都清除堆栈，则堆栈永远不会超过1 - 在每次undo / redo或任何移动方法被调用时都会被清除。 - javapalava

是的，确实，如果不知道上一步是撤销操作还是新操作，我就想不出任何解决方案。 - Pablo

Answer 4

这很容易解决。基本上，只有在立即前一个操作是撤消时，重做才有效。

一种解决方案是：当玩家进行移动时，清空堆栈2（撤消堆栈，用于重做）。

其他解决方案：将堆栈2的清除推迟到稍后。维护一个布尔标志，跟踪先前的操作是否为撤消（例如 boolean isRecentActionUndo ），它应始终表示先前的操作是否为撤消，通过在每次调用Undo（）时将其设置为true，并在每次调用Move（）时将其设置为false来实现。在Redo（）中检查此标志。

if(isRecentActionUndo) { // 执行重做 } else { // 清空堆栈2 }

可能有其他更好的解决方案来实现有效的重做。

- madhav-turangi

---

不一定-如果之前的操作是Redo，则Redo可能是有效的。（一个玩家可以连续撤销3步，然后连续重做3步，这不适用于布尔值:(.....Undo / Redo调用移动方法来更改玩家在游戏板上的位置，因此每当调用移动，撤消或重做方法时，Stack 2都会被清空。 - javapalava