![](https://habrastorage.org/getpro/habr/upload_files/76c/4d1/6e9/76c4d16e9753507c375c14afc238598c.png)
#дополненная реальность #комбинаторика #дискретная математика
Существует одна очень остроумная настольная игра. Называется Set. Это игра на внимание. Достоинство этой игры в том, что она для неограниченного количества игроков. Вот так она выглядит.
![](https://habrastorage.org/getpro/habr/upload_files/410/7f2/84a/4107f284a17a836fcf7d82f739a2f5c3.jpg)
У set есть ещё вариация: игра котики.
![](https://habrastorage.org/getpro/habr/upload_files/ae9/efd/308/ae9efd308ba952ce77827b5313eedfac.png)
Там признаки не фигуры, цвет, количество и заполнение, а - головной убор, очки, фотоаппарат.
В чем проблема?
Бывает так, что вот вы собрались сыграть в Set и никто не видит сет. А он на самом деле есть.
Решением проблемы был бы программно-аппаратный комплекс для автоматического нахождения сета!
Я решил заняться его конструированием.
Каков план?
Идея очень проста. Мысль в следующем...
1--Каждой карточке из игры Set поставить в соответствие натуральное число. Буквально один байт на карточку.
2--Натуральное число преобразовать в DataMatrix код.
3--Код распечатать на наклейке.
4--Наклейки c DataMatrix кодами приклеить на обратную сторону каждой карточки в игре Set. Это 81 наклейка.
5--Соединить считыватель QR кодов с микроконтроллером по UART.
6--Написать микроконтроллерную прошивку, которая находит все Set(ы) перебором и печатает в UART решение.
Как видно, план простой, а значит хороший. Ибо в сложном плане что-то может сломаться и пойти не так.
Аппаратная часть
Hardware первично, software вторично. Поэтому надо подготовить аппаратную часть.
Во-первых экземпляр игры Set надо дооснастить. Надо сгенерировать 81 DataMatrix код чтобы установить его на каждой карточке из колоды. Для этого я написал программную смесь, которая воплощает вот такой конвейер.
![](https://habrastorage.org/getpro/habr/upload_files/1c9/734/51a/1c973451a788355883ce6c26f88ac34d.png)
Каждая карточка однозначно кодируется 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 часов.
![](https://habrastorage.org/getpro/habr/upload_files/e4a/8c6/115/e4a8c61159c56f1738b66d8fa2bf35fb.png)
Вообще лично мне не понятно, почему производители игры set не печатают QR код или штрих код на обороте карточки, который бы давал информацию про эту карточку. Это было бы логично и помогло при автоматической сортировке этих карточек на производстве. Это же касается всех других настольных игр, где есть какие-либо карточки.
В качестве считывателя QR кодов я купил отдельный модуль GM67.
![](https://habrastorage.org/getpro/habr/upload_files/e9f/3f5/a87/e9f3f5a8706b8af48765ddf5b555c94e.png)
Чтобы модуль переключился в режим UART 9600 bit/s надо просканировать вот этот код.
![](https://habrastorage.org/getpro/habr/upload_files/d5c/695/71e/d5c69571efd56e36f372be3ce60d5bf7.png)
Теперь осталось соединить агрегаты вот по такой схеме.
![](https://habrastorage.org/getpro/habr/upload_files/ac1/552/d10/ac1552d10f5ffd203ea479c2c162617f.png)
Программу для вычисления расположения сета я написал для учебно-тренировочной электронной платы AT-Start-F437 с ARM-Cortex-M4 микроконтроллером AT32F437ZM на борту.
![Oрудие Победы в игре Set Oрудие Победы в игре Set](https://habrastorage.org/getpro/habr/upload_files/480/51b/382/48051b3822cc69a94cffd84e79721575.png)
Программная часть
В качестве языка программирования на котором решать задачу я выбрал язык программирования Си, компилятор 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 для наблюдения за глобальными переменными. Вот результат прочитанных сканером карточек.
![](https://habrastorage.org/getpro/habr/upload_files/2fb/3d1/6d8/2fb3d16d8687c48fd44550b516e9b162.png)
После добавления в массив новой карточки запускается процедура поиска сета. Решение выдается в виде списка массивов с индексами карточек которые образуют Set. Также печатается визуальные паттерны тех мест, где заложен каждый сет, чтобы его было удобно найти и подобрать на столе. Вот эти 5 set(ов) нашел сам микроконтроллер!
![](https://habrastorage.org/getpro/habr/upload_files/60b/24b/8e5/60b24b8e50cbce01857de79a26868f36.png)
Таким образом прошивка как лакмусовая бумажка в реальном времени дает целеуказание на физическое расположение 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 |
Игра Сет |
|
2 |
Математика и игра «Сет» |
|
3 |
Верификация DataMatrix Честный знак — почему она важна |
|
4 |
Штрихкоды и жизнь |
|
5 |
Исходники генератора Data Matrix кодов |
Комментарии (13)
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.