Розв’язання простих лабіринтів

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Вступ

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

Програма завантажує лабіринт із файлу, виконує побудову лабіринту, знаходить шлях до виходу (якщо він існує) і будує шлях розв'язання.

Постановка задачі

Лабіринт являє собою матрицю з одиниць і нулів і зберігається у файлі.

Для проходу по лабіринту існують наступні правила:

· Шлях починається у точці старту (позначається як «2»), а закінчується у точці фінішу (позначається як «3»).

· Клітина, що містить одиницю, вважається закритою, на неї заборонено входити.

· Ходи можливі лише на сусідні клітини, якщо вони вільні (містять нуль)

· Ходи по діагоналі заборонено

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

Також необхідно передбачити перевірку вхідних даних на коректність і вивести попередження, якщо данні не відповідають необхідним умовам.

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

Розробка структури програмного забезпечення

Програма містить чотири класи, які безпосередньо використовуються для виконання поставленої задачі

· Point - описує «клітину» лабіринту

· Labyrinth - описує матрицю лабіринту, яка складається з клітин

· Solver - наслідує клас Labyrinth, містить методи для розв'язання лабіринту

· vGraphics - містить методи для візуалізації роботи програми

Схема класів

Розробка алгоритму функціонування

лабіринт програмний алгоритм коректність

Блок-схема метода Solver::GetSolutionPath, який виконує пошук шляху розв'язання

Блок-схема метода Solver::Correct, який виконує перевірку коректності лабіринту

Блок-схема метода vGraphics::BuildSolution, який виконує побудову точок шляху

Розробка програмного забезпечення

Тестування програмного забезпечення

Для тестування програми було використано наступні файли:

· Maze_1.vmz, Maze_2.vmz, Maze_3.vmz - файли, які містять звичайні лабіринти.

· Maze_1_with_start_and_finish_error.vmz - лабіринт без старту і з двома фінішами

· Maze_1_without_exit.vmz - лабіринт, який не має виходу

· wrong_file.vmz - файл з розширенням лабіринту, який містить довільний текст, який не є лабіринтом

Тести звичайних лабіринтів:

Maze_1.vmz

Maze_2.vmz

Maze_3.vmz

Як видно з результатів тестування, програма коректно знаходить шлях розв'язку, не має за циклювань на петлях та розгалуженнях

Тестування файлів з помилками:

Maze_1_with_start_and_finish_error.vmz

Maze_1_without_exit.vmz

wrong_file.vmz

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

Інструкція користувача

Інтерфейс програми

Вікно програми складається з трьох областей:

1. Меню функцій

2. Інформація про відкритий лабіринт

3. Графічне зображення лабіринту

Кнопки в меню функцій стають активними при виконанні попередньої функції.

Для відкриття лабіринту необхідно натиснути кнопку загрузки лабіринту та вказати файл з розширенням .vmz.

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

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

У програмі можливі наступні помилки та попередження:

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

Виникає при спробі розв'язати лабіринт без старту/фінішу, або якщо їх більше ніж потрібно

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

Размещено на Allbest.ru