Существует одна очень остроумная настольная игра. Называется Set. Это игра на внимание. Достоинство этой игры в том, что она для неограниченного количества игроков. Вот так она выглядит.
У set есть ещё вариация: игра котики.
Там признаки не фигуры, цвет, количество и заполнение, а — головной убор, очки, фотоаппарат.
В чем проблема?
Бывает так, что вот вы собрались сыграть в Set и никто не видит сет. А он на самом деле есть.
Решением проблемы был бы электронный прибор для автоматического нахождения сета!
И я его соорудил!
Каков план?
Идея очень проста. Мысль в следующем...
Каждой карточке из игры Set поставить в соответствие натуральное число. Буквально один байт на карточку.
Натуральное число преобразовать в DataMatrix код.
Код распечатать на наклейке.
Наклейки c DataMatrix кодами приклеить на обратную сторону каждой карточки в игре Set. Это 81 наклейка.
Соединить считыватель QR кодов с микроконтроллером по UART.
Написать микроконтроллерную прошивку, которая находит все 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 на борту.
Программная часть
В качестве языка программирования на котором решать задачу я выбрал язык программирования Си, компилятор 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(ов).
Что можно улучшить?
Написать Android приложение, которое находит set по фотографии столешницы. Однако это очень трудоёмко, так как надо делать распознавание образов (вероятно в OpenCV).
Напечатать карты set на RFID карточках или сделать перфорацию, чтобы обычным фото резистором считывать код карты.
Можно отображать решения на OLED дисплее с I2C интерфейсом. Тогда отпадает нужда в LapTop(е)
Итоги
Этот электронный прибор можно использовать для проведения турниров по игре Set, если только такие проводятся.
Приятно осознавать, что полученные в институте знания пригодились хоть для чего-то.
К слову, аналогичные действия можно проделать для другой карточной игры, например Spot.
QR коды хороши тем, что это стандартизированный беспроводной способ передавать бинарные данные в камеру. Можно хоть прошивку обновлять последовательностью QR кодов.
Как это всё можно применить в реальной жизни?
Было бы здоров как-то нанести одинаковые ID коды на носки. Тогда при помощи простого считывателя всегда легко будет найти пары после стирки.
Если каждому ВУЗ(овцу) выдать QR код, то преподаватель таким сканером сможет контролировать посещаемость семинаров и выявлять прогульщиков.
Если нанести штрих коды на стержень актуатора, то получится датчик положения стержня.
BarCode на бумажных деньгах позволит автоматически считать наличные.
Словарь
Акроним |
перевод |
ПАК |
программно-аппаратный комплекс |
UART |
Universal asynchronous receiver-transmitter |
Ссылки
№ |
Название |
URL |
1 |
Игра Сет |
|
2 |
Математика и игра «Сет» |
|
3 |
Верификация DataMatrix Честный знак — почему она важна |
|
4 |
Штрихкоды и жизнь |
|
5 |
Исходники генератора Data Matrix кодов |
Комментарии (14)
kuzzdra
16.07.2024 05:38+1В эту игру с людями играть не интересно. А вот если микроконтроллер против микроконтроллера?
alcotel
16.07.2024 05:38+1Чтобы модуль переключился в режим UART 9600 bit/s надо просканировать вот этот код.
А взломать, или хотя-бы отключить подобный сканер через чтение какого-то другого QR-кода, получается, тоже можно? Интересная дыра
Вообще распознавание самих карточек по фотке - вроде, не сильно сложная задача. Не думаю, что сложнее распознавания текста. Влезет в микроконтроллер хотя-бы для каких-то простых случаев расположения карточек?
Вообще лично мне не понятно, почему производители игры set не печатают QR код или штрих код на обороте карточки
Колода, краплёная QR-кодом - это идея!)
aabzel Автор
16.07.2024 05:38Вообще распознавание самих карточек по фотке - вроде, не сильно сложная задача.
Вот только с чего начать решение этой задачи? И какая математика тут нужна?
alcotel
16.07.2024 05:38+1Скорее всего множество 2-мерных свёрток. Не нашёл про алгоритмы, но Википедия, например, пишет
Первой программой, распознающей кириллицу, была программа «AutoR» российской компании «ОКРУС». Программа начала распространяться в 1992 году, работала под управлением операционной системы DOS и обеспечивала приемлемое по скорости и качеству распознавание даже на персональных компьютерах IBM PC/XT с процессором Intel 8088 при тактовой частоте 4,77 МГц
8088 по максимальному объёму памяти похож. А по скорости Ваш мк в 50 раз быстрее
aabzel Автор
16.07.2024 05:38Распознавание карточек Set может стать отличным учебным выпускным проектом для ВУЗ(овцев), кто учится на математическом факультете.
aabzel Автор
16.07.2024 05:38А взломать, или хотя-бы отключить подобный сканер через чтение какого-то другого QR-кода, получается, тоже можно? Интересная дыра
Можно QR кодом отключить подсветку, коллиматор, звук.
Можно подключить его вместо клавиатуры по USB и картинками с экрана эмитировать набор текста.alcotel
16.07.2024 05:38+1Не понял из спеки, а можно ли у сканера отключить управление QЯ-кодами? Если такой сканер выставить на всеобщее пользование в каком-нибудь вендинге, его получается лекго поломать. Хорошо ещё, что не насовсем, и только сканер
aabzel Автор
16.07.2024 05:38Влезет в микроконтроллер хотя-бы для каких-то простых случаев расположения карточек?
У этого MCU 384kByte RAM и 4MByte ROM
NutsUnderline
"А у меня будет свой блекджэк! С qr кодами и китайской ардуиной"
aabzel Автор
Просто надоело постоянно проигрывать в игре Set.