Найти выход из лабиринта

@Taras_Z · Регистрация: 27.10.2010

Студворк — интернет-сервис помощи студентам

Как можно искать выход из лабиринта, который задается отрезками. То есть надо найти даже не выход, а можно ли добраться до выхода. Точка старта и финиша задаются координатами, также задаются координаты отрезков (стен) - начало и конец. Так как размеры могут быть достаточно велики, то рисовать попиксельно и искать путь не получится. Так как нужно ответить ли добраться до выхода, как это можно сделать?

@wingblack · 25.03.2014, 17:50

Может разбить свободное пространство на треугольники, построить граф соседних треугольников (откуда куда можно пройти) и свести к поиску пути на графе.

@Taras_Z · 25.03.2014, 19:49 **[ТС]**

wingblack, а если так? Как тогда разбивать на треугольники?

@wingblack · 25.03.2014, 20:01

Точно так же. Если общая сторона двух треугольников является границей, то просто между ними нет пути.

Добавлено через 3 минуты
Была у меня еще идея прыгать по видимым точкам границы (провести отрезок из текущей точки к предполагаемой, если отрезок не пересекается с границей то прыгнуть на точку) плюс обход по периметру.
Но адекватной стратегии тут я не придумаю, кроме как полным перебором. На фоне это триангуляция выглядит более правильно.

OldFedor · 25.03.2014, 20:06

Был фильм такой "Фараон".
Так там жрецы пользовались правилом левой руки.
Руку к стене и пошел, обойти можно все, но выход есть всегда.
Причем, если за стеной (Вашим треугольником) что-то и есть - по барабану идем и не обращаем внимания.

@Taras_Z · 25.03.2014, 20:09 **[ТС]**

wingblack, Как тогда делать триангуляцию в многоугольнике с самопересечениями? Тогда еще надо искать точки пересечения сторон или я неправильно понимаю?

Добавлено через 1 минуту
Я забыл уточнить, но в задачи может быть несколько выходов и тогда надо вывести все выходы через которые можно выйти. Хотя это несущественно меняет дело.

@wingblack · 25.03.2014, 20:43

Сообщение от OldFedor

Так там жрецы пользовались правилом левой руки.

Правило левой руки не везде работает.

Сообщение от Taras_Z

Как тогда делать триангуляцию в многоугольнике с самопересечениями?

Убрать самопересечения заменив 2 пересекающиеся отрезка на 4 с одной общей точкой.

Можно еще так сделать, менее быстро (наверное), но проще в реализации
-добавить старт в список обзора
-для каждой точки из списка обзора найти все видимые вершины и добавить в список обзора.
-текущую точку добавить в список "не проверять" и вычеркнуть из будущих проверок.

финишная точка считается достижимой если она попадала в список обзора, ну или по ней прошлись.

@Taras_Z · 25.03.2014, 20:47 **[ТС]**

Сообщение от wingblack

Можно еще так сделать, менее быстро (наверное), но проще в реализации
-добавить старт в список обзора
-для каждой точки из списка обзора найти все видимые вершины и добавить в список обзора.
-текущую точку добавить в список "не проверять" и вычеркнуть из будущих проверок.
финишная точка считается достижимой если она попадала в список обзора, ну или по ней прошлись.

Ну это поиск в ширину. Но какие точки будут называться видимыми?

@wingblack · 25.03.2014, 20:48

для упрощения работы все же даже в таком алгоритме следует исключить пересекающиеся отрезки границы

@Taras_Z · 25.03.2014, 20:49 **[ТС]**

Сообщение от wingblack

Убрать самопересечения заменив 2 пересекающиеся отрезка на 4 с одной общей точкой.

Тогда все равно будет несколько многоугольников, которые просто соприкасаются. Но как среди них делать триангуляцию я пока не очень понимаю.

@wingblack · 25.03.2014, 20:49

Сообщение от Taras_Z

Ну это поиск в ширину. Но какие точки будут называться видимыми?

точки назовем видимыми, если отрезок соединяющий исходную точку и исследуемую не пересекается с отрезком границы

@Taras_Z · 25.03.2014, 20:53 **[ТС]**

Сообщение от wingblack

точки назовем видимыми, если отрезок соединяющий исходную точку и исследуемую не пересекается с отрезком границы

Что есть "граница"?

@wingblack · 25.03.2014, 20:56

Сообщение от Taras_Z

Как можно искать выход из лабиринта, который задается отрезками.

вот эти отрезки и будут границей, они же "стены", возможно я не очень удачно обозвал

@Taras_Z · 25.03.2014, 20:59 **[ТС]**

Сообщение от wingblack

точки назовем видимыми, если отрезок соединяющий исходную точку и исследуемую не пересекается с отрезком границы

Тогда как их искать? Перебором?

@wingblack · 25.03.2014, 21:06

Сообщение от Taras_Z

Тогда как их искать? Перебором?

Угу.
Еще можно упростить если сначала все же удостоверится что "стены" взаимо не пересекаются, тогда можно в алгоритм добавить обход периметра, к которому данная точка принадлежит

Добавлено через 3 минуты
хотя тут уже проблема в выборе правильного периметра...
все же пока лучше без периметра

@Taras_Z · 25.03.2014, 21:15 **[ТС]**

Это действительно достаточно легкая реализация, но мне важнее время выполнения. Тогда остается триангуляция, но как ее сделать, если в нас несколько многоугольников?

@wingblack · 25.03.2014, 21:27

Сообщение от Taras_Z

Это действительно достаточно легкая реализация, но мне важнее время выполнения. Тогда остается триангуляция, но как ее сделать, если в нас несколько многоугольников?

Посмотреть алгоритмы по триангуляции по точкам, и дополнить чтобы стены всегда были сторонами треугольников

@Taras_Z · 26.03.2014, 13:36 **[ТС]**

wingblack, Спасибо!
Когда сделаю - отпишу.

Добавлено через 16 часов 6 минут

Сообщение от wingblack

Можно еще так сделать, менее быстро (наверное), но проще в реализации
-добавить старт в список обзора
-для каждой точки из списка обзора найти все видимые вершины и добавить в список обзора.
-текущую точку добавить в список "не проверять" и вычеркнуть из будущих проверок.

Попробовал сначала сделать так, но возникла одна проблема:
Со старта мы добавим синюю точку в очередь, так как она является видимой. Когда дойдет очередь до ее рассмотрения, с этой точки, финиш будет видим, но мы не можем дойти к старту до финиша.

@Igor3D · 26.03.2014, 13:58

С триангуляцией там долго пыль глотать. Чем не устраивает предложение OldFedor? Его только чуть оформить, напр

- соединяем текущую точку с конечной. Если не пересекаем ни один из отрезков - готово
- иначе из текущей находим любую в которую можно прийти и дальше просто идем-идем-идем проходя каждый отрезок 1 раз
- если какие-то доп треугольники/перекрытия, то их надо заранее учесть введя новые точки и разбив отрезки

@wingblack · 26.03.2014, 16:12

Сообщение от Igor3D

Чем не устраивает предложение OldFedor?

Метод правой руки не является универсальным. Про это много и везде говорили уже.
Вот вам лабиринт, пробуйте с помощью него пройти его.

Новые блоги и статьи Все статьи Все блоги /
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Символьное дифференцирование igorrr37 13.02.2026 / * Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет значение производной при заданном х Логарифм записывается как: (x-2)log(x^2+2) -. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.
«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .

@Taras_Z 102 / 86 / 5 Регистрация: 27.10.2010 Сообщений: 534 Записей в блоге: 2

	Найти выход из лабиринта 25.03.2014, 17:01. Показов 3671. Ответов 41 Метки нет (Все метки) Как можно искать выход из лабиринта, который задается отрезками. То есть надо найти даже не выход, а можно ли добраться до выхода. Точка старта и финиша задаются координатами, также задаются координаты отрезков (стен) - начало и конец. Так как размеры могут быть достаточно велики, то рисовать попиксельно и искать путь не получится. Так как нужно ответить ли добраться до выхода, как это можно сделать? Миниатюры 0

@wingblack 294 / 265 / 48 Регистрация: 09.04.2013 Сообщений: 1,038
	25.03.2014, 17:50
	Может разбить свободное пространство на треугольники, построить граф соседних треугольников (откуда куда можно пройти) и свести к поиску пути на графе. 1

@Taras_Z 102 / 86 / 5 Регистрация: 27.10.2010 Сообщений: 534 Записей в блоге: 2
	25.03.2014, 19:49 [ТС]
	wingblack, а если так? Как тогда разбивать на треугольники? Миниатюры 0

@wingblack 294 / 265 / 48 Регистрация: 09.04.2013 Сообщений: 1,038
	25.03.2014, 20:01
	Точно так же. Если общая сторона двух треугольников является границей, то просто между ними нет пути. Добавлено через 3 минуты Была у меня еще идея прыгать по видимым точкам границы (провести отрезок из текущей точки к предполагаемой, если отрезок не пересекается с границей то прыгнуть на точку) плюс обход по периметру. Но адекватной стратегии тут я не придумаю, кроме как полным перебором. На фоне это триангуляция выглядит более правильно. 0

OldFedor 7486 / 4150 / 474 Регистрация: 25.08.2012 Сообщений: 11,530 Записей в блоге: 11
	25.03.2014, 20:06
	Был фильм такой "Фараон". Так там жрецы пользовались правилом левой руки. Руку к стене и пошел, обойти можно все, но выход есть всегда. Причем, если за стеной (Вашим треугольником) что-то и есть - по барабану идем и не обращаем внимания. 1

@Taras_Z 102 / 86 / 5 Регистрация: 27.10.2010 Сообщений: 534 Записей в блоге: 2
	25.03.2014, 20:09 [ТС]
	wingblack, Как тогда делать триангуляцию в многоугольнике с самопересечениями? Тогда еще надо искать точки пересечения сторон или я неправильно понимаю? Добавлено через 1 минуту Я забыл уточнить, но в задачи может быть несколько выходов и тогда надо вывести все выходы через которые можно выйти. Хотя это несущественно меняет дело. 0

@wingblack 294 / 265 / 48 Регистрация: 09.04.2013 Сообщений: 1,038
	25.03.2014, 20:48
	для упрощения работы все же даже в таком алгоритме следует исключить пересекающиеся отрезки границы 0

@Taras_Z 102 / 86 / 5 Регистрация: 27.10.2010 Сообщений: 534 Записей в блоге: 2
	25.03.2014, 21:15 [ТС]
	Это действительно достаточно легкая реализация, но мне важнее время выполнения. Тогда остается триангуляция, но как ее сделать, если в нас несколько многоугольников? 0

@Igor3D 1969 / 825 / 115 Регистрация: 01.10.2012 Сообщений: 4,885 Записей в блоге: 2
	26.03.2014, 13:58
	С триангуляцией там долго пыль глотать. Чем не устраивает предложение OldFedor? Его только чуть оформить, напр - соединяем текущую точку с конечной. Если не пересекаем ни один из отрезков - готово - иначе из текущей находим любую в которую можно прийти и дальше просто идем-идем-идем проходя каждый отрезок 1 раз - если какие-то доп треугольники/перекрытия, то их надо заранее учесть введя новые точки и разбив отрезки 1