/godot-pathfinding

name: godot-pathfinding
description: TileMap BFS寻路实现、六边形网格寻路、路径追溯与流式寻路功能。用于需要网格寻路、动态障碍物避让、游戏AI导航等场景。

Godot TileMap 寻路系统

TileMap网格寻路实现，包含BFS扩散算法、六边形网格支持、路径追溯以及流场寻路功能。

何时使用此技能

• 需要为格子地图实现寻路功能
• 实现RTS、塔防、回合制策略等游戏
• 需要动态障碍物避让
• 需要流场寻路支持多单位导航

1. TileMap BFS 寻路实现

基础 BFS 扩散算法

# tile_map_bfs.gd
# TileMap网格BFS寻路实现
class_name TileMapBFS
extends Node2D

signal path_found(path: Array[Vector2i])
signal path_not_found

@export var tile_map: TileMap
@export var obstacles_layer: int = 0  # 障碍物所在的层

var _grid_size: Vector2i
var _walkable: Dictionary = {}  # {Vector2i: bool}

func _ready() -> void:
    if tile_map:
        _initialize_grid()

func _initialize_grid() -> void:
    _grid_size = tile_map.get_used_rect().size
    var origin := tile_map.get_used_rect().position

    for x in range(_grid_size.x):
        for y in range(_grid_size.y):
            var cell := Vector2i(origin.x + x, origin.y + y)
            var tile_data := tile_map.get_cell_tile_data(obstacles_layer, cell)
            _walkable[cell] = tile_data == null or not tile_data.get_custom_data("obstacle")

func find_path(start: Vector2i, end: Vector2i) -> Array[Vector2i]:
    if not _walkable.has(start) or not _walkable.has(end):
        return []

    if not _walkable.get(end, false):
        return []

    if start == end:
        return [start]

    var open_set: Array[Vector2i] = [start]
    var came_from: Dictionary = {}
    var visited: Dictionary = {start: true}

    while not open_set.is_empty():
        var current := open_set.pop_front()

        if current == end:
            return _reconstruct_path(came_from, current)

        for neighbor in _get_neighbors(current):
            if not visited.get(neighbor, false) and _walkable.get(neighbor, false):
                visited[neighbor] = true
                came_from[neighbor] = current
                open_set.append(neighbor)

    return []

func _get_neighbors(cell: Vector2i) -> Array[Vector2i]:
    return [
        cell + Vector2i(0, -1),  # 上
        cell + Vector2i(1, 0),   # 右
        cell + Vector2i(0, 1),   # 下
        cell + Vector2i(-1, 0),  # 左
    ]

func _reconstruct_path(came_from: Dictionary, current: Vector2i) -> Array[Vector2i]:
    var path: Array[Vector2i] = [current]

    while came_from.has(current):
        current = came_from[current]
        path.push_front(current)

    return path

func is_walkable(cell: Vector2i) -> bool:
    return _walkable.get(cell, false)

func set_obstacle(cell: Vector2i, obstacle: bool) -> void:
    _walkable[cell] = not obstacle

带权重的 BFS（用于斜向移动）

# weighted_bfs.gd
class_name WeightedBFS
extends Node

@export var tile_map: TileMap
@export var obstacles_layer: int = 0

var _cell_cost: Dictionary = {}  # 每个格子的移动成本

func _ready() -> void:
    _initialize_costs()

func _initialize_costs() -> void:
    var rect := tile_map.get_used_rect()
    for cell in tile_map.get_used_cells(obstacles_layer):
        var tile_data := tile_map.get_cell_tile_data(obstacles_layer, cell)
        if tile_data:
            _cell_cost[cell] = tile_data.get_custom_data("cost")
        else:
            _cell_cost[cell] = 1.0

func find_path(start: Vector2i, end: Vector2i) -> Array[Vector2i]:
    if start == end:
        return [start]

    var open_set: Array[Vector2i] = [start]
    var came_from: Dictionary = {}
    var cost_so_far: Dictionary = {start: 0.0}
    var visited: Dictionary = {}

    while not open_set.is_empty():
        open_set.sort_custom(func(a, b): return cost_so_far[a] < cost_so_far[b])
        var current := open_set.pop_front()

        if current == end:
            return _reconstruct_path(came_from, current)

        visited[current] = true

        for neighbor in _get_neighbors(current):
            if visited.get(neighbor, false):
                continue

            var move_cost := _get_move_cost(current, neighbor)
            var new_cost := cost_so_far[current] + move_cost

            if not cost_so_far.has(neighbor) or new_cost < cost_so_far[neighbor]:
                cost_so_far[neighbor] = new_cost
                came_from[neighbor] = current

                if not open_set.has(neighbor):
                    open_set.append(neighbor)

    return []

func _get_neighbors(cell: Vector2i) -> Array[Vector2i]:
    return [
        cell + Vector2i(0, -1),
        cell + Vector2i(1, 0),
        cell + Vector2i(0, 1),
        cell + Vector2i(-1, 0),
        cell + Vector2i(1, -1),  # 斜向
        cell + Vector2i(1, 1),
        cell + Vector2i(-1, 1),
        cell + Vector2i(-1, -1),
    ]

func _get_move_cost(from: Vector2i, to: Vector2i) -> float:
    var base_cost := _cell_cost.get(to, 1.0)

    # 斜向移动成本更高
    if from.x != to.x and from.y != to.y:
        return base_cost * 1.414  # sqrt(2)

    return base_cost

func _reconstruct_path(came_from: Dictionary, current: Vector2i) -> Array[Vector2i]:
    var path: Array[Vector2i] = [current]

    while came_from.has(current):
        current = came_from[current]
        path.push_front(current)

    return path

2. 六边形网格寻路

六边形网格坐标系统

# hexagon_pathfinding.gd
class_name HexagonPathfinding
extends Node

# 六边形网格偏移系统
enum OffsetSystem { POINTY_TOP, FLAT_TOP }
enum CoordinateSystem { CUBE, AXIAL, OFFSET }

@export var offset_system: OffsetSystem = OffsetSystem.POINTY_TOP
@export var tile_map: TileMap
@export var obstacles_layer: int = 0

var _cube_directions := [
    Vector3i(1, -1, 0), Vector3i(1, 0, -1), Vector3i(0, 1, -1),
    Vector3i(-1, 1, 0), Vector3i(-1, 0, 1), Vector3i(0, -1, 1)
]

func axial_to_cube(hex: Vector2i) -> Vector3i:
    return Vector3i(hex.x, hex.y, -hex.x - hex.y)

func cube_to_axial(cube: Vector3i) -> Vector2i:
    return Vector2i(cube.x, cube.y)

func offset_to_axial(offset: Vector2i) -> Vector2i:
    if offset_system == OffsetSystem.POINTY_TOP:
        return Vector2i(offset.x, offset.y - (offset.x - (offset.x & 1)) / 2)
    else:
        return Vector2i(offset.x - (offset.y