Jump-Point поиск в деталях
Я пытался реализовать поиск пути через Jump-point в моем уже реализованном коде поиска пути A*, но есть одна серьезная проблема, я не до конца понимаю, как он работает. Веб-сайт здесь (это все, что я смог найти по теме поиска в Jump-point): http://harablog.wordpress.com/2011/09/07/jump-point-search/, на самом деле, мало что объясняет как обрезать и как определить преемника Jump-point. Если бы кто-нибудь мог объяснить эти две вещи в деталях, это было бы очень ценно.
2 ответа
Технические подробности содержатся в исследовательской работе, которую можно найти на веб-странице Альбана Грастиена.
На aigamedev.com также есть учебное пособие.
Похоже, что улучшенная статья появится на ICAPS 2014, но я не верю, что документы еще находятся в сети.
Если этих ресурсов недостаточно, на более направленный вопрос (чего вы не понимаете) будет легче ответить. Но важно отметить, что JPS сканирует пространство состояний в поисках препятствий. При этом он может рассматривать гораздо больше состояний, чем A*. Но его экономия времени происходит из-за того, что большинство стран не включены в список OPEN.
В дополнение к оригинальной статье 2011 года я также нашел этот сайт: https://zerowidth.com/2013/a-visual-explanation-of-jump-point-search.html особенно полезным, так как он объясняет, как работает JPS в простом термины с диаграммами, а также включает в себя сетку, где вы можете добавлять/удалять препятствия и визуализировать, как JPS находит и расширяет точки перехода.