Automatic minesweeping is realized with Python+OpenCV, breaking the world record. Let's take a look at the effect first.
Intermediate - 0.74 sec 3BV/S=60.81
I believe many people have long known that there is such a classic game (graphics card test) play (software) as mine sweeping, and many people have heard of China's Lei Sheng. It is also the top name of Guo Weijia, who ranks first in mine sweeping in China and second in the world. As a classic game born in the era of Windows 9x, mine sweeping still has its unique charm from the past to the present: fast-paced, high-precision mouse operation requirements, fast response ability and record breaking pleasure. These are the unique excitement brought by mine sweeping to mine friends and only belong to mine sweeping.
▍ 0x00 preparation
Before preparing to make a set of mine sweeping automation software, you need to prepare the following tools / software / environment
-Development environment
- Python 3 environment - 3.6 or above is recommended [Anaconda3 is more recommended, and many of the following dependent libraries do not need to be installed]
- numpy dependent library [no installation if Anaconda is available]
- PIL dependent library [no installation if Anaconda is available]
- opencv-python
- win32gui and win32api dependent Libraries
- IDE supporting Python [optional, if you can stand writing programs with a text editor]
-Mine sweeping software
·Minesweeper Arbiter (MS arbiter must be used for mine clearance!)
Well, then our preparations have been completed! Let's start~
▍ 0x01 implementation 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. Only in this way can we ensure that in the process of doing this, we should think carefully as much as possible, so as to have a good result in the end. We should also try our best to have a general idea in mind before we officially start development.
For this project, the general development process is as follows:
- Complete the form content interception section
- Complete lightning block segmentation
- Complete the mine block type identification part
- Complete minesweeping algorithm
Well, now that we have an idea, roll up our sleeves and work hard!
-01 form interception
In fact, for this project, form interception is a logically simple but troublesome part to implement, and it is also an essential part. We got the following two information through Spy + +
class_name = "TMain" title_name = "Minesweeper Arbiter "
- ms_arbiter.exe's main form category is "TMain"
- ms_arbiter.exe's main form name is "Minesweeper Arbiter"
Notice? There is a space after the name of the main form. It is this space that bothers the author for a while. Only by adding this space can win32gui get the handle of the form normally.
The project uses Win32 GUI to obtain 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 intercept the checkerboard of the minesweeping interface through PIL.
We need to import the PIL library first
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 Magic Numbers at a glance. Yes, this is indeed Magic Numbers, which is the position of the whole chessboard relative to the form through a little fine adjustment.
Note: These data only pass the test under Windows10. If they are under other Windows systems, the correctness of the relative position is not guaranteed, because the old version of the system may have window borders with different widths.
The orange area is what we need
Well, we have the image of the chessboard. The next step is to segment the image of each mine block~
-02 lightning block segmentation
Before segmentation, we need to know the size of the thunder block and its frame size in advance. After the author's measurement, in MS_ Under the arbiter, the size of each lightning block is 16px*16px.
Knowing the size of the thunder block, we can cut each thunder block. First, we need to know the number of lightning blocks in the horizontal and vertical directions.
block_width, block_height = 16, 16 blocks_x = int((right - left) / block_width) blocks_y = int((bottom - top) / block_height)
After that, we establish a two-dimensional array to store the image of each mine block, segment the image and save it in the previously established 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)
Encapsulate the whole image acquisition and segmentation part into a library and call it at any time. In the author's implementation, we encapsulate this part into ImageProcess Py, where the function get_frame() is used to complete the above image acquisition and segmentation process.
-03 lightning block identification
This part may be the most important part of the whole project except the minesweeping algorithm itself. The author uses simple features in mine block detection, which is 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 = False
It can be seen that we use the method of reading the central point pixel of each lightning block to judge the category of lightning block, and make further judgment for the situations of flag insertion, not clicking, clicking but blank, etc. The specific color value is obtained directly by the author, and the color of the screenshot has not been compressed, so it is enough to judge the category through the central pixel combined with other feature points, and achieve high efficiency.
In this project, we adopt the following annotation methods when implementing:
- 1-8: numbers 1 to 8
- 9: It means mines
- 0: Flag insertion
- -1: Indicates that it is not open
- -2: Indicates open but blank
- -3: Indicates that it is not any box type in the minesweeping game
Through 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 each mine block that has a number, and judge whether the number of mine blocks that have not been opened in the surrounding Jiugong grid is the same as its own number. If the number is the same, it indicates that all mines in the surrounding Jiugong grid are marked.
- Traverse each mine block with numbers again, take all mine blocks that are not opened within the Jiugong grid, remove the mine blocks that have been marked as mines in the last traverse, record and click on.
- If the above methods cannot be continued, it indicates that a dead end has been encountered. Choose to click randomly among all currently unopened lightning blocks. (of course, this method is not optimal. There are better solutions, but it is relatively troublesome to implement.)
This is the basic minesweeping process. Let's implement it ourselves~
First of all, we need a method that can find out the positions of all blocks in the Jiugong grid range of a thunder block. Because of the particularity of the minesweeping game, there is no edge part of the Jiugong grid on the four sides of the chessboard, so we need to filter out visits 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 at each edge of the chessboard (in the core, 1 is reserved and 0 is discarded), and then 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 core, we have an "address book" of thunder blocks that need to be detected: to_visit. After that, we passed count_ unopen_ The blocks function is used to count the number of unopened thunder blocks in the surrounding Jiugong grid range, and compare them with the number of current thunder blocks. If they are equal, all thunder blocks in Jiugong grid will pass 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, and then generate the specific mine block location through count_mines function to obtain the number of all thunder blocks in the Jiugong grid, and judge whether all thunder blocks in the current Jiugong grid have been detected.
If yes, mark_to_click_block function to eliminate the mine blocks that have been marked as mines in the Jiugong grid, and add the remaining safety mine blocks to next_steps 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, which can be implemented through iterate_blocks_number method to process all thunder blocks with the passed in function, which is a bit similar to the function of Filter in Python.
After that, the author's work is to judge whether the current mouse position is within the chessboard. If so, it will automatically start to recognize and click. For the specific click part, the author adopts a code (collected from the Internet) of "wp", which realizes the window message sending based on Win32 API, and then completes the operation of mouse movement and click. The specific implementation is encapsulated in Mouseoperation Py, you can check it in Github Repo at the end of the article.
That's all for today's content. Xiaobian finally prepared a python gift bag [Jia junyang: 419693945] to help you learn better!
