use Python+OpenCV Automatic mine sweeping is realized , Break the world record , Let's take a look at the effect 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 ！）
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 += 15top += 101right -= 15bottom -= 43rect = (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 .
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 ~
- 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, 16blocks_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_heightx2, 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)
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# 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] = -1elif self.equal(block_color, self.rgb_to_bgr((0, 0, 255))):self.blocks_num[x][y] = 1elif self.equal(block_color, self.rgb_to_bgr((0, 128, 0))):self.blocks_num[x][y] = 2elif self.equal(block_color, self.rgb_to_bgr((255, 0, 0))):self.blocks_num[x][y] = 3elif self.equal(block_color, self.rgb_to_bgr((0, 0, 128))):self.blocks_num[x][y] = 4elif self.equal(block_color, self.rgb_to_bgr((128, 0, 0))):self.blocks_num[x][y] = 5elif self.equal(block_color, self.rgb_to_bgr((0, 128, 128))):self.blocks_num[x][y] = 6elif 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] = 9elif self.equal(block[5, 8], self.rgb_to_bgr((255, 0, 0))):# Is flagself.blocks_num[x][y] = 0else:self.blocks_num[x][y] = 7elif 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 = Falseif 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 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 - 1ls.append((loc_y + rel_y, loc_x + rel_x))return lskernel_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 mapto_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 countdef 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]] = 1unopen_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 countmines_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 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 .
Finally, I wish you progress every day ！！ Study Python The most important thing is mentality . We are bound to encounter many problems in the process of learning , Maybe you can't solve it if you want to break your head . It's all normal , Don't rush to deny yourself , Doubt yourself . If you have difficulties in learning at the beginning , Looking for one python Learning communication environment , You can join us , Get the learning materials 、 Discuss together .
