1515 / 639 / 62
Регистрация: 31.03.2009
Сообщений: 2,051
1

Оббежать по дуге (окружности)

18.12.2018, 05:54. Показов 845. Ответов 10
Метки нет (Все метки)

Помогите, пожалуйста, с идеей, как правильно реализовать такой алгоритм.
Есть некоторая точка с координатами X, Y и есть радиус R.
Также, имеется стартовая позиция персонажа X1, Y1 и конечная X2, Y2.
За один такт можно совершать движение на некоторые небольшие dX, dY.
Нужно попасть из точки X1, Y1 в точку X2, Y2, но не забегая в окружность с центром X, Y и радиусом R. То есть, натолкнувшись на неё, нужно оббежать её вокруг по периметру.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
18.12.2018, 05:54
Ответы с готовыми решениями:

Есть Add-On для создания 2D массивов, четырёхугольных, по дуге, буквы по дуге
Недавно закончил, писал в VS2017 Community. Отдам бесплатно в хорошие руки. Писал для себя но...

Ползунок по дуге
Всем добро! Скажите, можно ли на flash 8 создать ползунок (типа скруллбар), который можно было бы...

Перелёт объекта по дуге
Добрый день! Помогите сделать перелёт самолёта (например треугольника) из точки (\varphi1, \psi1)...

Вычислить интеграл по дуге C
Здравствуйте! Пытаюсь вычислить интеграл по дуге C, и возникла проблема. Подынтегральное функция...

10
Модератор
2918 / 2066 / 441
Регистрация: 26.03.2015
Сообщений: 8,050
18.12.2018, 11:57 2
1. Строим отрезок р1-р2 и проверяем, пересекает ли он окружность. Прямая, проходящая через эти точки, разбивает плоскость на две полуплоскости.
2. Если пересекает, то строим из точек р1 и р2 касательные к окружности. Касательных можно построить по две. Выбираем те, которые лежат в полуплоскости (см. п.1), не содержащей центр окружности.
Кратчайший маршрут будет касательная - дуга - касательная.
1
863 / 1221 / 161
Регистрация: 07.05.2013
Сообщений: 2,883
Записей в блоге: 12
18.12.2018, 15:08 3
Shamil1, "Кратчайший маршрут будет касательная - дуга - касательная" -- это если рассматривать движение как непрерывное. А у тс оно дискретно, более того, зафиксирована не длина пройденного шага, а dX dY. К тому же не указано - это конечная точка на каждом шаге не должна попадать в окружность - или нельзя пересекать окружность на каждом шаге.
Вообще, задача поставлена отвратительно.
0
1515 / 639 / 62
Регистрация: 31.03.2009
Сообщений: 2,051
18.12.2018, 18:08  [ТС] 4
Цитата Сообщение от vantfiles Посмотреть сообщение
Вообще, задача поставлена отвратительно.
Извините, сформулировал, как смог. Представьте себе простейшую двумерную компьютерную игру, вид сверху. По ней бегают персонажи. И им нужно добираться из одной точки в другую. Но на пути могут встречаться препятствия-окружности различного радиуса. Их персонаж должен оббегать, желательно по кратчайшей траектории, но, естесственно, не пересекая окружность - не может же персонаж частично просочиться внутрь препятствия.
0
1464 / 820 / 139
Регистрация: 12.10.2013
Сообщений: 5,421
18.12.2018, 19:25 5
https://ru.wikipedia.org/wiki/Поиск_пути
0
1464 / 820 / 139
Регистрация: 12.10.2013
Сообщений: 5,421
18.12.2018, 22:13 6
Цитата Сообщение от NightmareZ Посмотреть сообщение
могут встречаться препятствия-окружности различного радиуса. Их персонаж должен оббегать, желательно по кратчайшей траектории
Shamil1, примерно так?
А как же случай пересечения касательных с препятствиями, учет габаритов игрока?
Ведь игрок не точка.
Оббежать по дуге (окружности)
0
1515 / 639 / 62
Регистрация: 31.03.2009
Сообщений: 2,051
18.12.2018, 22:30  [ТС] 7
Цитата Сообщение от Excalibur921 Посмотреть сообщение
А как же случай пересечения касательных с препятствиями, учет габаритов игрока?
Можно считать игрока точкой, а радиусы препятствий для этих расчётов увеличить на радиус игрока.
0
1464 / 820 / 139
Регистрация: 12.10.2013
Сообщений: 5,421
18.12.2018, 22:56 8
Всеравно нужно проверять с кем пересекается каждая касательная, это будет приводить к странным ломанным траекториям и удлинению пути.
А если будет случай чередования диаметров это вообще швах…может быть зигзаг.
Оббежать по дуге (окружности)

Ох не дураки придумали алгоритмы поиска пути…да и смысл в велике когда вот они готовые и обкатаны временем.
0
Модератор
2918 / 2066 / 441
Регистрация: 26.03.2015
Сообщений: 8,050
19.12.2018, 09:18 9
Цитата Сообщение от Excalibur921 Посмотреть сообщение
примерно так?
В исходном вопросе было всего одно препятствие.
Для игры всё будет зависеть от интерфейса, который движок игры предоставляет интеллекту персонажа.
0
43 / 31 / 3
Регистрация: 27.03.2016
Сообщений: 116
19.12.2018, 13:09 10
Если препятствия несколько, то задача из "нормальной" превращается в "весьма и весьма сложную".
Недаром все кому не лень упрощают её до пиксельного прохождения, который много где описан.
Если решать полноценно, то нужно:
- получить некий граф возможных траекторий (пойди-ка его ещё получи. Возможно, проще создать его вручную вместе с картой)
- перебрать все возможные траектории движения по этому графу из точки в точку
-- для каждого варианта прохождения перебрать все касательные попарно (даже не соседние)
-- отбросить все касательные которые пересекают препятствия
-- оставшиеся касательные соединить дугами (не забыв о правиле запрета мгновенного разворота)
-- отбросить все касательные которые являются тупиками
-- построить граф нижнего уровня из возможных касательных (хотя, возможно, если отбросить всё лишнее, останется только 1 вариант), выбрать кратчайший путь из этого варианта и запомнить его
- и так с другими вариантами пути из общего графа
0
1464 / 820 / 139
Регистрация: 12.10.2013
Сообщений: 5,421
19.12.2018, 13:41 11
Цитата Сообщение от Дмитррр Посмотреть сообщение
Если решать полноценно, то нужно:
Видимо ТС этого не понимает, поэтому странно упростил до окружности в вакууме.
Веселуха начнется когда пойдут попытки в коде... А ведь мат анализ с неба не падает и весь этот велик будет есть ресурсы и капать время.

Недаром придумали правило форума “как можно полней описывайте задачу”.

По-хорошему нужно было весь пост 4 написать в первом посте. А еще лучше добавить хоть примерную картинку карты игры чтобы прикинуть какие колебания радиусов и плотности положения окружностей чтобы возможно сказали что такой велик это утопия. А вдруг окружности еще и пересекаются…
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
19.12.2018, 13:41
Помогаю со студенческими работами здесь

Движение круга по дуге
Здраствуйте!Как можно реализовать движение круга по дуге?Какой функцией задать дугу?

Вычислить интеграл по дуге L:
Помогите пожалуйста решить интеграл

Движение круга по дуге
создать программу демонстрирующую движение круга по дуге

Вычислить интеграл по дуге
Помогите пожалуйста, никак не получается \int_{C}^{}|z|dz, C: |z|=R


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru