Что такое филиппинский кроссворд.


Цветные филиппинские кроссворды — такой вид головоломок, в сетке которой с помощью чисел зашифрована картинка. Каждое число, расположенные в сетке, кроме единицы, имеет пару. Необходимо подобрать и соединить пары чисел линиями так, чтобы линии удовлетворяли следующим условиям:

— длина каждой линии должна соответствовать числам, расположенным на ее концах;
— линии не должны пересекаться друг с другом и проходить через одни и те же клетки;
— линии могут идти в вертикальном и горизонтальном направлениях, могут преломляться, но не могут проходить по диагонали;
— соединяемые пары чисел должны быть одного цвета.


Так как единица не имеет пары, то она закрашена по умолчанию. В результате решения кроссворда, когда все пары чисел (кроме единиц) соединены линиями, получается рисунок.



Обработка изображений


Работа началась с со сбора цветных картинок в различных форматах. После того, как я собрал достаточное количество изображений (более 4000), началась по полуручная-полуавтоматическая работа по их обработке.

Процедуры обработки реализовывал на C++ с использованием библиотеки Gdiplus — ее высокоуровневый интерфейс позволяет читать и создавать файл без глубоких познаний форматов хранения изображений. После чтения файла для удобства манипуляции информация представляется в памяти в виде матрицы, где каждый элемент массива хранит информацию о r,g,b — свойствах конкретного пикселя.

Покажу пример использования на простом примере. Возьмем изображение 3x5 пикселей (для презентации на хабре изображение смаштабировано).



и прочитаем его с помощью кода нижеприведенной процедуры.

ReadImageFile
void ReadImageFile(wchar_t filename[])
{
    Gdiplus::GdiplusStartupInput input;
    Gdiplus::GdiplusStartupOutput output;
    ULONG_PTR token;

    Gdiplus::Color color;
    Gdiplus::Bitmap* bitmap;

    // Инициализация GDI+.
    Gdiplus::GdiplusStartup(&token, &input, &output);
    
    bitmap = new Gdiplus::Bitmap(filename);		

    int w = bitmap->GetWidth();
    int h = bitmap->GetHeight();
    
    for (int i = 0; i < w; i++)
        for (int j = 0; j < h; j++)
        {
            bitmap->GetPixel(i, j, &color);
            printf("Pixel [%d %d]: %d %d %d\n", i, j, (unsigned)color.GetRed(), 
                                                      (unsigned)color.GetGreen(), 
                                                      (unsigned)color.GetBlue()
                  );
        }
    
    delete bitmap;

    // Деинициализация GDI+.
    Gdiplus::GdiplusShutdown(token);
}


Результат ее выполнения:


Обработка включает в себя:

  • Приведение всех форматов в формату png;

  • Обрезка. Определенное количество картинок имеет по краям белое поле, которое нам неинтересно;

  • Приведение к «пиксельному» виду. Поскольку рисунок, получаемый в результате решения филиппинского кроссворда, представлен в виде сетки, то наша картинка должна быть по высоте и ширине не более 100 пикселей (такое ограничение на ширину и высоту я выбрал изначально, все что больше — либо уменьшал, либо удалял из своей коллекции).

  • «Похожие цвета», которые в нотации RGB отличаются менее, чем на 30 одновременно по трем параметрам (r, g, b) — необходимо объединить в один цвет, так, чтобы в результате пользователь мог четко различать цвета. В противном случае цифры в «похожих» цветах на глаз будут неотличимы. Например, два таких соседних пикселя:



    привести к виду:



  • По возможности картинка не должна быть излишне переполнена цветами — не более 15 различных цветов.

  • Удаление дублей. В результате чтения изображение считается хеш-значение и сравнивается с остальными. В случае совпадения значения хеша, ширины, высоты и кол-ва цветов изображение считается дублем и далее не рассматривается.

Разумеется, после каждого этапа обработки необходимо глазками все проверить на адекватность и руками поправить все то, что получилось не так.

Генерация заданий


Начинается самое интересное. Необходимо для каждой картинки сгенерить задание (задание представляет из себя сетку с числами, пары которых необходимо соединить в процессе решения). Каждое задание должно иметь только одно решение. На написание алгоритма генерации-проверки задания у меня ушло 3 месяца. Алгоритм реализован двумя основными процедурами:

— процедура генерации задания, использует внутри себя rand() для генерации случайностей;
— процедура проверки задания.

Картинка представляется в памяти так же в виде матрицы, где каждый элемент массива хранит информацию о r,g,b — свойствах конкретного пикселя. Каждая из процедур в процессе выполнения делает многократные рекурсивные обходы этой матрицы. Достаточно просто реализовать, чтобы получить прямые линии, но в этом случае кроссворд будет неинтересен. Чтобы в кроссворде были неоднократно изгибающиеся линии — пришлось изрядно повозиться.

Алгоритм громоздкий, не вижу смысла приводить исходный код, приведу верхоуровневое описание.

Для каждой картинки запускается цикл на N возможных итераций. Опишу итерацию псеводокодом в произвольной форме:

for(...) // цикл по картинкам
{
    int cnt_try = 0; // кол-во попыток
    do
    {
        cnt_try++;
        
        Задание            = Сгенерить_Задание(картинка);
        Результат_проверки = Проверить_Задание(Задание);
        
        if(Результат_проверки == 0) // Если задание однозначное
            Сохранить_задание(Задание);
        
    }while(Результат_проверки != 0 && cnt_try <= N);
}

Кодинг приложения


Для реализации данного приложения за основу я взял движок, реализованный мною для черно-белых филиппинских кроссвордов FCross, о котором я уже подробно рассказывал ранее. Платформа работки — Marmalade SDK, язык программирования — C++.

Допилив его под новые нужды, я получил приложение для разгадывания цветных филиппинских кроссвордов.

Интеграция с Facebook и хостинг для картинок


Хочется дать возможность пользователю возможность постить решенный кроссворд (картинку) на свою стену стену Facebook. Для этого необходимо на developers.facebook.com зарегистрировать свое приложение, помимо всего прочего указать, какие разрешения приложение будет просить у вашего пользователя. Для моих сценариев достаточно разрешений, получаемых по умолчанию — «public_profile», «user_friends». Для публикации записи на стене по сценарию диалога с подтверждением дополнительных разрешений не требуется.

В таком случае фича Facebook-авторизации в вашем приложении будет доступна без необходимости ее подтверждения командой Facebook, если же вашему приложению нужны дополнительные разрешения, то требуется их аппрув.

Возможность постить картинку дается посредством указания ее URL для входного параметра API-метода публикации. Значит надо хранить изображение на публичном хостинге, который должен удовлетворять выдвигаемым мною требованиям:

— возможность bulk-овой первичной загрузки файлов;
— высокая доступность;
— высокая надежность — не хочется, чтобы он закрылся через месяц;
— по URL должен открываться именно png-файл, а не web-страница с рекламой;
— важно, чтобы URL генерился не путем получения какого-то хеша, а чтобы его без особого труда однозначно можно было бы сопоставить с именем исходного загружаемого изображения.

Пошарив по интернету несколько минут, я остановился на Google Cloud Storage. За определенную плату они покрывают все эти условия. Помимо всего прочего эта платформа дает командную консоль, которая упрощает манипулирование объектами. В моем случае — более 4000 изображений, и я воспользовался ею, когда одной командой (gsutil -m acl ch) сделал все объекты доступными по прямой ссылке.

Итак, поскольку URL изображения сгенерен не по хешу, а в соответствии с названием файла, то мое приложение всегда может получить ссылку на изображение в рантайме непосредственно перед публикацией. Требуется только захардкодить статическую часть URL-пути до папки, в которой лежат целевые файлы.

Для интеграции с Facebook использовалось входящее в стандартную сборку Marmalade SDK s3eFacebook API.

Диалог публикации записи выглядит так:


Подводя итоги


В результате этой работы получилось приложение, в которое я и сам играю время от времени. В процессе работы неоднократно приходила мысль бросить проект, но я не жалею, что довел его до логического конца.
Поделиться с друзьями
-->

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


  1. ginkage
    19.10.2016 13:56
    +7

    Открывая статью с заголовком «Разработка… на C++ для iOS и Android» (и соответствующими тегами), я ожидал интересных подробностей на тему организации кросплатформенной разработки мобильных приложений с нативным кодом.
    Чего я не ожидал, так это того, что всё обещанное в заголовке, уместилось в одно предложение:

    Допилив его под новые нужды, я получил приложение для разгадывания цветных филиппинских кроссвордов.

    Тогда как собственно C++, как оказалось, использовался для разработки под Windows.


    1. logiz
      19.10.2016 16:51

      Тоже ожидал что-нибудь на Qt


    1. akk0rd87
      19.10.2016 17:06

      В пункте Кодинг приложения есть отсылка к статье, где кроссплатформенная разработка рассмотрена более подробно.


      1. ginkage
        19.10.2016 17:23

        Обратите внимание: процитировал тот же раздел. И в этом разделе нет ни строчки кода или вообще чего-либо о процессе кодинга, кроме той самой ссылки.
        Я настаиваю на том, что название статьи нисколько не соответствует её содержанию.


        1. akk0rd87
          19.10.2016 17:40

          Переименовал статью.


  1. akk0rd87
    19.10.2016 14:01

    В пункте Кодинг приложения есть отсылка к статье, где кроссплатформенная разработка рассмотрена более подробно.


  1. eao197
    19.10.2016 16:18

    Заканчивался 2016-й год, а C++ники продолжали вручную вызывать new и delete…

    bitmap = new Gdiplus::Bitmap(filename);	
    ...
    delete bitmap;

    Скажите, а зачем вам вообще потребовалось Bitmap создавать динамически? Почему нельзя было объявить bitmap как автоматическую переменную на стеке?


    1. akk0rd87
      19.10.2016 16:56
      -2

      Не заострял на этом внимание. Так давалось в тех примерах работы c GdiPlus, которые я изучал. Ну и я также скопипастил, не увидев в этом ничего криминального.


      1. eao197
        19.10.2016 17:08
        +1

        > Ну и я также скопипастил

        Ну вот так в последствии C++ный код начинает и тормозить, и течь, и падать.

        Зато разработчики PVS-Studio без работы и клиентов не останутся :)


        1. akk0rd87
          19.10.2016 17:32
          -1

          Из-за того, что я создал Bitmap динамически, а потом в конце процедуры очистил занимаемую им память?


          1. eao197
            19.10.2016 17:45
            +1

            Ага.

            Со временем подобный код превращается во что-то такое:

            Gdiplus::Bitmap* bitmap; // (1)
            
                // Инициализация GDI+.
                Gdiplus::GdiplusStartup(&token, &input, &output);
            
                // Еще какие-то действия, которые появились в последствии.
                ...
            
                bitmap->SetSomeProperty(...); // Упс №1: bitmap еще не создан.
                    // Из-за того, что в (1) переменная bitmap даже не получила
                    // нулевого значения может произойти все, что угодно.
            
                // Еще какие-то действия, которые добавились позже.
                ...
            
                bitmap = new Gdiplus::Bitmap(filename); // Вот и создали объект.
            
                int w = bitmap->GetWidth();
                int h = bitmap->GetHeight();
                
                // Тут со временем появились какие-то проверки.
                if( w > SOME_LIMIT || h > SOME_ANOTHER_LIMIT )
                  return; // Упс №2: утекла память, т.к. delete сделать забыли.
            
                for (int i = 0; i < w; i++)
                    for (int j = 0; j < h; j++)
                    {
                       ...
                    }
                delete bitmap;
            

            Ну и работа с динамической памятью всегда дороже размещения объекта на стеке.

            Ничего бы этого не было, если бы вы просто написали:
            Gdiplus::Bitmap bitmap(filename);


            Если вам кажется, что показанные выше потенциальные проблемы — это плод моей паранойи, то поспрашивайте разработчиков статических анализаторов или тех, кому приходится древний легаси код поддерживать. Там еще и не такие чудеса случаются.


            1. akk0rd87
              19.10.2016 17:57

              Ваш аргумент понятен, ничего против не имею.


              1. eao197
                19.10.2016 17:59

                К сожалению, это не мой аргумент, а те рекомендации, которые рекомендуются к использованию уже пару десятков лет… :(