Алгоритм поиска пути с ограничениями C++

Цена договорная
24 ноября 2023, 04:28 • 7 откликов • 52 просмотра
Все числа ниже могут быть переменные.

Есть плоскость размером 600 x 600, по вертикали и горизонтали расположены точки на расстоянии 15 единиц друг от друга, т.е. 40 точек по горизонтали и 40 по вертикали. Некоторые точки представляют собой препятствие, поэтому будут убраны, но для упрощения предлагаю сделать версию без препятствий.

Идея заключается в том, что определённое физическое тело двигается на фиксированное расстояние без остановки. Для этого объекта нужно построить путь от точки старта A до точки назначения B, максимально избегая резких поворотов, и, если нужно, переиспользовать точки, которые уже были посещены, чтобы растянуть путь. Т.е. мы не ищем кратчайший путь, а наоборот пытаемся его "раздуть".

Требования:
1) Найти путь от точки A к точке B длиной 1200 единиц (± погрешность 50-100).
2) Траектория пути должна быть максимально пологая, избегая резких поворотов.
3) Алгоритмы поиска пути обычно не используют повторно точки, которые уже были посещены ранее, но, с учётом того, что искомое расстояние пути может быть намного больше, чем доступная область для поиска, нужно учесть, что путь может образовывать петли, чтобы уместить нужное расстояние в маленькую область и сделать это максимально плавно.

Учитывая, что точки упорядочены по сетке, соответственно, движения доступны в 8 направлениях: по горизонтали, по вертикали и по диагонали.

Расположение точек в формате grid не обязательное условие. Можно проверить возможность расположение точки в любом указанном месте и есть 2d луч для проверки препятствий.
Отзывы
Avatar r50 a6ce93fe35b158fd29ba0e8681c918c22117160e9586a56eee4ffbc20df9bda1
Заказчик
 
3 месяца назад
К заказчику никаких претензий, всё хорошо.
3 месяца назад