Мне нужен алгоритм, который дал бы мне путь от начального узла к конечному узлу, но путь должен иметь точное количество узлов, иначе поиск пути не удастся.
Для расширения у меня есть сетка из плиток. Перемещение может быть только на соседнюю плитку вверх, вниз, влево или вправо (то есть без движения по диагонали). Существует множество правил, определяющих, какую плитку можно и нельзя использовать в пути, но в основном это можно свести к простому логическому выражению, чтобы определить, можно или нельзя использовать плитку (и это можно вычислить еще до запуска алгоритма. . Что меня беспокоит, так это то, что у меня есть заданное расстояние, которое должен иметь путь, то есть каждое движение от одной плитки к соседней - это расстояние, равное единице, а весь путь должен иметь расстояние, равное единице. указанное расстояние, не больше и не меньше. Кроме того, после того, как на плитку наступили (но все плитки доступны в начале алгоритма), на нее нельзя наступить снова, как будто вы играете в старую игру Змейка, где вы надо следить, чтобы не съесть себя.
Я посмотрел на Dijkstra / A * и искал в Google алгоритмы поиска пути, но, насколько я могу судить, все они ориентированы на кратчайший путь, что не приносит мне особой пользы. Меня не волнует, какой это путь, если он следует вышеупомянутым правилам.
Я что-то пропустил, существует ли такой алгоритм и уже существует, или есть простой способ изменить Dijkstra / A *, чтобы получить такой результат? Поскольку я не являюсь носителем английского языка, я могу использовать неправильную терминологию, поэтому приветствую предложения ключевых слов для этого типа алгоритма.
Вот иллюстрация того, что я имею в виду, когда говорю, что это должно быть точное расстояние и нельзя использовать одну и ту же плитку дважды.
Допустим, расстояние должно быть 7. Теперь давайте отметим плитки, которые можно использовать на пути, с помощью O, плитки, которые нельзя использовать, и X, начальную точку с помощью S и цель с помощью E.
X X X X X X X X O O E S O O X O O O O O O
Если бы не было ограничения по расстоянию, можно было бы просто пойти налево и решить проблему. Если бы было ограничение расстояния, но не ограничение «нельзя наступить на одну плитку», можно было бы спуститься один раз вниз, затем влево, затем вправо, затем влево, затем вправо, затем влево, затем вверх и достичь цели. . Поскольку есть оба ограничения, нужно идти вправо, вниз, влево, влево, влево, вверх, а затем вправо, чтобы добраться до цели. Однако, если бы ситуация была такой, действительного пути не было бы.
X X X X X X X X O O E S O O X X O O O X O
На случай, если это будет актуально, я разрабатываю эту настольную игру на C #.
Что касается максимального расстояния, вот диапазон, в котором оно будет находиться. Игрок бросает кубик и получает число 1-6. Если игрок получает 6, он снова бросает кости, а если он получает еще 6, снова и снова, пока он не получит 6. Расстояние - это полученное число плюс количество поднятых игроком предметов, которые теоретически могут быть поднимитесь до 8, но обычно будет 0-3, мааайбе 4.
С другой стороны, я только что получил новые приказы, правила игры изменились, чтобы разрешить наступление на одну и ту же позицию дважды по одному и тому же пути, что, как я считаю, значительно упрощает процесс, но я оставлю этот вопрос как есть Я думаю, у него есть хорошие ответы, которые могут помочь кому-то в этой ситуации.
