Существует одна очень остроумная настольная игра. Называется 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 карточках или сделать перфорацию, чтобы обычным фото резистором считывать код карты.

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

Итоги

Этот электронный прибор можно использовать для проведения турниров по игре Set, если только такие проводятся.

Приятно осознавать, что полученные в институте знания пригодились хоть для чего-то.

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

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

Как это всё можно применить в реальной жизни?

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

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

  3. Если нанести штрих коды на стержень актуатора, то получится датчик положения стержня.

  4. BarCode на бумажных деньгах позволит автоматически считать наличные.

    Словарь

Акроним

перевод

ПАК

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

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

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


  1. NutsUnderline
    16.07.2024 05:38

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


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

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


  1. kuzzdra
    16.07.2024 05:38
    +1

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


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

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


      1. kuzzdra
        16.07.2024 05:38
        +1

        Смысл игры - соревнование. Соревноваться в быстродействии с микроконтроллером - тупо. Интересно - когда человек соревнуется с человеком в равных условиях.


  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