用Python實(shí)現(xiàn)自動(dòng)掃雷，挑戰(zhàn)世界紀(jì)錄！

來(lái)源：zhuanlan.zhihu.com/p/35755039

作者：Artrix

項(xiàng)目：github.com/ArtrixTech/BoomMine

中級(jí) - 0.74秒 3BV/S=60.81

相信許多人很早就知道有掃雷這么一款經(jīng)典的游（顯卡測(cè)試）戲（軟件），更是有不少人曾聽(tīng)說(shuō)過(guò)中國(guó)雷圣，也是中國(guó)掃雷第一、世界綜合排名第二的郭蔚嘉的頂頂大名。掃雷作為一款在Windows9x時(shí)代就已經(jīng)誕生的經(jīng)典游戲，從過(guò)去到現(xiàn)在依然都有著它獨(dú)特的魅力：快節(jié)奏高精準(zhǔn)的鼠標(biāo)操作要求、快速的反應(yīng)能力、刷新紀(jì)錄的快感，這些都是掃雷給雷友們帶來(lái)的、只屬于掃雷的獨(dú)一無(wú)二的興奮點(diǎn)。

準(zhǔn)備動(dòng)手制作一套掃雷自動(dòng)化軟件之前，你需要準(zhǔn)備如下一些工具/軟件/環(huán)境

- 開(kāi)發(fā)環(huán)境

1. Python3 環(huán)境 - 推薦3.6或者以上?[更加推薦Anaconda3，以下很多依賴庫(kù)無(wú)需安裝]

2. numpy依賴庫(kù) [如有Anaconda則無(wú)需安裝]

3. PIL依賴庫(kù) [如有Anaconda則無(wú)需安裝]

4. opencv-python

5. win32gui、win32api依賴庫(kù)

6. 支持Python的IDE [可選，如果你能忍受用文本編輯器寫程序也可以]

- 掃雷軟件

好啦，那么我們的準(zhǔn)備工作已經(jīng)全部完成了！讓我們開(kāi)始吧~

在去做一件事情之前最重要的是什么？是將要做的這件事情在心中搭建一個(gè)步驟框架。只有這樣，才能保證在去做這件事的過(guò)程中，盡可能的做到深思熟慮，使得最終有個(gè)好的結(jié)果。我們寫程序也要盡可能做到在正式開(kāi)始開(kāi)發(fā)之前，在心中有個(gè)大致的思路。

對(duì)于本項(xiàng)目而言，大致的開(kāi)發(fā)過(guò)程是這樣的：

1. 完成窗體內(nèi)容截取部分

2. 完成雷塊分割部分

3. 完成雷塊類型識(shí)別部分

4. 完成掃雷算法

好啦，既然我們有了個(gè)思路，那就擼起袖子大力干！

其實(shí)對(duì)于本項(xiàng)目而言，窗體截取是一個(gè)邏輯上簡(jiǎn)單，實(shí)現(xiàn)起來(lái)卻相當(dāng)麻煩的部分，而且還是必不可少的部分。我們通過(guò)Spy++得到了以下兩點(diǎn)信息：

class_name = "TMain"title_name = "Minesweeper Arbiter "

• ms_arbiter.exe的主窗體類別為"TMain"

• ms_arbiter.exe的主窗體名稱為"Minesweeper Arbiter "

注意到了么？主窗體的名稱后面有個(gè)空格。正是這個(gè)空格讓筆者困擾了一會(huì)兒，只有加上這個(gè)空格，win32gui才能夠正常的獲取到窗體的句柄。

本項(xiàng)目采用了win32gui來(lái)獲取窗體的位置信息，具體代碼如下：

hwnd = win32gui.FindWindow(class_name, title_name)if hwnd:left, top, right, bottom = win32gui.GetWindowRect(hwnd)

通過(guò)以上代碼，我們得到了窗體相對(duì)于整塊屏幕的位置。之后我們需要通過(guò)PIL來(lái)進(jìn)行掃雷界面的棋盤截取。

我們需要先導(dǎo)入PIL庫(kù)

from PIL import ImageGrab

然后進(jìn)行具體的操作。

left += 15top += 101right -= 15bottom -= 43
rect = (left, top, right, bottom)img = ImageGrab.grab().crop(rect)

聰明的你肯定一眼就發(fā)現(xiàn)了那些奇奇怪怪的Magic Numbers，沒(méi)錯(cuò)，這的確是Magic Numbers，是我們通過(guò)一點(diǎn)點(diǎn)細(xì)微調(diào)節(jié)得到的整個(gè)棋盤相對(duì)于窗體的位置。

注意：這些數(shù)據(jù)僅在Windows10下測(cè)試通過(guò)，如果在別的Windows系統(tǒng)下，不保證相對(duì)位置的正確性，因?yàn)槔习姹镜南到y(tǒng)可能有不同寬度的窗體邊框。

好啦，棋盤的圖像我們有了，下一步就是對(duì)各個(gè)雷塊進(jìn)行圖像分割了~

在進(jìn)行雷塊分割之前，我們事先需要了解雷塊的尺寸以及它的邊框大小。經(jīng)過(guò)筆者的測(cè)量，在ms_arbiter下，每一個(gè)雷塊的尺寸為16px*16px。

知道了雷塊的尺寸，我們就可以進(jìn)行每一個(gè)雷塊的裁剪了。首先我們需要知道在橫和豎兩個(gè)方向上雷塊的數(shù)量。

block_width, block_height = 16, 16  blocks_x = int((right - left) / block_width)  blocks_y = int((bottom - top) / block_height)

之后，我們建立一個(gè)二維數(shù)組用于存儲(chǔ)每一個(gè)雷塊的圖像，并且進(jìn)行圖像分割，保存在之前建立的數(shù)組中。

def crop_block(hole_img, x, y):        x1, y1 = x * block_width, y * block_height        x2, y2 = x1 + block_width, y1 + block_heightreturn hole_img.crop((x1, y1, x2, y2))
blocks_img = [[0 for i in range(blocks_y)] for i in range(blocks_x)]
for y in range(blocks_y):for x in range(blocks_x):        blocks_img[x][y] = crop_block(img, x, y)

將整個(gè)圖像獲取、分割的部分封裝成一個(gè)庫(kù)，隨時(shí)調(diào)用就OK啦~在筆者的實(shí)現(xiàn)中，我們將這一部分封裝成了imageProcess.py，其中函數(shù)get_frame()用于完成上述的圖像獲取、分割過(guò)程。

這一部分可能是整個(gè)項(xiàng)目里除了掃雷算法本身之外最重要的部分了。筆者在進(jìn)行雷塊檢測(cè)的時(shí)候采用了比較簡(jiǎn)單的特征，高效并且可以滿足要求。

def analyze_block(self, block, location):    block = imageProcess.pil_to_cv(block)
    block_color = block[8, 8]    x, y = location[0], location[1]
    # -1:Not opened    # -2:Opened but blank    # -3:Un initialized
    # Openedif self.equal(block_color, self.rgb_to_bgr((192, 192, 192))):if not self.equal(block[8, 1], self.rgb_to_bgr((255, 255, 255))):self.blocks_num[x][y] = -2self.is_started = Trueelse:self.blocks_num[x][y] = -1
    elif self.equal(block_color, self.rgb_to_bgr((0, 0, 255))):self.blocks_num[x][y] = 1
    elif self.equal(block_color, self.rgb_to_bgr((0, 128, 0))):self.blocks_num[x][y] = 2
    elif self.equal(block_color, self.rgb_to_bgr((255, 0, 0))):self.blocks_num[x][y] = 3
    elif self.equal(block_color, self.rgb_to_bgr((0, 0, 128))):self.blocks_num[x][y] = 4
    elif self.equal(block_color, self.rgb_to_bgr((128, 0, 0))):self.blocks_num[x][y] = 5
    elif self.equal(block_color, self.rgb_to_bgr((0, 128, 128))):self.blocks_num[x][y] = 6
    elif self.equal(block_color, self.rgb_to_bgr((0, 0, 0))):if self.equal(block[6, 6], self.rgb_to_bgr((255, 255, 255))):            # Is mineself.blocks_num[x][y] = 9        elif self.equal(block[5, 8], self.rgb_to_bgr((255, 0, 0))):            # Is flagself.blocks_num[x][y] = 0else:self.blocks_num[x][y] = 7
    elif self.equal(block_color, self.rgb_to_bgr((128, 128, 128))):self.blocks_num[x][y] = 8else:self.blocks_num[x][y] = -3self.is_mine_form = False
if self.blocks_num[x][y] == -3 or not self.blocks_num[x][y] == -1:self.is_new_start = False

可以看到，我們采用了讀取每個(gè)雷塊的中心點(diǎn)像素的方式來(lái)判斷雷塊的類別，并且針對(duì)插旗、未點(diǎn)開(kāi)、已點(diǎn)開(kāi)但是空白等情況進(jìn)行了進(jìn)一步判斷。具體色值是筆者直接取色得到的，并且屏幕截圖的色彩也沒(méi)有經(jīng)過(guò)壓縮，所以通過(guò)中心像素結(jié)合其他特征點(diǎn)來(lái)判斷類別已經(jīng)足夠了，并且做到了高效率。

在本項(xiàng)目中，我們實(shí)現(xiàn)的時(shí)候采用了如下標(biāo)注方式：

• 1-8：表示數(shù)字1到8

• 9：表示是地雷

• 0：表示插旗

• -1：表示未打開(kāi)

• -2：表示打開(kāi)但是空白

• -3：表示不是掃雷游戲中的任何方塊類型

通過(guò)這種簡(jiǎn)單快速又有效的方式，我們成功實(shí)現(xiàn)了高效率的圖像識(shí)別。

這可能是本篇文章最激動(dòng)人心的部分了。在這里我們需要先說(shuō)明一下具體的掃雷算法思路：

1. 遍歷每一個(gè)已經(jīng)有數(shù)字的雷塊，判斷在它周圍的九宮格內(nèi)未被打開(kāi)的雷塊數(shù)量是否和本身數(shù)字相同，如果相同則表明周圍九宮格內(nèi)全部都是地雷，進(jìn)行標(biāo)記。

2. 再次遍歷每一個(gè)有數(shù)字的雷塊，取九宮格范圍內(nèi)所有未被打開(kāi)的雷塊，去除已經(jīng)被上一次遍歷標(biāo)記為地雷的雷塊，記錄并且點(diǎn)開(kāi)。

3. 如果以上方式無(wú)法繼續(xù)進(jìn)行，那么說(shuō)明遇到了死局，選擇在當(dāng)前所有未打開(kāi)的雷塊中隨機(jī)點(diǎn)擊。（當(dāng)然這個(gè)方法不是最優(yōu)的，有更加優(yōu)秀的解決方案，但是實(shí)現(xiàn)相對(duì)麻煩）

基本的掃雷流程就是這樣，那么讓我們來(lái)親手實(shí)現(xiàn)它吧~

首先我們需要一個(gè)能夠找出一個(gè)雷塊的九宮格范圍的所有方塊位置的方法。因?yàn)閽呃子螒虻奶厥庑裕谄灞P的四邊是沒(méi)有九宮格的邊緣部分的，所以我們需要篩選來(lái)排除掉可能超過(guò)邊界的訪問(wèn)。

def generate_kernel(k, k_width, k_height, block_location):
     ls = []     loc_x, loc_y = block_location[0], block_location[1]
for now_y in range(k_height):for now_x in range(k_width):if k[now_y][now_x]:                 rel_x, rel_y = now_x - 1, now_y - 1                 ls.append((loc_y + rel_y, loc_x + rel_x))return ls
 kernel_width, kernel_height = 3, 3
# Kernel mode:[Row][Col] kernel = [[1, 1, 1], [1, 1, 1], [1, 1, 1]]
# Left borderif x == 0:for i in range(kernel_height):         kernel[i][0] = 0
# Right borderif x == self.blocks_x - 1:for i in range(kernel_height):         kernel[i][kernel_width - 1] = 0
# Top borderif y == 0:for i in range(kernel_width):         kernel[0][i] = 0
# Bottom borderif y == self.blocks_y - 1:for i in range(kernel_width):         kernel[kernel_height - 1][i] = 0
# Generate the search map to_visit = generate_kernel(kernel, kernel_width, kernel_height, location)

我們?cè)谶@一部分通過(guò)檢測(cè)當(dāng)前雷塊是否在棋盤的各個(gè)邊緣來(lái)進(jìn)行核的刪除（在核中，1為保留，0為舍棄），之后通過(guò)generate_kernel函數(shù)來(lái)進(jìn)行最終坐標(biāo)的生成。

def count_unopen_blocks(blocks):    count = 0for single_block in blocks:if self.blocks_num[single_block[1]][single_block[0]] == -1:            count += 1return count
def mark_as_mine(blocks):for single_block in blocks:if self.blocks_num[single_block[1]][single_block[0]] == -1:self.blocks_is_mine[single_block[1]][single_block[0]] = 1
unopen_blocks = count_unopen_blocks(to_visit)if unopen_blocks == self.blocks_num[x][y]:     mark_as_mine(to_visit)

在完成核的生成之后，我們有了一個(gè)需要去檢測(cè)的雷塊“地址簿”：to_visit。之后，我們通過(guò)count_unopen_blocks函數(shù)來(lái)統(tǒng)計(jì)周圍九宮格范圍的未打開(kāi)數(shù)量，并且和當(dāng)前雷塊的數(shù)字進(jìn)行比對(duì)，如果相等則將所有九宮格內(nèi)雷塊通過(guò)mark_as_mine函數(shù)來(lái)標(biāo)注為地雷。

def mark_to_click_block(blocks):for single_block in blocks:
# Not Mineif not self.blocks_is_mine[single_block[1]][single_block[0]] == 1:# Click-ableif self.blocks_num[single_block[1]][single_block[0]] == -1:
# Source Syntax: [y][x] - Convertedif not (single_block[1], single_block[0]) in self.next_steps:self.next_steps.append((single_block[1], single_block[0]))
def count_mines(blocks):    count = 0for single_block in blocks:if self.blocks_is_mine[single_block[1]][single_block[0]] == 1:            count += 1return count
mines_count = count_mines(to_visit)
if mines_count == block:    mark_to_click_block(to_visit)

掃雷流程中的第二步我們也采用了和第一步相近的方法來(lái)實(shí)現(xiàn)。先用和第一步完全一樣的方法來(lái)生成需要訪問(wèn)的雷塊的核，之后生成具體的雷塊位置，通過(guò)count_mines函數(shù)來(lái)獲取九宮格范圍內(nèi)所有雷塊的數(shù)量，并且判斷當(dāng)前九宮格內(nèi)所有雷塊是否已經(jīng)被檢測(cè)出來(lái)。

如果是，則通過(guò)mark_to_click_block函數(shù)來(lái)排除九宮格內(nèi)已經(jīng)被標(biāo)記為地雷的雷塊，并且將剩余的安全雷塊加入next_steps數(shù)組內(nèi)。

# Analyze the number of blocksself.iterate_blocks_image(BoomMine.analyze_block)
# Mark all minesself.iterate_blocks_number(BoomMine.detect_mine)
# Calculate where to clickself.iterate_blocks_number(BoomMine.detect_to_click_block)
if self.is_in_form(mouseOperation.get_mouse_point()):for to_click in self.next_steps:         on_screen_location = self.rel_loc_to_real(to_click)         mouseOperation.mouse_move(on_screen_location[0], on_screen_location[1])         mouseOperation.mouse_click()

在最終的實(shí)現(xiàn)內(nèi)，筆者將幾個(gè)過(guò)程都封裝成為了函數(shù)，并且可以通過(guò)iterate_blocks_number方法來(lái)對(duì)所有雷塊都使用傳入的函數(shù)來(lái)進(jìn)行處理，這有點(diǎn)類似Python中Filter的作用。

之后筆者做的工作就是判斷當(dāng)前鼠標(biāo)位置是否在棋盤之內(nèi)，如果是，就會(huì)自動(dòng)開(kāi)始識(shí)別并且點(diǎn)擊。具體的點(diǎn)擊部分，筆者采用了作者為"wp"的一份代碼（從互聯(lián)網(wǎng)搜集而得），里面實(shí)現(xiàn)了基于win32api的窗體消息發(fā)送工作，進(jìn)而完成了鼠標(biāo)移動(dòng)和點(diǎn)擊的操作。具體實(shí)現(xiàn)封裝在mouseOperation.py中，有興趣可以在文末的Github Repo中查看。

作者的記錄

這張錄像最后的點(diǎn)擊部分遇到了死局，最終是通過(guò)隨機(jī)完成的

筆者還實(shí)現(xiàn)了在新開(kāi)局的時(shí)候隨機(jī)點(diǎn)擊來(lái)開(kāi)出局面的功能，不過(guò)由于比較簡(jiǎn)單，所以詳細(xì)解析就不在這里貼出啦~

注明一下：如果在實(shí)驗(yàn)的時(shí)候發(fā)現(xiàn)會(huì)有雷塊炸掉的情況，不要擔(dān)心，這是因?yàn)楫?dāng)前已經(jīng)遇到了死局，沒(méi)法通過(guò)本項(xiàng)目的算法來(lái)進(jìn)行直接的推斷了，這個(gè)時(shí)候程序會(huì)隨機(jī)進(jìn)行點(diǎn)擊，有一定幾率炸裂哦！

項(xiàng)目完整代碼/GitHub地址：

https://github.com/ArtrixTech/BoomMine

感謝轉(zhuǎn)發(fā)和點(diǎn)贊的各位~

_往期文章推薦_