Как сократить время, затраченное на поиск пути, до недостижимого места? [Дубликат]

    

У этого вопроса уже есть ответ:

    

У меня есть карта 2048x2048, и если я path-find в недоступном месте, это делает прокрутку через каждый узел на карте, который замораживает поток в течение 4 секунд.

Как я могу уменьшить это время?

  • Я использую JPS
  • Это динамическая карта (она изменяется во время выполнения)
9 голосов | спросил KayleMaster 28 FebruaryEurope/MoscowbWed, 28 Feb 2018 13:01:09 +0300000000pmWed, 28 Feb 2018 13:01:09 +030018 2018, 13:01:09

3 ответа


17

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

ответил Bálint 28 FebruaryEurope/MoscowbWed, 28 Feb 2018 13:24:40 +0300000000pmWed, 28 Feb 2018 13:24:40 +030018 2018, 13:24:40
14

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

Кроме того, вы можете полностью удалить все изолированные недостижимые области из пути.

ответил Kromster 28 FebruaryEurope/MoscowbWed, 28 Feb 2018 13:18:14 +0300000000pmWed, 28 Feb 2018 13:18:14 +030018 2018, 13:18:14
3

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

ответил Philipp 28 FebruaryEurope/MoscowbWed, 28 Feb 2018 13:27:01 +0300000000pmWed, 28 Feb 2018 13:27:01 +030018 2018, 13:27:01

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

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132