与众不同的扫雷之一

刚刚完成了一个有点特别的扫雷游戏，游戏的逻辑全部是用 Lua 实现的。虽然不同的语言可以用来描述相同的思想，但是不同的语言亦会有不同的表达方式。从网上看到的各种版本的扫雷游戏，实现算法大同小异，人云亦云，简直就是应试教育的产物。就像毕加索说的，有些画家把太阳画成一个黄斑，但有些画家借助于他们的技巧和智慧把黄斑画成太阳。我实在是没有兴趣重复别人走过的路，所以打算动手写个不同的版本。

设计一个游戏的算法，刚开始的时候自然是考虑如何存储游戏过程中的数据。由于 Lua 语言本身的一些特性，我使用字符串来存储这些数据，这样可以方便的使用 Lua 内置的高效字符串库来处理游戏数据。

假设扫雷游戏的地图大小为 width x height，那么可以用一个长度为 width * height 的字符串来保存地图数据。在游戏过程中，需要两份地图数据，一份用来保存地图的原始数据，其中记录了地雷的分布情况，以及地雷周围的数字。另一份地图用来保存当前在程序界面上显示的地图数据。地图中每一个的小方格的状态可以用这样的一些字符来表示：

"0"：表示空白区域
"1" ~ "8"：表示地雷周围的数字区域，理论上一个小方格周围最多可以存在 8 颗地雷，所以用数字 1~8 表示数字区域足够了。
"?"：表示未知区域，这个是用于在程序界面上显示的，原始地图数据中不会出现这样的字符。
"@"：表示地雷，之所以选择这个字符，一是因为它比较形象，而是因为它的 ASCII 码增加 1 就变成大写字母 A 的 ASCII 码。这在接下来的字符串处理中将有个巧妙的用处。

地图的数据结构定义好了，剩下的就该开始实现游戏过程中的逻辑了。首先要实现的是在地图上随机放置地雷。首先生成一个全部字符为 "0" 的字符串。然后利用 Lua 数学库中的随机数生成函数产生一个处于 [1, len] 区间的数字，len 表示字符串的长度。将这个数字所对应位置处的字符替换为 "@" 就大功告成了。因为 Lua 没有直接替换字符串指定位置处的函数，所以我是用字符串取子串和字符串连接来实现的（代码第11行）。接下来的几个函数中的字符替换方法也采用了相似的方式（代码第13、15行）。

需要注意的是，循环过程中随机产生的数字有可能是重复的，为了能够放置指定数量的地雷，需要在循环中判断 "@" 字符的数量，如果达到指定数量的话才能退出循环（代码第19行）。

function lay_mine(width, height, number)
    local len = width * height
    if number > len then
         return string.rep("@", len)
    end
    local origin_map = string.rep("0", len)
    math.randomseed(os.time())
    while true do
        local pos = math.random(len)
        if pos == 1 then
            origin_map = "@" .. string.sub(origin_map, 2, len)
        elseif pos == len then
            origin_map = string.sub(origin_map, 1, len - 1) .. "@"
        else
            origin_map = string.sub(origin_map, 1, pos - 1) ..
            "@" ..
            string.sub(origin_map, pos + 1, len)
        end
        count = select(2, string.gsub(origin_map, "@", "@"))
        if count == number then
            break
        end
    end
    origin_map = take_count_of_mine(origin_map, width)
    return origin_map
end

布置好地雷之后，还需要计算与地雷相邻区域的数字。这个算法很简单，既可以依次查找空白区域，计算周围 8 个区域中地雷的数量，也可以反过来，依次查找地雷区域，将周围八个区域的字符加 1。考虑到一般地图中地雷的数量是远少于空白区域的，我采取第二种计算方法。按照上，下，左，右，左上，左下，右下，右上的顺序把周围区域的字符值加 1。如果超出地图边界的话，就跳过。

function take_count_of_mine(origin_map, width)
    local i = 0
    while true do 
        i = string.find(origin_map, "[%u@]", i + 1)
        if i == nil then break end
        if (i - width > 0) then
            local prefix = ""
            local postfix = string.sub(origin_map, i - width, -1)
            postfix = string.gsub(postfix, "[%d@%u]", string.char(1 + string.byte(postfix)), 1)
            if i - width > 1 then
                prefix = string.sub(origin_map, 1, i - width - 1)
            end
            origin_map = prefix .. postfix
        end
        if (i + width < #origin_map + 1) then
            local prefix = string.sub(origin_map, 1, i + width - 1)
            local postfix = string.sub(origin_map, i + width, -1)
            postfix = string.gsub(postfix, "[%d@%u]", string.char(1 + string.byte(postfix)), 1)
            origin_map = prefix .. postfix
        end
        if (i % width ~= 1) then
            local prefix = ""
            local postfix = string.sub(origin_map, i - 1, -1)
            postfix = string.gsub(postfix, "[%d@%u]", string.char(1 + string.byte(postfix)), 1)
            if i - 1 > 1 then
                prefix = string.sub(origin_map, 1, i - 2)
            end
            origin_map = prefix .. postfix
        end
        if (i % width ~= 0) then
            local prefix = string.sub(origin_map, 1, i)
            local postfix = string.sub(origin_map, i + 1, -1)
            postfix = string.gsub(postfix, "[%d@%u]", string.char(1 + string.byte(postfix)), 1)
            origin_map = prefix .. postfix
        end
        if ((i - width - 1) > 0) and (i % width ~= 1) then
            local prefix = ""
            local postfix = string.sub(origin_map, i - width - 1, -1)
            postfix = string.gsub(postfix, "[%d@%u]", string.char(1 + string.byte(postfix)), 1)
            if (i - width - 1) > 1 then
                prefix = string.sub(origin_map, 1, i - width - 2)
            end
            origin_map = prefix .. postfix
        end
        if ((i + width - 1) < #origin_map) and (i % width ~= 1) then
            local prefix = string.sub(origin_map, 1, i + width - 2)
            local postfix = string.sub(origin_map, i + width - 1, -1)
            postfix = string.gsub(postfix, "[%d@%u]", string.char(1 + string.byte(postfix)), 1)
            origin_map = prefix .. postfix
        end
        if ((i + width + 1) < (#origin_map + 1)) and (i % width ~= 0) then
            local prefix = string.sub(origin_map, 1, i + width)
            local postfix = string.sub(origin_map, i + width + 1, -1)
            postfix = string.gsub(postfix, "[%d@%u]", string.char(1 + string.byte(postfix)), 1)
            origin_map = prefix .. postfix
        end
        if ((i - width + 1) > 0) and (i % width ~= 0) then
            local prefix = string.sub(origin_map, 1, i - width)
            local postfix = string.sub(origin_map, i - width + 1, -1)
            postfix = string.gsub(postfix, "[%d@%u]", string.char(1 + string.byte(postfix)), 1)
            origin_map = prefix .. postfix
        end
    end

    origin_map = string.gsub(origin_map, "[%u]", "@")
    return origin_map
end

代码比较长，其实算法很简单。使用 Lua 的字符查找函数，依次查找地雷的位置，使用模式 "[%u@]" 进行匹配。模式 "[%u@]" 的含义是大写字母或者 "@"，每当找到一颗地雷，就把周围区域的字符值加 1。由于地雷周围的区域中也可能存在地雷，加 1 之后，"@" 就会变成大写字母，这也正是选择 "@" 来表示地雷的原因，如此就可以方便的使用模式 "[%u@]" 来匹配字符。

在执行加 1 操作的时候，要对所有的字符都加 1。空白 "0" 加 1 之后还是数字（对应的模式为"%d"），"@" 加 1 之后就会变成大写字母（对应的模式为"%u"），所以在模式匹配的时候使用的模式为 "[%d@%u]"。

完成所有地雷区域的计算之后，要记得把地图数据字符串中的大写字母还原为 "@"（代码第65行）。