Разработка мобильной 2D головоломки Филиппинские кроссворды на C++ для iOS и Android19.10.2016 13:48

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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