#дополненная реальность #комбинаторика #дискретная математика
Существует одна очень остроумная настольная игра. Называется 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:0 |
2 |
фигура |
волна, ромб, овал |
Тут 8 бит код кары преобразуется в бинарное представление DataMatrix кода (100 бит). Для генерации кода я скачал сорцы на Си из GitHub.
Затем запускается код генератор Graphviz кода и компонуется черно-белая плитка на языке Graphviz. На финише текстовый *.gv файл утилитой dot.exe преобразуется в *.svg. И так для 81 случаев. Получается 81 *.svg файлов. Кидает *.svg на USB flash(ку) и относим в ближайшую типографию и просим распечатать их на клеящейся бумаге. Каждый код со стороонй 4 см.
Самой утомительной частью этого проекта было наклеить DataMatrix коды на каждую карточку. Это надо было сделать очень внимательно без ошибок. Иначе всё пойдёт прахом. Я наклеивал эти наклейки порядка 3 часов.
Вообще лично мне не понятно, почему производители игры set не печатают QR код на обороте карточки, который бы давал информацию про эту карточку. Это было бы логично и помогло при автоматической сортировке этих карточек на производстве. Это же касается всех других настольных игр, где есть какие-либо карточки.
В качестве считывателя QR кодов я купил отдельный модуль GM67.
Чтобы модуль переключился в режим UART надо просканировать вот этот код.
Теперь осталось соединить агрегаты вот по такой схеме.
Программу для вычисления расположения сета я написал для учебно-тренировочной электронной платы 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(ов).
Что можно улучшить?
1—Написать Android приложение, которое находит set по фотографии столешницы. Однако это очень трудоёмко, так как надо делать распознавание образов (вероятно в OpenCV).
2—Напечатать карты set на RFID карточках или сделать перфорацию, чтобы обычным фото резистором считывать код карты.
4—Можно отображать решения на OLED дисплее с I2C интерфейсом.
Итоги
Этот программно-аппаратный комплекс (ПАК) можно использовать для проведения турниров по игре Set (если только такие проводятся).
К слову, аналогичные действия можно проделать для другой карточной игры — Spot.
QR коды хороши тем, что это стандартизированный способ передавать бинарные данные от экрана к камере. Можно хоть прошивку обновлять последовательностью QR кодов.
Как это всё можно применить в реальной жизни?
Было бы здоров как-то нанести одинаковые ID коды на носки. Тогда при помощи простого считывателя всегда легко будет найти пары после стирки.
Словарь
|
Акроним |
перевод |
|
ПАК |
программно-аппаратный комплекс |
|
UART |
Universal asynchronous receiver-transmitter |
Ссылки
|
№ |
Название |
URL |
|
1 |
Игра Сет |
|
|
2 |
Математика и игра «Сет» |
|
|
3 |
Верификация DataMatrix Честный знак — почему она важна |
|
|
4 |
Штрихкоды и жизнь |
|
|
5 |
Исходники генератора Data Matrix кодов |
ссылка на оригинал статьи https://habr.com/ru/articles/827128/
Добавить комментарий