Я работаю над изометрической RPG в режиме реального времени в python и хочу настроить таргетинг мобильных устройств как платформы. Основная область, где у меня возникают трудности, - это мой путь. Я попробовал несколько алгоритмов, включая A *, и несколько настроек, чтобы лучше соответствовать картам, которые я использую.
Я удовлетворен результатами моего алгоритма - они дают иллюзию некоторого интеллекта, будучи детерминированным, и согласуются в любом направлении, так что два символа, нацеленные на места друг друга, будут сталкиваться посередине.
Моя проблема заключается в том, что, хотя результаты выглядят хорошо на ПК, где у меня есть все вычислительные мощности, которые я мог бы попросить, на моем мобильном телефоне это совсем другая история, и часто алгоритм рассчитывается на вторую или более задержку. По этой причине я подумываю о написании библиотеки для этого с использованием наиболее интенсивного с точки зрения производительности кода, написанного на C, однако, если для этого существует существующее решение или лучше, я мог бы сделать все уши.
Я наткнулся на python-pathfinding, но это, кажется, медленнее, чем то, что я создал для моего использования.
Мой прецедент:
Мои карты строятся из уровней, которые окружены стенами (видимыми или невидимыми) и должны быть связаны дверями (видимыми или невидимыми).
Мой текущий подход состоит в том, чтобы иметь два разных алгоритма:
-
Внутри комнаты я просматриваю отдельные плитки как узлы с каждой границей как край с равной стоимостью, используя первую глубину в направлении целевого местоположения
-
Между комнатами, где каждая дверь node. Самый короткий путь через комнату (от двери до двери) вычисляется с использованием первого алгоритма и сохраняется в хеш-таблице в качестве стоимости края между этими узлами. Затем вычисляются наборы ребер, которые могут пересекаться, чтобы получить от одного node к другому, и также сохраняются в хэш-таблице, и не разрешено включать один и тот же ребро более одного раза в один и тот же путь.
Я запускаю отдельный процесс при запуске, который генерирует график для второго алгоритма с использованием первого, и это решает многие из моих проблем, комнаты, как правило, относительно малы и поэтому наказание "на лету" - поиск остается ниже, чем в противном случае, а затем на большие расстояния:
- первый алгоритм используется для вычисления расстояния от текущего местоположения до каждой двери в текущей комнате.
- первый алгоритм используется для расчета расстояния от каждой двери в целевой комнате до места назначения.
- вывод второго алгоритма используется для получения набора путей между комнатами
- стоимость их добавляется к стоимости получения до первой двери и от последней двери
- набор решений сортируется по стоимости таким образом, что порядок путей с одинаковой стоимостью всегда будет согласован.
- выбирается первый элемент в наборе решений.