Существуют ли полезные библиотеки для поиска путей для python?

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

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

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

Я наткнулся на python-pathfinding, но это, кажется, медленнее, чем то, что я создал для моего использования.

Мой прецедент:

Мои карты строятся из уровней, которые окружены стенами (видимыми или невидимыми) и должны быть связаны дверями (видимыми или невидимыми).

Мой текущий подход состоит в том, чтобы иметь два разных алгоритма:

  • Внутри комнаты я просматриваю отдельные плитки как узлы с каждой границей как край с равной стоимостью, используя первую глубину в направлении целевого местоположения

  • Между комнатами, где каждая дверь node. Самый короткий путь через комнату (от двери до двери) вычисляется с использованием первого алгоритма и сохраняется в хеш-таблице в качестве стоимости края между этими узлами. Затем вычисляются наборы ребер, которые могут пересекаться, чтобы получить от одного node к другому, и также сохраняются в хэш-таблице, и не разрешено включать один и тот же ребро более одного раза в один и тот же путь.

Я запускаю отдельный процесс при запуске, который генерирует график для второго алгоритма с использованием первого, и это решает многие из моих проблем, комнаты, как правило, относительно малы и поэтому наказание "на лету" - поиск остается ниже, чем в противном случае, а затем на большие расстояния:

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

Ответы

Ответ 1

Прежде всего, я знаю довольно эффективную и универсальную библиотеку для обработки алгоритма поиска A *. Это lib2dp. Вы можете легко подключить свой python-сгенерированный граф в эту библиотеку и получить быстрый ответ.

Во-вторых, A * по существу хорош для нахождения оптимального пути в соответствии с этим:

  • У вас есть полная и полная информация о вашем окружении.
  • Ваше окружение считается "статическим".

Если вы нарушите одно из этих правил, вы можете рассмотреть альтернативный алгоритм, называемый D* '.

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

Ответ 2

Если вы можете уменьшить свою игровую среду в графике, то http://networkx.lanl.gov/ имеет много хороших встроенных алгоритмов для такого рода вещей.

Ответ 3

Если у вас уже есть версия python, вы довольны, то почему бы не запустить ее через py2cmod? Это должно дать вам большую часть пути к версии вашего текущего алгоритма.

Другой альтернативой является psyco, хотя у него высокие накладные расходы.

Ответ 4

Вы можете проверить libtcod и обертку libtcodpy Python. Лично, однако, мне не очень нравится, как обертка не очень Pythonic, будучи излишне монолитной script с чрезмерным использованием префиксов имени функции (по крайней мере, в последний раз, когда я ее использовал). Я реорганизовал обертку в один момент и исправил ее для Python 3, но это было год назад, и поэтому с тех пор все может измениться.