Picture puzzle на C++. Часть 1
1-ая часть о разработке игры с использованием фреймворка FLTK.
Суть игры
Picture puzzle (или игра в 8). Подобная игра была в комплекте стандартных виджетов в ОС Windows 7. В этой и последующих статьях будут описаны этапы разработки игры на C++ совместно с графической библиотекой FLTK. Репозиторий с исходным кодом игры находится здесь: https://git.scratko.xyz/picture-puzzle/ Игра представляет собой поле, в котором располагаются 8 квадратных паззлов (частей общей картинки) в случайном порядке. 1 клетка всегда остаётся пустой – в неё нужно сдвинуть один паззл, находящийся рядом. В итоге должна сформироваться исходная картинка.
Особенности программы
-
Возможность загружать свои изображения для паззла в любом формате и разрешении. Программа сама изменит размер, разрежет на паззлы, создаст соответствующую директорию и сохранит их в ней
-
Получить полное решение головоломки с помощью алгоритма A*. Программа сама начнет пошагово передвигать паззлы до сборки исходной картинки
-
Игра распространяется в виде единого исполняемого файла (Windows версия), в который вшито стандартное изображение (тукана). Данное изображение хранится в виде массива в объектном файле (resources.o)
-
Поддержка платформ *unix и Windows. Для первой распространяется в виде исходных файлов и make-файла. Нужно только собрать через утилиту Make. Для второй можно скачать готовый исполняемый файл
-
Использован C++ с фичами из 17 стандарта. В осовном задействована стандартная библиотека шаблонов STL
-
Графическая часть реализована с помощью простой билиотека виджетов FLTK (в отличие от монструозного Qt)
Концепт программы
На изображении выше нарисована концпепция программы. Каждый паззл по ширине и длине составляет 100 px. Меню-бар сверху имеет ширину 20 px. Промежутки составляют 5 px.
В итоге получаем: ширина = 3 * 100 + 5 * 4 = 320 px; длина = 20 + 3 * 100 + 5 * 4 = 340 px.
Main.cpp
1int main()
2{
3 srand(time(nullptr));
4 MainWindow *win = new MainWindow(320, 340, "Picture puzzle");
5 GameParams *params = GameParams::SetUpParams(win);
6 Fl_Sys_Menu_Bar *sys_bar = new Fl_Sys_Menu_Bar(0, 0, 320, 20, nullptr);
7 sys_bar->add("&File/&New game", nullptr, new_game_callback, params);
8 sys_bar->add("&File/&Load file", nullptr, load_file_callback);
9 sys_bar->add("&File/&Exit", nullptr, exit_callback);
10 sys_bar->add("&Options/&Show solution", nullptr, solve_problem_callback,
11 params);
12 sys_bar->add("&About", nullptr, about_callback);
13 PuzzleGame::StartGame(params);
14 win->show();
15 return Fl::run();
16}
В самом начале программы инициализируем генератор псевдослучайных чисел значением – числом секунд с 1 января 1970 года. Это понадобится для расставления паззлов в случайном порядке.
Далее создаём экземпляр главного окна, меню-бара с соответствущими значениями высоты и ширины.
sys_bar->add("&File/&New game", nullptr, new_game_callback, params); и далее
нескольки подобных строк. Здесь мы добавляем подпункты в меню-бар. 1-ый аргумент
– название подпункта, 2-ой аргумент позволяет навешать шорткат (здесь
пропускаем), 3 и 4 аргументы особенно здесь важны: передаём адрес
callback-функции и данные для неё соответственно. Таким образом, при нажатии
подпункта будет вызвана эта callback-функция с переданным параметром.
GameParams *params = GameParams::SetUpParams(win); Через статический метод
получаем экземпляр парметров игры. По сути там происходит только вычисление
стандартных положений паззлов и сохранение указателя на главное окно игры. Это
нужно только один раз за запуск программы. Поэтому мы через паттерн синглтон
получаем только один экземпляр настроек на всю продолжительность работы
программы.
PuzzleGame::StartGame(params);
win->show();
return Fl::run();
PuzzleGame::StartGame(params); Это статический метод будет вызываться перед
каждым началом новой игры. Что он делает:
- Выбор случайного изображения (в случае если пользователь загрузил свои изображения).
- Создание виджетов-кнопок (паззлы) с частями изображения в случайном порядке
- Перерисовка главного экрана
Далее, собственно говоря, просто показываем окно с виджетами-кнопками. Запускаем главный цикл для обработки событий.
puzzle.hpp
Этот заголовочный файл связан непосредственно с созданием параметров, виджетов (паззлов).
1enum {
2 puzzle_pieces = 9, // including empty puzzle
3 puzzles_per_side = 3,
4 puzzle_size = 100,
5 spacing = 5
6};
7
8class Puzzle : public Fl_Button{
9public:
10 unsigned char sequence_number;
11 std::string path;
12 Fl_PNG_Image *stored_img_pointer;
13 Puzzle(int x, int y)
14 : Fl_Button(x, y, puzzle_size, puzzle_size),
15 stored_img_pointer(nullptr) {
16 }
17 ~Puzzle() { delete stored_img_pointer; }
18};
19
20class GameParams {
21public:
22 struct coordinates {
23 int x, y;
24 bool operator==(const coordinates& v) const {
25 return this->x == v.x && this->y == v.y;
26 }
27 };
28private:
29 static GameParams *instance;
30 coordinates standard_puzzle_coordinates[puzzle_pieces];
31 char free_puzzles[puzzle_pieces];
32 coordinates empty_box;
33 std::vector<std::unique_ptr<Puzzle>> puzzles;
34 Fl_Window *win;
35 std::string cur_directory;
36
37 GameParams(Fl_Window *a_win = nullptr)
38 : win(a_win)
39 {}
40 void CalculateStandardPuzzlePos();
41 void ResetFreePuzzles();
42 void NextUntestedPuzzles();
43 bool IsSolvability();
44 void CreateNewPuzzles();
45 void SelectRandomPicture();
46 Fl_PNG_Image *LoadPictureParts(std::unique_ptr<Puzzle>& tmp_puzzle);
47public:
48 void SetXYEmptyBox(int x, int y) { empty_box.x = x; empty_box. y = y; }
49 coordinates GetXYEmptyBox() { return empty_box; }
50 static GameParams *SetUpParams(Fl_Window *win) {
51 if(instance)
52 return instance;
53 GameParams *gi = new GameParams(win);
54 gi->CalculateStandardPuzzlePos();
55 return gi;
56 }
57 friend class PuzzleGame;
58 friend class ASearch;
59 friend void press_button_callback(Fl_Widget*, void*);
60 friend void solve_problem_callback(Fl_Widget*, void*);
61};
Класс Puzzle открыто наследуется от Fl_Button. Представляет собой пользовательский виджет. По 3-ём причинам потребовалось добавить свои свойства в стандартный виджет кнопки:
- Каждому виджету присваивается номер из последовательности следования паззлов. Это позволяет проверить, находится ли каждый паззл на своём месте. Если это так – головоломка решена.
- Когда выбирается пользовательская картинка (не стандартная) для создания паззла, то path позволяет обнаружить путь до части картинки, при загрузке которой могла произойти ошибка.
- Хранение указателя на картинку связанной с виджетом. Например, при создание
новой игры предыдущие виджеты должны быть освобождены из диманической памяти.
Однако они сами также должны освободить и ресурсы свяазанные с картинкой. Для
этого в деструкторе
~Puzzle() { delete stored_img_pointer; }требуется эта строка.
Переходим к классу GameParams. Здесь хочется отметить массив
standard_puzzle_coordinates. Он содержит элементы, состоящие из простой
структуры coordinates. Используется во время создания виджетов, а также для
проверки, находится ли виджет на своём месте. В классе Puzzle есть поле
sequence_number. Когда будет происходить проверка, то соответствующий номер
виджета (sequence_number) будет соответствовать индексу в массиве
standard_puzzle_coordinates. Затем проверятся текущие координаты виджета и
координаты выбранного элемента из массива.
cur_directory хранит путь к пользовательской директории с картинкой, если она,
конечно, будет выбрана. Выбор картинок происходит случайно c помощью метода
SelectRandomPicture(). Если это стандартное изображение, то будет просто
храниться строка “standard”, по которой можно определить, что части для паззла
берутся из массива данных стандартной картинки (об этом будет позже). Так что
этот путь тоже используется для создания паззлов.
empty box хранит координаты случайно выбранной пустой клетки.
После создания паззлов (представляют собой виджеты Puzzle) они хранятся в
последовательном контейнере vector: std::vector<std::unique_ptr<Puzzle>> puzzles; Однако стоит заметить, что сами виджеты оборачиваются в “умные
указатели”. Дело в том, что виджеты создаются в динамической памяти и,
соответственно, имеют фиксированный адрес соданного объекта. Нам этот адрес
пригодится как раз при восстановлении цепочки решения с помощью алгоритма A*.
Динамически созданные объекты довольно проблематично хранить в контейнерах STL.
При очистке (clear()) контейнера он будет вызывать деструктор хранимого объекта.
Но если бы хранились обычные указатели, то у них нет деструкторов. Нужно просто
для каждого из них вызвать оператор delete. Именно это позволяет сделать
“интеллектуальный” указатель, который представляет собой объект с деструктором.
Именно последний и вызовет delete для хранимого указателя в нём.
Метод IsSolvability(); позволяет проверить, решается ли созданная головоломка.
Подробнее о нём будет сказано позже.
50static GameParams *SetUpParams(Fl_Window *win) {
51 if(instance)
52 return instance;
53 GameParams *gi = new GameParams(win);
54 gi->CalculateStandardPuzzlePos();
55 return gi;
56}
Этот участок кода реализует паттерн singleton. Статический указатель *instance
хранит на протяжении всей работы программы единственный экземпляр параметров
игры. Если будет вызван метод SetUpParams второй раз, то он вернёт этот же
объект.
LoadPictureParts() создаёт объект Fl_PNG_Image, который представляет собой часть
изображения (т.е. паззл). Возвращённый этим методом объект затем будет связан с
виджетом. Это позволит виджету-кнопке показывать соответствующее изображение.
puzzle.cpp
Этот файл будет показан частями постепенно, иначе неудобно будет каждый раз возвращаться к одному большому куску кода.
Прежде всего должны вычисляться стандартные местоположения виджетов кнопок. Как
раз выше вызывается gi->CalculateStandardPuzzlePos();. Смотрим на описание
метода в файле реализации:
19void GameParams::CalculateStandardPuzzlePos()
20{
21 coordinates tmp;
22
23 int i, j, k = 0;
24 for(i = 0; i < puzzles_per_side; ++i)
25 for(j = 0; j < puzzles_per_side; ++j, ++k) {
26 tmp.x = i * (puzzle_size + spacing) + spacing;
27 tmp.y = j * (puzzle_size + spacing) + spacing + 20;
28 standard_puzzle_coordinates[k] = tmp;
29 }
30}
В общем-то здесь довольно простое заполнение массива координат. Учитывается свой промежуток и промежуток предыдущих вычисленных координат для виджетов. Индекс массива соответствует порядковумо номеру виджета. Координаты вычисляются сверху вниз:
В файле main.cpp после вычисления этих координат происходил запуск игры через
статический метод PuzzleGame::StartGame(params);. Хоть он и находится в другом
файле, но он очень простой, поэтому можно даже сейчас его рассмотреть. Всего-навсего он
состоит из поочередного вызова методов класса GameParams:
void PuzzleGame::StartGame(GameParams *gp)
{
gp->SelectRandomPicture();
gp->ResetFreePuzzles();
gp->CreateNewPuzzles();
gp->win->redraw();
}
Работа с файловой системой (перебор подкаталогов)
Теперь рассмотрим описание метода SelectRandomPicture():
150void GameParams::SelectRandomPicture()
151{
152 std::filesystem::path res_path = std::string("resources");
153 bool res_path_exists = std::filesystem::exists(res_path);
154 if(res_path_exists) {
155 std::vector<std::string> choices;
156 for (const auto& entry : std::filesystem::directory_iterator("resources"))
157 choices.emplace_back(entry.path().string());
158 choices.emplace_back("standard");
159 std::random_device rd;
160 std::mt19937 g(rd());
161 std::shuffle(choices.begin(), choices.end(), g);
162 if(choices[0] == "standard")
163 cur_directory.clear();
164 else {
165 cur_directory = choices[0];
166#if defined(_WIN32)
167 cur_directory.append("\\");
168#else
169 cur_directory.append("/");
170#endif
171 }
172 }
Первым делом проверяем, существует ли каталог с именем “resources”. Он создаётся
только тогда, когда пользователь мог загрузить своё изображение. В этом случае
также создаётся подкаталог с таким же именем, как и у картинки. Всё это надо
учитывать. То есть теоретически надо попытаться открыть каталог “resources” на
чтение, и если он есть, далее перебрать содержимое каталога – подкаталоги.
Для Unix-подобных систем всё это делается средставами, входящими в стандартную
библиотеку C и являющимися частью POSIX спецификации: заголовочный файл
"direct.h" и функции opendir и readdir. Однако нам нужна совместимость и с
Windows платформой. На Stackoverflow предлагают вариант с использованием
пользовательского заголовочника, который представляет собой совместимый слой как
с Windows, так и с Unix платформой: https://github.com/tronkko/dirent. Но там же
есть ещё вариант с использованием средств из стандарта C++ 17 STL. Ими мы и
воспользуемся.
152 std::filesystem::path res_path = std::string("resources");
153 bool res_path_exists = std::filesystem::exists(res_path);
154 if(res_path_exists) {
155 std::vector<std::string> choices;
156 for (const auto& entry : std::filesystem::directory_iterator("resources"))
157 choices.emplace_back(entry.path().string());
158 choices.emplace_back("standard");
Инициализируем объект класса path на основе строки, которая содержит
относительный путь (т.е. просто название каталога “resources”). Функция
filesystem::exists позволяет проверить, существует ли указанный путь на самом
деле. Она должна принимать экземпляр класса Path и возвращать логическое
значение false или true.
Если каталог “resources” существует, то теперь можно перебирать его. Для этого
зайдествован класс directory_iterator. Через цикл foreach можно итерироваться
по элементам, которые предтавляют собой экземплярами класса directory_entry (в
коде вместо этого используется спецификатор auto). Вообще, сам класс
directory_iterator очень необычен. Он одновременно является и диапазоном, а
также и просто итератором, который может быть задейстовован в алгоритмах STL.
Про этот класс можно сказать следующее:
- он проверяет каждый элемент один раз;
- порядок, в котором выполняется перебор, не определен;
- элементы каталога . и .. уже отфильтрованы.
Далее мы извлекаем информацию из объекта directory_entry, а именно путь через
метод path. Он вернёт объект типа path. У него также вызываем метод
string(), чтобы получить путь в виде этого объекта. Добавляем в контейнер
choices.
159 std::random_device rd;
160 std::mt19937 g(rd());
161 std::shuffle(choices.begin(), choices.end(), g);
162 if(choices[0] == "standard")
163 cur_directory.clear();
164 else {
165 cur_directory = choices[0];
166#if defined(_WIN32)
167 cur_directory.append("\\");
168#else
169 cur_directory.append("/");
170#endif
Теперь мы должны выбрать один каталог случайно. Для этого можно перешать
содержимое контейнера choices. Раньше для этого можно было бы использовать
алгоритм random_shuffle, однако с 17 стандарта его убрали. Остался только
shuffle, который 3-им аргументом принимает объект-генератор. Из примера отсюда
https://en.cppreference.com/w/cpp/algorithm/random_shuffle и был взят код.
Выбираем каталог с помощью первого выбранного в контейнере choises[0]. Если он
содержит имя “standard”, то cur_directory для GameParams очищаем, иначе
присваиваем название каталого и, в зависимости от платформы, добавляем
разделитель пути. Соответствующие макросимволы определены во время сборки
проекта в Make файле.
Далее в PuzzleGame::StartGame у нас идёт метод ResetFreePuzzles(). Он
довольно просто описан. Массив free_puzzles заполняется 1, что означает
свободные паззлы для создания игры.
Переходим к важному методу – CreateNewPuzzles(); для создания паззлов и
начала игры.
143void GameParams::CreateNewPuzzles()
144{
145 do {
146 NextUntestedPuzzles();
147 } while(!IsSolvability());
148}
Он состоит из попытки создания паззлов в случайном порядке до тех пор, пока не будет найдено состояния, в котором головоломка будет решаемой.
70void GameParams::NextUntestedPuzzles()
71{
72 int idx_random_puzzle;
73 std::unique_ptr<Puzzle> tmp_puzzle;
74 /*
75 * check if puzzles already were created
76 */
77 if(puzzles.size() != 0) {
78 puzzles.clear();
79 Fl::do_widget_deletion();
80 }
81 /*
82 * ======== creating puzzles ===========
83 */
84 win->begin();
85 for(int i = 0; i < puzzle_pieces; ++i) {
86 idx_random_puzzle =
87 0 + (int)((double)puzzle_pieces * rand()/(RAND_MAX + 1.0));
88 while(!free_puzzles[idx_random_puzzle])
89 idx_random_puzzle =
90 0 + (int)((double)puzzle_pieces * rand()/(RAND_MAX + 1.0));
91 free_puzzles[idx_random_puzzle] = 0;
92 /* empty puzzle */
93 if(idx_random_puzzle == puzzle_pieces-1) {
94 SetXYEmptyBox(standard_puzzle_coordinates[i].x,
95 standard_puzzle_coordinates[i].y);
96 continue;
97 }
98 /* common puzzle */
99 tmp_puzzle =
100 std::unique_ptr<Puzzle>(new Puzzle(standard_puzzle_coordinates[i].x,
101 standard_puzzle_coordinates[i].y));
102 tmp_puzzle->sequence_number = idx_random_puzzle;
103 Fl_PNG_Image *img = LoadPictureParts(tmp_puzzle);
104 switch (img->fail()) {
105 case Fl_Image::ERR_NO_IMAGE:
106 case Fl_Image::ERR_FILE_ACCESS:
107 fl_alert("%s: %s", tmp_puzzle->path.c_str(), strerror(errno));
108 exit(1);
109 case Fl_Image::ERR_FORMAT:
110 fl_alert("couldn't decode image");
111 exit(1);
112 }
113 tmp_puzzle->image(img);
114 tmp_puzzle->stored_img_pointer = img;
115 tmp_puzzle->callback(press_button_callback, this);
116 puzzles.push_back(std::move(tmp_puzzle));
117 }
118 ResetFreePuzzles();
119 /*
120 * Checking image shuffling
121 */
122 bool shuffled_img = false;
123 for(int i = 0; i < puzzle_pieces-1; ++i)
124 if(puzzles[i]->sequence_number != i) {
125 shuffled_img = true;
126 break;
127 }
128 if(!shuffled_img)
129 NextUntestedPuzzles();
130 win->end();
131}
Если мы заново начинаем игру, то перед созданием паззлов необходимо очистить
предыдущие. Они хранятся в контейнере vector под именем puzzles. Как уже
было раньше сказано, виджеты оборачиваются в умные указатели, поэтому очистка
контейнера приведёт и к очистке самих виджетов.
77 if(puzzles.size() != 0) {
78 puzzles.clear();
79 Fl::do_widget_deletion();
80 }
Проблема здесь ещё в том, что библиотека FLTK может удерживать удаление
виджетов. Вместо этого просто запланировать их удаление.
Fl::do_widget_deletion() удаляет виджеты, ранее запланированные на удаление.
Создание паззлов
81/*
82 * ======== creating puzzles ===========
83 */
84 win->begin();
85 for(int i = 0; i < puzzle_pieces; ++i) {
86 idx_random_puzzle =
87 0 + (int)((double)puzzle_pieces * rand()/(RAND_MAX + 1.0));
88 while(!free_puzzles[idx_random_puzzle])
89 idx_random_puzzle =
90 0 + (int)((double)puzzle_pieces * rand()/(RAND_MAX + 1.0));
91 free_puzzles[idx_random_puzzle] = 0;
92 /* empty puzzle */
93 if(idx_random_puzzle == puzzle_pieces-1) {
94 SetXYEmptyBox(standard_puzzle_coordinates[i].x,
95 standard_puzzle_coordinates[i].y);
96 continue;
97 }
98 /* common puzzle */
99 tmp_puzzle =
100 std::unique_ptr<Puzzle>(new Puzzle(standard_puzzle_coordinates[i].x,
101 standard_puzzle_coordinates[i].y));
102 tmp_puzzle->sequence_number = idx_random_puzzle;
103 Fl_PNG_Image *img = LoadPictureParts(tmp_puzzle);
Сначала мы указываем библиотеке FLTK, что все последующие соданные виджеты будут
непосредственно вложены в главное окно программы (оно тоже является виджетом с
точки зрения FLTK). Для этого используется win->begin().
Далее в цикле создаём непосредственно сами виджеты-кнопки-паззлы. Цикл будет
проходить 9 раз (puzzle_pieces = 9).
Выбирается случайное число от 0 до 9 (не включительно): 0 + (int)((double)puzzle_pieces * rand()/(RAND_MAX + 1.0));. Почему именно с помощью такого выражения получаем
псевдослучайное число? На сайте opennet есть документация и пример по
использованию функции rand(). https://www.opennet.ru/man.shtml?topic=rand
idx_random_puzzle получит случайное число только в том случае, если в массиве
free_puzzles в соответствующем индексе (idx_random_puzzle) будет значение 1
(т.е. этот паззл свободен).
Суть в том, что цикл последовательно проходит и по массиву
standard_puzzle_coordinates. Как уже было раньше сказано (и показано) он
последовательно содержит координаты как именно должны располагаться виджеты.
Если кратко – проход идёт по столбцам. Таким образом, мы по очереди заполняем
главное окно программы. Но выбираем картинку для виджета в случайном порядке.
Именно для этого нужен idx_random_puzzle.
Выбор пустой клетки осуществляется следующим образом: если индекс получается
равным 8 (puzzle_pieces-1), то empty_box заполняется координатами из
очередного элемента в standard_puzzles. Поэтому пустая клетка может
расположиться в любом месте поля. Отрывок кода с определением пустой клетки:
92 /* empty puzzle */
93 if(idx_random_puzzle == puzzle_pieces-1) {
94 SetXYEmptyBox(standard_puzzle_coordinates[i].x,
95 standard_puzzle_coordinates[i].y);
96 continue;
97 }
Здесь мы после заполнения empty_box через continue пропускаем оставшуюся
часть цикла. То есть никакого виджета с координатами
standard_puzzle_coordinates[i].x и standard_puzzle_coordinates[i].y не будет
создано.
Значит idx_random_puzzle от 0 по 7 соответствует частям картинки. Сама
картинка при этом строга сортирована согласно этим же номерам. Имеется в виду
то, что название частей в каталоге содержат в себе число (об этом позже). Пример
соответствия:
tmp_puzzle является “умным указателем”, который содержит адрес на объект типа
Puzzle. Инициализируем его с помощью динамического создания виджета Puzzle.
Последнему передаём через конструктор аргументы с координатами размещения. Они
берутся из standard_puzzle_coordinates. Индекс соответствует текущей итерации
цикла for. Присваиваем номер случайно выбранной части картинки
tmp_puzzle->sequence_number = idx_random_puzzle;:
98 /* common puzzle */
99 tmp_puzzle =
100 std::unique_ptr<Puzzle>(new Puzzle(standard_puzzle_coordinates[i].x,
101 standard_puzzle_coordinates[i].y));
102 tmp_puzzle->sequence_number = idx_random_puzzle;
103 Fl_PNG_Image *img = LoadPictureParts(tmp_puzzle);
Стоит отметить, что используется “умный указатель” unique_ptr со своей
концепцией владения. Только один unique_ptr может владеть объектом. Поэтому
при копировании или присваивании задействуется механизм копирования перемещением
или присваивание перемещением соответственно. Для этого требуется rvalue
выражение (временный объект, анонимный объект, литерал и т.п.). Выражение new Puzzle(standard_puzzle_coordinates[i].x, standard_puzzle_coordinates[i].y)
вполне подходит.
Fl_PNG_Image *img = LoadPictureParts(tmp_puzzle); создаст часть изображения в
зависимости от sequence_number: найдет этот номер в каталоге. Сам католог, как
уже было сказано, определяется в cur_directory. В нём находится относительный
путь к пользовательской картинке. Например, resources/test_picture. Для
стандартной картинки cur_directory не нужен будет, т.к. оно будет в виде
массива данных.
На самом деле загрузка изображения довольно сложная тема. Подробнее о Вызове
метода LoadPictureParts() будет сказано в следующей статье. Пока что
достаточно знать, что указатель *img содержит адрес созданного изображения
как объект Fl_PNG_Image.
Далее void GameParams::NextUntestedPuzzles() содержит оставшуюся такую часть:
113 tmp_puzzle->image(img);
114 tmp_puzzle->stored_img_pointer = img;
115 tmp_puzzle->callback(press_button_callback, this);
116 puzzles.push_back(std::move(tmp_puzzle));
117 }
118 ResetFreePuzzles();
119 /*
120 * Checking image shuffling
121 */
122 bool shuffled_img = false;
123 for(int i = 0; i < puzzle_pieces-1; ++i)
124 if(puzzles[i]->sequence_number != i) {
125 shuffled_img = true;
126 break;
127 }
128 if(!shuffled_img)
129 NextUntestedPuzzles();
130 win->end();
Через метод image передаём указатель на только что созданный объект
изображения. Это позволит виджету-кнопке иметь изображение. Затем сохраняем этот
же адрес в stored_img_pointer, чтобы деструктор виджета потом освободил
динамическую память, связанную с объектом картинки.
tmp_puzzle->callback(press_button_callback, this); связываем виджет с
callback-функцией press_button_callback, а также передаём данные для неё –
это будет такущий объект GameParams (указатель this). Эта функция позволит
при каждом нажатии на виджет проверить, можно ли поменять местами текущий виджет
и пустое место. Такая ситуация возможна только в том случае, если виджет
находится рядом с пустым местом. Также callback-функция проверяет нахождения
всех виджетов на своих местах по координатам. Если это так – головоломка
решена.
Это краткое описание callback-функции. Подробнее о ней будет ниже. Но сейчас
продолжу описание оставшихся строк в NextUntestedPuzzles().
puzzles.push_back(std::move(tmp_puzzle)); добавляем в контейнер vector
созданный виджет. Здесь используется функция std::move из стандартной библиотеки.
Дело в том, что tmp_puzzle у нас является l-value выражением. Для добавления в
контейнер через push_back при передаче l-value выражения будет соответственно
вызван обычный конструктор копирования класса unique_ptr, однако он описан в
библиотеке как удаленный (= delete). Это значит, что можно использовать только
конструктор перемещения. Для этого нужно зайдествовать перегруженный метод
push_back, который принимает r-value выражения. Чтобы превратить l-value в
r-value как раз и вызвана функция std::move.
После добавления заполняем массив free_puzzles единицами. Делаем это сейчас,
потому что созданная головоломка может быть нерешаемой или неперемешанной, и придётся снова
создавать виджеты.
Затем проверяем, действительно ли мы получили головоломку. Может так быть, что
все виджеты случайно окажутся на верных местах. Мы просто в цикле перебираем все
виджеты, смотрим, есть ли хоть одно несовпадение sequence_number со счётчиком
итерации. Если есть несовпадение, то значит как минимум один виджет не находится
на своём месте, иначе проходим путь создания виджетов по новой. Если что, в
контейнере puzzles все виджеты хранятся в порядке создания.
В завершении win->end() указываем, что больше нет вложенных виджетов в главном
экране программы.
gameplay.hpp
Объявление callback функции presss_button_callback для обработки нажатий на
виджеты находится в заголовочном файле gameplay.hpp. Он
содержит следущее:
1#ifndef GAMEPLAY_HPP_SENTRY
2#define GAMEPLAY_HPP_SENTRY
3
4#include "puzzle.hpp"
5
6void press_button_callback(Fl_Widget *w, void *params);
7
8class PuzzleGame {
9public:
10 static bool IsFinalPlacement(GameParams *gp);
11 static void StartGame(GameParams *gp);
12};
13
14#endif
StartGame() ранее уже был рассмотрен. IsFinalPlacement() используется как
press_button_callback(), так и алгоритмом A* для решения головоломки.
gameplay.cpp:
10static bool is_next_to_empty_box(GameParams::coordinates empty_box_pos,
11 GameParams::coordinates current_pos)
12{
13 return
14 (current_pos.x - spacing - puzzle_size == empty_box_pos.x &&
15 current_pos.y == empty_box_pos.y) ||
16 (current_pos.x == empty_box_pos.x &&
17 current_pos.y - spacing - puzzle_size == empty_box_pos.y) ||
18 (current_pos.x + puzzle_size + spacing == empty_box_pos.x &&
19 current_pos.y == empty_box_pos.y) ||
20 (current_pos.x == empty_box_pos.x &&
21 current_pos.y + puzzle_size + spacing == empty_box_pos.y);
22}
23
24static bool is_coordinate_match(GameParams::coordinates& first,
25 GameParams::coordinates& second)
26{
27 return first.x == second.x && first.y == second.y;
28}
29
30bool PuzzleGame::IsFinalPlacement(GameParams *gp)
31{
32 bool is_match = 1;
33 auto lambda = [gp, &is_match](const std::unique_ptr<Puzzle>& next_puzzle) {
34 GameParams::coordinates pos_next_puzzle =
35 { next_puzzle->x(), next_puzzle->y() };
36 GameParams::coordinates target_pos =
37 gp->standard_puzzle_coordinates[next_puzzle->sequence_number];
38 if(!is_coordinate_match(pos_next_puzzle, target_pos))
39 is_match = 0;
40 };
41 std::for_each(gp->puzzles.begin(), gp->puzzles.end(), lambda);
42 return is_match;
43}
44
45void press_button_callback(Fl_Widget *w, void *params)
46{
47 GameParams *gp = reinterpret_cast<GameParams*>(params);
48 GameParams::coordinates current_pos = { w->x(), w->y() };
49 if(is_next_to_empty_box(gp->GetXYEmptyBox(), current_pos)) {
50 w->position(gp->GetXYEmptyBox().x, gp->GetXYEmptyBox().y);
51 gp->SetXYEmptyBox(current_pos.x, current_pos.y);
52 }
53 w->parent()->redraw();
54 if(PuzzleGame::IsFinalPlacement(gp)) {
55 int answer = fl_choice("You win. Play again?", "No", "Yes", nullptr);
56 if(answer)
57 PuzzleGame::StartGame(gp);
58 else
59 gp->win->hide();
60 }
61}
62
63void PuzzleGame::StartGame(GameParams *gp)
64{
65 gp->SelectRandomPicture();
66 gp->ResetFreePuzzles();
67 gp->CreateNewPuzzles();
68 gp->win->redraw();
69}
Начнём с press_button_callback(). Эта функция прнимает 2 аргумента: указатель
на виджет, который вызвал её, а также ресурс, который может использоваться при
обработке нажатий. В puzzle.cpp была такая строка
tmp_puzzle->callback(press_button_callback, this);. Здесь мы передавали объект
GameParams. В нём хранится вся необходимая информация: контейнер паззлов,
стандартные координаты размещений, координаты пустой клетки. Поэтому сейчас
callback-функция может воспользоваться этой информацией.
Преобразуем явно указатель void * на GameParams. Кстати, в языке Си это
можно было сделать неявно. Здесь пришлось задействовать механизм приведений
через reinterpret_cast.
current_pos запоминает текущие координаты виджета. Затем проверяем, находится
ли он рядом с пустым квадратом. Для этого вызываем функцию is_next_to_empty_box().
10static bool is_next_to_empty_box(GameParams::coordinates empty_box_pos,
11 GameParams::coordinates current_pos)
12{
13 return
14 (current_pos.x - spacing - puzzle_size == empty_box_pos.x &&
15 current_pos.y == empty_box_pos.y) ||
16 (current_pos.x == empty_box_pos.x &&
17 current_pos.y - spacing - puzzle_size == empty_box_pos.y) ||
18 (current_pos.x + puzzle_size + spacing == empty_box_pos.x &&
19 current_pos.y == empty_box_pos.y) ||
20 (current_pos.x == empty_box_pos.x &&
21 current_pos.y + puzzle_size + spacing == empty_box_pos.y);
22}
Порядок проверки таков: слева, сверху, справа и снизу. Например, (current_pos.x -spacing - puzzle_size == empty_box_pos.x && current_pos.y == empty_box_pos.y)
для проверки нахождения empty box слева. Мы учитываем промежуток перед виджетом
и саму ширину пустой клетки (она имеет тот же размер, что и все паззлы), поэтому
отнимаем от текущего местоположения по оси x spacing и puzzle_size.
Координаты по оси y должны оставаться такими же. Сравниваем получившиеся
координаты с координатами empty_box. С остальными сторонами действует похожий
принцип.
На рисунке синим отмечены промежутки, которые учитываются для вычисления пустой клетки.
Если действительно оказалось так, что виджет находится рядом с пустой клеткой, тогда обмениваем их координаты:
49 if(is_next_to_empty_box(gp->GetXYEmptyBox(), current_pos)) {
50 w->position(gp->GetXYEmptyBox().x, gp->GetXYEmptyBox().y);
51 gp->SetXYEmptyBox(current_pos.x, current_pos.y);
52 }
После обмена надо перерисовать главное окно программы. Это можно сделать через
текущий виджет. Он хранит указатель на своего родителя. Родитель текущего
виджета – главное окно программы. Поэтому можно написать
w->parent()->redraw();
Теперь надо узнать, оказались ли все виджеты на своих местах, чтобы завершить
текущую игру. Для этого описан статический метод IsFinalPlacement:
30bool PuzzleGame::IsFinalPlacement(GameParams *gp)
31{
32 bool is_match = 1;
33 auto lambda = [gp, &is_match](const std::unique_ptr<Puzzle>& next_puzzle) {
34 GameParams::coordinates pos_next_puzzle =
35 { next_puzzle->x(), next_puzzle->y() };
36 GameParams::coordinates target_pos =
37 gp->standard_puzzle_coordinates[next_puzzle->sequence_number];
38 if(!is_coordinate_match(pos_next_puzzle, target_pos))
39 is_match = 0;
40 };
41 std::for_each(gp->puzzles.begin(), gp->puzzles.end(), lambda);
42 return is_match;
43}
Здесь мы используем алгоритм for_each из STL для перебора контейнера vector,
который состоит из наших паззлов. 3-им аргументом для него мы описали lambda
выражение. Оно захватывает ресурсы из локальной области:
- указатель
*gpпо значению - переменная
is_matchпо ссылке. Она используется как флажок: при значении true – все виджеты на месте, иначе будет false.
Так как контейнер puzzles у нас состоит из элементов
std::unique_ptr<Puzzle>, то и lambda выражение будет принимать параметр этого
типа по ссылке на константу (т.к. сам виджет изменяться не будет здесь).
В pos_next_puzzle запоминаем координаты текущего виджета при обходе
контейнера. target_pos хранит координаты, которые должны быть у этого виджета.
С помощью массива standard_puzzle_coordinates мы можем получить эти
координаты. Каждый паззл хранит свой порядковый номер sequence_number. Именно
он и будет ключом/индексом к массиву. Далее просто проверяем координаты x и y
для pos_next_puzzle и targer_pos через функцию:
24static bool is_coordinate_match(GameParams::coordinates& first,
25 GameParams::coordinates& second)
26{
27 return first.x == second.x && first.y == second.y;
28}
Здесь просто происходит сравнения по x и y. Если произойдёт несовпадение, то
вернётся false, а is_match присваивается 0 (которое тоже преобразуется к
false, т.к. тип bool). Сам метод IsFinalPlacement вернёт значение
is_match.
Если оказалось так, что все виджеты на месте, то выводим диалоговое окно. Раньше
для этого использовалась функция fl_ask из FLTK, но т.к. она стала deprecated,
то вместо неё используем fl_choice:
24 if(PuzzleGame::IsFinalPlacement(gp)) {
25 int answer = fl_choice("You win. Play again?", "No", "Yes", nullptr);
26 if(answer)
27 PuzzleGame::StartGame(gp);
28 else
29 gp->win->hide();
30 }
31}
fl_choice похожа на функцию printf из стандартной библиотеки Си: первым
аргументом она принимает форматную строку, которая может включать директиву
пребразования (начинается с символа %), а сам аргумент для неё будет последним
в списке параметров fl_choice. Но т.к. нам не нужны параметры для строки, то
последним аргументом указываем nullptr.
fl_choice возвращает значение в зависимости от того, какую кнопку нажмёт
пользователь. Нумерация параметров начинается с 0 со второго аргумента. Это
значит, что No соответствует 0, Yes 1. В зависимости от этого начинаем
новую игру, или завершаем работу программы через gp->win->hide() – это значит
скрыть главное окно программы. Диалоговое окно будет таким:
Проверка решаемости головоломки
Ранее описывался метод создания паззлов:
143void GameParams::CreateNewPuzzles()
144{
145 do {
146 NextUntestedPuzzles();
147 } while(!IsSolvability());
148}
NextUntestedPuzzles() уже был рассмотрен. Он относится непосредственно к
созданию паззлов. Настал черёд IsSolvability().
133bool GameParams::IsSolvability()
134{
135 int counter = 0;
136 for(size_t i = 0; i < puzzles.size()-1; ++i)
137 for(size_t j = i+1; j < puzzles.size(); ++j)
138 if(puzzles[i]->sequence_number > puzzles[j]->sequence_number)
139 ++counter;
140 return counter % 2 == 0;
141}
Благодаря нему мы отсеиваем нерешаемые головоломки. Правило, позволяющее проверить, можно ли решить головоломку:
невозможно решить головоломку, если количество инверсий во входном состоянии нечётное.
Что такое инверсия? Пара плиток образует инверсию, если значения на плитках расположены в обратном порядке по сравнению с тем, где они должны находиться. Например:
Количество инверсий составляет здесь 8. Пары: (7, 6), (7, 4), (7, 5), (8, 6), (8, 4), (8, 5), (6, 4), (6, 5). Так как число чётное, то головоломка решаемая.
Алгоритм IsSolvability проходит по контейнеру паззлов puzzles внешним циклом на 1 элемент меньше, т.к. как внутренний цикл будет брать следующие значения и сравнивать с ним. То есть будет попарное сравнение. Если предыдущий элемент оказался больше следущего, то счётчик counter увеличиваем на 1. После всего этого проверяем на чётность. Находим остаток от деления на 2. Если он равен 0, то получили чётное количество пар, а значит – головоломка решаема.
В следующей статье будет рассматривать метод LoadPictureParts, создание
массива данных из стандартной картинки, загрузка пользовательских изображений. В
общем всё, что связано с изображениями.