Существуют ли какие-либо библиотеки для поиска путей для Python? [закрыто]

Закрыто. Этот вопрос не по теме . В настоящее время он не принимает ответы.

Хотите улучшить этот вопрос? Обновите вопрос , чтобы он был по теме для Stack Overflow.

Закрыт 6 лет назад .

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

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

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

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

Мой вариант использования:

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

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

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

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

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

python c performance path-finding

задан theheadofabroom 1 August 2011 в 11:43

0 ответов

Другие вопросы по тегам:

python c performance path-finding

Существуют ли какие-либо библиотеки для поиска путей для Python? [закрыто]

0 ответов

Похожие вопросы: