使用 Scala 生成游戏动作

Question

我试图了解如何使用 Scala 功能性地编写策略游戏，但不幸的是我似乎停留在最基本的知识上。 （这不是家庭作业，而是我尝试学习新东西，即“纯”函数式编程。）

让我们进行以下简单的“游戏”：（唯一的）玩家在无尽的棋盘上拥有x个相同的棋子。一排正方形。棋子从 0 格开始，每一回合他都可以将棋子向前移动一格。

作为数据结构，我将使用 List[Int]，其中每个项目都是一个片段的位置（正方形）。

为了生成可能的移动，我想出了：

def moves(start: List[Int]) = 
    (0 until start.length).map({i => start.updated(i, start(i) + 1)});

val m1 = moves(List(0,0,0))
// m1 then contains Vector(List(1, 0, 0), List(0, 1, 0), List(0, 0, 1))

val m2 = moves(List(1,2,3))
// m1 then contains Vector(List(2, 2, 3), List(1, 3, 3), List(1, 2, 4))

我不喜欢的是使用索引循环（0直到start.length）。对我来说，它似乎不太“实用”。这是正确的方法还是有更好的方法？

---

现在，在我的游戏示例中，所有棋子都是相同的，因此在 m1 的情况下，所有三个可能的动作也是相同的，并且可以/应该压缩为一个动作。我修改了 moves 对每个移动项目进行排序，以便我可以获得不同项目的列表：

def moves(start: List[Int]) = 
    (0 until start.length).map({i => start.updated(i, start(i) + 1).sorted}).distinct;

val m1 = moves(List(0,0,0))
// m1 then contains Vector(List(0, 0, 1))

val m2 = moves(List(1,2,3))
// m1 then contains Vector(List(2, 2, 3), List(1, 3, 3), List(1, 2, 4))

但是，这需要数据结构可排序，并且在我的“真实”应用程序中，它很可能不是 < code>List[Int]，而是一个 Tuple 或 case 类。我想我需要的是一个 distinct 方法，它采用一个定义相等的函数。我将如何实施？

Answer 1

如果你的部分是相同的，我认为你的数据结构是错误的。您需要一个 Map[Int,Int]，其中键告诉您方块的索引，值告诉您有多少块（没有默认的计数集，否则这会更容易）。然后

def moves(start: Map[Int,Int]) = start.keySet.map(k => {
  val n = start(k)
  val pickup = (if (n == 1) (start - k) else start + (k -> (n-1)))
  pickup + ((k+1) -> (start.getOrElse(k+1, 0) + 1))
})

这解决了您的玩具示例中的所有问题（但可能不是您真正的问题）。它组成得很好：

scala> val firstmoves = moves(Map(0->3))                          
firstmoves: scala.collection.Set[scala.collection.immutable.Map[Int,Int]] =
Set(Map((0,2), (1,1)))

scala> val secondmoves = firstmoves.flatMap(moves)                           
secondmoves: scala.collection.Set[scala.collection.immutable.Map[Int,Int]] =
Set(Map((0,1), (1,2)), Map((0,2), (2,1)))

scala> val thirdmoves = secondmoves.flatMap(moves)
thirdmoves: scala.collection.Set[scala.collection.immutable.Map[Int,Int]] =
Set(Map((1,3)), Map((0,1), (1,1), (2,1)), Map((0,2), (3,1)))

Answer 2

作为次要选择，您可以将 (0 直到 start.length) 替换为 start.indices。递归解决方案完全避免使用索引：

def moves(start: List[Int]): List[List[Int]] =  start match {
  case Nil => Nil
  case head :: tail => (head + 1 :: tail) :: (moves(tail) map (head :: _))
}

这比使用索引访问具有更好的性能，并且比您的解决方案具有更好的内存占用，因为它对列表组件的重用率非常高。它还使用一种常见的函数技术，将问题分为已知步骤和递归步骤。

让我解释一下。对于任何非空列表，解决方案的一个元素将是第一个元素加一的列表，所有其他元素相同。这是上面非空列表的解决方案的第一部分：

head + 1 :: tail

现在，所有其他解决方案的共同点是第一个元素是相同的。因此，想象 solutions 具有减去第一个元素的所有其他解决方案，然后以下内容将重新创建该解决方案：

solutions map (solution => head :: solution)

或者，以压缩形式，

solutions map (head :: _)

现在我们只需要计算 solutions 。碰巧的是，我们已经有了一个计算方法：移动本身！我们只需要将列表的 tail 提供给它：

(moves(tail) map (head :: _))

因此，如果我们将这两者结合在一起，我们就会得到上面代码中显示的解决方案。

话虽如此，我也不确定列表是否是解决这个问题的良好数据结构。

至于获取不同的解决方案列表，如果您创建一个类来存储移动，那么您可以有一个忽略元素顺序的 equals 方法，在这种情况下，诸如 distinct 之类的方法 会工作得很好。

如果这不可行，您可以使用 SortedSet 的特性（它们使用隐式 Ordering 来确定相等性）来解决问题。例如：

object LO extends Ordering[List[Int]] {
  def compare(x: List[Int], y: List[Int]) = cmp(x.sorted, y.sorted)
  def cmp(x: List[Int], y: List[Int]): Int = (x, y) match {
    case (Nil, Nil) => 0
    case (Nil, _  ) => -1
    case (_  , Nil) => 1
    case (h1 :: t1, h2 :: t2) if h1 < h2 => -1
    case (h1 :: t1, h2 :: t2) if h2 < h1 => 1
    case (h1 :: t1, h2 :: t2) => cmp(t1, t2)
  }
}

val m1 = SortedSet(moves(List(0, 0, 0)): _*)(LO).toList