Решатель Игры Set на Микроконтроллере
#дополненная реальность #комбинаторика #дискретная математика
Существует одна очень остроумная настольная игра. Называется 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 на борту.
Oрудие Победы в игре Set
Программная часть
В качестве языка программирования на котором решать задачу я выбрал язык программирования Си, компилятор GCC, систему сборки Make. Всё это абсолютно бесплатно скачивается из интернета.
Саму бизнес логику игры я сперва отладил на DeskTop PC, как Windows консольное приложение. Далее пересобрал тот же самый код для микропроцессора ARM Cortex-M4.
Вот код основного программного компонента — решателя игры Set
#include "set_game.h"
#include
#include
#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;icard_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;iset_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;icard_cnt;i++){
for(j=0;jcard_cnt;j++){
for(k=0;kcard_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 |
