Поколение на лабиринта и неговото преминаване

> C ++> Генериране на лабиринт и неговото преминаване

В предишна статия описах метод за генериране на лабиринти от свързани помещения с различни размери. Този път ще анализираме друг начин за генериране на лабиринти, при който лабиринти ще бъдат получени в класическа форма. Също така ще говоря за това как да намеря най-краткия път между всякакви две точки в лабиринта.

Ще генерираме по метода "рекурсивно разделяне".

неговото

  1. Помещението е разделено на 4 секции
  2. На всякакви три граници вратите се изрязват на произволни места
  3. Рекурсивно изпълнение на елементи 1. и 2. за всяка от четирите получени секции не се извършва рекурсия в тези секции, в които поне една от страните е равна на 1 клетка.

Резултатът е лабиринт като този:

лабиринта

Моля, обърнете внимание, че лабиринтът се получава без затворени зони, в него винаги можете да намерите път от една клетка до друга.

Намиране на път между две точки

Ще намерим пътя между две точки, използвайки алгоритъма на Лий (алгоритъм за проследяване на вълните).

  1. Търсим пътя от червената точка до жълтата
    поколение
  2. Нека зададем един и същ атрибут = -1 за всички клетки, с изключение на тези, в които се намират точките. Начален атрибут = 0, крайна точка = -2.
    лабиринта
  3. „Разпространение на вълната“: всички клетки в съседство с оригинала променят стойността на своя атрибут до стойността на атрибута на оригиналната клетка + 1 (т.е. с 1), но само ако можете свободно да се придвижите до съседната клетка от продължете разпространението на вълната: сега за всички клетки с атрибут = 1 (т.е. за онези клетки, в които успяхме да преминем от оригиналната) изпълняваме същата операция, клетки с атрибут, равен на 2, ще се появят около такива клетки Продължете операцията, докато достигнем крайната точка.
    поколение
  4. Възстановяваме пътя: движим се от крайната точка по онези клетки, чийто атрибут е по-малък с един от атрибута на клетката, в която се намираме в момента. В същото време вземаме предвид, че е възможно да се премести в нова клетка само ако няма бариери.

Сподели "Поколение на лабиринта и неговото преминаване"