Класичні п’ятнашки

Ця відома головоломка стала популярною в Америці в 1870-х роках. Її мета — упорядкувати плитки на полі, пересуваючи їх горизонтально й вертикально. На початку головоломки плитки розташовано впереміш.

У найпоширенішому варіанті головоломки на плитках зображено числа 1–15. Однак її можна дещо ускладнити, зробивши плитки частинами зображення. Перш ніж почати, спробуйте розв’язати головоломку. Натисніть плитку поруч із порожньою клітинкою, щоб пересунути її на вільне місце.

Створення проєкту

1. Запустіть Defold.
2. Виберіть New Project ліворуч.
3. Виберіть вкладку From Template.
4. Виберіть Empty Project
5. Виберіть місце для проєкту на локальному диску.
6. Натисніть Create New Project.

Відкрийте файл налаштувань game.project і задайте розміри гри 512⨉512. Вони відповідатимуть зображенню, яке ви використовуватимете.

Наступний крок — завантажити відповідне зображення для головоломки. Виберіть будь-яке квадратне зображення, але обов’язково змініть його розмір на 512 на 512 пікселів. Якщо не хочете шукати зображення, можете використати це:

Завантажте зображення, а потім перетягніть його до папки main вашого проєкту.

Подання сітки

Defold містить вбудований компонент (component) Tilemap, який ідеально підходить для відображення поля головоломки. Карти плиток дають змогу задавати й зчитувати окремі плитки — це все, що потрібно для цього проєкту.

Але перш ніж створювати карту плиток, вам знадобиться джерело плиток Tilesource, з якого карта братиме зображення плиток.

Натисніть правою кнопкою миші папку main і виберіть New ▸ Tile Source. Назвіть новий файл monalisa.tilesource.

Установіть значення властивостей плитки Width і Height на 128. Це розділить зображення розміром 512⨉512 пікселів на 16 плиток. Коли ви розмістите їх на карті плиток, вони матимуть номери 1–16.

Далі натисніть правою кнопкою миші папку main і виберіть New ▸ Tile Map. Назвіть новий файл “grid.tilemap”.

У Defold потрібно ініціалізувати сітку. Для цього виберіть шар “layer1” і намалюйте сітку плиток 4⨉4 безпосередньо праворуч угорі від початку координат. Які саме плитки ви виберете, не має значення. Незабаром ви напишете код, який автоматично задаватиме їхній вміст.

Поєднання складових

Відкрийте main.collection. Натисніть правою кнопкою миші кореневий вузол у Outline і виберіть Add Game Object. Установіть властивість Id нового ігрового об’єкта (game object) на “game”.

Натисніть правою кнопкою миші ігровий об’єкт і виберіть Add Component File. Виберіть файл grid.tilemap. Установіть властивість Id на “tilemap”.

Натисніть правою кнопкою миші ігровий об’єкт і виберіть Add Component ▸ Label. Установіть властивість Id текстової мітки на “done”, а властивість Text — на “Well done”. Перемістіть текстову мітку в центр карти плиток.

Установіть координату Z текстової мітки на 1, щоб вона відображалася поверх сітки.

Далі створіть файл скрипту Lua для логіки головоломки: натисніть правою кнопкою миші папку main і виберіть New ▸ Script. Назвіть новий файл “game.script”.

Потім натисніть правою кнопкою миші ігровий об’єкт із назвою “game” у main.collection і виберіть Add Component File. Виберіть файл game.script.

Запустіть гру. Ви маєте побачити сітку в тому вигляді, у якому її намалювали, і текстову мітку з повідомленням “Well done” поверх неї.

Логіка головоломки

Тепер усі складові на місці, тож решту уроку присвятимо створенню логіки головоломки.

Скрипт зберігатиме власне подання плиток поля, окреме від карти плиток. Це дасть змогу спростити роботу з ними. Замість двовимірного масиву плитки зберігатимуться як одновимірний список у таблиці Lua. Список міститиме номери плиток послідовно, від верхнього лівого кута сітки до нижнього правого:

-- The completed board looks like this:
self.board = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0}

Код, який бере такий список плиток і відображає його на нашій карті плиток, досить простий, але потребує перетворення позиції в списку на координати x та y:

-- Draw a table list of tiles onto a 4x4 tilemap
local function draw(t)
    for i=1, #t do
        local y = 5 - math.ceil(i/4) -- <1>
        local x = i - (math.ceil(i/4) - 1) * 4
        tilemap.set_tile("#tilemap","layer1",x,y,t[i])
    end
end

1. На карті плиток плитка з координатами x = 1 та y = 1 розташована внизу ліворуч. Тому координату y потрібно інвертувати.

Можете перевірити, чи функція працює належним чином, створивши тестову функцію init():

function init(self)
    -- An inverted board, for test
    self.board = {15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0}
    draw(self.board)
end

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

-- Swap two items in a table list
local function swap(t, i, j)
    local tmp = t[i]
    t[i] = t[j]
    t[j] = tmp
    return t
end

-- Randomize the order of a the elements in a table list
local function scramble(t)
    local n = #t
    for i = 1, n - 1 do
        t = swap(t, i, math.random(i, n))
    end
    return t
end

Перш ніж рухатися далі, потрібно врахувати одну особливість п’ятнашок: якщо перемішати плитки так, як показано вище, з імовірністю 50% головоломку буде неможливо розв’язати.

Це погана новина, адже ви точно не хочете пропонувати гравцеві головоломку, яку неможливо розв’язати.

На щастя, можна визначити, чи має певне розташування плиток розв’язок. Ось як це зробити:

Розв’язність

Щоб визначити, чи можна розв’язати головоломку 4⨉4 з певним розташуванням плиток, потрібні два значення:

1. Кількість «інверсій» у цьому розташуванні. Інверсія виникає, коли одна плитка передує іншій плитці з меншим номером. Наприклад, список {1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 11, 10, 13, 14, 15, 0} має 3 інверсії:

   • після числа 12 стоять 11 і 10, що дає 2 інверсії.
   • після числа 11 стоїть 10, що дає ще 1 інверсію.

   (Зауважте, що в розв’язаній головоломці немає жодної інверсії)

2. Рядок, у якому розташована порожня клітинка (позначена в списку як 0).

Ці два значення можна обчислити за допомогою таких функцій:

-- Count the number of inversions in a list of tiles
local function inversions(t)
    local inv = 0
    for i=1, #t do
        for j=i+1, #t do
            if t[i] > t[j] and t[j] ~= 0 then -- <1>
                inv = inv + 1
            end
        end
    end
    return inv
end

1. Зауважте, що порожня клітинка не враховується.

-- Find the x and y position of a given tile
local function find(t, tile)
    for i=1, #t do
        if t[i] == tile then
            local y = 5 - math.ceil(i/4) -- <1>
            local x = i - (math.ceil(i/4) - 1) * 4
            return x,y
        end
    end
end

1. Координата Y, відрахована знизу.

Тепер за цими двома числами можна визначити, чи має головоломка в певному стані розв’язок. Стан поля 4⨉4 є розв’язним, якщо:

• Порожня клітинка розташована в непарному рядку (1 або 3, рахуючи знизу), а кількість інверсій парна.
• Порожня клітинка розташована в парному рядку (2 або 4, рахуючи знизу), а кількість інверсій непарна.

Як це працює?

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

Горизонтальне переміщення плитки не змінює ані кількість інверсій, ані номер рядка, у якому розташована порожня клітинка.

Натомість вертикальне переміщення змінює парність кількості інверсій (із непарної на парну або з парної на непарну). Воно також змінює парність номера рядка з порожньою клітинкою.

Наприклад:

Цей хід змінює порядок плиток із:

{ ... 0, 11, 2, 13, 6 ... }

на

{ ... 6, 11, 2, 13, 0 ... }

У новому стані додаються 3 інверсії так:

• Число 6 додає 1 інверсію (число 2 тепер стоїть після 6)
• Число 11 втрачає 1 інверсію (число 6 тепер стоїть перед 11)
• Число 13 втрачає 1 інверсію (число 6 тепер стоїть перед 13)

Унаслідок вертикального переміщення кількість інверсій може змінитися на ±1 або ±3.

Номер рядка з порожньою клітинкою внаслідок вертикального переміщення може змінитися на ±1.

У кінцевому стані головоломки порожня клітинка розташована в нижньому правому куті (у непарному рядку 1), а кількість інверсій дорівнює парному числу 0. Кожен допустимий хід або залишає ці два значення незмінними (горизонтальний хід), або змінює їхню парність (вертикальний хід). Жоден допустимий хід не може зробити кількість інверсій непарною, а номер рядка з порожньою клітинкою — непарним, або кількість інверсій парною, а номер рядка — парним.

Отже, головоломку в будь-якому стані, де обидва числа непарні або обидва парні, неможливо розв’язати.

Ось код, який перевіряє розв’язність:

-- Is the given table list of 4x4 tiles solvable?
local function solvable(t)
    local x,y = find(t, 0)
    if y % 2 == 1 and inversions(t) % 2 == 0 then
        return true
    end
    if y % 2 == 0 and inversions(t) % 2 == 1 then
        return true
    end
    return false    
end

Введення користувача

Тепер залишилося лише зробити головоломку інтерактивною.

Створіть функцію init(), яка виконає всі початкові налаштування під час виконання за допомогою створених вище функцій:

function init(self)
    msg.post(".", "acquire_input_focus") -- <1>
    math.randomseed(socket.gettime()) -- <2>
    self.board = scramble({1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0}) -- <3>
    while not solvable(self.board) do -- <4>
        self.board = scramble(self.board)
    end
    draw(self.board) -- <5>
    self.done = false -- <6>
    msg.post("#done", "disable") -- <7>
end

1. Повідомте рушію, що цей ігровий об’єкт має отримувати введення.
2. Задайте початкове значення генератора випадкових чисел.
3. Створіть початковий випадковий стан поля.
4. Якщо стан нерозв’язний, перемішайте плитки ще раз.
5. Відобразіть поле.
6. Установіть прапорець завершення, щоб відстежувати стан перемоги.
7. Вимкніть текстову мітку з повідомленням про завершення.

Відкрийте /input/game.input_bindings і додайте новий Mouse Trigger. Задайте дії назву “press”:

Поверніться до скрипту й створіть функцію on_input().

-- Deal with user input
function on_input(self, action_id, action)
    if action_id == hash("press") and action.pressed and not self.done then -- <1>
        local x = math.ceil(action.x / 128) -- <2>
        local y = math.ceil(action.y / 128)
        local ex, ey = find(self.board, 0) -- <3>
        if math.abs(x - ex) + math.abs(y - ey) == 1 then -- <4>
            self.board = swap(self.board, (4-ey)*4+ex, (4-y)*4+x) -- <5>
            draw(self.board) -- <6>
        end
        ex, ey = find(self.board, 0)
        if inversions(self.board) == 0 and ex == 4 then -- <7>
            self.done = true
            msg.post("#done", "enable")
        end
    end
end

1. Якщо натиснуто кнопку миші й гра ще триває, виконайте наведені далі дії.
2. Обчисліть координати x та y клітинки, яку натиснув користувач.
3. Знайдіть поточну позицію порожньої (0) клітинки.
4. Якщо натиснута клітинка розташована безпосередньо над порожньою, під нею, ліворуч або праворуч від неї, виконайте наведені далі дії:
5. Поміняйте місцями плитки в натиснутій і порожній клітинках.
6. Перемалюйте оновлене поле.
7. Якщо кількість інверсій на полі дорівнює 0, тобто все розташовано в правильному порядку, а порожня клітинка перебуває в крайньому правому стовпці (щоб кількість інверсій дорівнювала 0, вона має бути в останньому рядку), то головоломку розв’язано, тож виконайте наведені далі дії:
8. Установіть прапорець завершення.
9. Увімкніть/покажіть повідомлення про завершення.

Ось і все! Ви впоралися — гра-головоломка готова!

Повний скрипт

Ось повний код скрипту для довідки:

local function inversions(t)
    local inv = 0
    for i=1, #t do
        for j=i+1, #t do
            if t[i] > t[j] and t[j] ~= 0 then
                inv = inv + 1
            end
        end
    end
    return inv
end

local function find(t, tile)
    for i=1, #t do
        if t[i] == tile then
            local y = 5 - math.ceil(i/4)
            local x = i - (math.ceil(i/4) - 1) * 4
            return x,y
        end
    end
end

local function solvable(t)
    local x,y = find(t, 0)
    if y % 2 == 1 and inversions(t) % 2 == 0 then
        return true
    end
    if y % 2 == 0 and inversions(t) % 2 == 1 then
        return true
    end
    return false    
end

local function scramble(t)
    for i=1, #t do
        local tmp = t[i]
        local r = math.random(#t)
        t[i] = t[r]
        t[r] = tmp
    end
    return t
end

local function swap(t, i, j)
    local tmp = t[i]
    t[i] = t[j]
    t[j] = tmp
    return t
end

local function draw(t)
    for i=1, #t do
        local y = 5 - math.ceil(i/4)
        local x = i - (math.ceil(i/4) - 1) * 4
        tilemap.set_tile("#tilemap","layer1",x,y,t[i])
    end
end

function init(self)
    msg.post(".", "acquire_input_focus")
    math.randomseed(socket.gettime())
    self.board = scramble({1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0})   
    while not solvable(self.board) do
        self.board = scramble(self.board)
    end
    draw(self.board)
    self.done = false
    msg.post("#done", "disable")
end

function on_input(self, action_id, action)
    if action_id == hash("press") and action.pressed and not self.done then
        local x = math.ceil(action.x / 128)
        local y = math.ceil(action.y / 128)
        local ex, ey = find(self.board, 0)
        if math.abs(x - ex) + math.abs(y - ey) == 1 then
            self.board = swap(self.board, (4-ey)*4+ex, (4-y)*4+x)
            draw(self.board)
        end
        ex, ey = find(self.board, 0)
        if inversions(self.board) == 0 and ex == 4 then
            self.done = true
            msg.post("#done", "enable")
        end
    end
end

function on_reload(self)
    self.done = false
    msg.post("#done", "disable")
end

Додаткові вправи

1. Створіть головоломку 5⨉5, а потім 6⨉5. Переконайтеся, що перевірки розв’язності працюють для різних розмірів поля.
2. Додайте анімації пересування. Плитки не можна переміщувати окремо від карти плиток, тож вам доведеться знайти спосіб розв’язати цю проблему. Можливо, варто використати окрему карту плиток, яка міститиме лише плитку, що пересувається?