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

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

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

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

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

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

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

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



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


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


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

• Приведение всех форматов в формату 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.

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

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

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