Pathfinding вдоль сетки, с завихрением

Question

Ive скремблировал мои мозги, пытаясь найти способ найти кратчайший путь между двумя точками на 2-й сетке. Я видел сообщения о алгоритмах Ли и А *, но никто нигде не может ответить на мой самый важный вопрос. Как эти алгоритмы могут быть tweeked для работы с десятичными координатами.

Все, что я видел, было простым целым числом. Но что происходит, когда вы пытаетесь найти кратчайший путь между отправной точкой (3.3, 4) и конечной точкой (5, 4.6)?

В основном мне нужно найти кратчайший путь между двумя точками, где точки содержат десятичные значки, но вам все равно придется следовать за целыми линиями сетки. вы не можете двигаться по диагонали, только на северо-восток или запад вдоль сетки, но ваш не начинается или не заканчивается на пересечении (например, 1,1).

Подумайте о идеальном городе, где каждое пространство между линиями сетки (каждый квадрат) является городским блоком, а линии сетки - дороги, на которых вы можете путешествовать.

Я лаяю неправильное дерево с Ли или A *? Я чрезвычайно новичок в поиске пути, и я полностью самоучитель. Я знаю, что заново изобретать алгоритм за пределами моей сферы на данный момент, но я смотрю на мои 80 + if заявления и думаю, что «это не может быть способом эффективного поиска пути». И тестирование всех возможностей с использованием операторов if почти невозможно.

Любые мысли или статьи на веб-сайте приветствуются. Заранее спасибо

Answer 1

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

Как только вы знакомы с общими структурами графов, модификации, которые вам нужно выполнить для алгоритма A * или Dijkstra, основанного на сетке, для работы в вашем случае относительно незначительны. Вы бы просто добавили новые узлы, представляющие начальное и конечное местоположения, и подключили их с соответствующими взвешенными краями к четырем соседним точкам решетки. Оттуда вы можете запустить A *, как обычно.

Если вы ищете отправную точку, некоторое время назад я преподавал класс по базовым структурам данных и алгоритмам графа и собирал some slides on Dijkstra's algorithm and A* search, что может дать вам хорошее введение в тему. Удачи!