Розробка мобільного 2D головоломки Філіппінські кросворди на C++ для iOS і Android

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

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


Так як одиниця не має пари, то вона зафарбований за замовчуванням. В результаті розв'язання кросворду, коли всі пари чисел (крім одиниць) з'єднані лініями, виходить малюнок.



Обробка зображень
Робота почалася зі збору кольорових зображень у різних форматах. Після того, як я зібрав достатню кількість зображень (понад 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.

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


Підбиваючи підсумки
В результаті цієї роботи вийшло додаток, яке я і сам граю час від часу. У процесі роботи неодноразово приходила думка кинути проект, але я не шкодую, що довів його до логічного кінця.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.