AStarGrid2D

继承: RefCounted < Object

A* 的一种实现,用于寻找疏松 2D 网格中两点之间的最短路径。

描述

AStarGrid2DAStar2D 的变种,针对疏松 2D 网格进行了优化。因为不需要手动创建点并进行连接,所以用起来更加简单。这个类还支持使用不同的启发方法、斜向移动模式、跳跃模式,从而加速运算。

要使用 AStarGrid2D,你只需要设置网格的 regioncell_size 可以不设置,最后调用 update 方法即可:

GDScriptC#

  1. var astar_grid = AStarGrid2D.new()
  2. astar_grid.region = Rect2i(0, 0, 32, 32)
  3. astar_grid.cell_size = Vector2(16, 16)
  4. astar_grid.update()
  5. print(astar_grid.get_id_path(Vector2i(0, 0), Vector2i(3, 4))) # 输出 (0, 0), (1, 1), (2, 2), (3, 3), (3, 4)
  6. print(astar_grid.get_point_path(Vector2i(0, 0), Vector2i(3, 4))) # 输出 (0, 0), (16, 16), (32, 32), (48, 48), (48, 64)
  1. AStarGrid2D astarGrid = new AStarGrid2D();
  2. astarGrid.Region = new Rect2I(0, 0, 32, 32);
  3. astarGrid.CellSize = new Vector2I(16, 16);
  4. astarGrid.Update();
  5. GD.Print(astarGrid.GetIdPath(Vector2I.Zero, new Vector2I(3, 4))); // 输出 (0, 0), (1, 1), (2, 2), (3, 3), (3, 4)
  6. GD.Print(astarGrid.GetPointPath(Vector2I.Zero, new Vector2I(3, 4))); // 输出 (0, 0), (16, 16), (32, 32), (48, 48), (48, 64)

要从寻路网格中移除某个点,必须使用 set_point_solid 将其设置为“实心”。

属性

Vector2

cell_size

Vector2(1, 1)

Heuristic

default_compute_heuristic

0

Heuristic

default_estimate_heuristic

0

DiagonalMode

diagonal_mode

0

bool

jumping_enabled

false

Vector2

offset

Vector2(0, 0)

Rect2i

region

Rect2i(0, 0, 0, 0)

Vector2i

size

Vector2i(0, 0)

方法

float

_compute_cost ( Vector2i from_id, Vector2i to_id ) virtual const

float

_estimate_cost ( Vector2i from_id, Vector2i to_id ) virtual const

void

clear ( )

void

fill_solid_region ( Rect2i region, bool solid=true )

void

fill_weight_scale_region ( Rect2i region, float weight_scale )

Vector2i[]

get_id_path ( Vector2i from_id, Vector2i to_id )

PackedVector2Array

get_point_path ( Vector2i from_id, Vector2i to_id )

Vector2

get_point_position ( Vector2i id ) const

float

get_point_weight_scale ( Vector2i id ) const

bool

is_dirty ( ) const

bool

is_in_bounds ( int x, int y ) const

bool

is_in_boundsv ( Vector2i id ) const

bool

is_point_solid ( Vector2i id ) const

void

set_point_solid ( Vector2i id, bool solid=true )

void

set_point_weight_scale ( Vector2i id, float weight_scale )

void

update ( )


枚举

enum Heuristic:

Heuristic HEURISTIC_EUCLIDEAN = 0

欧几里德启发式算法将被用于寻路,使用的公式如下:

  1. dx = abs(to_id.x - from_id.x)
  2. dy = abs(to_id.y - from_id.y)
  3. result = sqrt(dx * dx + dy * dy)

注意:这也是 AStar3DAStar2D 默认使用的内部启发式算法(包括可能的 z 轴坐标)。

Heuristic HEURISTIC_MANHATTAN = 1

曼哈顿启发式算法将被用于寻路,使用的公式如下:

  1. dx = abs(to_id.x - from_id.x)
  2. dy = abs(to_id.y - from_id.y)
  3. result = dx + dy

注意:该启发式算法旨在与 4 边正交运动一起使用,4 边正交运动可通过将 diagonal_mode 设置为 DIAGONAL_MODE_NEVER 来提供。

Heuristic HEURISTIC_OCTILE = 2

Octile 启发式算法将被用于寻路,使用的公式如下:

  1. dx = abs(to_id.x - from_id.x)
  2. dy = abs(to_id.y - from_id.y)
  3. f = sqrt(2) - 1
  4. result = (dx < dy) ? f * dx + dy : f * dy + dx;

Heuristic HEURISTIC_CHEBYSHEV = 3

切比雪夫启发式算法将被用于寻路,使用的公式如下:

  1. dx = abs(to_id.x - from_id.x)
  2. dy = abs(to_id.y - from_id.y)
  3. result = max(dx, dy)

Heuristic HEURISTIC_MAX = 4

代表 Heuristic 枚举的大小。


enum DiagonalMode:

DiagonalMode DIAGONAL_MODE_ALWAYS = 0

该寻路算法将忽略目标单元格周围的实体邻居,并允许沿对角线通过。

DiagonalMode DIAGONAL_MODE_NEVER = 1

该寻路算法将忽略所有对角线,并且路径始终是正交的。

DiagonalMode DIAGONAL_MODE_AT_LEAST_ONE_WALKABLE = 2

如果在特定路径段的相邻单元格周围放置了至少两个障碍物,则该寻路算法将避免使用对角线。

DiagonalMode DIAGONAL_MODE_ONLY_IF_NO_OBSTACLES = 3

如果在特定路径段的相邻单元格周围放置了任意障碍物,则该寻路算法将避免使用对角线。

DiagonalMode DIAGONAL_MODE_MAX = 4

代表 DiagonalMode 枚举的大小。


属性说明

Vector2 cell_size = Vector2(1, 1)

要用于计算由 get_point_path 返回的结果点位置的点单元的大小。如果更改了这个值,在查找下一个路径之前需要调用 update


Heuristic default_compute_heuristic = 0

  • void set_default_compute_heuristic ( Heuristic value )

  • Heuristic get_default_compute_heuristic ( )

默认 Heuristic,用于在没有覆盖 _compute_cost 时计算两点之间的消耗。


Heuristic default_estimate_heuristic = 0

  • void set_default_estimate_heuristic ( Heuristic value )

  • Heuristic get_default_estimate_heuristic ( )

默认 Heuristic,用于在没有覆盖 _estimate_cost 时计算该点和终点之间的消耗。


DiagonalMode diagonal_mode = 0

特定的 DiagonalMode,会强制路径避免或接受特定的对角线。


bool jumping_enabled = false

  • void set_jumping_enabled ( bool value )

  • bool is_jumping_enabled ( )

启用或禁用跳跃,以跳过中间点并加快搜索算法的速度。

注意:目前,打开它会在寻路过程中忽略权重缩放。


Vector2 offset = Vector2(0, 0)

栅格的偏移量,将被应用以计算 get_point_path 返回的结果点的位置。如果发生变化,需要在查找下一条路径之前调用 update


Rect2i region = Rect2i(0, 0, 0, 0)

栅格上用来寻路的区域。如果发生变化,需要在查找下一条路径之前调用 update


Vector2i size = Vector2i(0, 0)

栅格的大小(每个轴上大小为 cell_size 的单元格数)。如果发生变化,需要在查找下一条路径之前调用 update

已弃用。请使用 region 替代。


方法说明

float _compute_cost ( Vector2i from_id, Vector2i to_id ) virtual const

计算两个连接点之间的成本时调用。

注意这个函数隐藏在默认的 AStarGrid2D 类中。


float _estimate_cost ( Vector2i from_id, Vector2i to_id ) virtual const

估计一个点和路径终点之间的成本时调用。

注意这个函数隐藏在默认的 AStarGrid2D 类中。


void clear ( )

清空网格并将 region 设置为 Rect2i(0, 0, 0, 0)


void fill_solid_region ( Rect2i region, bool solid=true )

使用指定的值填充网格上 region 区域的实心标志。

注意:调用该函数后不需要调用 update


void fill_weight_scale_region ( Rect2i region, float weight_scale )

使用指定的值填充网格上 region 区域的权重缩放。

注意:调用该函数后不需要调用 update


Vector2i[] get_id_path ( Vector2i from_id, Vector2i to_id )

返回一个数组,其中包含形成 AStar2D 在给定点之间找到的路径的点的 ID。该数组从路径的起点到终点排序。


PackedVector2Array get_point_path ( Vector2i from_id, Vector2i to_id )

返回一个数组,其中包含 AStarGrid2D 在给定点之间找到的路径上的点。数组从路径的起点到终点排序。

注意:该方法不是线程安全的。如果从 Thread 中调用它,它将返回一个空的 PackedVector3Array 并打印一条错误消息。


Vector2 get_point_position ( Vector2i id ) const

返回与给定 id 相关联的点的位置。


float get_point_weight_scale ( Vector2i id ) const

返回与给定 id 关联的点的权重比例。


bool is_dirty ( ) const

表示网格参数发生改变,需要调用 update


bool is_in_bounds ( int x, int y ) const

如果 xy 是有效的网格坐标(ID),即如果它位于 region 内部,则返回 true。相当于 region.has_point(Vector2i(x, y))


bool is_in_boundsv ( Vector2i id ) const

如果 id 向量是有效的网格坐标,即如果它位于 region 内部,则返回 true。相当于 region.has_point(id)


bool is_point_solid ( Vector2i id ) const

如果寻路时会禁用某个点,则返回 true。默认情况下,所有点均处于启用状态。


void set_point_solid ( Vector2i id, bool solid=true )

禁用或启用指定的寻路点。用于制造障碍物。默认情况下,启用所有点。

注意:调用该函数后不需要调用 update


void set_point_weight_scale ( Vector2i id, float weight_scale )

为具有给定 id 的点设置 weight_scale。在确定从相邻点到该点穿越路段的总成本时,weight_scale 要乘以 _compute_cost 的结果。

注意:调用该函数后不需要调用 update


void update ( )

根据参数更新网格的内部状态,以准备搜索路径。如果更改了 regioncell_sizeoffset 等参数就需要调用它。如果是这种情况,则 is_dirty 将返回 true,需要调用此方法。

注意:会清空所有点的数据(坚固以及权重比例)。

Previous Next


© 版权所有 2014-present Juan Linietsky, Ariel Manzur and the Godot community (CC BY 3.0). Revision b1c660f7.

Built with Sphinx using a theme provided by Read the Docs.