[Из песочницы] Алгоритм поиска пути — на раз, два, три!
Поиск пути — это алгоритм, осуществляющий прокладку маршрута из точки 1 в точку 2, в обход препятствий.Чаще всего находит применение в играх жанра стратегии и у военных роботов, для поиска пути к врагу.
На сегодня обладает неимоверной известностью алгоритм астар, иногда пишут как А*. Но на хабре была обнаружена статья рассказывающая о новом, революционном алгоритме «прыгающих точек», на английском выглядит так «Jump Point Search».
Введение
Эта статья направлена на тех, кто вообще никак не понимает данный алгоритм, но хочет его понять снова и снова.
Прочитав эту статью, вы сразу все поймете и сможете на любом языке объяснить его любому желающему.
И главное не забывайте, для закрепления материала, рекомендую рассказать о принципе работы этого хитрого алгоритма кому нибудь еще.
Представляю, что у меня есть некий полигон, с ячейками. Уважаемые читатели, смотрите на рисунок ниже. В нем вы должны увидеть зеленый кубик, а справа о него обнаружите красный кубик. Так вот, зеленый квадратик — начало пути нашего героя, красный квадратик — место где сидит дракон. Наш герой просто обязан найти путь к дракону и вальнуть его.
Читать дальше →
