RM连连看两次转弯算法：XP代码与测试用例

一、难点与选型

连连看的画面和玩法都不复杂，开发成本主要集中在规则实现上。规则是：两个相同图案之间存在一条转弯不超过两次的通路，就可以消除。实现时有四个难点。

第一是棋盘存储。RPG Maker XP的事件层没有原生二维网格，只能用变量和开关模拟。脚本层可以直接使用Ruby二维数组。用事件页逐格模拟棋盘时，事件数量会迅速膨胀，改一条规则要改很多处。

第二是连通判定。判断两格能否相连是图搜索问题。事件指令很难表达“最多转两次弯”这种约束，所以这一步应放在脚本里完成。

第三是死局处理。随机布局可能没有任何可消除的对。程序需要检测死局，并在必要时重排方块。

第四是素材与交互。方块图标、光标、连线和洗牌按钮都要排进640×480的画面里。

实现路线有三条，下表列出它们的差别。

路线	是否保留RM生态	是否需要写Ruby	适合场景	主要风险
A：纯事件加变量	是	否	只想验证玩法的一次性demo	路径判定基本做不了，事件数量多
B：RGSS脚本	是	是，需要读一点Ruby和RGSS API	要做完整游戏	脚本接线出错时较难定位
C：HTML5加JavaScript	否	否（写JS）	快速验证算法或做网页版	离开RM生态，素材和存档要重做

推荐做法是先用普通Ruby验证算法，确认无误后再把同一套逻辑放进路线B。本文代码就是按这个思路写的：核心逻辑与画面分离，逻辑部分可以脱离XP独立运行测试。

二、棋盘补圈与数据结构

棋盘用二维数组表示。0表示空格，非0表示方块种类编号。搜索时需要在棋盘四周补一圈0。

补圈的原因是：如果不补，从棋盘外侧绕过去的合法通路会被漏判。玩家会看到明明能连却连不上的情况。补圈之后，数组的坐标分成两部分：

• 真实方块区域是第1行到第rows行、第1列到第cols列。
• 外圈是第0行、第rows+1行、第0列、第cols+1列，外圈的值始终为0。

数组总大小是(rows+2)行、(cols+2)列。搜索时可以在外圈上行走，但不能越过外圈的边界。代码里的open?方法负责这个边界检查，这一步省略会导致数组下标为-1时取到数组末尾的值，结果会悄悄出错。

三、两次转弯搜索

搜索的状态是“走到某个空格，并且是沿某个方向进入的”。状态用三元组表示：格子坐标和进入方向，再加上已经转过的弯数。

转弯规则如下：

1. 从起点出发时，四个方向都可以选，不算转弯。
2. 沿当前方向直行一格，不增加转弯数。
3. 在当前格改成垂直方向，转弯数加1。转弯数到2就不能再转。
4. 不允许原地掉头，因为掉头必然经过两次转弯，且路径上总能找到更短的替代路线。

每个状态只记录最少的转弯数。如果同一格、同一方向已经以更少的转弯数到达过，就直接剪枝。这样搜索的状态数是有限的，不会因为棋盘上存在环而无限递归。

四、死局检测与洗牌

死局指的是剩余方块中找不到任何一对可以消除。检测方法是两两枚举剩余方块，对同种图案的组合调用连通判定。只要找到一对，就不是死局。

死局时需要洗牌。洗牌只重排剩余方块的图案，不改变剩余方块占用的位置集合，这样棋盘的格子数不变。洗牌后再次检测，如果仍是死局，就继续重试。重试次数有上限，超过上限后返回失败，由调用方决定是提示玩家还是重开一局。

洗牌使用Fisher-Yates算法，不依赖Ruby 1.8没有的Array#shuffle。

五、完整代码

下面的代码保存为linkgame.rb。它只使用Ruby 1.8就有的语法和方法，不使用key: value形式的哈希、&.、->和each_with_object。注释使用英文，避免中文编码在XP脚本编辑器里出现乱码。

# linkgame.rb: core logic, Ruby 1.8 compatible
class LinkGame
  DR = [-1, 0, 1, 0]   # direction index: 0 up, 1 right, 2 down, 3 left
  DC = [0, 1, 0, -1]
  attr_reader :rows, :cols, :grid
  def initialize(rows, cols)
    @rows = rows
    @cols = cols
    @height = rows + 2
    @width = cols + 2
    @grid = Array.new(@height) { Array.new(@width, 0) }
  end
  # Build a board from text lines. Digits are tiles, "." is empty.
  def self.from_text(lines)
    game = new(lines.length, lines[0].length)
    lines.each_with_index do |line, i|
      line.split('').each_with_index do |ch, j|
        game.set_cell(i + 1, j + 1, ch == '.' ? 0 : ch.to_i)
      end
    end
    game
  end
  def set_cell(r, c, v)
    @grid[r][c] = v
  end
  # Fill the inner area from a flat list of length rows*cols.
  def fill(values)
    idx = 0
    1.upto(@rows) do |r|
      1.upto(@cols) do |c|
        @grid[r][c] = values[idx]
        idx += 1
      end
    end
  end
  def open?(r, c)
    r >= 0 && r < @height && c >= 0 && c < @width && @grid[r][c] == 0
  end
  # True if the tiles at (r1,c1) and (r2,c2) can be joined with at most two turns.
  def linked?(r1, c1, r2, c2)
    return false if r1 == r2 && c1 == c2
    v = @grid[r1][c1]
    return false if v == 0 || v != @grid[r2][c2]
    @tr = r2
    @tc = c2
    @seen = {}
    0.upto(3) do |d|
      nr = r1 + DR[d]
      nc = c1 + DC[d]
      return true if nr == @tr && nc == @tc
      return true if open?(nr, nc) && walk(nr, nc, d, 0)
    end
    false
  end
  # Enter empty cell (r,c) moving in direction d, having already turned t times.
  def walk(r, c, d, t)
    key = (r * @width + c) * 4 + d
    old = @seen[key]
    return false if old && old <= t
    @seen[key] = t
    # keep going straight
    nr = r + DR[d]
    nc = c + DC[d]
    return true if nr == @tr && nc == @tc
    return true if open?(nr, nc) && walk(nr, nc, d, t)
    # turn 90 degrees, at most two turns in total
    return false if t >= 2
    [(d + 1) % 4, (d + 3) % 4].each do |nd|
      ar = r + DR[nd]
      ac = c + DC[nd]
      return true if ar == @tr && ac == @tc
      return true if open?(ar, ac) && walk(ar, ac, nd, t + 1)
    end
    false
  end
  # Clear both tiles if they can be joined. Returns true when a pair is removed.
  def remove_pair(r1, c1, r2, c2)
    return false unless linked?(r1, c1, r2, c2)
    @grid[r1][c1] = 0
    @grid[r2][c2] = 0
    true
  end
  # Positions [r, c] of all remaining tiles.
  def tile_positions
    list = []
    1.upto(@rows) do |r|
      1.upto(@cols) do |c|
        list.push([r, c]) if @grid[r][c] != 0
      end
    end
    list
  end
  def remaining
    tile_positions.length
  end
  # True if at least one removable pair exists.
  def has_moves?
    cells = tile_positions
    i = 0
    while i < cells.length
      j = i + 1
      while j < cells.length
        return true if linked?(cells[i][0], cells[i][1], cells[j][0], cells[j][1])
        j += 1
      end
      i += 1
    end
    false
  end
  def shuffle_array!(arr)
    i = arr.length - 1
    while i > 0
      j = rand(i + 1)
      arr[i], arr[j] = arr[j], arr[i]
      i -= 1
    end
    arr
  end
  def write_values(cells, values)
    i = 0
    while i < cells.length
      @grid[cells[i][0]][cells[i][1]] = values[i]
      i += 1
    end
  end
  # Reshuffle remaining tiles among the remaining positions until a move exists.
  # Returns false and restores the original arrangement if no playable layout is found.
  def shuffle_tiles(max_tries = 50)
    cells = tile_positions
    original = cells.map { |pos| @grid[pos[0]][pos[1]] }
    max_tries.times do
      values = original.dup
      shuffle_array!(values)
      write_values(cells, values)
      return true if has_moves?
    end
    write_values(cells, original)
    false
  end
  # Create a random playable layout. kind_count is how many different images to use.
  def new_layout(kind_count)
    total = @rows * @cols
    raise "rows * cols must be even" if total % 2 != 0
    values = []
    (total / 2).times do |i|
      kind = (i % kind_count) + 1
      values.push(kind)
      values.push(kind)
    end
    shuffle_array!(values)
    fill(values)
    shuffle_tiles
  end
end

测试文件保存为test_linkgame.rb，与linkgame.rb放在同一目录，运行命令是ruby test_linkgame.rb。

# test_linkgame.rb: run with "ruby test_linkgame.rb"
require 'linkgame'
$passed = 0
$failed = 0
def check(name, actual, expected)
  if actual == expected
    $passed += 1
    puts "PASS  #{name}"
  else
    $failed += 1
    puts "FAIL  #{name} (expected #{expected.inspect}, got #{actual.inspect})"
  end
end
g = LinkGame.from_text(["11", ".."])
check("01 adjacent tiles", g.linked?(1, 1, 1, 2), true)
g = LinkGame.from_text(["1.", ".1"])
check("02 one turn", g.linked?(1, 1, 2, 2), true)
g = LinkGame.from_text(["191", "...", "..."])
check("03 two turns around a blocker", g.linked?(1, 1, 1, 3), true)
g = LinkGame.from_text(["12"])
check("04 different images", g.linked?(1, 1, 1, 2), false)
g = LinkGame.from_text(["1.", ".."])
check("05 empty target cell", g.linked?(1, 1, 1, 2), false)
g = LinkGame.from_text(["19.", "919", ".9."])
check("06 enclosed start tile", g.linked?(2, 2, 1, 1), false)
g = LinkGame.from_text(["191"])
check("07 path through outer border", g.linked?(1, 1, 1, 3), true)
g = LinkGame.from_text(["12", "21"])
check("08 dead board detected", g.has_moves?, false)
puts "passed: #{$passed}, failed: #{$failed}"

运行后应看到8行PASS和最后一行passed: 8, failed: 0。测试2和测试7的期望值依赖补圈的设计：测试2的路线可以是直接转一次弯，也可以绕到外圈再转弯，只要结果为真即可；测试7专门验证外圈通路。

六、8个测试用例的含义

• 用例01：相邻同图案，0次转弯，验证最基本的直连。
• 用例02：一次转弯，验证L形路线。
• 用例03：两次转弯，中间的方块挡住直线，只能绕行。这是“两次转弯”上限的正向验证。
• 用例04：图案不同，即使有路径也不能消除。
• 用例05：目标是空格，应返回假。
• 用例06：起点四周都是其他方块，无法出发。验证搜索不会越界或漏判。
• 用例07：路径要经过外圈。验证补圈的作用。
• 用例08：棋盘没有可消除的对，has_moves?应返回假。调用shuffle_tiles后，这个棋盘应能恢复可消除状态。

测试用例没有覆盖三次转弯被拒绝的情况。这是因为棋盘外圈永远开放，在小棋盘上很难构造只能靠三次转弯才能连接的布局。如果需要覆盖这一点，可以在较大的棋盘上手工设计布局，再用linked?验证。

七、接入RPG Maker XP

本文代码没有在真实的RPG Maker XP中运行过。接入前请先在普通Ruby中跑通测试，再在XP中按下面步骤做。

1. 备份工程。复制整个项目文件夹，之后的所有改动都在副本里做。
2. 打开脚本编辑器，在Main之前新建一个脚本段，名称填LinkGame，把linkgame.rb的内容粘贴进去。注释使用英文，避免编码问题。
3. 准备素材。把一张图片放进Graphics/Pictures/，例如LinkTiles.png。图片中每个方块为48×48像素，8种图案横向排列，第k种图案的源矩形左上角是x = (k - 1) * 48，y = 0。
4. 在地图事件里调用逻辑层。行数在前、列数在后，并指定图案种类数。

$link = LinkGame.new(6, 8)   # 6 rows, 8 columns
$link.new_layout(8)          # 8 different images

1. 坐标映射。640×480画面里，棋盘宽384像素、高288像素，左上角放在(128, 96)。第r行第c列方块的左上角像素是：

• x = 128 + (c - 1) * 48
• y = 96 + (r - 1) * 48

1. 点击处理。玩家用方向键移动光标，按确认键选中第一块，再选中第二块，然后调用remove_pair。如果返回真，就把两个方块的精灵隐藏。如果返回假，就取消选中。

if $link.remove_pair(r1, c1, r2, c2)
  # hide the two sprites
else
  # clear the selection
end

1. 死局提示。每次消除后调用$link.has_moves?。如果返回假，调用$link.shuffle_tiles。如果它也返回假，提示玩家重开一局。

RGSS的场景循环、精灵创建与释放的写法因工程而异。上面的步骤给出的是逻辑与画面之间的接口，具体的场景类请按项目已有的结构编写。

八、排错清单

现象：明明能连却提示不能连。
原因通常是坐标偏移。真实方块的行列是1到rows、1到cols，如果把0当成第一行，就会取错格子。修正方法是检查调用linked?时传入的坐标，确认它们来自tile_positions或从1开始的光标位置。

现象：三次转弯也能消除。
原因通常是walk中的转弯计数写错了位置，或者在t >= 2的判断之前就进入了转弯分支。修正方法是保证转弯分支只在t < 2时执行，并且转弯后传入的是t + 1。

现象：能消除的对被判为死局。
原因通常是has_moves?里漏掉了某些配对，或者linked?的open?判断把目标格误当成空格。修正方法是用测试用例08和用例03手工核对，确认目标格的值在判断前仍是非0。

现象：洗牌后仍然无解。
shuffle_tiles只在50次尝试内寻找可解布局。如果剩余方块很少，随机排列可能很难碰到可解布局。修正方法是增加尝试次数，或在剩余方块较少时改为直接重开一局。

现象：XP中报语法错误。
常见原因是使用了Ruby 1.8不认识的写法，例如key: value形式的哈希、&.、->或each_with_object。修正方法是对照linkgame.rb，确认没有引入这些写法。另一个常见原因是中文注释在脚本编辑器中显示乱码，此时把注释改为英文即可。

九、风险提示

接入前请务必备份工程，并在副本中测试。洗牌和消除只修改$link对象内的棋盘数组，不会改变存档结构。如果项目把棋盘状态保存到存档中，需要在存档字段里新增棋盘数据，并在读档时调用fill恢复。这部分逻辑本文没有覆盖，需要读者根据自己的存档方式补充。

本文的代码只保证逻辑层通过测试，不保证在任意XP项目中都能直接运行。素材、分辨率和场景结构都会影响最终效果，请以实际运行结果为准。