Совершенный лабиринт
Вы, вероятно, хорошо знакомы с лабиринтами – удивительно забавными головоломками, которые могут удерживать ваш интерес долгое время. В этом разделе мы поговорим об AI, используемом в создании случайных, но совершенных лабиринтов. Но сначала вы должны знать, что такое совершенный лабиринт в сравнении с несовершенным лабиринтом. Совершенный лабиринт имеет лишь один путь между любыми двумя ячейками. В совершенном лабиринте, вы можете выбрать любые две ячейки, и всегда будет существовать путь между ними – но только один. В совершенном лабиринте замкнутый путь невозможен, и нет огороженных областей.
IMPERFECT MAZE
НЕСОВЕРШЕННЫЙ ЛАБИРИНТ
PERFECT MAZE
СОВЕРШЕННЫЙ ЛАБИРИНТ
На иллюстрации выше вы можете увидеть как совершенный, так и несовершенный лабиринты. Несовершенный лабиринт имеет замкнутые области и несколько путей между некоторыми ячейками. Совершенный лабиринт не имеет замкнутых областей и лишь один путь между любыми двумя ячейками. Ниже приводится более крупный и более интересный совершенный лабиринт.
Правила для совершенного лабиринта
Это довольно простое приложение, которое использует двухмерный массив для хранения информации о каждой плитке. Лабиринт построен на плиточной основе, а каждая плитка имеет четыре стены. Теперь давайте разберем правила создания совершенного лабиринта.
1. Выберите, сколько строк и столбцов вы хотите сделать в лабиринте. Вы получите число ячеек в этом лабиринте равным rows*columns. Все стены этих ячеек в данный момент подняты. Создайте переменную с именем cellsVisited со значением 0.
2. Создайте массив с именем visitedList. Когда ячейка была посещена, она будет добавлена в этот массив.
3. Выберите случайным образом начальную ячейку. Сделайте ее текущей ячейкой. Увеличьте на единицу переменную cellsVisited.
4. Если значение cellsVisited равно числу ячеек, ваш лабиринт завершен. Иначе переходите к шагу 5.
5. Создайте массив с именем neighbors
Русская версия