Давно хотел попробовать свои силы в компьютерном зрении и вот этот момент настал. Интереснее обучаться на играх, поэтому тренироваться будем на боте. В статье я попытаюсь подробно расписать процесс автоматизации игры при помощи связки Python + OpenCV.

Ищем цель

Идем на тематический сайт miniclip.com и ищем цель. Выбор пал на цветовую головоломку Coloruid 2 раздела Puzzles, в которой нам необходимо заполнить круглое игровое поле одним цветом за заданное количество ходов.

Выбранным внизу экрана цветом заливается произвольная область, при этом соседние области одного цвета сливаются в единую.

Подготовка

Использовать будем Python. Бот создан исключительно в образовательных целях. Статья рассчитана на новичков в компьютером зрении, каким я сам и являюсь.

Игра находится тут
GitHub бота тут

Для работы бота нам понадобятся следующие модули:

opencv-python
Pillow
selenium

Бот написан и протестирован для версии Python 3.8 на Ubuntu 20.04.1. Устанавливаем необходимые модули в ваше виртуальное окружение или через pip install. Дополнительно для работы Selenium нам понадобится geckodriver для FireFox, скачать можно тут github.com/mozilla/geckodriver/releases

Управление браузером

Мы имеем дело с онлайн-игрой, поэтому для начала организуем взаимодействие с браузером. Для этой цели будем использовать Selenium, который предоставит нам API для управления FireFox. Изучаем код страницы игры. Пазл представляет из себя canvas, которая в свою очередь располагается в iframe.

Ожидаем загрузки фрейма с id = iframe-game и переключаем контекст драйвера на него. Затем ждем canvas. Она единственная во фрейме и доступна по XPath /html/body/canvas.

wait(self.__driver, 20).until(EC.frame_to_be_available_and_switch_to_it((By.ID, "iframe-game")))
self.__canvas = wait(self.__driver, 20).until(EC.visibility_of_element_located((By.XPATH, "/html/body/canvas")))

Далее наша канва будет доступна через свойство self.__canvas. Вся логика работы с браузером сводится к получению скриншота canvas и клику по ней в заданной координате.

Полный код Browser.py:

from selenium import webdriver
from selenium.webdriver.support import expected_conditions as EC
from selenium.webdriver.support.ui import WebDriverWait as wait
from selenium.webdriver.common.by import By

class Browser:
    def __init__(self, game_url):
        self.__driver = webdriver.Firefox()
        self.__driver.get(game_url)
        wait(self.__driver, 20).until(EC.frame_to_be_available_and_switch_to_it((By.ID, "iframe-game")))
        self.__canvas = wait(self.__driver, 20).until(EC.visibility_of_element_located((By.XPATH, "/html/body/canvas")))

    def screenshot(self):
        return self.__canvas.screenshot_as_png

    def quit(self):
        self.__driver.quit()

    def click(self, click_point):
        action = webdriver.common.action_chains.ActionChains(self.__driver)
        action.move_to_element_with_offset(self.__canvas, click_point[0], click_point[1]).click().perform()

Состояния игры

Приступим к самой игре. Вся логика бота будет реализована в классе Robot. Разделим игровой процесс на 7 состояний и назначим им методы для их обработки. Выделим отдельно обучающий уровень. Он содержит большой белый курсор, указывающий куда нажимать, который не позволит корректно распознавать элементы игры.

Приветственный экран
Экран выбора уровня
Выбор цвета на обучающем уровне
Выбор области на обучающем уровне
Выбор цвета
Выбор области
Результат хода

class Robot:
    STATE_START = 0x01
    STATE_SELECT_LEVEL = 0x02
    STATE_TRAINING_SELECT_COLOR = 0x03
    STATE_TRAINING_SELECT_AREA = 0x04
    STATE_GAME_SELECT_COLOR = 0x05
    STATE_GAME_SELECT_AREA = 0x06
    STATE_GAME_RESULT = 0x07

    def __init__(self):
        self.states = {
            self.STATE_START: self.state_start,
            self.STATE_SELECT_LEVEL: self.state_select_level,
            self.STATE_TRAINING_SELECT_COLOR: self.state_training_select_color,
            self.STATE_TRAINING_SELECT_AREA: self.state_training_select_area,
            self.STATE_GAME_RESULT: self.state_game_result,
            self.STATE_GAME_SELECT_COLOR: self.state_game_select_color,
            self.STATE_GAME_SELECT_AREA: self.state_game_select_area,
        }

Для большей стабильности бота будем проверять, успешно ли произошла смена игрового состояния. Если self.state_next_success_condition не вернет True за время self.state_timeout — продолжаем обрабатывать текущее состояние, иначе переключаемся на self.state_next. Также переведем скриншот, полученный от Selenium, в понятный для OpenCV формат.


import time
import cv2
import numpy
from PIL import Image
from io import BytesIO

class Robot:

    def __init__(self):

	# …

	self.screenshot = []
        self.state_next_success_condition = None  
        self.state_start_time = 0  
        self.state_timeout = 0 
        self.state_current = 0 
        self.state_next = 0  

    def run(self, screenshot):
        self.screenshot = cv2.cvtColor(numpy.array(Image.open(BytesIO(screenshot))), cv2.COLOR_BGR2RGB)
        if self.state_current != self.state_next:
            if self.state_next_success_condition():
                self.set_state_current()
            elif time.time() - self.state_start_time >= self.state_timeout
                    self.state_next = self.state_current
            return False
        else:
            try:
                return self.states[self.state_current]()
            except KeyError:
                self.__del__()

    def set_state_current(self):
        self.state_current = self.state_next

    def set_state_next(self, state_next, state_next_success_condition, state_timeout):
        self.state_next_success_condition = state_next_success_condition
        self.state_start_time = time.time()
        self.state_timeout = state_timeout
        self.state_next = state_next

Реализуем проверку в методах обработки состояний. Ждем кнопку Play на стартовом экране и кликаем по ней. Если в течении 10 секунд мы не получили экран выбора уровней, возвращаемся к предыдущему этапу self.STATE_START, иначе переходим к обработке self.STATE_SELECT_LEVEL.


# …

class Robot:
   DEFAULT_STATE_TIMEOUT = 10
   
   # …
 
   def state_start(self):
        # пытаемся получить координату кнопки Play
        # …

        if button_play is False:
            return False
        self.set_state_next(self.STATE_SELECT_LEVEL, self.state_select_level_condition, self.DEFAULT_STATE_TIMEOUT)
        return button_play

    def state_select_level_condition(self):
        # содержит ли скриншот выбор уровней
	# …

Зрение бота

Пороговая обработка изображения

Определим цвета, которые используются в игре. Это 5 игровых цветов и цвет курсора на учебном уровне. COLOR_ALL будем использовать, если нужно найти все объекты, независимо от цвета. Для начала этот случай мы и рассмотрим.

    COLOR_BLUE = 0x01  
    COLOR_ORANGE = 0x02
    COLOR_RED = 0x03
    COLOR_GREEN = 0x04
    COLOR_YELLOW = 0x05
    COLOR_WHITE = 0x06
    COLOR_ALL = 0x07

Для поиска объекта в первую очередь необходимо упростить изображение. Для примера возьмем символ «0» и применим к нему пороговую обработку, то есть отделим объект от фона. На этом этапе нам не важно, какого цвета символ. Для начала переведем изображение в черно-белое, сделав его 1-канальным. В этом нам поможет функция cv2.cvtColor со вторым аргументом cv2.COLOR_BGR2GRAY, который отвечает за перевод в градации серого. Далее производим пороговую обработку при помощи cv2.threshold. Все пиксели изображения ниже определенного порога устанавливаются в 0, все, что выше, в 255. За значение порога отвечает второй аргумент функции cv2.threshold. В нашем случае там может стоят любое число, так как мы используем cv2.THRESH_OTSU и функция сама определит оптимальный порог по методу Оцу на основе гистограммы изображения.

image = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
_, thresh = cv2.threshold(image, 0, 255, cv2.THRESH_OTSU)

Цветовая сегментация

Дальше интереснее. Усложним задачу и найдем все символы красного цвета на экране выбора уровней.

По умолчанию, все изображения OpenCV хранит в формате BGR. Для цветовой сегментации больше подходит HSV (Hue, Saturation, Value — тон, насыщенность, значение). Ее преимущество перед RGB заключается в том, что HSV отделяет цвет от его насыщенности и яркости. Цветовой тон кодируется одним каналом Hue. Возьмем для примера салатовый прямоугольник и будем постепенно уменьшать его яркость.

В отличии от RGB, в HSV данное преобразование выглядит интуитивно — мы просто уменьшаем значение канала Value или Brightness. Тут стоит обратить внимание на то, что в эталонной модели шкала оттенков Hue варьируется в диапазоне 0-360°. Наш салатовый цвет соответствует 90°. Для того, чтобы уместить это значение в 8 битный канал, его следует разделить на 2.
Сегментация цветов работает с диапазонами, а не с одним цветом. Определить диапазон можно опытным путем, но проще написать небольшой скрипт.

import cv2
import numpy as numpy

image_path = "tests_data/SELECT_LEVEL.png"
hsv_max_upper = 0, 0, 0
hsv_min_lower = 255, 255, 255


def bite_range(value):
    value = 255 if value > 255 else value
    return 0 if value < 0 else value


def pick_color(event, x, y, flags, param):
    if event == cv2.EVENT_LBUTTONDOWN:
        global hsv_max_upper
        global hsv_min_lower
        global image_hsv
        hsv_pixel = image_hsv[y, x]
        hsv_max_upper = bite_range(max(hsv_max_upper[0], hsv_pixel[0]) + 1), \
                        bite_range(max(hsv_max_upper[1], hsv_pixel[1]) + 1), \
                        bite_range(max(hsv_max_upper[2], hsv_pixel[2]) + 1)
        hsv_min_lower = bite_range(min(hsv_min_lower[0], hsv_pixel[0]) - 1), \
                        bite_range(min(hsv_min_lower[1], hsv_pixel[1]) - 1), \
                        bite_range(min(hsv_min_lower[2], hsv_pixel[2]) - 1)
        print('HSV range: ', (hsv_min_lower, hsv_max_upper))
        hsv_mask = cv2.inRange(image_hsv, numpy.array(hsv_min_lower), numpy.array(hsv_max_upper))
        cv2.imshow("HSV Mask", hsv_mask)


image = cv2.imread(image_path)
cv2.namedWindow('Original')
cv2.setMouseCallback('Original', pick_color)
image_hsv = cv2.cvtColor(image, cv2.COLOR_BGR2HSV)
cv2.imshow("Original", image)
cv2.waitKey(0)
cv2.destroyAllWindows()

Запустим его с нашим скриншотом.

Кликаем по красному цвету и смотрим на полученную маску. Если вывод нас не устраивает — выбираем оттенкам красного, увеличивая диапазон и площадь маски. Работа скрипта основана на функции cv2.inRange, которая работает как цветовой фильтр и возвращает пороговое изображение для заданного цветового диапазона.
Остановимся на следующих диапазонах:


    COLOR_HSV_RANGE = {
   COLOR_BLUE: ((112, 151, 216), (128, 167, 255)),
   COLOR_ORANGE: ((8, 251, 93), (14, 255, 255)),
   COLOR_RED: ((167, 252, 223), (171, 255, 255)),
   COLOR_GREEN: ((71, 251, 98), (77, 255, 211)),
   COLOR_YELLOW: ((27, 252, 51), (33, 255, 211)),
   COLOR_WHITE: ((0, 0, 159), (7, 7, 255)),
}

Поиск контуров

Вернемся к нашему экрану выбора уровней. Применим цветовой фильтр красного диапазона, который мы только что определили, и передадим найденный порог в cv2.findContours. Функция найдет нам контуры красных элементов. Укажем вторым аргументом cv2.RETR_EXTERNAL — нам нужны только внешние контуры, и третьим cv2.CHAIN_APPROX_SIMPLE — нас интересуют прямые контуры, экономим память и храним только их вершины.

thresh = cv2.inRange(image, self.COLOR_HSV_RANGE[self.COLOR_RED][0], self.COLOR_HSV_RANGE[self.COLOR_RED][1])
contours, _ = cv2.findContours(thresh, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE

Удаление шума

Полученные контуры содержат много шума от фона. Чтобы убрать его воспользуемся свойством наших цифр. Они состоят из прямоугольников, которые параллельны осям координат. Перебираем все контуры и вписываем каждый в минимальный прямоугольник при помощи cv2.minAreaRect. Прямоугольник определяется 4 точками. Если наш прямоугольник параллелен осям, то одна из координат для каждой пары точек должны совпадать. Значит у нас будет максимум 4 уникальных значения, если представить координаты прямоугольника как одномерный массив. Дополнительно отфильтруем слишком длинные прямоугольники, где соотношение сторон больше, чем 3 к 1. Для этого найдем их ширину и длину при помощи cv2.boundingRect.


squares = []
        for cnt in contours:
            rect = cv2.minAreaRect(cnt)
            square = cv2.boxPoints(rect)
            square = numpy.int0(square)
            (_, _, w, h) = cv2.boundingRect(square)
            a = max(w, h)
            b = min(w, h)
            if numpy.unique(square).shape[0] <= 4 and a <= b * 3:
                squares.append(numpy.array([[square[0]], [square[1]], [square[2]], [square[3]]]))

Объединение контуров

Уже лучше. Теперь нам нужно объединить найденные прямоугольники в общий контур символов. Нам понадобится промежуточное изображение. Создадим его при помощи numpy.zeros_like. Функция создает копию матрицы image с сохранением ее формы и размера, затем заполняет ее нулями. Другими словами, мы получили копию нашего оригинального изображения, залитую черным фоном. Переводим его в 1-канальное и наносим найденные контуры при помощи cv2.drawContours, заполнив их белым цветом. Получаем бинарный порог, к которому можно применить cv2.dilate. Функция расширяет белую область, соединяя отдельные прямоугольники, расстояние между которыми в пределах 5 пикселей. Еще раз вызываем cv2.findContours и получаем контуры красных цифр.


        image_zero = numpy.zeros_like(image)
        image_zero = cv2.cvtColor(image_zero, cv2.COLOR_BGR2RGB)
        cv2.drawContours(image_zero, contours_of_squares, -1, (255, 255, 255), -1)
	  _, thresh = cv2.threshold(image_zero, 0, 255, cv2.THRESH_OTSU)
	  kernel = numpy.ones((5, 5), numpy.uint8)
        thresh = cv2.dilate(thresh, kernel, iterations=1)	
        dilate_contours, _ = cv2.findContours(thresh, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)

Оставшийся шум отфильтруем по площади контуров при помощи cv2.contourArea. Убираем все, что занимает меньше 500 пикселей².

digit_contours = [cnt for cnt in digit_contours if cv2.contourArea(cnt) > 500]

Вот теперь отлично. Реализуем все вышеописанное в нашем классе Robot.


# ...

class Robot:
     
    # ...
    
    def get_dilate_contours(self, image, color_inx, distance):
        thresh = self.get_color_thresh(image, color_inx)
        if thresh is False:
            return []
        kernel = numpy.ones((distance, distance), numpy.uint8)
        thresh = cv2.dilate(thresh, kernel, iterations=1)
        contours, _ = cv2.findContours(thresh, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
        return contours

    def get_color_thresh(self, image, color_inx):
        if color_inx == self.COLOR_ALL:
            image = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
            _, thresh = cv2.threshold(image, 0, 255, cv2.THRESH_OTSU)
        else:
            image = cv2.cvtColor(image, cv2.COLOR_BGR2HSV)
            thresh = cv2.inRange(image, self.COLOR_HSV_RANGE[color_inx][0], self.COLOR_HSV_RANGE[color_inx][1])
        return thresh
			
	def filter_contours_of_rectangles(self, contours):
        squares = []
        for cnt in contours:
            rect = cv2.minAreaRect(cnt)
            square = cv2.boxPoints(rect)
            square = numpy.int0(square)
            (_, _, w, h) = cv2.boundingRect(square)
            a = max(w, h)
            b = min(w, h)
            if numpy.unique(square).shape[0] <= 4 and a <= b * 3:
                squares.append(numpy.array([[square[0]], [square[1]], [square[2]], [square[3]]]))
        return squares

    def get_contours_of_squares(self, image, color_inx, square_inx):
        thresh = self.get_color_thresh(image, color_inx)
        if thresh is False:
            return False
        contours, _ = cv2.findContours(thresh, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
        contours_of_squares = self.filter_contours_of_rectangles(contours)
        if len(contours_of_squares) < 1:
            return False
        image_zero = numpy.zeros_like(image)
        image_zero = cv2.cvtColor(image_zero, cv2.COLOR_BGR2RGB)
        cv2.drawContours(image_zero, contours_of_squares, -1, (255, 255, 255), -1)
        dilate_contours = self.get_dilate_contours(image_zero, self.COLOR_ALL, 5)
        dilate_contours = [cnt for cnt in dilate_contours if cv2.contourArea(cnt) > 500]
        if len(dilate_contours) < 1:
            return False
        else:
            return dilate_contours

Распознание цифр

Добавим возможность распознания цифр. Зачем нам это нужно? ~~Потому что мы можем~~ . Данная возможность не является обязательной для работы бота и при желании ее можно смело вырезать. Но так как мы обучаемся, добавим ее для подсчета набранных очков и для понимания бота, на каком он шаге на уровне. Зная завершающий ход уровня, бот будет искать кнопку перехода на следующий или повтор текущего. Иначе пришлось бы осуществлять их поиск после каждого хода. Откажемся от использования Tesseract и реализуем все средствами OpenCV. Распознание цифр будет построено на сравнении hu моментов, что позволит нам сканировать символы в разном масштабе. Это важно, так как в интерфейсе игры есть разные размеры шрифта. Текущий, где мы выбираем уровень, определим SQUARE_BIG_SYMBOL: 9, где 9 — средняя сторона квадрата в пикселях, из которых состоит цифра. Кадрируем изображения цифр и сохраним их в папке data. В словаре self.dilate_contours_bi_data у нас содержатся эталоны контуров, с которым будет происходить сравнение. Индексом будет название файла без расширения (например «digit_0»).

# …

class Robot:

    # ...

    SQUARE_BIG_SYMBOL = 0x01

    SQUARE_SIZES = {
        SQUARE_BIG_SYMBOL: 9,  
    }

    IMAGE_DATA_PATH = "data/" 

    def __init__(self):

        # ...

        self.dilate_contours_bi_data = {} 
        for image_file in os.listdir(self.IMAGE_DATA_PATH):
            image = cv2.imread(self.IMAGE_DATA_PATH + image_file)
            contour_inx = os.path.splitext(image_file)[0]
            color_inx = self.COLOR_RED
            dilate_contours = self.get_dilate_contours_by_square_inx(image, color_inx, self.SQUARE_BIG_SYMBOL)
            self.dilate_contours_bi_data[contour_inx] = dilate_contours[0]

    def get_dilate_contours_by_square_inx(self, image, color_inx, square_inx):
        distance = math.ceil(self.SQUARE_SIZES[square_inx] / 2)
        return self.get_dilate_contours(image, color_inx, distance)

В OpenCV для сравнения контуров на основе Hu моментов используется функция cv2.matchShapes. Она скрывает от нас детали реализации, принимая на вход два контура и возвращает результат сравнения в виде числа. Чем оно меньше, тем более схожими являются контуры.

cv2.matchShapes(dilate_contour, self.dilate_contours_bi_data['digit_' + str(digit)], cv2.CONTOURS_MATCH_I1, 0)

Сравниваем текущий контур digit_contour со всеми эталонами и находим минимальное значение cv2.matchShapes. Если минимальное значение меньше 0.15, цифра считается распознанной. Порог минимального значения найден опытным путем. Также объединим близко расположенные символы в одно число.

# …

class Robot:

    # …

    def scan_digits(self, image, color_inx, square_inx):
        result = []
        contours_of_squares = self.get_contours_of_squares(image, color_inx, square_inx)
        before_digit_x, before_digit_y = (-100, -100)
        if contours_of_squares is False:
            return result
        for contour_of_square in reversed(contours_of_squares):
            crop_image = self.crop_image_by_contour(image, contour_of_square)
            dilate_contours = self.get_dilate_contours_by_square_inx(crop_image, self.COLOR_ALL, square_inx)
            if (len(dilate_contours) < 1):
                continue
            dilate_contour = dilate_contours[0]
            match_shapes = {}
            for digit in range(0, 10):
                match_shapes[digit] = cv2.matchShapes(dilate_contour, self.dilate_contours_bi_data['digit_' + str(digit)], cv2.CONTOURS_MATCH_I1, 0)
            min_match_shape = min(match_shapes.items(), key=lambda x: x[1])
            if len(min_match_shape) > 0 and (min_match_shape[1] < self.MAX_MATCH_SHAPES_DIGITS):
                digit = min_match_shape[0]
                rect = cv2.minAreaRect(contour_of_square)
                box = cv2.boxPoints(rect)
                box = numpy.int0(box)
                (digit_x, digit_y, digit_w, digit_h) = cv2.boundingRect(box)
                if abs(digit_y - before_digit_y) < digit_y * 0.3 and abs(
                        digit_x - before_digit_x) < digit_w + digit_w * 0.5:
                    result[len(result) - 1][0] = int(str(result[len(result) - 1][0]) + str(digit))
                else:
                    result.append([digit, self.get_contour_centroid(contour_of_square)])
                before_digit_x, before_digit_y = digit_x + (digit_w / 2), digit_y
        return result

На выходе метод self.scan_digits выдаст массив, содержащий распознанную цифру и координату клика по ней. Точкой клика будет центроид ее контура.

# …

class Robot:

    # …

def get_contour_centroid(self, contour):
        moments = cv2.moments(contour)
        return int(moments["m10"] / moments["m00"]), int(moments["m01"] / moments["m00"])

Радуемся полученной распознавалке цифр, но не долго. Hu моменты помимо масштаба инвариантны также к повороту и зеркальности. Следовательно бот будет путать цифры 6 и 9 / 2 и 5. Добавим дополнительную проверку этих символов по вершинам. 6 и 9 будем отличать по правой верхней точке. Если она ниже горизонтального центра, значит это 6 и 9 для обратного. Для пары 2 и 5 проверяем, лежит ли верхняя правая точка на правой границе символа.

if digit == 6 or digit == 9:
    extreme_bottom_point = digit_contour[digit_contour[:, :, 1].argmax()].flatten()
    x_points = digit_contour[:, :, 0].flatten()
    extreme_right_points_args = numpy.argwhere(x_points == numpy.amax(x_points))
    extreme_right_points = digit_contour[extreme_right_points_args]
    extreme_top_right_point = extreme_right_points[extreme_right_points[:, :, :, 1].argmin()].flatten()
    if extreme_top_right_point[1] > round(extreme_bottom_point[1] / 2):
        digit = 6
    else:
        digit = 9
if digit == 2 or digit == 5:
    extreme_right_point = digit_contour[digit_contour[:, :, 0].argmax()].flatten()
    y_points = digit_contour[:, :, 1].flatten()
    extreme_top_points_args = numpy.argwhere(y_points == numpy.amin(y_points))
    extreme_top_points = digit_contour[extreme_top_points_args]
    extreme_top_right_point = extreme_top_points[extreme_top_points[:, :, :, 0].argmax()].flatten()
    if abs(extreme_right_point[0] - extreme_top_right_point[0]) > 0.05 * extreme_right_point[0]:
        digit = 2
    else:
        digit = 5

Анализируем игровое поле

Пропустим тренировочный уровень, он заскриптован по клику на белом курсоре и приступаем к игре.

Представим игровое поле как сеть. Каждая область цвета будет узлом, который связан с граничащими рядом соседями. Создадим класс self.ColorArea, который будет описывать область цвета/узел.

class ColorArea: 
        def __init__(self, color_inx, click_point, contour):
            self.color_inx = color_inx  # индекс цвета
            self.click_point = click_point  # клик поинт области
            self.contour = contour  # контур области
            self.neighbors = []  # индексы соседей

Определим список узлов self.color_areas и список того, как часто встречается цвет на игровом поле self.color_areas_color_count. Кадрируем игровое поле из скриншота канвы.

image[pt1[1]:pt2[1], pt1[0]:pt2[0]]

Где pt1, pt2 – крайние точки кадра. Перебираем все цвета игры и применяем к каждому метод self.get_dilate_contours. Нахождение контура узла аналогично тому, как мы искали общий контур символов, с тем отличием, что на игровом поле отсутствуют шумы. Форма узлов может быть вогнутой или иметь отверстие, поэтому центроид будет выпадать за пределы фигуры и не подходит в качестве координата для клика. Для этого найдем экстремальную верхнюю точку и опустимся на 20 пикселей. Способ не универсальный, но в нашем случае рабочий.

        self.color_areas = []
        self.color_areas_color_count = [0] * self.SELECT_COLOR_COUNT
        image = self.crop_image_by_rectangle(self.screenshot, numpy.array(self.GAME_MAIN_AREA))
        for color_inx in range(1, self.SELECT_COLOR_COUNT + 1):
            dilate_contours = self.get_dilate_contours(image, color_inx, 10)
            for dilate_contour in dilate_contours:
                click_point = tuple(
                    dilate_contour[dilate_contour[:, :, 1].argmin()].flatten() + [0, int(self.CLICK_AREA)])
                self.color_areas_color_count[color_inx - 1] += 1
                color_area = self.ColorArea(color_inx, click_point, dilate_contour)
                self.color_areas.append(color_area)

Связываем области

Будем считать области соседями, если расстояние между их контурами в пределах 15 пикселей. Перебираем каждый узел с каждым, пропуская сравнение, если их цвета совпадают.

        blank_image = numpy.zeros_like(image)
        blank_image = cv2.cvtColor(blank_image, cv2.COLOR_BGR2GRAY)
        for color_area_inx_1 in range(0, len(self.color_areas)):
            for color_area_inx_2 in range(color_area_inx_1 + 1, len(self.color_areas)):
                color_area_1 = self.color_areas[color_area_inx_1]
                color_area_2 = self.color_areas[color_area_inx_2]
                if color_area_1.color_inx == color_area_2.color_inx:
                    continue
                common_image = cv2.drawContours(blank_image.copy(), [color_area_1.contour, color_area_2.contour], -1, (255, 255, 255), cv2.FILLED)
                kernel = numpy.ones((15, 15), numpy.uint8)
                common_image = cv2.dilate(common_image, kernel, iterations=1)
                common_contour, _ = cv2.findContours(common_image, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
                if len(common_contour) == 1:
self.color_areas[color_area_inx_1].neighbors.append(color_area_inx_2)
self.color_areas[color_area_inx_2].neighbors.append(color_area_inx_1)

Ищем оптимальный ход

У нас есть вся информация об игровом поле. Приступим к выбору хода. Для этого нам нужен индекс узла и цвета. Количество вариантов хода можно определить формулой:

Варианты ходов = Количество узлов * Количество цветов — 1

Для предыдущего игрового поля у нас есть 7*(5-1) = 28 вариантов. Их немного, поэтому мы можем перебрать все ходы и выбрать оптимальный. Определим варианты как матрицу
select_color_weights, в которой строкой будет индекс узла, столбцом индекс цвета и ячейкой вес хода. Нам нужно уменьшить количество узлов до одного, поэтому отдадим приоритет областям, цвет которых уникален на игровом поле и которые исчезнут после хода на них. Дадим +10 к весу ко все строке узла с уникальным цветом. Как часто встречается цвет на игровом поле, мы ранее собрали в self.color_areas_color_count

if self.color_areas_color_count[color_area.color_inx - 1] == 1:
   select_color_weight = [x + 10 for x in select_color_weight]

Далее рассмотрим цвета соседних областей. Если у узла есть соседи цвета color_inx, и их количество равно общему количеству данного цвета на игровом поле, назначим +10 к весу ячейки. Это также уберет цвет color_inx с поля.

for color_inx in range(0, len(select_color_weight)):
   color_count = select_color_weight[color_inx]
   if color_count != 0 and self.color_areas_color_count[color_inx] == color_count:
      select_color_weight[color_inx] += 10

Дадим +1 к весу ячейки за каждого соседа одного цвета. То есть если у нас есть 3 красных соседа, красная ячейка получит +3 к весу.

for select_color_weight_inx in color_area.neighbors:
   neighbor_color_area = self.color_areas[select_color_weight_inx]
   select_color_weight[neighbor_color_area.color_inx - 1] += 1

После сбора всех весов, найдем ход с максимальным весом. Определим к какому узлу и к какому цвету он относится.


max_index = select_color_weights.argmax()
self.color_area_inx_next = max_index // self.SELECT_COLOR_COUNT
select_color_next = (max_index % self.SELECT_COLOR_COUNT) + 1
self.set_select_color_next(select_color_next)

Полный код для определения оптимального хода.

# …

class Robot:

    # …

def scan_color_areas(self):
        self.color_areas = []
        self.color_areas_color_count = [0] * self.SELECT_COLOR_COUNT
        image = self.crop_image_by_rectangle(self.screenshot, numpy.array(self.GAME_MAIN_AREA))
        for color_inx in range(1, self.SELECT_COLOR_COUNT + 1):
            dilate_contours = self.get_dilate_contours(image, color_inx, 10)
            for dilate_contour in dilate_contours:
                click_point = tuple(
                    dilate_contour[dilate_contour[:, :, 1].argmin()].flatten() + [0, int(self.CLICK_AREA)])
                self.color_areas_color_count[color_inx - 1] += 1
                color_area = self.ColorArea(color_inx, click_point, dilate_contour, [0] * self.SELECT_COLOR_COUNT)
                self.color_areas.append(color_area)
        blank_image = numpy.zeros_like(image)
        blank_image = cv2.cvtColor(blank_image, cv2.COLOR_BGR2GRAY)
        for color_area_inx_1 in range(0, len(self.color_areas)):
            for color_area_inx_2 in range(color_area_inx_1 + 1, len(self.color_areas)):
                color_area_1 = self.color_areas[color_area_inx_1]
                color_area_2 = self.color_areas[color_area_inx_2]
                if color_area_1.color_inx == color_area_2.color_inx:
                    continue
                common_image = cv2.drawContours(blank_image.copy(), [color_area_1.contour, color_area_2.contour],
                                                -1, (255, 255, 255), cv2.FILLED)
                kernel = numpy.ones((15, 15), numpy.uint8)
                common_image = cv2.dilate(common_image, kernel, iterations=1)
                common_contour, _ = cv2.findContours(common_image, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
                if len(common_contour) == 1:
                    self.color_areas[color_area_inx_1].neighbors.append(color_area_inx_2)
                    self.color_areas[color_area_inx_2].neighbors.append(color_area_inx_1)

    def analysis_color_areas(self):
        select_color_weights = []
        for color_area_inx in range(0, len(self.color_areas)):
            color_area = self.color_areas[color_area_inx]
            select_color_weight = numpy.array([0] * self.SELECT_COLOR_COUNT)
            for select_color_weight_inx in color_area.neighbors:
                neighbor_color_area = self.color_areas[select_color_weight_inx]
                select_color_weight[neighbor_color_area.color_inx - 1] += 1
            for color_inx in range(0, len(select_color_weight)):
                color_count = select_color_weight[color_inx]
                if color_count != 0 and self.color_areas_color_count[color_inx] == color_count:
                    select_color_weight[color_inx] += 10
            if self.color_areas_color_count[color_area.color_inx - 1] == 1:
                select_color_weight = [x + 10 for x in select_color_weight]
            color_area.set_select_color_weights(select_color_weight)
            select_color_weights.append(select_color_weight)
        select_color_weights = numpy.array(select_color_weights)
        max_index = select_color_weights.argmax()
        self.color_area_inx_next = max_index // self.SELECT_COLOR_COUNT
        select_color_next = (max_index % self.SELECT_COLOR_COUNT) + 1
        self.set_select_color_next(select_color_next)

Добавим возможность перехода между уровнями и радуемся результату. Бот работает стабильно и проходит игру за одну сессию.

Вывод

Созданный бот не несет никакой практической пользы. Но автор статьи искренне надеется, что подробное описание базовых принципов OpenCV поможет новичкам разобраться с данной библиотекой на начальном этапе.

Пишем бот для пазл игры на Python