Знаходження найкоротшого шляху в лабіринті

Організація роботи

Для зручної колаборації над програмою ми створили GitHub репозиторію для нашого проєкту. Під час першої особистої зустрічі ми вивчали разом наш основний алгоритм BFS, та декомпозували увесь проєкт на менші функції, а саме read_file(filename: str) -> list[list[int | str]], get_shortest_path(matrix: list[list[int | str]], start: tuple[int, int]) -> list[tuple[int, int]] | int, visualize_results(shortest_path: list[tuple[int, int]], matrix: list[list[int | str]]) -> str | None, а також допоміжні функції: find_start(matrix: list[list[int | str]]) -> tuple[int, int], is_valid(matrix: list[list[int | str]], row: int, column: int) -> bool (щоб перевіряти, чи клітина лабіринту є валідною для відвідування), get_neighbors(matrix: list[list[int | str]], row: int, column: int) -> list[tuple[int, int]]. Кінцевою стала розробка головної функції main(), що об’єднувала б увесь функціонал в єдину програму. Розподіливши завдання між собою ми виконували їх, підтримуючи зв’язок одне з одним, а також із Софією. Наша менторка швидко відповідала на наші запитання, та зрозуміло пояснювала вимоги до проєкту, даючи практичні поради щодо реалізації, за що ми їй вдячні.

Частина Джії

Функція read_file призначена для обробки лабіринту, збереженого у файлі формату .csv і перетворення його у список списків. Лабіринт може містити цілі числа 0 і 1, а також символи S (старт) і F (фініш). Головне завдання функції — повернути коректно оброблений лабіринт або повідомити про помилку, якщо дані не відповідають очікуваному формату.

Функція починає з відкриття файлу у режимі читання з кодуванням UTF-8. Далі вона читає файл пострічково, кожен рядок обробляється за допомогою методу split(','), який розбиває рядок на окремі елементи. Кожен елемент аналізується: якщо це '1' або '0', вони конвертуються в цілі числа; символи S і F залишаються рядками. Якщо зустрічається будь-який інший символ, функція негайно повертає рядок 'Incorrect maze', вказуючи на помилку у вхідних даних.

Функція також перевіряє наявність ключових символів S і F. Для цього ведеться підрахунок цих символів у змінній count_s_f. Крім того, функція перевіряє, чи обидва символи зустрічаються хоча б в одному рядку. Якщо S і F відсутні або зустрічаються більше одного разу, функція також повертає 'Incorrect maze'. Кінцевий результат залежить від коректності вхідних даних. Якщо всі перевірки пройдені успішно, повертається список списків, де кожен вкладений список відповідає одному рядку лабіринту. Якщо ні - ‘Incorrect maze’

Функція main() є точкою входу для користувача, що керує всім процесом: від обробки вхідних даних до збереження та візуалізації результатів. Далі - детальний опис того, що відбувається в цій функції та для чого використовується кожна змінна і дія. Спершу, за допомогою argparse, функція налаштовує інтерфейс командного рядка. Об’єкт ArgumentParser створює можливість приймати параметри від користувача Змінна parser описує програму: користувач отримує короткий опис програми, що допомагає зрозуміти ї призначення. У цьому випадку це пошук найкоротшого шляху лабіринті.

Далі визначаються два аргументи:

1. input_file — параметр, який вказує шлях до CSV-файлу з лабіринт
2. -no-visualization — параметр-прапорець, що відключає візуалізац результатів. Якщо цей флаг присутній, змінна disable_visualization отримує значення True.

Отримавши аргументи за допомогою args = parser.parse_args(), програма зчитує їх у змінні: input_file — містить шлях до файлу лабіринту. disable_visualization — визначає, чи потрібно показувати візуалізацію.

Далі функція перевіряє існування файлу за допомогою os.path.isfile. Якщо файл не знайдено, програма виводить повідомлення про помилку і завершує роботу. Якщо файл існує, його зчитування відбувається за допомогою функції read_file. Вона повертає матрицю лабіринту (matrix_maze) або викликає виключення у разі помилок. Якщо лабіринт має неправильний формат (наприклад: відсутні початкова або кінцева точки), функція перевіряє це і повідомляє користувача про помилку.

Далі функція find_start шукає початкову точку лабіринту. Якщо ї немає, програ завершується з повідомленням про помилку.

Основний етап — виклик функції get_shortest_path, яка знаходить найкоротший шлях від старту до фінішу. Якщо шлях не знайдено (функція повертає -1), програ повідомляє, що шляхів до виходу немає.

Після успішного знаходження шляху його довжина виводиться в консоль. Якщо візуалізація не вимкнена (тобто disable_visualization = False), функц visualize_results виводить графічне представлення лабіринту і шляху в консоль або зберігає у файл, якщо лабіринт занадто великий.

На фінальному етапі функція створює текстовий файл з координатами кроків. Файл іменується залежно від кількості кроків та розмірів лабіринту ({кількість_кроків} steps{розмір_матриці}_matrix.txt) і містить покроковий шлях.

Таким чином, функція main() забезпечує повний цикл: отримання даних, їх обробка, пошук шляху, виведення результатів і їх збереження. Кожен ї етап також слідкує помилками.

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

Частина Марти

def get_shortest_path_recurtione(matrix: list[tuple[int, int]], start: tuple[int, int]) - list[tuple[int, int]]: Функція get_shortest_path знаходить найкоротший шлях у лабіринті, представленому у вигляді двовимірної матриці.

Матриця: • 0 означає прохідну клітинку • 1 означає стіну (непрохідна клітинка) • 'S' позначає стартову позицію. • 'F' позначає кінцеву позицію.

Функція повертає список координат у форматі (рядок, стовпець), які представляють послідовність кроків від старту до фінішу. Якщо шляху не існує, повертається -1

Принцип роботи функції:

Вхідні параметри: matrix: Двовимірний список, який представляє лабіринт. start: Кортеж координат стартової позиції у форматі (рядок, стовпець).

Допоміжна функція recurtione: Виконує пошук сусідніх клітинок (get_neighbors) і додає їх до черги queue. Якщо клітинка вже відвідана (є у множині visited), вона пропускається. Якщо знайдена клітинка з кінцевою точкою ('F'), пошук завершується, і повертається шлях. В іншому випадку функція рекурсивно викликає себе для наступних сусідніх клітинок.

Основна логіка: Ініціалізується черга queue для зберігання клітинок, які потрібно перевірити. Створюється множина visited, щоб уникнути повторного відвідування клітинок. Викликається рекурсивна функція recurtione, яка будує шлях.

Повернення результату Шлях формується як список координат, починаючи зі стартової позиції і додаючи результат роботи recurtione.

Порівняння із реалізацією через цикл while Використання рекурсії в пошуках найкоротшого шляху є менш оптимальним рішенням через ризик переповнення черги викликів (особливо на великих матрицях). Тому в результаті ми обрали використання циклу while в остаточній програмі.

Досвід роботи: Мені дуже сподобалась робота в команді, усі ми були організовані, разом розібралися в алгоритмі та декомпозували задачу і кожен відповідально поставився до своїх завдань. Також ми отримали корисний досвід та покращення розуміння теорії графів: • Розуміння пошуку в ширину (BFS) Завдяки цьому проєкту ми зрозуміли, як працює BFS на практиці. Ми побачили, як використання черги допомагає систематично проходити всі вершини та знаходити найкоротший шлях. • Моделювання графів Ми отримали досвід у представленні реальних задач (лабіринт) у вигляді графу. Це допомогло краще зрозуміти зв’язки між клітинками та алгоритми їх обробки • Робота з пошуком шляху Ми навчилися розв’язувати задачі оптимізації шляхів, які мають багато практичних застосувань зокрема у робототехніці, логістиці та ігровому програмуванні. • Практичне розуміння складності Проєкт продемонстрував важливість вибору ефективного алгоритму для задачі. Ми усвідомили, як структура коду (рекурсія або цикл) впливає на продуктивність і можливість роботи з великими даними. • Готовність до реальних задач Робота над цією функцією дала розуміння, як алгоритми пошуку в графах можна використовувати для розв’язання прикладних задач: навігації, аналізу мереж, і навіть створення ігор Цей проєкт був важливим кроком у поглибленні наших знань з теорії графів та їх застосування в програмуванні.

Частина Віктора

Я, Сиротюк Віктор, працював над такими функціями, як "find_start" і "generate_maze". Спочатку я розповім як працює моя перша функція.

Отже, функція "find_start" шукає в лабіринті позицію старту, позначену символом "S" і повертає ї координати. Лабіринт представлений у вигля двовимірного списку, кожен елемент якого можу бути числом або стрічкою. Я використав вкладені цикли, щоб ітеруватися і по рядках, і по стовпцях нашого лабіринту. Таким чином я перебирав всі елементи двовимірного списку(матриці) і перевіряв чи вони не містять символ "S". У позитивному випадку функція повертає кортеж із координатами точки старту. Тепер я розповім про функцію, яка генерує лабіринт допомогою алгоритму глибини пошуку (Depth-First Search, DFS). Лабіринт представлений у вигляді двовимірної матриці, де: "1" означає стіну, "0" означає відкритий прохід, "S" — початкова точка, "F" — фінішна точка. Перш за все я перевіряю чи введені допустимі розміри лабіринту: якщо значення аргументів менші за 3, викидається виняток ValueError. Мінімальний розмір лабіринту має бути 3x3, оскільки для коректної роботи алгоритму потрібно хоча б мінімальну кількість простору для створення стін і проходів. Якщо матриця має менші розміри, неможливо ефективно використовувати алгоритм DFS, оскільки це призведе до того, що не буде можливості побудувати хоча б один прохід між клітинками. Наступним кроком, я генерую лабіринт повністю заповнений одиничками. Далі випадковим чином обираю координати початкової позиції. Причому я працюю лише з парними індексами, оскільки в лабіринті використовуються стіни, що розташовані між парними клітинками. Створення стін між парними індексами дозволяє правильно формувати прохід. Замість того, щоб використовувати кожну клітинку, ми працюємо тільки з тими, що знаходяться на парних індексах. Використання парних індексів дає можливість чітко відокремити стіни та проходи, що дозволяє алгоритму працювати ефективно та створювати правильні лабіринти.

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

1. Забирає поточну клітинку зі стеку(перший елемент стеку це позиц старту)
2. Випадково обирає напрямок руху(вгору, вниз, ліворуч, праворуч рухаючись лише через парні індекси. Довжина кроку рівна 2. Використовується для того, щоб "пересуватися" через дві клітинки, тобто між поточною клітинкою і новою, пропускаючи одну клітинку. Це дозволяє створити правильні проходи. Коли ми рухаємось від поточної клітинки на 2 клітинки вперед, ми "розбиваємо" стіну між ними, створюючи прохід. Крок з довжиною 2 дозволяє ефективно вирізати стіни і створювати лабіринт з правильними, чітко визначеними проходами і стінами.
3. Якщо нова клітинка є валідною (не виходить за межі лабіринту та стіною), алгоритм розбиваю стіну між поточною клітинкою та сусідньою і додає нову клітинку до стека
4. Алгоритм припиняється, коли стек буде порожнім, тобто всі клітин лабіринту, які потрібно відвідати, вже оброблені або більше немає доступних сусідніх клітинок для створення проходів Стек — це спеціальна структура для зберігання даних, яка працює за принципом "останній прийшов — перший вийшов" (LIFO). Це означає, що останній елемент, який ми додали в стек, буде першим, який ми витягнемо. Стек дозволяє контролювати, яку клітинку перевіряти наступною, не використовуючи рекурсії (яка іноді може викликати помилки, якщо виклики занадто глибокі). Для дуже великих лабіринтів (наприклад, розміром 10 000 клітинок) рекурсія може не працювати через обмеження на глибину викликів функцій. Стек дозволяє уникнути цієї проблеми і працювати з великими лабіринтами без обмежень. Після створення проходів генерується фінішна точка ("F"). Вона також випадковим чином розміщується в доступному місці (де є прохід, тобто значення 0) Функція повертає лабіринт як двовимірний список, де кожен елемент — це або стіна, або шлях, або одна з двох точок ("S" для старту і "F" для фінішу). Результат функції я записую в файл з роширенням ".csv".

Частина Арсенія

Візуалізація результатів: Unicode, ASCII та ANSI

Після успішної реалізації необхідного функціоналу та проміжного захисту ми з командою вирішили взятися за додаткові функції як-от візуалізація чи генерація випадкових лабіринтів. Візуалізація є важливою складовою для кращого розуміння результатів роботи алгоритму. Тому після розробки та тестування основного алгоритму з Мартою, я, Стратюк Арсеній, написав visualize_results. У процесі розробки функції я обрав використання Unicode-символів, зокрема емодзі, для створення візуалізації. Це рішення було прийнято після розгляду альтернатив, таких як ASCII-art та кольорові коди ANSI. Ось основні причини, плюси та мінуси цього підходу, а також опис роботи візуалізації.

Чому Unicode?

1. Чіткість і візуальна естетика:
   Unicode-символи, такі як 🟩, 🧱, 🚩 і 🏁, забезпечують інтуїтивно зрозуміле й привабливе уявлення елементів лабіринту.

   • 🧱 — стіна
   • 🟩 — шлях
   • 🚩 — старт
   • 🏁 — фініш

2. Глобальна підтримка:
   Unicode підтримується багатьма платформами, включаючи сучасні термінали, браузери й текстові редактори.

3. Простота реалізації:
   Використання Unicode дозволяє уникнути складного управління кольорами (як у випадку з ANSI-кодами), оскільки кожен символ вже містить візуально розпізнавані елементи.

Порівняння з альтернативами

Підхід	Переваги	Недоліки
Unicode	Чіткість, естетика, доступність, легка інтеграція.	Різні рендеринги символів на різних платформах. Використання більшого обсягу пам'яті.
ASCII-art	Висока сумісність, легкість у використанні для великих лабіринтів.	Менш привабливий вигляд, відсутність кольорів.
ANSI-коди	Підтримка кольорів у терміналах. Сумісність з ASCII-art.	Складність у читанні у файлах, несумісність із текстовими редакторами.

Особливості реалізації функції visualize_results

1. Логіка роботи:

   • Функція visualize_results працює в кілька етапів. Спочатку вона проходить по всіх клітинах матриці лабіринту, перетворюючи кожну з них у відповідний символ за допомогою словника cell_map. Якщо клітина є частиною знайденого найкоротшого шляху, їй призначається символ 🟩, для старту використовується 🚩, для фінішу 🏁, а стіни й порожні клітини позначаються 🧱 та ⬜ відповідно. Отриманий візуалізований рядок додається до списку visualizing_data.

   • Після обробки всіх клітин лабіринту, створюється фінальний результат — стрічка, яка об'єднує всі рядки матриці. Для лабіринтів розміром до 31x31 ця стрічка повертається напряму для виведення в терміналі. Якщо ж лабіринт перевищує цей розмір, результат записується у файл у папці Visualization, де ім'я файлу вказує кількість кроків та розмір матриці. Такий підхід дозволяє зберігати високу читабельність для невеликих лабіринтів та ефективно працювати з великими структурами даних.

2. Часова складність:

   • Хоча основний алгоритм BFS працює за час O(V + E), візуалізація додає накладні витрати через ітерацію всієї матриці, що має складність O(n × m). Це призводить до уповільнення на великих матрицях (наприклад, для розмірів понад 1000x1000). Через це ми додали можливість вимкнення візуалізації для тестування.

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

Частина Богдана

Я, Павлунишин Богдан, працював над функціями get_neighbors та is_valid. Обидві функції виконують допоміжну роль в основному алгоритмі.

Принцип роботи функції: get_neighbors(matrix: list[tuple[int, int]], row: int, column: int) > list[tuple[int, int

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

Результат функції: Результатом функції є список із кортежів, де кожен кортеж відповідає координатам певного елемента.

Алгоритм роботи: Після отримання вищезгаданих значень, функція записує координати усіх сусідніх елементів (зверху, знизу, зліва та справа від головного), після чого перевіряє, чи координати задано правильно (для цього застосовується функція is_valid) та записує лише ті елементи, значення яких дорівнює 0 або F.

Застосування допоміжної функції is_valid: is_valid(matrix: list[list[int | str]], row: int, column: int) > boo

Приймає ту саму матрицю та значення рядка та стовпця, котрі є координатами елемента. Функція перевіряє, чи значення рядка та стовпця знаходяться у межах від нуля (включно) до значення довжини матриці (не включно) та повертає True або False залежно від результату перевірки.

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

Речі, котрі ми зрозуміли завдяки роботі над про’єктом Ми навчилися моделювати матрицю як граф, де елементи є вузлами, а переходи між ними відповідають ребрам. Це дало змогу зрозуміти поняття суміжності та шляху в графі. Ми краще зрозуміли околиці точок у дискретних структурах: функція get_neighbors показує, як формувати множину сусідніх вузлів, а is_valid забезпечує коректність відношень між індексами та матрицею. Завдяки реалізації BFS ми освоїли, як знаходити найкоротший шлях між двома вузлами у графі. Це поглибило знання про алгоритмічні методи розв’язання задач у графах, а також допомогла нам зрозуміт чому саме цей метод є найефективнішим тут. BFS дав змогу краще зрозуміти, як застосовувати чергу для поступового дослідження вузлів та забезпечувати оптимальний пошук шляхів. Ми навчилися використовувати механізм батьківських вузлів для побудови шляху.

Функція read_file навчила нас перевіряти коректність введених даних, обробляти виняткові ситуації та забезпечувати правильне читання з файлів. Це покращило наше розуміння обробки структурованої інформації. Завдяки функції visualize_results ми освоїли методи представлення даних у зрозумілому форматі, зокрема візуалізацію лабіринту та шляхів.