Hello everyone , Welcome to Programming classroom ！
The case shared with you today is Python+OpenCV Automatic mine sweeping is realized , And broke the human world record .（ Of course
That doesn't count ）
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 sweeping in China
One 、 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 , From the past to the present, there are still
Its unique charm ： Fast paced, high-precision mouse operation requirements 、 Quick response 、 Record breaking pleasure , These are brought by mine sweeping to mine friends 、 It only belongs to minesweeping
The unique excitement of .
Before preparing to make a set of mine sweeping automation software , You need to prepare the following tools / Software / Environmental Science
1.Python3 Environmental Science - recommend 3.6 Or above [ More recommend Anaconda3, Many of the following dependent libraries do not need to be installed ]
2.numpy Dependency Library [ if there be Anaconda There is no need to install ]
3.PIL Dependency Library [ if there be Anaconda There is no need to install ]
4.opencv-python
5.win32gui、win32api Dependency Library
6. Support Python Of IDE [ Optional , If you can stand writing programs with a text editor ]
· 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 ~
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
in , 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 , I have a general thought in my heart
road .
For this project , The general development process is like this ：
1. Complete the form content interception part
2. Complete the thunder block segmentation part
3. Complete the part of mine block type identification
4. Complete the minesweeping algorithm
All right. , Now that we have an idea , Then roll up your sleeves and work hard ！
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++ have to
To 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 be able to normally obtain
Handle to form .
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 ImageGrab
Then 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 through a little bit of fine-tuning that we get
The position of the entire chessboard relative to the form .
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
Form borders of different widths .
The orange area is what we need
All right. , We have the image of the chessboard , The next step is to segment the image of each mine block ~
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 .
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 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] = -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
You 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 is blank
Made a further judgment . The specific color value is obtained directly by the author , And the color of the screenshot is not compressed , So the center pixel is combined with other feature points to
It is enough to judge the category , 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 .
This is probably the most exciting part of this article . Here we need to explain the specific idea of mine sweeping algorithm ：
1. 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 means that the surrounding nine palaces
There are all mines in the area , marked .
2. 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 point
open .
3. 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 , On the four sides of the chessboard, there are no nine palaces
Of the edge part of , 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 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)
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 = 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)
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 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)
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 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()
In the final implementation , The author encapsulates several processes into functions , And through iterate_blocks_number Method to use the passed in function for all mine blocks
To process , 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 is "wp" A copy of the code （ Collected from the Internet ）, It's based on win32api Form message sending work , And then completed the mouse movement and click operation
do . 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 , There is no way to enter... Through the algorithm of this project
Line directly infers , At this time, the program will randomly click , There is a certain chance of cracking ！
