Робот из 70х предвосхитил стандарты игровой индустрии
Сейчас буду рассказывать про A*. Читается как А-стар, типа восьмиконечная звезда, хотя это, на самом деле, обозначение оптимальности, поэтому расшифровка - оптимальный А-алгоритм.
Алгоритм поиска пути Дейкстры (боже помоги это нормально выговорить) честно перебирает всё вокруг, пока не найдёт кратчайший путь, и ему всё равно, в какую сторону цель. A* - это тот же Dijkstra, только его прокачали, прошептав на ухо примерное направление, и перебирать половину графа больше не надо.
Придумали алгоритм в 1968-м Питер Харт, Нильс Нильссон и Бертрам Рафаэль в Стэнфорде — не в вакууме, а под конкретную задачу - робота Шейки. Это был первый мобильный робот, способный сам планировать действия, а не просто выполнять команды — камера, дальномер, радио с мейнфреймом, который весил больше самого робота, поэтому и Шейки. Шейки катался по комнате с фанерными блоками и должен был строить маршрут между ними в реальном времени, а не пересчитывать весь граф на каждый шаг — отсюда и родилась эвристика: не просто "дёшево дойти досюда", а "дёшево дойти досюда плюс примерно докуда ещё топать".
Принцип Астар чуть сложнее, но та же база: берем графовый Дейкстра алгоритм, накидываем ему глобальное направление, которое он будет стараться выбирать приоритетнее остальных и осознаем, что это и его сильная сторона и слабая одновременно. Если с направлением не угадал - он станет простым Дейкстра алгоритмом.
В играх A* - это буквально база, особенно в стратегиях: близзард в своих StarCraft и Warcraft гоняют юнитов по нему, Age of Empires II, Total War, Baldur's Gate и вся линейка CRPG на его основе строят маршруты партии, Cities: Skylines считает так трафик по улицам, а любой NavMesh в Unity или Unreal под капотом — тоже он, просто с готовым слоем поверх, обычно, с динамическим пересчетом глобального направления.
Помимо того, что это база для игр, астар и его производные очень часто используются в настоящей и сложной навигации в реальном мире, особенно междугородных с учетом настоящих дорог в жизни, о чем, кстати, рассказывал Veritassium в одном из видео, которое и побудило меня обсасывать все эти базовые батя-алгоритмы навигации. А разные каналы на ютубе и тиктоке вообще получают миллионы просмотров только потому, что ставят а-стар на куски реальных карт мира и делают красивую визуализацию.
Но в навигации, GPS и прочих используют более сложные запекаемые варианты просчета, в которые входит а-стар только для того, чтоб твой айфон в бардачке смог не за 20 минут построить путь до лукойла, а за 3.2 секунды.
Лично я в немом восторге от того, как одна идея выросла в другую. Орков в Warcraft и реальные маршруты в GPS гоняет, по сути, один и тот же принцип - просто в разных масштабах. Это прям красиво.
