|
|
|
Найти выход из лабиринта25.03.2014, 17:01. Показов 4307. Ответов 41
Метки нет (Все метки)
Как можно искать выход из лабиринта, который задается отрезками. То есть надо найти даже не выход, а можно ли добраться до выхода. Точка старта и финиша задаются координатами, также задаются координаты отрезков (стен) - начало и конец. Так как размеры могут быть достаточно велики, то рисовать попиксельно и искать путь не получится. Так как нужно ответить ли добраться до выхода, как это можно сделать?
0
|
|
| 25.03.2014, 17:01 | |
|
Ответы с готовыми решениями:
41
Помогите с выбором алгоритма(найти все ходы на карте лабиринта)
|
| 26.03.2014, 17:08 | ||
Хорошо, пусть есть разорванные отрезки и.т.п. Тогда каждая точка отрезка/пересечения - вершина графа. Строим ребра как говорилось выше. Задача свелась к хорошо известной.
0
|
||
| 26.03.2014, 18:30 | ||
|
0
|
||
|
294 / 265 / 48
Регистрация: 09.04.2013
Сообщений: 1,038
|
||
| 26.03.2014, 19:25 | ||
|
Из одной точки может исходить несколько отрезков. Возможно нужно знать взаимное расположение отрезков ("по кругу"). Видимость точки из исходной можно задать как угол между двумя отрезками, образующими сектор видимости (в котором мы пришли в исходную точку) и отрезком образованным исходной и рассматриваемой точкой, т.е. входит ли точка в такой сектор (например через скалярное произведение векторов).
0
|
||
|
294 / 265 / 48
Регистрация: 09.04.2013
Сообщений: 1,038
|
|
| 27.03.2014, 00:22 | |
|
Пусть мы пришли из точки S в точку D и из которой потом пойдем в точку F
Сначала нужно определить какие отрезки DC и DB ограничивают сектор обзора точки D. Если мы знаем очередность отрезков выходящих через точку (например, по часовой стрелке), то нужно найти такой отрезок DB у которого минимальный угол с DF, следующий отрезок DC выбирается из соображения что угол CDB должен быть больше чем угол CDF, а DC и DB являются соседними. угол CDB задает сектор обзора точки D. Видимость точки F аналогично определяется как углы CDF и BDF которые должны быть не больше чем угол CDB. Естественно, также должно выполняться условие что отрезки FD и SD не должны пересекаться с стенами. Отдельный случай когда точка принадлежит только одному отрезку - тогда никаких этих проверок делать не надо (кроме пересечения с границей), ибо у неё обзор 360о
1
|
|
|
294 / 265 / 48
Регистрация: 09.04.2013
Сообщений: 1,038
|
|
| 27.03.2014, 00:25 | |
|
Скалярное произведение векторов
(a,b)=x1x2 + y1y2 чем дальше тем триангуляция выглядит более элегантным решением.
0
|
|
| 27.03.2014, 14:36 | |||
|
0
|
|||
|
294 / 265 / 48
Регистрация: 09.04.2013
Сообщений: 1,038
|
||
| 27.03.2014, 15:16 | ||
|
0
|
||
|
|
|
| 27.03.2014, 17:51 [ТС] | |
|
Я здесь придумал другой алгоритм:
1. Ищем любую точку, чтобы отрезок, соединяющий начальную и конечную точки не пересекался с другими. 2. С той точки обходим многоугольник по правилу правой руки. 3. Когда обошли полностью, то смотрим: Если точка старта или точка финиша не лежат в нем, то стираем все стороны многоугольника, не принадлежащих другим многоугольникам. 4. пока есть точки см. пункт 1
0
|
|
|
294 / 265 / 48
Регистрация: 09.04.2013
Сообщений: 1,038
|
||
| 27.03.2014, 23:38 | ||
|
в таком алгоритме предварительно нужно соединить финиш и старт отрезками с одной из видимых точек Добавлено через 19 минут и не понятно как мы выбираем точки в (1) хотелось бы более конкретные формулировки
0
|
||
|
294 / 265 / 48
Регистрация: 09.04.2013
Сообщений: 1,038
|
||
| 28.03.2014, 13:11 | ||
|
Один раз прошли по многоугольнику и убрали его, теперь между стартом и финишем есть проход, которого быть не должно.
0
|
||
|
294 / 265 / 48
Регистрация: 09.04.2013
Сообщений: 1,038
|
|
| 28.03.2014, 14:19 | |
|
Тут я нашел упоминание алгоритма, который сначала ищет все тупики и убирает их из рассмотрения (страницу уже закрыл, а название не запомнил) Возможно его сюда тоже можно внести.
Если придумать как отойти от привязки к координатам, то можно удалить все лишние отрезки а то и многоугольники. Если предположить что финиши и старт находятся внутри многоугольника, то первым делом можно безболезненно рекурсивно удалить все точки принадлежащие только одному отрезку (вместе с отрезком)
0
|
|
| 28.03.2014, 15:35 | ||
0
|
||
| 28.03.2014, 15:35 | |
|
Найти выход из лабиринта, прочертив весь путь Составить программу, которая позволяет игроку найти выход из лабиринта Выход из лабиринта
Выход из лабиринта Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Транслитерация текста с кириллицы на латиницу (вариант №5)
Maks 17.11.2026
Дабы оставить позади все споры о том, какая буква каким образом должна транслитерироваться на латиницу - решил таки доработать данное решение и довести его до мало-мальски логического завершения. . . .
|
Просмотровщик HLP и конвертер в CHM
Argus19 16.11.2026
Просмотровщик HLP и конвертер в CHM
Давно хотел переделать справку Microsoft® Win32® Programmer's Reference, чтобы иметь её под рукой.
Но использовать несколько программ не удобно. Искал другие. . .
|
BitTorrent (версия 7.11 English) и Меню Настройки
russiannick 15.11.2026
Пункты, отвечающие за отключение обновлений в BitTorrent версии 7. 11 (английской)
Options
Preferences
General
Language
|
Транслитерация текста с кириллицы на латиницу (вариант №4)
Maks 15.11.2026
Что-то я перемудрил с предыдущими версиями, в этот раз сделал всё проще, обратившись к функции "СтрокаЛатиницей" из типового общего модуля "СтроковыеФункцииКлиент".
В данной функции нет апострофов,. . .
|
|
BitTorrent (версия 4.3.9) и Меню Настройки
russiannick 15.11.2026
В меню Настройки можно отключить автоматическое обновление программы.
Карта этого меню приложена ниже.
Нужный пункт выделен красным.
Сервис
Настройки
Поведение
|
Транслитерация текста с кириллицы на латиницу (вариант №3)
Maks 15.11.2026
Обновленная версия предыдущей обработки.
Изменения коснулись букв: Ъ, Ы, Ь, Э, отображения которых зависят от положения реквизита "Транслитерация имён".
Изменено отображение буквы Й.
Добавлена. . .
|
Транслитерация текста с кириллицы на латиницу (вариант №2)
Maks 13.11.2026
Обновленная версия ранее созданной обработки.
Добавлено:
- Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .
|
Часы с термометром и праздничным календарем
yariko 12.11.2026
Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы.
Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .
|