source ：zhuanlan.zhihu.com/p/35755039
author ：Artrix
project ：github.com/ArtrixTech/BoomMine
Life is too short , Learn quickly Python！ Benefits at the end of today's article ！
The case shared with you today is Python+OpenCV Automatic mine sweeping is realized , And broke the human world record .（ Of course it's not ）
We don't talk much nonsense , Look at the results first ~
intermediate - 0.74 second 3BV/S=60.81
I believe many people have known for a long time that there is such a classic tour as mine sweeping （ Video card test ） Play （ Software ）, Many people have heard of Chinese Lei Sheng , It is also the first mine clearance in China 、 The top name of Guo Weijia, who ranks second in the world . Mine sweeping is used in Windows9x A classic game that was born in the era , It still has its unique charm from the past to the present ： Fast paced, high-precision mouse operation requirements 、 Quick response 、 Record breaking pleasure , These are brought by mine sweeping to mine friends 、 Only belong to the unique excitement of mine clearance .
▍0x00 Get ready
Before preparing to make a set of mine sweeping automation software , You need to prepare the following tools / Software / Environmental Science
- development environment
Python3 Environmental Science - recommend 3.6 Or above [ More recommend Anaconda3, Many of the following dependent libraries do not need to be installed ]
numpy Dependency Library [ if there be Anaconda There is no need to install ]
PIL Dependency Library [ if there be Anaconda There is no need to install ]
opencv-python
win32gui、win32api Dependency Library
Support Python Of IDE [ Optional , If you can stand writing programs with a text editor ]
- Mine sweeping software
· Minesweeper Arbiter（ You have to use MS-Arbiter To clear the mines ！）
http://saolei.net/Download/Arbiter_0.52.3.zip
Of course , Before the official start , We also need to know the basic knowledge of mine clearance . If you don't know, you can refer to China's largest minesweeping forum saolei.net The article in ：
http://saolei.net/BBS/Title.asp?Id=177
All right. , Then all our preparations have been completed ！ Let's get started ~
▍0x01 Realize the idea
What is the most important thing before you do something ？ This is what we will do to build a step framework in our mind . That's the only way , To ensure that in the process of doing this , Be as thoughtful as possible , Make a good result in the end . We should also try our best to write the program before the formal start of development , Have a general idea in mind .
For this project , The general development process is like this ：
Complete the form content interception part
Complete the thunder block segmentation part
Complete the part of mine block type identification
Complete the minesweeping algorithm
All right. , Now that we have an idea , Then roll up your sleeves and work hard ！
- 01 Form interception
In fact, for this project , Form interception is a logically simple , The part that is quite troublesome to implement , And it's an essential part . We go through Spy++ Got the following two information ：
class_name = "TMain"
title_name = "Minesweeper Arbiter "ms_arbiter.exe The main form category of is "TMain"
ms_arbiter.exe The name of the main form is "Minesweeper Arbiter "
Have you noticed ？ There is a space after the name of the main form . It is this space that bothers the author for a while , Only add this space ,win32gui To get the handle of the form normally .
This project adopts win32gui To get the location information of the form , The specific code is as follows ：
hwnd = win32gui.FindWindow(class_name, title_name)
if hwnd:
left, top, right, bottom = win32gui.GetWindowRect(hwnd)Through the above code , We get the position of the form relative to the whole screen . Then we need to go through PIL To intercept the checkerboard of the minesweeping interface .
We need to import PIL library
from PIL import ImageGrabThen carry out specific operations .
left += 15
top += 101
right -= 15
bottom -= 43
rect = (left, top, right, bottom)
img = ImageGrab.grab().crop(rect)Smart, you must have found those strange things at a glance Magic Numbers, you 're right , This is really Magic Numbers, It is the position of the whole chessboard relative to the window through a little fine adjustment .
Be careful ： These data are only available in Windows10 Pass the next test , If in another Windows Under the system , The correctness of the relative position is not guaranteed , Because the old version of the system may have different widths of the form border .
All right. , We have the image of the chessboard , The next step is to segment the image of each mine block ~
- 02 Thunder block segmentation
Before thunder block segmentation , We need to know the size of the thunder block and its frame size in advance . After the author's measurement , stay ms_arbiter Next , The size of each mine block is 16px*16px.
I know the size of the thunder block , We can cut each thunder block . First of all, we need to know the number of vertical and horizontal mines .
block_width, block_height = 16, 16
blocks_x = int((right - left) / block_width)
blocks_y = int((bottom - top) / block_height)after , We build a two-dimensional array to store the image of each mine block , And image segmentation , Save in the previously created array .
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)Capture the entire image 、 The divided parts are encapsulated into a library , Call at any time OK La ~ In the author's implementation , We encapsulated this part into imageProcess.py, The function get_frame() Used to complete the above image acquisition 、 Segmentation process .
- 03 Thunder block identification
This part may be the most important part of the whole project besides the minesweeping algorithm itself . The author uses a relatively simple feature when detecting lightning blocks , Efficient and can meet the requirements .
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 = FalseYou can see , We use the method of reading the central pixel of each thunder block to judge the category of thunder block , And for flag insertion 、 Not clicked 、 It has been clicked but left blank for further judgment . The specific color value is obtained directly by the author , And the color of the screenshot is not compressed , Therefore, it is enough to judge the category by combining the central pixel with other feature points , And achieve high efficiency .
In this project , When we implement it, we use the following annotation method ：
1-8： Representation number 1 To 8
9： It means mine
0： Means to insert a flag
-1： Indicates that... Is not opened
-2： Indicates open but blank
-3： Indicates that it is not any box type in mine sweeping game
In this simple, fast and effective way , We have successfully realized efficient image recognition .
- 04 Implementation of mine sweeping algorithm
This is probably the most exciting part of this article . Here we need to explain the specific idea of mine sweeping algorithm ：
Traverse every mine block that already has a number , Judge whether the number of unopened thunder blocks in the nine palace grid around it is the same as its own number , If they are the same, it indicates that all the surrounding nine palaces are mines , marked .
Traverse each mine block with a number again , Take all unopened thunder blocks within the nine palace grid , Remove landmine blocks that have been marked as mines in the last traversal , Record and click on .
If the above methods cannot continue , Then it means a dead end , Select to randomly click... Among all currently unopened lightning blocks .（ Of course, this method is not optimal , There are better solutions , But the implementation is relatively troublesome ）
The basic minesweeping process is like this , So let's do it ourselves ~
First of all, we need a method that can find out the positions of all squares in the Jiugong grid range of a thunder block . Because of the particularity of mine sweeping game , There is no edge part of Jiugong grid on the four sides of the chessboard , So we need to filter to exclude access that may exceed the boundary .
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)In this part, we delete the core by detecting whether the current thunder block is on each edge of the chessboard （ In the nucleus ,1 For the sake of reservation ,0 To give up ）, After through generate_kernel Function to generate the final coordinates .
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)After completing the generation of the nucleus , We have a piece of thunder that needs to be detected “ Address book ”：to_visit. after , We go through count_unopen_blocks Function to count the number of unopened cells in the surrounding nine palaces , And compare it with the number of the current lightning block , If equal, pass all nine palaces of gnere blocks through mark_as_mine Function to label as mine .
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)The second step in the minesweeping process is also realized by a method similar to the first step . First, use the same method as the first step to generate the core of the mine block to be accessed , After that, the specific mine block position is generated , adopt count_mines Function to obtain the number of all thunder blocks within the nine palace grid , And judge whether all thunder blocks in the current Jiugong grid have been detected .
If it is , Through mark_to_click_block Function to eliminate the landmine blocks that have been marked as mines in the Jiugong grid , And add the remaining safety mine blocks to next_steps In array .
# 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()In the final implementation , The author encapsulates several processes into functions , And through iterate_blocks_number Method to process all thunder blocks with the passed in function , It's kind of similar Python in Filter The role of .
Then the author's job is to judge whether the current mouse position is within the chessboard , If it is , It will automatically start to recognize and click . Specific click part , The author adopts the author as "wp" A copy of the code （ Collected from the Internet ）, It's based on win32api Form message sending work , Then completed the operation of mouse movement and click . The specific implementation is encapsulated in mouseOperation.py in , If you are interested, you can see at the end of the article Github Repo View in .
Author's record
This result , Even the number one in the world has to tremble ！
The last click of this video has met a dead end , Finally, it is done at random
The author also realizes the function of randomly clicking to open the situation at the beginning of the new game , But because it's simpler , So the detailed analysis is not posted here ~
Make a note of ： If it is found during the experiment that there will be thunder pieces blown up , Don't worry about , This is because there is a dead end , It is impossible to infer directly through the algorithm of this project , At this time, the program will randomly click , There is a certain chance of cracking ！
Project complete code /GitHub Address ：
https://github.com/ArtrixTech/BoomMine
Benefit time
We send books to you every month ( Cumulative delivery 428 Multiple copies ）, Those who often leave messages and have familiar faces will have the opportunity ！ This time, I sent out "Python dependent " Books 6 Ben , It's worth reading . The students on the list are as follows ：
This book systematically introduces... From scratch Python Development and practical skills of web crawler and anti crawler , The whole book is divided into 4 piece , The specific contents are arranged as follows .
The first 1 piece ： The basic chapter （ The first 1～3 Chapter ）. Systematically explained Python Construction of crawler and anti crawler development environment 、 General basic knowledge of reptiles and anti reptiles 、Python Programming based .
The first 2 piece ： Reptile （ The first 4～8 Chapter ）. This part explains the relevant knowledge and skills of web crawler , Mainly includes web crawler quick start 、XPath Match web data 、re Regular match data 、WebSocket Data capture 、Scrapy Crawler framework application and development .
The first 3 piece ： Anti reptile （ The first 9～16 Chapter ）. This part explains the relevant knowledge and skills of Web anti crawler , It mainly includes the difference and understanding between reptiles and anti reptiles 、 Anti creeping —Header Information verification 、 Anti creeping —IP Limit 、 Anti creeping — Dynamically render the page 、 Anti creeping — Text confusion 、 Anti creeping — Feature recognition 、 Anti creeping — Verification code recognition 、 Anti creeping —APP Data capture, etc .
The first 4 piece ： Project practice （ The first 17 Chapter ）. This chapter mainly lists 4 A case , Comprehensive explanation Python The actual combat application of crawler and anti crawler project .
This month's list
Congratulations A few friends who often leave messages on the list , Get the above books , Contact your assistant as soon as possible , Provide your express information . Don't worry if you don't get on the list , You can contact your assistant , Consult other benefit opportunities . Code ： Other benefits .
Recommended reading :
introduction : The most complete zero Foundation Python The problem of | Zero Basics 8 Months Python | Actual project | learn Python That's the shortcut
dried food : A short comment on crawling Douban , The movie 《 The rest of us 》 | 38 year NBA Best player analysis | From people's expectation to public praise ！ Tang Dynasty detective 3 disappointing | Laugh at the story of the new Yitian dragon slaying | Riddle answer King ｜ use Python Make a massive sketch of my little sister ｜ Mission impossible is so hot , I use machine learning to make a mini recommendation system movie
Interest : Pinball game | squared paper for practicing calligraphy | Beautiful flowers | Two hundred lines Python《 Cool run every day 》 game !
AI: A robot that can write poetry | Color the picture | Forecast revenue | Mission impossible is so hot , I use machine learning to make a mini recommendation system movie
Gadget : Pdf turn Word, Easily handle forms and watermarks ！ | One touch html Save the page as pdf！| bye PDF Withdrawal charges ！ | use 90 Lines of code create the strongest PDF converter ,word、PPT、excel、markdown、html One click conversion | Make a nail low-cost ticket reminder ！ ｜60 Line of code to do a voice wallpaper switcher, look at my little sister every day ！｜Click to read the original , see B My station 20 A video ！
Data cleaning: processing method of missing value and abnormal value -- operation of filling missing value with regression equation (with Python code)
Operation method of filling mi
