Use PyAutoGUI to play Two Turn Puzzle

I've been playing sumikko farm recently, and it has an activity related to the two turn puzzle. The details are as follows:

The rules of the game are also very simple, which is to connect two identical patterns, but make sure that there are no any other patterns in the connection path and there can be at most two turns.

I racked my brains to play puzzle for a day to do this activity. But in a trance, I suddenly realized that I am a programmer, why not write a script to play?

Preparation stage

First of all, we can't do some obviously illegal behavior such as changing data. Then we can only simulate playing by ourself. At this time, I thought of Python's pyautogui library. PyAutoGUI lets your Python scripts control the mouse and keyboard to automate interactions with other applications. This is in line with our needs. The next thing I have to do is to directly array the puzzle gameboard, and then run the solution!

gameboard

I used a screenshot tool to find the top left and bottom right corners of the puzzle board, and used [pillow](https://python-pillow.org/) to take screenshots. The specific code is as follows

from PIL import Image, ImageGrab
IMAGEPOS1 = (294, 453)
IMAGEPOS2 = (1240, 969)
COL = 11
ROW = 6
MAX_TURN = 2
BOXES = 35
PIC_WIDTH = (IMAGEPOS2[0] - IMAGEPOS1[0]) / COL
PIC_HEIGHT = (IMAGEPOS2[1] - IMAGEPOS1[1]) / ROW
image = ImageGrab.grab(bbox=(IMAGEPOS1[0], IMAGEPOS1[1], IMAGEPOS2[0], IMAGEPOS2[1]))

Next, split each small image directly according to rows and columns

minigame_board = [[-1] * (COL + 2) for _ in range(ROW + 2)]
for i in range(ROW):
  for j in range(COL):
    small_image = image.crop((j * PIC_WIDTH, i * PIC_HEIGHT, (j + 1) * PIC_WIDTH, (i + 1) * PIC_HEIGHT))

Then we need to compare each image and group the same type.

Difficulty 1: Same type of items

Originally I was going to use dhash (reference), because dhash is good for finding exact duplicates and near duplicates. However, I used an emulator to play on my phone + used a screenshot tool to manually find the gameboard, which resulted in each small picture not fitting perfectly, and their margins were slightly different. This made dhash completely unusable.

Solution:

Use template matching of opencv-python. But this brings a lot of work. I need to manually trim each type of image to ensure that each image can be matched. The code is as follows:

import cv2
import numpy as np
img = cv2.cvtColor(np.array(img), cv2.COLOR_RGB2BGR)
template = cv2.cvtColor(np.array(template), cv2.COLOR_RGB2BGR)
res = cv2.matchTemplate(img, template, cv2.TM_CCOEFF_NORMED)
min_val, max_val, min_loc, max_loc = cv2.minMaxLoc(res)

In this way, for each small image, I only need to compare max_val, and the one with the highest max_val is naturally matched. Just when I was excitedly preparing to write the solution, I found another problem.

Difficulty 2: Same model, different color

In the puzzle, many characters have the same model and relatively similar colors, and they cannot be distinguished when compared.

Solution:

After searching for a while, I finally decided to compare the colors again.

match_area = img[max_loc[1]:max_loc[1]+template.shape[0], max_loc[0]:max_loc[0]+template.shape[1]]
mean1 = cv2.mean(cv2.cvtColor(match_area, cv2.COLOR_BGR2HSV))[:3]
mean2 = cv2.mean(cv2.cvtColor(template, cv2.COLOR_BGR2HSV))[:3]
color_diff = np.linalg.norm(np.array(mean1) - np.array(mean2))

Here, we use the return value of matchTemplate to find the most matching part of the image, and cut out this part to compare with template. The template with the lowest color_diff is what we want

So after some operations, we can finally find the corresponding template for each small image, and then we give the template an id, so that each small image can be represented by a number.

Solution

Originally, I wrote bfs, but it runs too slowly. It is estimated that the time complexity is at least2^{30+}. So I decided to do it "brute force".

First, we record the corresponding positions of each template. Secondly, we need a function to determine whether two points can be connected. The code is as follows:

def move(board, st, ed):
  directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
  def dfs(x, y, turn, dir):
    if x < 0 or x >= ROW + 2 or y < 0 or y >= COL + 2 or turn > MAX_TURN: 
      return False
    if (x, y) == ed:
      board[st[0]][st[1]] = -1
      board[ed[0]][ed[1]] = -1
      return True
    if board[x][y] == BOXES or board[x][y] != -1:  
      return False
    for next in directions:  
      if next == dir:  
        res = dfs(x + next[0], y + next[1], turn, next)  
      else:
        res = dfs(x + next[0], y + next[1], turn + 1, next)
      if res:
        return True 
    return False
  for dir in directions:
    if dfs(st[0] + dir[0], st[1] + dir[1], 0, dir):
      return True
  return False

Here we pass in the starting point and the end point, and start in four directions, using dfs to determine whether we can find the path between two points it in the limit of turn.

After writing it, we only need to add some pyautogui click operations to start running! For example:

import pyautogui
def click(x, y):
  real_x = IMAGEPOS1[0] + x * PIC_WIDTH + PIC_WIDTH / 2
  real_y = IMAGEPOS1[1] + y * PIC_HEIGHT + PIC_HEIGHT / 2
  pyautogui.moveTo(real_x, real_y, duration=0.1)
  # pyautogui.sleep(0.2)
  pyautogui.click()

For example, we may need to click an icon (but we don’t know when the icon will appear):

try:
  ok_pos = pyautogui.locateCenterOnScreen('./img/ok.png')
  if ok_pos:
    pyautogui.click(ok_pos)
except:
  pass  

For specific code, please refer to two turn puzzle solver.