2

所以我正在开发一款在机制上与 Bejeweled 类似的游戏——你知道类型，你可以在网格中交换相邻的瓷砖以匹配相同类型的瓷砖组。所以这是我的问题：如果我有一个 MxM 网格的瓷砖，并且有 N 种不同的瓷砖类型，我如何计算瓷砖的“随机”放置，以使 3 个相同类型的瓷砖的组数开始最小化？

目前，我只是完全随机地放置它们，但这会导致从一开始就进行许多分组，从而消除了游戏中的所有技能。我什至不知道从哪里开始提出一种算法来最小化这些初始组。如果它有帮助或很重要，现在 10x10 网格中有 5 种瓷砖类型。

4

2 回答 2

0

我能想到的最简单的方法：

for each tile
  based on the surrounding already generated tiles,
    generate a random type among those which won't result in 3-in-a-row

还有一种未优化的方法，假设只有水平和垂直匹配（不是对角线）：（伪代码）

for x = 1 to M
for y = 1 to M
  do
    board[x][y] = randomType()
  while ((x >= 3 && board[x-1][y] == board[x-2][y] && board[x-1][y] == board[x][y]) ||
         (y >= 3 && board[x][y-1] == board[x][y-2] && board[x][y-1] == board[x][y]))

一种完全避免重复生成的方法：（假设类型是数字）

for x = 1 to M
for y = 1 to M
  limit = N
  horizontal = (x >= 3 && board[x-1][y] == board[x-2][y] && board[x-1][y] == board[x][y])
  vertical   = (y >= 3 && board[x][y-1] == board[x][y-2] && board[x][y-1] == board[x][y])
  if horizontal
    limit--
  if vertical
    limit--
  board[x][y] = randomType(limit)
  offset = 0
  if (vertical && board[x][y] >= board[x][y-1])
    offset++
  if (horizontal && board[x][y] >= board[x-1][y])
    offset++

  board[x][y] += offset

上述方法的工作原理类似于在 [0,A-1] 和 [A+1,B] 范围内生成数字，方法是在 [0,B-1] 范围内生成数字，然后，如果生成的数字是 A 或更大，我们将其增加 1。

N至少需要 3，否则您可能会得到类似的结果：

..A
..A
BB?

为此，上述算法将陷入无限循环。

于 2013-10-12T22:55:43.550 回答
0

两个观察：

  • 瓦片的数量非常少，所以我们的算法不需要非常有效
  • 初始序列不需要“完全”未分组，所以我们不需要解决问题，而只是尽力而为

这导致了一个简单的算法，对你来说可能“足够好”：

  • 从一个空板和所有瓷砖的列表（例如数组）开始
  • 随机播放列表
  • 遵循简单的规则，将一个列表元素一个接一个地放在板上：
    • 为当前图块列出仍然可能的位置，每个位置以 1 点开始
    • 对于相同颜色的每个对角相邻的瓦片，将位置点乘以 N
    • 对于每个直接相邻的相同颜色的瓦片，将位置点乘以 M (M>N)
    • 找到最低点的位置
    • 如果这不是唯一的，则使用距中心距离最短的位置
    • 如果这仍然不是唯一的，随机选择
于 2013-10-12T22:56:42.317 回答