#дополненная реальность #комбинаторика #дискретная математика

Существует одна очень остроумная настольная игра. Называется Set. Это игра на внимание. Достоинство этой игры в том, что она для неограниченного количества игроков. Вот так она выглядит.

У set есть ещё вариация: игра котики.


Там признаки не фигуры, цвет, количество и заполнение, а - головной убор, очки, фотоаппарат.

В чем проблема?

Бывает так, что вот вы собрались сыграть в Set и никто не видит сет. А он на самом деле есть.

Решением проблемы был бы программно-аппаратный комплекс для автоматического нахождения сета!

Я решил заняться его конструированием.

Каков план?

Идея очень проста. Мысль в следующем...

1--Каждой карточке из игры Set поставить в соответствие натуральное число. Буквально один байт на карточку.

2--Натуральное число преобразовать в DataMatrix код.

3--Код распечатать на наклейке.

4--Наклейки c DataMatrix кодами приклеить на обратную сторону каждой карточки в игре Set. Это 81 наклейка.

5--Соединить считыватель QR кодов с микроконтроллером по UART.

6--Написать микроконтроллерную прошивку, которая находит все Set(ы) перебором и печатает в UART решение.

Как видно, план простой, а значит хороший. Ибо в сложном плане что-то может сломаться и пойти не так.

Аппаратная часть

Hardware первично, software вторично. Поэтому надо подготовить аппаратную часть.

Во-первых экземпляр игры Set надо дооснастить. Надо сгенерировать 81 DataMatrix код чтобы установить его на каждой карточке из колоды. Для этого я написал программную смесь, которая воплощает вот такой конвейер.

Каждая карточка однозначно кодируется 8-ю битами.

номера
битов

количество
бит

параметр

варианты

1

1:0

2

количество

1, 2, 3

2

3:2

2

заполнение

пустой, сплошной, полосатый

3

5:4

2

цвет

фиолетовый, красный, зелёный

4

7:6

2

фигура

волна, ромб, овал

Тут 8-битный код карты преобразуется в бинарное представление DataMatrix кода (100 бит). Для генерации кода я скачал сорцы на Си из GitHub.
Затем запускается мой самописный код генератор Graphviz кода и компонуется черно-белая плитка на языке Graphviz. На финише текстовый *.gv файл утилитой dot.exe преобразуется в *.svg. И так для 81 случаев. Получается 81 *.svg файлов. Кидает *.svg на USB flash(ку) и относим в ближайшую типографию и просим распечатать их на клеящейся бумаге. Каждый код со стороной 4 см.

Самой утомительной частью этого проекта было как раз нанести DataMatrix коды на каждую карточку. Это надо было сделать очень внимательно без ошибок. Иначе всё пойдёт прахом. Я наклеивал эти 81 наклейку порядка 3 часов.

Вообще лично мне не понятно, почему производители игры set не печатают QR код или штрих код на обороте карточки, который бы давал информацию про эту карточку. Это было бы логично и помогло при автоматической сортировке этих карточек на производстве. Это же касается всех других настольных игр, где есть какие-либо карточки.

В качестве считывателя QR кодов я купил отдельный модуль GM67.

Чтобы модуль переключился в режим UART 9600 bit/s надо просканировать вот этот код.

Теперь осталось соединить агрегаты вот по такой схеме.

Программу для вычисления расположения сета я написал для учебно-тренировочной электронной платы AT-Start-F437 с ARM-Cortex-M4 микроконтроллером AT32F437ZM на борту.

Oрудие Победы в игре Set
Oрудие Победы в игре Set

Программная часть

В качестве языка программирования на котором решать задачу я выбрал язык программирования Си, компилятор GCC, систему сборки Make. Всё это абсолютно бесплатно скачивается из интернета.

Бизнес логику игры я сперва отладил на DeskTop PC, как Windows консольное приложение. Далее пересобрал тот же самый код для микропроцессора ARM Cortex-M4.

Вот код основного программного компонента - решателя игры Set
#include "set_game.h"

#include <string.h>
#include <stdlib.h>

#include "debug_info.h"
#include "log.h"
#include "code_generator.h"
#ifdef HAS_GM67
#include "gm67_drv.h"
#endif

COMPONENT_GET_NODE(SetGame, set_game)
COMPONENT_GET_CONFIG(SetGame, set_game)

#define SET_GAME_IS_XXXX_SET(CardA,CardB,CardC,ATTRIBUTE)              \
    bool set_game_is_##ATTRIBUTE##_set(SetCard_t* CardA,               \
                                       SetCard_t* CardB,               \
                                       SetCard_t* CardC) {             \
    bool res = false;                                                  \
    if(CardA->Info.ATTRIBUTE == CardB->Info.ATTRIBUTE){                \
        if(CardB->Info.ATTRIBUTE == CardC->Info.ATTRIBUTE){            \
            if(CardA->Info.ATTRIBUTE == CardC->Info.ATTRIBUTE){        \
                res = true;                                            \
            }                                                          \
        }                                                              \
    }                                                                  \
    if(CardA->Info.ATTRIBUTE != CardB->Info.ATTRIBUTE){                \
        if(CardB->Info.ATTRIBUTE != CardC->Info.ATTRIBUTE){            \
            if(CardA->Info.ATTRIBUTE != CardC->Info.ATTRIBUTE){        \
                res = true;                                            \
            }                                                          \
        }                                                              \
    }                                                                  \
    return res;                                                        \
 }


bool set_game_proc_one(uint8_t num) {
    bool res = false;
    LOG_PARN(SET_GAME, "Proc:%u", num);
    SetGameHandle_t* Node = SetGameGetNode(  num);
    if (Node) {
#ifdef HAS_GM67
        Gm67Handle_t* Gm67Node=Gm67GetNode(Node->scanner_num);
        if(Gm67Node){
            if(Gm67Node->unptoc_frame){
                LOG_DEBUG(SET_GAME, "%s", SetNodeToStr(Node));
                SetCardInfo_t Card;
                Card.byte = Gm67Node->DataFixed[0];
                res = set_game_add_card(num, Card);
                Gm67Node->unptoc_frame = false ;

                res = set_game_seek_set(num);
            }
        }
#endif
    }
    return res;
}

bool set_game_init_custom(void) {
    bool res = true ;
    srand(time(0));
    log_level_get_set(SET_GAME, LOG_LEVEL_INFO  );
    return res;
}

bool set_game_is_uniq_ll(  SetGameHandle_t* Node,SetCardInfo_t Card){
    bool res = true;
    uint8_t i = 0 ;
    for(i=0;i<Node->card_cnt;i++){
        if(Card.byte == Node->Cards[i].Info.byte){
            res = false ;
        }
    }
    return res;
}


bool set_game_is_set_index(const SetInstance_t* const SetNode, uint8_t index){
    bool res = false ;
    if(index==SetNode->CardA.index){
    	res = true;
    }
    if(index==SetNode->CardB.index){
    	res = true;
    }
    if(index==SetNode->CardC.index){
    	res = true;
    }
    return res;
}

bool set_game_add_card(uint8_t num, SetCardInfo_t Card){
    bool res = false;
    SetGameHandle_t* Node = SetGameGetNode(  num);
    if(Node) {
        LOG_DEBUG(SET_GAME,"New:%s",SetCardInfoToStr( Card)  );
        if( Node->card_cnt < SET_GAME_TOTAL_ON_TABLE){
            //is uniq?
            res = set_game_is_uniq_ll(Node,Card);
            if(res) {
                LOG_INFO(SET_GAME,"+%s",SetCardInfoToStr( Card)  );
                Node->Cards[Node->card_cnt].Info=Card;
                Node->Cards[Node->card_cnt].index = Node->card_cnt;
                Node->card_cnt++;
                res = true;
            } else {
                LOG_ERROR(SET_GAME,"Duplicate:%s",SetCardInfoToStr( Card)  );
            }
        } else {
            LOG_ERROR(SET_GAME,"TooManyCardsOnnTable:%s",SetCardInfoToStr( Card) );
        }
        SetGameDiag(Node);
    }
    return res;
}



SET_GAME_IS_XXXX_SET(CardA,CardB,CardC,color)

SET_GAME_IS_XXXX_SET(CardA,CardB,CardC,filling)

SET_GAME_IS_XXXX_SET(CardA,CardB,CardC,quantity)

SET_GAME_IS_XXXX_SET(CardA,CardB,CardC,shape)


bool set_game_is_set(SetCard_t* CardA, SetCard_t* CardB, SetCard_t* CardC) {
    bool res = false;

    res = set_game_is_color_set(CardA, CardB,CardC) ;
    if(res) {
        res = false;
        res = set_game_is_filling_set(CardA, CardB, CardC) ;
        if(res){
            res = false;
            res = set_game_is_quantity_set(CardA, CardB, CardC) ;
            if(res){
                res = false;
                res = set_game_is_shape_set(CardA, CardB, CardC) ;
            }
        }
    }

    return res;
}

int uint32_compare(const void * x1, const void * x2)  {
  return ( *(uint32_t*)x1 - *(uint32_t*)x2 );              // если результат вычитания равен 0, то числа равны, < 0: x1 < x2; > 0: x1 > x2
}

bool set_game_is_set_uniq(SetGameHandle_t* Node , SetInstance_t* Instance){
    bool res = true ;
    uint32_t i =0;
    for (i=0;i<Node->set_cnt;i++){
        if(Instance->qword==Node->SetArray[i].qword){
            res = false ;
            break;
        }
    }
    return res;
}

bool set_game_seek_set(uint8_t num){
    bool res = false ;
    SetGameHandle_t* Node = SetGameGetNode(num);
    uint32_t cur_arr[3] ={0};
    uint32_t i =0;
    uint32_t j =0;
    uint32_t k =0;
    for(i=0;i<Node->card_cnt;i++){
        for(j=0;j<Node->card_cnt;j++){
            for(k=0;k<Node->card_cnt;k++){
                if(i!=j){
                    if(i!=k){
                        if(j!=k){
                            res = set_game_is_set(
                                    &Node->Cards[i],
                                    &Node->Cards[j],
                                    &Node->Cards[k]);
                            if(res){
                                cur_arr[0] =i;
                                cur_arr[1] =j;
                                cur_arr[2] =k;
                                size_t item_size = sizeof(uint32_t);
                                qsort((void *)cur_arr, (size_t)3,   item_size, uint32_compare);


                                SetInstance_t Instance;
                                Instance.qword = 0;
                                Instance.CardA=Node->Cards[cur_arr[0]];//2
                                Instance.CardB=Node->Cards[cur_arr[1]];//2
                                Instance.CardC=Node->Cards[cur_arr[2]];//2
                                res = set_game_is_set_uniq(Node,&Instance);
                                if (res) {
                                    Node->SetArray[Node->set_cnt]=Instance;
                                    Node->set_cnt++;
                                    res = true;
                                    LOG_INFO(SET_GAME,"%u,SpotNewSet:%u,%u,%u!",Node->set_cnt,cur_arr[0],cur_arr[1],cur_arr[2]);
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    if(Node->set_cnt){
        LOG_INFO(SET_GAME,"SetCnt:%u",Node->set_cnt);
    }else {
        LOG_ERROR(SET_GAME,"NoSets");

    }

    return res;
}

bool set_game_init_one(uint8_t num) {
    LOG_WARNING(SET_GAME, "Init:%u", num);
    bool res = false;
    const SetGameConfig_t* Config = SetGameGetConfig(num);
    if(Config) {
        LOG_WARNING(SET_GAME, "%s", SetGameConfigToStr(Config));
        SetGameHandle_t* Node = SetGameGetNode(num);
        if(Node) {
            LOG_INFO(SET_GAME, "%u", num);
            Node->num = Config->num;
            Node->scanner_num = Config->scanner_num;
            Node->valid = true;
            Node->set_cnt = 0;
            Node->card_cnt = 0;
            memset(Node->StepLog,0,sizeof(Node->StepLog));
            SetGameDiag(Node) ;
            res = true;
        }
    }
    return res;
}

COMPONENT_INIT_PATTERT(SET_GAME, SET_GAME, set_game)
COMPONENT_PROC_PATTERT(SET_GAME, SET_GAME, set_game)

Отладка

Когда карточки просканированы они попадают в массив структур. Благо в прошивке есть UART-CLI для наблюдения за глобальными переменными. Вот результат прочитанных сканером карточек.

После добавления в массив новой карточки запускается процедура поиска сета. Решение выдается в виде списка массивов с индексами карточек которые образуют Set. Также печатается визуальные паттерны тех мест, где заложен каждый сет, чтобы его было удобно найти и подобрать на столе. Вот эти 5 set(ов) нашел сам микроконтроллер!

Таким образом прошивка как лакмусовая бумажка в реальном времени дает целеуказание на физическое расположение set(ов).

Что можно улучшить?
1--Написать Android приложение, которое находит set по фотографии столешницы. Однако это очень трудоёмко, так как надо делать распознавание образов (вероятно в OpenCV).

2--Напечатать карты set на RFID карточках или сделать перфорацию, чтобы обычным фото резистором считывать код карты.

4--Можно отображать решения на OLED дисплее с I2C интерфейсом. Тогда отпадает нужда в LapTop(е)

Итоги

Этот программно-аппаратный комплекс (ПАК) можно использовать для проведения турниров по игре Set (если только такие проводятся).

К слову, аналогичные действия можно проделать для другой карточной игры, например Spot.

QR коды хороши тем, что это стандартизированный беспроводной способ передавать бинарные данные в камеру. Можно хоть прошивку обновлять последовательностью QR кодов.

Как это всё можно применить в реальной жизни?
1--Было бы здоров как-то нанести одинаковые ID коды на носки. Тогда при помощи простого считывателя всегда легко будет найти пары после стирки.

2--Если каждому ВУЗ(овцу) выдать QR код, то преподаватель таким сканером сможет контролировать посещаемость семинаров и выявлять прогульщиков.

Словарь

Акроним

перевод

ПАК

программно-аппаратный комплекс

UART

Universal asynchronous receiver-transmitter

Ссылки

Название

URL

1

Игра Сет

https://habr.com/ru/articles/48714/

2

Математика и игра «Сет»

https://habr.com/ru/articles/455634/

3

Верификация DataMatrix Честный знак — почему она важна

https://habr.com/ru/articles/599405/

4

Штрихкоды и жизнь

https://habr.com/ru/articles/17036/

5

Исходники генератора Data Matrix кодов

https://github.com/rdoeffinger/iec16022.git

Комментарии (13)


  1. NutsUnderline
    16.07.2024 05:38

    "А у меня будет свой блекджэк! С qr кодами и китайской ардуиной"


    1. aabzel Автор
      16.07.2024 05:38

      Просто надоело постоянно проигрывать в игре Set.


  1. kuzzdra
    16.07.2024 05:38
    +1

    В эту игру с людями играть не интересно. А вот если микроконтроллер против микроконтроллера?


    1. aabzel Автор
      16.07.2024 05:38

      А во что интересно?


  1. Jury_78
    16.07.2024 05:38

    Игра вариант лото?


    1. aabzel Автор
      16.07.2024 05:38

      Вот текст про правила игры
      Игра Сет
      https://habr.com/ru/articles/48714/


  1. alcotel
    16.07.2024 05:38
    +1

    Чтобы модуль переключился в режим UART 9600 bit/s надо просканировать вот этот код.

    А взломать, или хотя-бы отключить подобный сканер через чтение какого-то другого QR-кода, получается, тоже можно? Интересная дыра

    Вообще распознавание самих карточек по фотке - вроде, не сильно сложная задача. Не думаю, что сложнее распознавания текста. Влезет в микроконтроллер хотя-бы для каких-то простых случаев расположения карточек?

    Вообще лично мне не понятно, почему производители игры set не печатают QR код или штрих код на обороте карточки

    Колода, краплёная QR-кодом - это идея!)


    1. aabzel Автор
      16.07.2024 05:38

      Вообще распознавание самих карточек по фотке - вроде, не сильно сложная задача.

      Вот только с чего начать решение этой задачи? И какая математика тут нужна?


      1. alcotel
        16.07.2024 05:38
        +1

        Скорее всего множество 2-мерных свёрток. Не нашёл про алгоритмы, но Википедия, например, пишет

        Первой программой, распознающей кириллицу, была программа «AutoR» российской компании «ОКРУС». Программа начала распространяться в 1992 году, работала под управлением операционной системы DOS и обеспечивала приемлемое по скорости и качеству распознавание даже на персональных компьютерах IBM PC/XT с процессором Intel 8088 при тактовой частоте 4,77 МГц

        8088 по максимальному объёму памяти похож. А по скорости Ваш мк в 50 раз быстрее


        1. aabzel Автор
          16.07.2024 05:38

          Распознавание карточек Set может стать отличным учебным выпускным проектом для ВУЗ(овцев), кто учится на математическом факультете.


    1. aabzel Автор
      16.07.2024 05:38

      А взломать, или хотя-бы отключить подобный сканер через чтение какого-то другого QR-кода, получается, тоже можно? Интересная дыра

      GM67 Bar Code Reader Module User Manual
      Вот его спека
      https://docs.yandex.ru/docs/view?tm=1721145511&tld=ru&lang=en&name=qr-barkod-okuyucu-datasheet.pdf&text=GM67 scanner pdf&url=https%3A%2F%2Fpdf.direnc.net%2Fupload%2Fqr-barkod-okuyucu-datasheet.pdf&lr=213&mime=pdf&l10n=ru&sign=bbf726b1f03e6ccf608bf0aeab52eb7d&keyno=0&nosw=1&serpParams=tm%3D1721145511%26tld%3Dru%26lang%3Den%26name%3Dqr-barkod-okuyucu-datasheet.pdf%26text%3DGM67%2Bscanner%2Bpdf%26url%3Dhttps%253A%2F%2Fpdf.direnc.net%2Fupload%2Fqr-barkod-okuyucu-datasheet.pdf%26lr%3D213%26mime%3Dpdf%26l10n%3Dru%26sign%3Dbbf726b1f03e6ccf608bf0aeab52eb7d%26keyno%3D0%26nosw%3D1

      Можно QR кодом отключить подсветку, коллиматор, звук.

      Можно подключить его вместо клавиатуры по USB и картинками с экрана эмитировать набор текста.


      1. alcotel
        16.07.2024 05:38
        +1

        Не понял из спеки, а можно ли у сканера отключить управление QЯ-кодами? Если такой сканер выставить на всеобщее пользование в каком-нибудь вендинге, его получается лекго поломать. Хорошо ещё, что не насовсем, и только сканер


    1. aabzel Автор
      16.07.2024 05:38

      Влезет в микроконтроллер хотя-бы для каких-то простых случаев расположения карточек?


      У этого MCU 384kByte RAM и 4MByte ROM