Генерація лабіринту та його проходження
> C++ > Генерація лабіринту та його проходження
У попередній статті я описав метод генерації лабіринтів із зв'язаних кімнат різних розмірів. Цього разу ми розберемо інший спосіб генерації лабіринтів, у якому лабіринти отримуватимуть класичну форму. Крім того, я розповім про те, як знаходити найкоротший шлях між будь-якими двома точками лабіринту.
Генерувати ми методом «рекурсивного поділу».
- Кімната ділиться на 4 секції
- На будь-яких трьох межах прорізуються двері у довільних місцях
- Рекурсивно виконуємо 1. та 2. пункти для кожної з чотирьох отриманих секцій, рекурсія не виконується в тих секціях у яких хоча б одна із сторін виявляється рівною 1 осередку.
В результаті вийде такий лабіринт:
Зверніть увагу на те, що лабіринт виходить без замкнутих областей, в ньому завжди можна знайти шлях від одного осередку до іншого.
Пошук шляху між двома точками
Пошук шляху між двома точками ми будемо робити алгоритмом Лі (алгоритм хвильового трасування).
- Шлях шукаємо від червоної точки до жовтої
- Задамо всім осередкам крім тих, у яких знаходяться точки, однаковий атрибут = -1. Вихідної точки атрибут = 0, кінцевої = -2.
- «Поширюємо хвилю»: всі сусідні осередки з вихідної змінюють значення свого атрибута на значення атрибута вихідного осередку + 1 (тобто на 1), але тільки в тому випадку, якщо в сусідній осередок можна безперешкодно перейти з вихідного. Продовжуємо поширення хвилі: тепер для всіх осередків з атрибутом = 1 (тобто для тих осередків в які вдалося перейти з вихідної) проводимо ту ж операцію, навколо таких осередків з'являться осередки з атрибутом рівним 2. Операцію продовжуємо доти, доки непотрапимо до кінцевої точки.
- Відновлюємо шлях: рухаємося від кінцевої точки по тих осередках, атрибут яких менший на одиницю атрибута осередку в якому знаходимося в даний момент. При цьому враховуємо, що переміщатися в новий осередок можна лише за умови відсутності бар'єрів.
Поділитись "Генерація лабіринту та його проходження"