- Курс-практикум «Педагогический драйв: от выгорания к горению»
- «Труд (технология): специфика предмета в условиях реализации ФГОС НОО»
- «ФАООП УО, ФАОП НОО и ФАОП ООО для обучающихся с ОВЗ: специфика организации образовательного процесса по ФГОС»
- «Специфика работы с детьми-мигрантами дошкольного возраста»
- «Учебный курс «Вероятность и статистика»: содержание и специфика преподавания в условиях реализации ФГОС ООО и ФГОС СОО»
- «Центр «Точка роста»: создание современного образовательного пространства в общеобразовательной организации»
Свидетельство о регистрации
СМИ: ЭЛ № ФС 77-58841
от 28.07.2014
- Бесплатное свидетельство – подтверждайте авторство без лишних затрат.
- Доверие профессионалов – нас выбирают тысячи педагогов и экспертов.
- Подходит для аттестации – дополнительные баллы и документальное подтверждение вашей работы.
в СМИ
профессиональную
деятельность
Алгоритм построения лабиринта
733
0
ФИО автора: Трофимов Виктор Геннадьевич
Место работы: ГКООУ санаторная школа-интернат №28 г. Ростова-на-Дону
Должность: учитель информатики и ИКТ
АЛГОРИТМ ПОСТРОЕНИЕ ЛАБИРИНТА
Задать лабиринт в программе с помощью чтения данных из файла достаточно легко. Но как научить компьютер «строить» лабиринт? Лабиринт, гарантирующий доступ из одной точки в другую без помех?
Допустим, у нас есть некое поле. Поле хранится в двумерном массиве структуры. Структура содержит следующие триггеры (логический тип, bool):
in - внутри
out - снаружи
wall - стена
start - следующая точка для прохода из текущей
Первоначально все «проходы» лабиринта находятся снаружи «пути», т.е. параметрout = true.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
1 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
2 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
3 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
4 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
5 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
6 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
7 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
8 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
9 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
10 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
11 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
12 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
13 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
14 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
15 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
1 шаг. Выбираем случайную точку и помечаем её in, переключая параметр out. На рисунке точка: x = 5, y = 10. Одновременно инициализируем всем окружающим её точкам параметр wall, сбрасывая остальные.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
1 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
2 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
3 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
4 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
5 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
6 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
7 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
8 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
9 | out | out | out | W | W | W | out | out | out | out | out | out | out | out | out |
10 | out | out | out | W | IN | W | out | out | out | out | out | out | out | out | out |
11 | out | out | out | W | W | W | out | out | out | out | out | out | out | out | out |
12 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
13 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
14 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
15 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
2 шаг. От этой точки ставим точки, в которые будет возможно пройти из текущей точки. Учитывая, что ширина границ в этом лабиринте равна 1 символу, то точки будут располагаться в x + 2, x - 2, y + 2 и y - 2 координатах. Но при условии, что параметр «следующей возможно» точки out равен истине (то есть точка находится ВНЕ лабиринта). На рисунке такие точки помечены символом S. Параметр out сбрасывается.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
1 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
2 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
3 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
4 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
5 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
6 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
7 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
8 | out | out | out | out | S | out | out | out | out | out | out | out | out | out | out |
9 | out | out | out | W | W | W | out | out | out | out | out | out | out | out | out |
10 | out | out | S | W | IN | W | S | out | out | out | out | out | out | out | out |
11 | out | out | out | W | W | W | out | out | out | out | out | out | out | out | out |
12 | out | out | out | out | S | out | out | out | out | out | out | out | out | out | out |
13 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
14 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
15 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
3 шаг. Выбираем случайную точку из текущих, помеченных маркером S(параметр start). Допустим, это будет точка S справа от блока, по координатам 7, 10. Выбрав, помечаем точку, лежащую между первоначальной и выбранной параметромin, сбрасывая остальные (то есть это будет «проход». Переходим к шагу №1. Выполняем алгоритм до тех пор, пока у нас не останется точек, помеченных параметром out. Или выполняем, пока не закончатся точкиS, с которых можно выполнять следующий «ход».
В конце алгоритма все «проходы» будут помечены параметром in (внутри лабиринта), все стены - wall. На рисунке обозначено - серый фон у стен, зелёный - у проходов будущего лабиринта.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
1 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
2 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
3 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
4 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
5 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
6 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
7 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
8 | out | out | out | out | S | out | S | out | out | out | out | out | out | out | out |
9 | out | out | out | W | W | W | W | W | out | out | out | out | out | out | out |
10 | out | out | S | W | IN | IN | IN | W | S | out | out | out | out | out | out |
11 | out | out | out | W | W | W | W | W | out | out | out | out | out | out | out |
12 | out | out | out | out | S | out | S | out | out | out | out | out | out | out | out |
13 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
14 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
15 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
Схематичная реализация (случайно выбрали точку S на координатах 7, 8):
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
1 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
2 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
3 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
4 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
5 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
6 | out | out | out | out | out | out | S | out | out | out | out | out | out | out | out |
7 | out | out | out | out | out | W | W | W | out | out | out | out | out | out | out |
8 | out | out | out | out | S | W | IN | W | S | out | out | out | out | out | out |
9 | out | out | out | W | W | W | IN | W | out | out | out | out | out | out | out |
10 | out | out | S | W | IN | IN | IN | W | S | out | out | out | out | out | out |
11 | out | out | out | W | W | W | W | W | out | out | out | out | out | out | out |
12 | out | out | out | out | S | out | S | out | out | out | out | out | out | out | out |
13 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
14 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
15 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
Схематичная реализация (случайно выбрали точку S на координатах 5, 12):
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
1 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
2 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
3 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
4 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
5 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
6 | out | out | out | out | out | out | S | out | out | out | out | out | out | out | out |
7 | out | out | out | out | out | W | W | W | out | out | out | out | out | out | out |
8 | out | out | out | out | S | W | IN | W | S | out | out | out | out | out | out |
9 | out | out | out | W | W | W | IN | W | out | out | out | out | out | out | out |
10 | out | out | S | W | IN | IN | IN | W | S | out | out | out | out | out | out |
11 | out | out | out | W | IN | W | W | W | out | out | out | out | out | out | out |
12 | out | out | S | W | IN | W | S | out | out | out | out | out | out | out | out |
13 | out | out | out | W | W | W | out | out | out | out | out | out | out | out | out |
14 | out | out | out | out | S | out | out | out | out | out | out | out | out | out | out |
15 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
Схематичная реализация (случайно выбрали точку S на координатах 5, 8):
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
1 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
2 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
3 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
4 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
5 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
6 | out | out | out | out | S | out | S | out | out | out | out | out | out | out | out |
7 | out | out | out | W | W | W | W | W | out | out | out | out | out | out | out |
8 | out | out | S | W | IN | W | IN | W | S | out | out | out | out | out | out |
9 | out | out | out | W | IN | W | IN | W | out | out | out | out | out | out | out |
10 | out | out | S | W | IN | IN | IN | W | S | out | out | out | out | out | out |
11 | out | out | out | W | IN | W | W | W | out | out | out | out | out | out | out |
12 | out | out | S | W | IN | W | S | out | out | out | out | out | out | out | out |
13 | out | out | out | W | W | W | out | out | out | out | out | out | out | out | out |
14 | out | out | out | out | S | out | out | out | out | out | out | out | out | out | out |
15 | out | out | out | out | out | out | out | out | out | out | out | out | out | out | out |
Когда «закончатся» все точки S - поле будет заполнено лабиринтом.
Адрес публикации: https://www.prodlenka.org/metodicheskie-razrabotki/172953-algoritm-postroenija-labirinta
БЕСПЛАТНО!
Для скачивания материалов с сайта необходимо авторизоваться на сайте (войти под своим логином и паролем)
Если Вы не регистрировались ранее, Вы можете зарегистрироваться.
После авторизации/регистрации на сайте Вы сможете скачивать необходимый в работе материал.
- «Основы профессиональной деятельности классного руководителя (куратора) с учётом требований ФГОС СПО»
- «Дистанционное обучение в ДОУ: особенности работы с детьми дошкольного возраста»
- «Организация работы с одаренными детьми»
- «Охрана здоровья обучающихся: содержание и особенности организации»
- «Педагогическая деятельность: развитие профессиональной компетентности учителя»
- «Содержание и методы преподавания учебного предмета «Кубановедение» по ФГОС НОО»
- Методист образовательной организации: основы педагогической и методической деятельности
- Организация работы классного руководителя в образовательной организации
- Преподавание предмета «Основы безопасности и защиты Родины» в общеобразовательных организациях»
- Теория и методика дополнительного образования детей
- Деятельность учителя-методиста в рамках сопровождения реализации общеобразовательных программ
- Методика организации образовательного процесса в начальном общем образовании
Чтобы оставлять комментарии, вам необходимо авторизоваться на сайте. Если у вас еще нет учетной записи на нашем сайте, предлагаем зарегистрироваться. Это займет не более 5 минут.