1D поиск пути с «телепортами»

Question

Задача

Я хочу написать простую 1D RTS игру , и у меня возникнет следующая проблема path pathing : Существует множество одномерных линий , и везде есть телепорты , которые можно использовать для перемещения между линиями, а также для перемещения внутри текущей линии. Телепорты - единственный способ передвижения между линиями. Какой алгоритм или псевдокод можно использовать для определения кратчайшего пути между позицией po1 на линии li1 и po2 на li2? У нас есть набор телепортов T (у каждого есть po и li), которые связаны друг с другом с нулевой стоимостью.

Почему бы не A * или Dijkstra-алгоритм

Это потому, что я думаю, что это было бы излишним в 1D.

Разъяснение

• Возможно, это звучит немного двумерно, но это не потому, что вы можете двигаться только влево или вправо по одной строке.
• Есть расходы на проезд к телепорту, но телепортация от одного к другому бесплатна. Посмотреть это ascii art:

    ...0....s..0
    ......0.x...

Здесь самый короткий путь от начала s до цели x равен

• чтобы перейти к нужному телепорту
• телепортируется на одну строку вниз (только на этом рисунке; ​​действительно самолеты неупорядочены)
• и идите прямо к цели (окончательная стоимость = 5)

Answer 1

Вы можете перейти с любого телепорта из любого другого? В этом случае есть только два возможных пути: направо и налево от вашей исходной позиции. Как только вы доберетесь до телепорта, подойдите к телепорту, ближайшему к месту назначения. Готово. Хорошо, если вы не знаете, какой телепорт находится ближе всего к месту назначения, вы можете попробовать их все в одной плоскости, но все же.

Answer 2

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

На первом шаге начните с начальной точки и рассмотрите 2 пути поиска. Путь, идущий влево, и путь, идущий направо

Каждая итерация делает шаг по обоим путям, пока не окажется по одному из путей ...

1. ... вы нажали x (поиск, это самый короткий путь)
2. ... вы попали в телепорт

В случае (2) поставить отметку на пути, который еще не попал в телепорт.

Теперь начните с конечной точки x и начните поиск также по 2 путям. Идем налево и направо, 1 шаг за каждую итерацию. Теперь есть 2 возможных результата снова:

3. вы попали в отмеченное место -> кратчайший путь идет от начала в направлении знака и достигает конца без телепортов.
4. вы попали в телепорт -> ваш кратчайший путь идет от начала к телепорту на шаге (2), а затем от телепорта на шаге (4) к концу x.

Это найдет кратчайший путь за 2n шагов, где n - длина этого пути. (Так как вы всегда смотрите в 2 направлениях).

Answer 3

Поскольку, двигаясь влево или вправо, вы можете попасть только в один другой телепорт, вы можете считать, что каждый телепорт подключен к тем, которые расположены слева и справа от него по обе стороны от телепорта;поэтому каждый телепорт связан с четырьмя другими телепортами.

Это просто создает график, где каждый узел имеет максимум четыре ребра.Итак, просто построите этот граф в памяти и решите свою проблему, используя алгоритм Дейкстры (который не является избыточным, поскольку мы больше не "в" одномерном) .Это будет намного быстрее, чем алгоритм грубой силы, предложенный @ Jakob.