Java-поиск пути в реальной 2D-области

Question

Я делаю исследовательский проект по ориентации RC-автомобиля с использованием малины pi и 2D-сканера LIDAR. В основном автомобиль будет проходить через место со сканером, чтобы получить 2D-представление места, а затем он вернется к исходной точке. После этого вы сможете выбрать точку на месте и найти в ней путь. Поскольку я в значительной степени начинаю программировать, возможно, это будет почти невозможно сделать за 1 месяц, но я постараюсь изо всех сил :) Ну, что я хотел знать на данный момент - какой алгоритм для поиска пути я должен использовать? Поскольку разрешение 2D-места будет составлять около 5000 х 5000 "пикселей", что будет представлять собой место в сантиметрах, я считаю, что мне понадобится достаточно эффективный. Есть ли какой-либо конкретный алгоритм, который бы работал достаточно быстро на малине pi, чтобы сделать работу почти мгновенно? Если есть, есть ли эффективная реализация?

Некоторая дополнительная информация: Я использую «Pixel» 2D массив, в котором значения означает следующее:

EMPTY_SPACE = 0 
FILLED_SPACE = 1 
START_POINT = 2 
END_POINT = 3 
PROCESSING = 4 
PROCESSED = 5 
VISUAL_ASSISTANCE_POINTS = 6 

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

Возможно, это обман: Pathfinding in 2D Arrays, но я не нашел решения для всех своих вопросов, так как я ищу более конкретный ответ.

EDIT:

Я нашел this код, реализующий алгоритм *, но я нахожу это очень медленно ... Есть ли способ ускорить его? Я использовал изображение, связанное ниже, чтобы проверить его, и это заняло около 80 минут, чтобы решить.

Answer 1

A* pathfinding является одной из лучших ставок. Он широко используется в играх, где необходимо найти путь между A и B в 2D сетке. Он использует эвристику для определения благоприятных узлов (назовем их пикселями, если хотите) и, следовательно, достигает хорошей производительности (хотя зависит от того, насколько хорошо вы выбираете функцию эвристики). Реализация достаточно проста по сравнению с любыми конкретными/сильно оптимизированными алгоритмами. Кроме того, доступны различные реализации.

Что касается «почти мгновенной» скорости, я сомневаюсь, что вы можете получить это только с помощью алгоритма. Когда такая производительность требуется, необходимо будет внести изменения в домене. Одним из решений может быть предварительное вычисление определенных путей. Пути могут представлять полное сопоставление одного узла с каждым другим узлом (в вашем случае с сеткой 5000x5000 это непрактично). В качестве альтернативы предварительно вычисленные пути могут обрабатывать блок узлов в сетке как один узел, т. Е. Из области x, y в 0..10,0..10 любое перемещение в область x, y в 10..20.0. .10 использовать один предварительно вычисленный путь. Это может не дать вам лучший путь, но он определенно будет быстрее. Как и в любом случае в вычислениях, всегда есть компромисс между памятью и скоростью.

Также стоит уточнить, относится ли «пиксель» к вашему вопросу к одному движению на автомобиле. Это может быть так, что площадь 5000x5000, но автомобиль фактически занимает 50 пикселей за раз. Затем вы можете использовать один узел для представления 50 пикселей для ускорения вычислений и получения более точных результатов.