Всё про геймдев для девелоперов, художников, левел- и геймдизайнеров, сценаристов
Разместить рекламу: @tproger_sales_bot
Другие каналы: @tproger_channels
Другие наши проекты: https://tprg.ru/media
Post #2058
1.02K

Как A* ищет короткий путь по игровой карте
Для алгоритма карта выглядит как граф: узлы обозначают положения, рёбра задают допустимые переходы. Поиск в ширину обходит граф равномерно, алгоритм Дейкстры учитывает стоимость перемещения, а A* использует оценку расстояния до цели и направляет поиск преимущественно к ней.
В примере проход по воде стоит в десять раз дороже прохода по траве. Представление карты тоже влияет на производительность: A* быстрее работает с меньшим числом узлов, хотя сетку проще использовать.
Интерактивный разбор Red Blob Games содержит анимации и код на Python: от очереди и восстановления пути до приоритетов и эвристики. Откройте его, если настраиваете навигацию персонажей и хотите увидеть, как граф и стоимость переходов меняют поиск.
Для алгоритма карта выглядит как граф: узлы обозначают положения, рёбра задают допустимые переходы. Поиск в ширину обходит граф равномерно, алгоритм Дейкстры учитывает стоимость перемещения, а A* использует оценку расстояния до цели и направляет поиск преимущественно к ней.
В примере проход по воде стоит в десять раз дороже прохода по траве. Представление карты тоже влияет на производительность: A* быстрее работает с меньшим числом узлов, хотя сетку проще использовать.
Интерактивный разбор Red Blob Games содержит анимации и код на Python: от очереди и восстановления пути до приоритетов и эвристики. Откройте его, если настраиваете навигацию персонажей и хотите увидеть, как граф и стоимость переходов меняют поиск.
- ❤ 3

















