Поколение на лабиринта и неговото преминаване
> C ++> Генериране на лабиринт и неговото преминаване
В предишна статия описах метод за генериране на лабиринти от свързани помещения с различни размери. Този път ще анализираме друг начин за генериране на лабиринти, при който лабиринти ще бъдат получени в класическа форма. Също така ще говоря за това как да намеря най-краткия път между всякакви две точки в лабиринта.
Ще генерираме по метода "рекурсивно разделяне".
- Помещението е разделено на 4 секции
- На всякакви три граници вратите се изрязват на произволни места
- Рекурсивно изпълнение на елементи 1. и 2. за всяка от четирите получени секции не се извършва рекурсия в тези секции, в които поне една от страните е равна на 1 клетка.
Резултатът е лабиринт като този:
Моля, обърнете внимание, че лабиринтът се получава без затворени зони, в него винаги можете да намерите път от една клетка до друга.
Намиране на път между две точки
Ще намерим пътя между две точки, използвайки алгоритъма на Лий (алгоритъм за проследяване на вълните).
- Търсим пътя от червената точка до жълтата
- Нека зададем един и същ атрибут = -1 за всички клетки, с изключение на тези, в които се намират точките. Начален атрибут = 0, крайна точка = -2.
- „Разпространение на вълната“: всички клетки в съседство с оригинала променят стойността на своя атрибут до стойността на атрибута на оригиналната клетка + 1 (т.е. с 1), но само ако можете свободно да се придвижите до съседната клетка от продължете разпространението на вълната: сега за всички клетки с атрибут = 1 (т.е. за онези клетки, в които успяхме да преминем от оригиналната) изпълняваме същата операция, клетки с атрибут, равен на 2, ще се появят около такива клетки Продължете операцията, докато достигнем крайната точка.
- Възстановяваме пътя: движим се от крайната точка по онези клетки, чийто атрибут е по-малък с един от атрибута на клетката, в която се намираме в момента. В същото време вземаме предвид, че е възможно да се премести в нова клетка само ако няма бариери.
Сподели "Поколение на лабиринта и неговото преминаване"
- Упътване за бумеранг
- Singularity (2010) Упътване
- Stronghold Legends пълен преглед на играта, Stronghold Legends разходки съвети, как да преминете
- Daemonica (Упътване)
- Stronghold Legends - преглед на играта, ръководство, тайни и други