Простой алгоритм парковки

Question

Я ищу простой алгоритм парковки для игры.

Положение автомобиля и гаража, каждое из которых определяется 3 числами (x, y, theta). Где x и y - центр объекта и theta - угол между осью объекта и осью X.

Движение автомобиля упрощено - это точка (не нужно рассчитывать точное движение шины), которая может двигаться с fixed speed назад и вперед или поворачивать по кругу с радиусом R ( Радиус поворота может быть фиксированным или гибким - не имеет значения - любой вариант подходит для меня), и он имеет no inertia or acceleration.

В гараже есть 3 стены, которые не должны касаться машины. Для столкновения можно использовать точные размеры, но для простоты столкновение проверяется путем измерения углов между автомобилем и гаражом и расстоянием между осью автомобиля и центром гаража. Когда автомобиль и гараж находятся достаточно близко (расстояние между центрами меньше некоторой постоянной CloseEnough), столкновение проверяется (alpha, d) < (maxAlpha, maxDistance)

Мир, смоделированный тиками, мы берем текущие элементы управления автомобилем - moving direction вперед или назад и turning angle и вычисляем автомобиль на следующую позицию.

Алгоритм должен выдавать последовательность команд управления, например [forward, left], [forward, left], [backward, straight], [forward, right].

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

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

Answer 1

Есть несколько изломов, которые нужно решить, например, какая точность требуется для успешного дока, и какая точность позволяют «галочки». Вам придется экспериментировать. Но вот общий подход:

Без потери общности предположим, что машина движется по прямым линиям и окружностям с минимальным радиусом. (Большие круги дадут более короткую и мягкую езду, но оставим это на потом.) На практике это будет означать чередование линии-круга-линии-круга-линии ...

Конечная цель - ехать прямо в гараж.

Цель до этого («предпоследняя») - попасть на один из кругов, касающихся этого пути, как можно ближе к гаражу. Так, если гараж находится в (0,0,0), круги центрированы в (0, + / 1r). Как правило, если гараж находится в точке (x, y, θ), окружности центрируются в точке (x - / + rsinθ, y +/- rcosθ).

Цель до этого ("antepenultimate"?) Состоит в том, чтобы попасть из одного из кругов, на котором уже находится машина (влево или вправо), в линию, касающуюся как этого круга, так и целевого круга.

Цель до этого состоит в том, чтобы обойти гараж, если это необходимо, чтобы машина могла выполнять уже описанные движения, не ударяя по ней. Один из способов решения этой проблемы - нарисовать круг с центром в каждом углу гаража и переходить от круга к кругу.

Этого достаточно?