It broke the world record by 0.74 seconds and realized automatic minesweeping with Python

Automatic minesweeping is realized with Python+OpenCV, breaking the world record. Let's take a look at the effect first.

Intermediate - 0.74 seconds 3BV/S=60.81

I believe many people have known for a long time 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

  1. 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]

  2. numpy dependent library [no installation required if Anaconda is available]

  3. PIL dependent library [no installation if Anaconda is available]

  4. opencv-python

  5. win32gui and win32api dependent Libraries

  6. 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 achieve a good result in the end. We should also try our best to have a general idea in mind before we officially start the development.

For this project, the general development process is as follows:

  1. Complete the form content interception section

  2. Complete the lightning block segmentation

  3. Complete the part of mine block type identification

  4. 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. The main form category of exe 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.

In this project, win32gui is used 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 += 15top += 101right -= 15bottom -= 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 it is 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_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)

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 adopts relatively 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
 # 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] = -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] = -3self.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 screen shot 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 mine sweeping 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:

  1. 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.

  2. Traverse each mine block with numbers again, take all the mine blocks that have not been opened within the nine palace grid, remove the mine blocks that have been marked as mines in the last traverse, record and click.

  3. If the above methods cannot be continued, it indicates that a dead end has been encountered. Choose to click randomly among all the 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 by 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 the minesweeping game, there is no edge part of the nine palace 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 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 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 = 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 core, we have an "address book" of mine blocks that need to be detected: to_visit. After that, we passed count_ unopen_ The blocks function is used to count the unopened number of the surrounding Jiugong grid, and compare it with the current number of thunder blocks. If it is 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 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, 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 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 can use 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 sending of window message 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.

Finally, I wish you progress every day!! The most important thing to learn Python is mentality. We are bound to encounter many problems in the process of learning. We may not be able to solve them if we want to break our head. This is normal. Don't rush to deny yourself and doubt yourself. If you have difficulties in learning at the beginning and want to find a python learning and communication environment, you can join us to receive learning materials and discuss together.



Keywords: Python Back-end

Added by gwizz on Tue, 15 Feb 2022 04:57:11 +0200