Оглавление
Проблема
У вас есть среда на основе сетки и вы хотели бы настроить поиск пути для навигации.
Решение
Godot предоставляет несколько методов для поиска пути. В этом рецепте мы рассмотрим алгоритм A*.
A* — широко используемый алгоритм для нахождения кратчайшего пути между двумя точками. Его можно использовать в любой структуре данных, основанной на графах, не только в сетке.
AStarGrid2D — это специализированная версия более общего класса AStar2D в Godot. Поскольку он специализирован для использования с сеткой, его проще и быстрее настраивать, потому что вам не нужно вручную добавлять все отдельные ячейки сетки и их соединения.
Настройка сетки
Самым важным аспектом при настройке является размер ячеек и размер самой сетки. В этом примере мы используем (64, 64), и мы будем использовать размер окна для определения того, сколько ячеек помещается на экране, но все будет работать так же, независимо от размера ячейки.
Добавьте этот код к Node2D.
extends Node2D
@export var cell_size = Vector2i(64, 64)
var astar_grid = AStarGrid2D.new()
var grid_size
func _ready():
initialize_grid()
func initialize_grid():
grid_size = Vector2i(get_viewport_rect().size) / cell_size
astar_grid.size = grid_size
astar_grid.cell_size = cell_size
astar_grid.offset = cell_size / 2
astar_grid.update()В этом коде мы делим размер экрана на размер ячейки, чтобы вычислить размер всей сетки. Это позволяет нам установить свойство size для AStarGrid2D.
Свойство offset будет использоваться, когда мы будем запрашивать путь между двумя точками. Использование cell_size / 2 означает, что путь будет рассчитан от центра каждой ячейки, а не от её углов.
Наконец, после установки или изменения любого из свойств AStarGrid2D, нам нужно вызвать update().
Отрисовка сетки
В целях этой демонстрации мы будем рисовать сетку на экране в коде. В приложении игры у вас, вероятно, будет TileMap или какое-то другое визуальное представление вашего мира.
Вот код для отрисовки сетки:
func _draw():
draw_grid()
func draw_grid():
for x in grid_size.x + 1:
draw_line(Vector2(x * cell_size.x, 0),
Vector2(x * cell_size.x, grid_size.y * cell_size.y),
Color.DARK_GRAY, 2.0)
for y in grid_size.y + 1:
draw_line(Vector2(0, y * cell_size.y),
Vector2(grid_size.x * cell_size.x, y * cell_size.y),
Color.DARK_GRAY, 2.0)Этот код дает нам красивую визуализацию сетки:
Отрисовка пути
Для того чтобы найти путь, нам нужны начальная и конечная точки. Добавьте эти переменные в верхней части скрипта:
var start = Vector2i.ZERO
var end = Vector2i(5, 5)И несколько строк в _draw(), чтобы их показать:
draw_rect(Rect2(start * cell_size, cell_size), Color.GREEN_YELLOW)
draw_rect(Rect2(end * cell_size, cell_size), Color.ORANGE_RED)Мы можем найти путь между двумя точками, используя метод get_point_path(), но нам также нужно визуализировать его. Мы можем использовать Line2D, поэтому добавьте его в сцену.
Вот как мы можем получить путь и добавить полученные точки к Line2D:
func update_path():
$Line2D.points = PackedVector2Array(astar_grid.get_point_path(start, end))Вот результат:
Обратите внимание, что у нас есть диагональная линия между двумя точками. Это потому, что по умолчанию путь будет использовать диагонали. Это можно изменить, изменив diagonal_mode:
- DIAGONAL_MODE_ALWAYS — Значение по умолчанию, использует диагонали.
- DIAGONAL_MODE_NEVER — Вся передвижение ортогонально. DIAGONAL_MODE_AT_LEAST_ONE_WALKABLE — Это позволяет использовать диагонали, но предотвращает прохождение пути «между» диагонально расположенными препятствиями.
- DIAGONAL_MODE_ONLY_IF_NO_OBSTACLES — Это позволяет использовать диагонали только в «открытых» областях, а не рядом с препятствиями.
Изменение этих свойств может дать вам совершенно разные результаты, поэтому экспериментируйте в зависимости от вашей конфигурации. Давайте добавим это в функцию initialize_grid():
astar_grid.diagonal_mode = AStarGrid2D.DIAGONAL_MODE_NEVERТеперь у нас есть только ортогональные движения:
Добавление препятствий
Мы также можем добавить препятствия на сетку. Пометив ячейку как «твердую», путь не будет включать эту ячейку. Ячейку можно переключить между твердой/нетвердой с помощью функции set_point_solid().
Добавим код для отрисовки наших стен (когда они существуют), найдя все твердые ячейки и закрашивая их:
func fill_walls():
for x in grid_size.x:
for y in grid_size.y:
if astar_grid.is_point_solid(Vector2i(x, y)):
draw_rect(Rect2(x * cell_size.x, y * cell_size.y, cell_size.x, cell_size.y), Color.DARK_GRAY)Вызовите эту функцию в _draw().
Затем мы можем использовать мышь, чтобы кликнуть по ячейкам и переключить их состояние:
func _input(event):
if event is InputEventMouseButton:
# Add/remove wall
if event.button_index == MOUSE_BUTTON_LEFT and event.pressed:
var pos = Vector2i(event.position) / cell_size
if astar_grid.is_in_boundsv(pos):
astar_grid.set_point_solid(pos, not astar_grid.is_point_solid(pos))
update_path()
queue_redraw()Обратите внимание, что мы сначала проверяем is_in_boundsv() — это предотвратит возникновение ошибок при клике за пределами границ сетки.
Теперь мы можем увидеть эффект препятствий на пути:
Выбор маршрута пути
Важным фактором, влияющим на получаемый путь, является выбор эвристики (маршрута пути). Термин «эвристика» относится к «лучшему предположению» и в контексте поиска пути означает: в каком направлении мы должны попытаться двигаться к цели сначала?
Например, евклидово расстояние использует теорему Пифагора для оценки пути:
В то время как манхэттенское расстояние учитывает только расстояние в направлениях N/S или E/W:
А эвристика октанта приводит к такому пути:
Вы можете выбрать эвристику, используя это свойство:
astar_grid.default_estimate_heuristic = AStarGrid2D.HEURISTIC_OCTILEКакая из них работает лучше (приводит к наиболее удовлетворительным путям), зависит от характера вашей среды. Обязательно экспериментируйте с вашим конкретным проектом.
Загрузите пример проекта ниже, чтобы попробовать эту настройку самостоятельно. Помимо установки стен, вы можете использовать правую/среднюю кнопки мыши для перемещения конечных/начальных точек.
Скачайте этот проект
Скачайте код проекта здесь: https://github.com/godotrecipes/grid_pathfinding