1. Розробка і обгрунтування технічного завдання

1.1 Вимоги користувача

У курсовій роботі я розробив об'єктно-орієнтовану систему для генерації лабіринту. Умови програми придумані для її цікавості цікавості користувачеві. Якщо поглянути на розробку і суб’єктивно обґрунтувати її, то можна сказати, що це буде не тільки система генерації лабіринту, а ще й гра.

Умови цієї гри наступні:

Для того щоб виграти, потрібно пройти в протилежний кут лабіринту, не втративши при цьому все здоров'я. Спочатку у гравця 100 життів. Якщо гравець зустрінеться з перешкодою, він втрачає деяку кількість життів.

Можливі наступні перешкоди:

1. Монстр. Він завжди видно на екрані, забирає 25 життів.

2. Пастка. Її не можна побачити, зате легко знайти, забирає 10 життів.

3. Стіна міцна. Гравець може пройти через неї і втратить 10 життів.

4. Стіна слабка (напівпрозора). Те ж саме, забирає 5 життів.

Відмінність монстрів і пасток від стін полягає в тому, що при зустрічі з монстром персонаж при нестачі здоров'я гине, а через стіну він не зможе пройти.

Управління: персонаж управляється стрілками і мишею. При управлінні мишею (напівавтоматичне управління), вам просто потрібно клікнути на будь-який порожній клітці, а ваш персонаж сам знайде найкоротший шлях до неї. Щоб пройти крізь стіну, клацніть по ній, коли персонаж знаходиться поруч зі стіною. Будьте уважні - він може наступити на пастку або на монстра! Стрілками персонаж управляється повністю вручну.

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

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

Esc - вихід з гри

F10 - включити / відключити монстрів у грі

Стрілки - переміщення персонажа

Home - знайти вихід автоматично

Ви можете вибирати різні рівні складності клавішами F1-F9.

Клавіша	Розмір лабіринту	Кількість монстрів (тільки режим F10)
F1	18х17	мало
F2	30х30	багато
F3	50х50	мало
F4	50х50	багато
F5	100х100	мало
F6	100х100	багато
F7	200х200	мало
F8	500х500	мало
F9	1000х1000	мало

1.2 Вимоги до інтерфейсу програми

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

При розробці об'єктно-орієнтованої системи для генерації лабіринту я опирався на наступні вимоги користувальницького інтерфейсу.

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

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

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

Інтерфейс не має підказок щодо клавіш пересування гравця, так як програма дуже проста у використанні.

3. Вимоги до програмної реалізації

Програма повинна відповідати вимогам користувача.

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

Вимоги до програмної реалізації:

• Програма має бути реалізована графічно;

• Вибір відповідних клітинок здійснюється за допомогою клавіш;

• Вибір відповідних клітинок здійснюється за допомогою курсора;

• Програма має витримувати усі тести користувача;

• Програмний комплекс повинен містити стандартні модулі, а також модулі користувача (за наявності), процедури і функції користувача;

• Програма повинна відтворювати об'єктно-орієнтовану систему для генерації лабіринту.

Вимоги до реалізації коду:

• Код має бути написаний з урахуванням деяких коментарів;

• Код має бути написаний з вимогами до усіх абзаців, відступів тощо;

3. Аналіз і вибір методу розв'язання основної задачі

При розробці об'єктно-орієнтованої системи для генерації лабіринту, основною задачею було зобразити генерацію нового лабіринту . Розглянемо основні методи генерації лабіринту.

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

Якщо ліміт M і N невеликий, можна зробити рекурсію. Встановлюємо точку входу . Спочатку генерується основний хід. Рухаємося по клітинках, змінюючи вектор руху випадково за або проти годинникової стрілки, в залежності від значення випадкового числа, і з перевіркою touch краю (якщо торкнулися, то ставимо вихід). З кожним кроком запам'ятовуємо координати "пройденої точки" і збільшуємо рівень рекурсії. Отже, припустимо, вихід досягнутий. Коли досягаємо виходу, починаємо зниження рівня рекурсії з відновленням координат вищезгаданої точки, і в залежності від випадковості (наприклад 50%) з того ж алгоритму генеруємо боковий хід. Тоді, при створенні основного ходу, кінцем створення у нас служитиме досягнення краю лабіринту.

При генерації бічних ходів кінцем процесом можна зробити ліміт на рівень рекурсії - наприклад лише 50 клітинок, але взагалі це на власний розсуд. Закінчуємо генерацію бічного ходу, зменшуємо рівень рекурсії основного ходу, відновлюємо координати, і розраховуємо вірогідність створення нового бічного ходу. Якщо треба, то створюємо його. А потім знову повертаємося до основного ходу.

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

Недоліком такого методу є рекурсія, яка, при великих лабіринтах, їсть пам'ять у великих кількостях.

Наступним прикладом розглянемо приклад одного з найпростіших методів створення прямокутного лабіринту. Консольна програма приймає в якості параметрів ширину і висоту лабіринту (цілі числа більше 1, задаються за допомогою ключів-W та H, відповідно), а також значення ініціалізуюче генератор випадкових чисел (ціле число, задається за допомогою ключа-S). Створений візерунок виводиться у стандартний вивід символами псевдографіки у кодуванні UTF8 (за замовчуванням) або CP866 (для цього потрібно скомпілювати додаток з певним макросом ENCODE_CP866). NB! Для розбору параметрів командного рядка використовується GNU getopt.h

Лабіринт складається з прямокутних комірок, кожні дві сусідні (по вертикалі або горизонталі) комірки можуть бути з'єднані тунелем. Принцип побудови лабіринту досить простий. Для випадково вибраної комірки у випадковому порядку відвідуються 4 сусідні комірки: "північна", "південний", "західна" і "східна". Якщо сусідній осередок не знаходиться за межами лабіринту і не був відвідано раніше, то ця комірка з'єднується з сусіднім "тунелем", і процес повторюється вже для цієї сусідньої комірки. Таким чином обходяться всі комірки в лабіринті.

Недолік – простота.

У курсовій роботі використані обидва методи, але з доопрацюванням графіки та маленької гри.

3. Висновки

У розділі «Розробка і обґрунтування технічного завдання» було розроблено об'єктно-орієнтовану систему для генерації лабіринту, розглянуто та проаналізовано вимоги користувача, визначено вимоги до інтерфейсу програми, до реалізації програмного коду а також проаналізовано та розглянуто основні методи для генерації лабіринту.