Тогда он движется вдоль препятствия, до тех пор, пока не обогнет ее. Этот трюк с поиском пути – использованный во многих реальных роботах – называется трассировкой.
Каждый из этих видов алгоритмов поиска пути имеет свои достоинства и недостатки. Некоторые сверх быстры для вычисления, но в результате дают очень длинные и странно выглядящие пути. Некоторые дают прекрасно выглядящие пути при определенных условиях, таких как пространства без вогнутостей типа ниш. Как всегда, вы должны взвесить все «за» и «против» и сделать свой выбор.
Лучший из известных алгоритмов поиска пути называется A*. При условии, что вы выполняете некоторые условия (которые мы обсудим позднее), A* гарантирует получение самого короткого из возможных путей между двумя точками. Однако, подобно другим алгоритмам поиска пути, A* также имеет недостаток: он медленный. Алгоритм A* является одним из лучших (если не лучшим) среди алгоритмов поиска пути, требующих интенсивных вычислений процессора. Однако, невзирая на его невысокую скорость, алгоритм A* используется больше любых других алгоритмов поиска пути в играх. Когда вы играете в игру вроде Diablo, и нажимаете на область на экране, персонаж идет к этому месту. Если на пути есть препятствие, персонаж обходит препятствие. В любой игре, в которую вы играете, и которая имеет способность подобного рода, вероятно, используется алгоритм A*. В этом разделе мы собираемся познакомить вас с этим алгоритмом и провести вас через него.
Алгоритм поиска пути A* ищет путь из точки A в точку B.
POINT A
ТОЧКА A
POINT B
ТОЧКА B
На иллюстрации выше вы можете видеть основное применение алгоритма A*. То, что вы видите, представляет собой сетку 20 на 20. Белые ячейки являются пустыми. Черные ячейки содержат стены. Серая ячейка в верхнем левом углу (точка A) является начальной позицией персонажа; темно-серая ячейка в нижнем правом углу (точка B) является конечным положением персонажа. Светло серый путь, соединяющий эти две точки, является путем, созданным алгоритмом поиска пути A*
Русская версия