破世界紀(jì)錄了 0.74 秒！用 Python 實(shí)現(xiàn)自動(dòng)掃雷！
（點(diǎn)擊上方快速關(guān)注并設(shè)置為星標(biāo)，一起學(xué)Python）
作者：Artrix
來源：https://zhuanlan.zhihu.com/p/35755039
用Python+OpenCV實(shí)現(xiàn)了自動(dòng)掃雷，突破世界記錄，我們先來看一下效果吧。
中級 - 0.74秒 3BV/S=60.81
相信許多人很早就知道有掃雷這么一款經(jīng)典的游（顯卡測試）戲（軟件），更是有不少人曾聽說過中國雷圣，也是中國掃雷第一、世界綜合排名第二的郭蔚嘉的頂頂大名。
準(zhǔn)備動(dòng)手制作一套掃雷自動(dòng)化軟件之前，你需要準(zhǔn)備如下一些工具/軟件/環(huán)境
- 開發(fā)環(huán)境
Python3 環(huán)境 - 推薦3.6或者以上?[更加推薦Anaconda3，以下很多依賴庫無需安裝]
numpy依賴庫 [如有Anaconda則無需安裝]
PIL依賴庫 [如有Anaconda則無需安裝]
opencv-python
win32gui、win32api依賴庫
支持Python的IDE [可選，如果你能忍受用文本編輯器寫程序也可以]
- 掃雷軟件
· Minesweeper Arbiter（必須使用MS-Arbiter來進(jìn)行掃雷?。?/strong>
好啦，那么我們的準(zhǔn)備工作已經(jīng)全部完成了！讓我們開始吧~
在去做一件事情之前最重要的是什么？是將要做的這件事情在心中搭建一個(gè)步驟框架。只有這樣，才能保證在去做這件事的過程中，盡可能的做到深思熟慮，使得最終有個(gè)好的結(jié)果。我們寫程序也要盡可能做到在正式開始開發(fā)之前，在心中有個(gè)大致的思路。
對于本項(xiàng)目而言，大致的開發(fā)過程是這樣的：
完成窗體內(nèi)容截取部分
完成雷塊分割部分
完成雷塊類型識別部分
完成掃雷算法
好啦，既然我們有了個(gè)思路，那就擼起袖子大力干！
其實(shí)對于本項(xiàng)目而言，窗體截取是一個(gè)邏輯上簡單，實(shí)現(xiàn)起來卻相當(dāng)麻煩的部分，而且還是必不可少的部分。我們通過Spy++得到了以下兩點(diǎn)信息：
class_name?=?"TMain"
title_name?=?"Minesweeper?Arbiter?"ms_arbiter.exe的主窗體類別為"TMain"
ms_arbiter.exe的主窗體名稱為"Minesweeper Arbiter "
注意到了么？主窗體的名稱后面有個(gè)空格。正是這個(gè)空格讓筆者困擾了一會兒，只有加上這個(gè)空格，win32gui才能夠正常的獲取到窗體的句柄。
本項(xiàng)目采用了win32gui來獲取窗體的位置信息，具體代碼如下：
hwnd?=?win32gui.FindWindow(class_name,?title_name)
if?hwnd:
????left,?top,?right,?bottom?=?win32gui.GetWindowRect(hwnd)
通過以上代碼，我們得到了窗體相對于整塊屏幕的位置。之后我們需要通過PIL來進(jìn)行掃雷界面的棋盤截取。
我們需要先導(dǎo)入PIL庫
from?PIL?import?ImageGrab然后進(jìn)行具體的操作。
left?+=?15
top?+=?101
right?-=?15
bottom?-=?43
rect?=?(left,?top,?right,?bottom)
img?=?ImageGrab.grab().crop(rect)聰明的你肯定一眼就發(fā)現(xiàn)了那些奇奇怪怪的Magic Numbers，沒錯(cuò)，這的確是Magic Numbers，是我們通過一點(diǎn)點(diǎn)細(xì)微調(diào)節(jié)得到的整個(gè)棋盤相對于窗體的位置。
注意：這些數(shù)據(jù)僅在Windows10下測試通過，如果在別的Windows系統(tǒng)下，不保證相對位置的正確性，因?yàn)槔习姹镜南到y(tǒng)可能有不同寬度的窗體邊框。
好啦，棋盤的圖像我們有了，下一步就是對各個(gè)雷塊進(jìn)行圖像分割了~
在進(jìn)行雷塊分割之前，我們事先需要了解雷塊的尺寸以及它的邊框大小。經(jīng)過筆者的測量，在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ù)組用于存儲每一個(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_height
????????return?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è)庫，隨時(shí)調(diào)用就OK啦~在筆者的實(shí)現(xiàn)中，我們將這一部分封裝成了imageProcess.py，其中函數(shù)get_frame()用于完成上述的圖像獲取、分割過程。
這一部分可能是整個(gè)項(xiàng)目里除了掃雷算法本身之外最重要的部分了。筆者在進(jìn)行雷塊檢測的時(shí)候采用了比較簡單的特征，高效并且可以滿足要求。
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
????#?Opened
????if?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]?=?-2
????????????self.is_started?=?True
????????else:
????????????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?mine
????????????self.blocks_num[x][y]?=?9
????????elif?self.equal(block[5,?8],?self.rgb_to_bgr((255,?0,?0))):
????????????#?Is?flag
????????????self.blocks_num[x][y]?=?0
????????else:
????????????self.blocks_num[x][y]?=?7
????elif?self.equal(block_color,?self.rgb_to_bgr((128,?128,?128))):
????????self.blocks_num[x][y]?=?8
????else:
????????self.blocks_num[x][y]?=?-3
????????self.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)像素的方式來判斷雷塊的類別，并且針對插旗、未點(diǎn)開、已點(diǎn)開但是空白等情況進(jìn)行了進(jìn)一步判斷。具體色值是筆者直接取色得到的，并且屏幕截圖的色彩也沒有經(jīng)過壓縮，所以通過中心像素結(jié)合其他特征點(diǎn)來判斷類別已經(jīng)足夠了，并且做到了高效率。
在本項(xiàng)目中，我們實(shí)現(xiàn)的時(shí)候采用了如下標(biāo)注方式：
1-8：表示數(shù)字1到8
9：表示是地雷
0：表示插旗
-1：表示未打開
-2：表示打開但是空白
-3：表示不是掃雷游戲中的任何方塊類型
通過這種簡單快速又有效的方式，我們成功實(shí)現(xiàn)了高效率的圖像識別。
這可能是本篇文章最激動(dòng)人心的部分了。在這里我們需要先說明一下具體的掃雷算法思路：
遍歷每一個(gè)已經(jīng)有數(shù)字的雷塊，判斷在它周圍的九宮格內(nèi)未被打開的雷塊數(shù)量是否和本身數(shù)字相同，如果相同則表明周圍九宮格內(nèi)全部都是地雷，進(jìn)行標(biāo)記。
再次遍歷每一個(gè)有數(shù)字的雷塊，取九宮格范圍內(nèi)所有未被打開的雷塊，去除已經(jīng)被上一次遍歷標(biāo)記為地雷的雷塊，記錄并且點(diǎn)開。
如果以上方式無法繼續(xù)進(jìn)行，那么說明遇到了死局，選擇在當(dāng)前所有未打開的雷塊中隨機(jī)點(diǎn)擊。（當(dāng)然這個(gè)方法不是最優(yōu)的，有更加優(yōu)秀的解決方案，但是實(shí)現(xiàn)相對麻煩）
基本的掃雷流程就是這樣，那么讓我們來親手實(shí)現(xiàn)它吧~
首先我們需要一個(gè)能夠找出一個(gè)雷塊的九宮格范圍的所有方塊位置的方法。因?yàn)閽呃子螒虻奶厥庑裕谄灞P的四邊是沒有九宮格的邊緣部分的，所以我們需要篩選來排除掉可能超過邊界的訪問。
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?border
?if?x?==?0:
?????for?i?in?range(kernel_height):
?????????kernel[i][0]?=?0
?#?Right?border
?if?x?==?self.blocks_x?-?1:
?????for?i?in?range(kernel_height):
?????????kernel[i][kernel_width?-?1]?=?0
?#?Top?border
?if?y?==?0:
?????for?i?in?range(kernel_width):
?????????kernel[0][i]?=?0
?#?Bottom?border
?if?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)我們在這一部分通過檢測當(dāng)前雷塊是否在棋盤的各個(gè)邊緣來進(jìn)行核的刪除（在核中，1為保留，0為舍棄），之后通過generate_kernel函數(shù)來進(jìn)行最終坐標(biāo)的生成。
def?count_unopen_blocks(blocks):
????count?=?0
????for?single_block?in?blocks:
????????if?self.blocks_num[single_block[1]][single_block[0]]?==?-1:
????????????count?+=?1
????return?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è)需要去檢測的雷塊“地址簿”：to_visit。之后，我們通過count_unopen_blocks函數(shù)來統(tǒng)計(jì)周圍九宮格范圍的未打開數(shù)量，并且和當(dāng)前雷塊的數(shù)字進(jìn)行比對，如果相等則將所有九宮格內(nèi)雷塊通過mark_as_mine函數(shù)來標(biāo)注為地雷。
def?mark_to_click_block(blocks):
???for?single_block?in?blocks:
???????#?Not?Mine
???????if?not?self.blocks_is_mine[single_block[1]][single_block[0]]?==?1:
???????????#?Click-able
???????????if?self.blocks_num[single_block[1]][single_block[0]]?==?-1:
???????????????#?Source?Syntax:?[y][x]?-?Converted
???????????????if?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?=?0
????for?single_block?in?blocks:
????????if?self.blocks_is_mine[single_block[1]][single_block[0]]?==?1:
????????????count?+=?1
????return?count
mines_count?=?count_mines(to_visit)
if?mines_count?==?block:
????mark_to_click_block(to_visit)掃雷流程中的第二步我們也采用了和第一步相近的方法來實(shí)現(xiàn)。先用和第一步完全一樣的方法來生成需要訪問的雷塊的核，之后生成具體的雷塊位置，通過count_mines函數(shù)來獲取九宮格范圍內(nèi)所有雷塊的數(shù)量，并且判斷當(dāng)前九宮格內(nèi)所有雷塊是否已經(jīng)被檢測出來。
如果是，則通過mark_to_click_block函數(shù)來排除九宮格內(nèi)已經(jīng)被標(biāo)記為地雷的雷塊，并且將剩余的安全雷塊加入next_steps數(shù)組內(nèi)。
#?Analyze?the?number?of?blocks
?self.iterate_blocks_image(BoomMine.analyze_block)
?#?Mark?all?mines
?self.iterate_blocks_number(BoomMine.detect_mine)
?#?Calculate?where?to?click
?self.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è)過程都封裝成為了函數(shù)，并且可以通過iterate_blocks_number方法來對所有雷塊都使用傳入的函數(shù)來進(jìn)行處理，這有點(diǎn)類似Python中Filter的作用。
之后筆者做的工作就是判斷當(dāng)前鼠標(biāo)位置是否在棋盤之內(nèi)，如果是，就會自動(dòng)開始識別并且點(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中查看。項(xiàng)目完整代碼/GitHub地址：https://github.com/ArtrixTech/BoomMine
（完）
看完本文有收獲？請轉(zhuǎn)發(fā)分享給更多人
