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

@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?

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

Новые блоги и статьи Все статьи Все блоги /
My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .
Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача №1: при указании работ (справочник РаботыПоРемонтуСпецтехники),. . .

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

	Найти выход из лабиринта 25.03.2014, 17:01. Показов 3817. Ответов 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 1973 / 829 / 115 Регистрация: 01.10.2012 Сообщений: 5,010 Записей в блоге: 2
	26.03.2014, 13:58
	С триангуляцией там долго пыль глотать. Чем не устраивает предложение OldFedor? Его только чуть оформить, напр - соединяем текущую точку с конечной. Если не пересекаем ни один из отрезков - готово - иначе из текущей находим любую в которую можно прийти и дальше просто идем-идем-идем проходя каждый отрезок 1 раз - если какие-то доп треугольники/перекрытия, то их надо заранее учесть введя новые точки и разбив отрезки 1