为 A* 算法编写启发式函数
Program a heuristic function for A* algorithm
我必须对机器人进行编程以找到到目标位置的最短距离。在一个随机位置包含障碍物的竞技场中（事先不知道）。
问题是，我将得到一个代表网格的数组。在这个网格中，0代表可移动space，1代表障碍物。我必须对其进行编程，以找到到达我选择的目标位置的最短路径，避开所有障碍物（墙壁）。
A* 是解决这个问题的好方法还是有更好的方法？
As @Vesper said in the comments, A* is the way to go. As for the heuristic...
If your robot is restricted to moving left/right and up/down, typically Manhattan (or Taxicab or L1) distance is used as a heuristic function:
h(x,y) = |x - x_goal| + |y - y_goal|
It should be obvious that if there are no obstacles, then moving |x - x_goal| steps right or left, then |y - y_goal| steps up or down (or y, then x) cannot be longer than the actual shortest path to the goal with obstacles, therefore the heuristic is admissible.
If your robot can move on the diagonal, then Manhattan distance is no longer admissible, so you can use the Euclidean (or L2) distance:
h(x,y) = sqrt( (x - x_goal)^2 + (y - y_goal)^2 )
This is the straight-line distance between the two points and will never be any longer than any other possible path.
This makes Euclidean distance not only admissible for diagonal motion (at any angle), it also admissible for the case above where movement is restricted to the x and y directions. But in the case of restricted movement, Manhattan distance will generally give a path length that is closer to the actual path length, and so may speed up your pathfinding, and it's faster to compute.
我必须对机器人进行编程以找到到目标位置的最短距离。在一个随机位置包含障碍物的竞技场中（事先不知道）。
问题是，我将得到一个代表网格的数组。在这个网格中，0代表可移动space，1代表障碍物。我必须对其进行编程，以找到到达我选择的目标位置的最短路径，避开所有障碍物（墙壁）。
A* 是解决这个问题的好方法还是有更好的方法？
As @Vesper said in the comments, A* is the way to go. As for the heuristic...
If your robot is restricted to moving left/right and up/down, typically Manhattan (or Taxicab or L1) distance is used as a heuristic function:
h(x,y) = |x - x_goal| + |y - y_goal|
It should be obvious that if there are no obstacles, then moving |x - x_goal| steps right or left, then |y - y_goal| steps up or down (or y, then x) cannot be longer than the actual shortest path to the goal with obstacles, therefore the heuristic is admissible.
If your robot can move on the diagonal, then Manhattan distance is no longer admissible, so you can use the Euclidean (or L2) distance:
h(x,y) = sqrt( (x - x_goal)^2 + (y - y_goal)^2 )
This is the straight-line distance between the two points and will never be any longer than any other possible path.
This makes Euclidean distance not only admissible for diagonal motion (at any angle), it also admissible for the case above where movement is restricted to the x and y directions. But in the case of restricted movement, Manhattan distance will generally give a path length that is closer to the actual path length, and so may speed up your pathfinding, and it's faster to compute.