大家好！我的A*算法一直有问题。它能够到达终点并解决迷宫，但当重建路径时，它最终会在几个点之间无限地绕一圈。我已经花了几天时间在这上面了，所以这可能只是一个愚蠢的错误，我看不见。
解释得很快：网格是一个二维数组，分布在一个维度上(Odin没有nD数组(，它表示一个点是否被阻塞，Point是int x和y的结构，0值只是暂时的，所以我可以看到值本身，而不是天文数字。路径的重建正在另一个函数中进行，如果需要，可以共享相应的代码。然而，我相信问题就在其中。
这是我使用的网格(这个网格从1开始，但实际的网格从0开始(：
1 2 3 4 5 6 7 8 9 10
............###...............
1.S..........###...............
............###...............
...#########......#########...
2...#########......#########...
...#########......#########...
...###...###...###...###......
3...###...###...###...###......
...###...###...###...###......
.........###...###...###...###
4.........###...###...###...###
.........###...###...###...###
...###...###...###............
5...###...###...###............
...###...###...###............
...............###......###...
6...............###......###...
...............###......###...
###.........###......######...
7###.........###......######...
###.........###......######...
############...###.........###
8############...###.........###
############...###.........###
......###.........###...###...
9......###.........###...###...
......###.........###...###...
###.........###...###.........
1###.........###...###.........
0###.........###...###.........
......###...###.........###...
1......###.F.###.........###...
1......###...###.........###...
这是我的代码(奥丁(：
astar :: proc(grid: []bool,
sizex, sizey: int,
start, end: Point) -> map[u64]Point {
// Initialize the "point_score_priority" priority queue
point_score_priority := Priority_Queue(Point, f64) {make([dynamic]Point),
make([dynamic]f64),
0};
push(&point_score_priority, start, 0 - heuristic(start, end));
came_from := make(map[u64]Point);
costs := make(map[u64]f64);
costs[hash_point(start)] = 0;
// Loop until point_score_priority is exhausted or we've reached the end
for {
if (point_score_priority.size == 0) {
break;
}
curr, curr_cost := pop(&point_score_priority);
if (curr.x == end.x && curr.y == end.y) {
return came_from;
}
for next in neighbors(curr, sizex, sizey) {
// If not the beginning and not blocked, proceed with heuristic
if (!grid[next.y * u32(sizex) + next.x]) {
overall_cost := curr_cost - heuristic(curr, next);
curr_g := costs[hash_point(curr)];
previous_cost, ok := costs[hash_point(next)];
previous_cost = ok ? previous_cost : 0;
if (overall_cost <= previous_cost && !is_equal(came_from[hash_point(curr)], next) && !is_equal(curr, next)) {
// Make the bigger heuristic values smaller for priority
costs[hash_point(next)] = overall_cost;
came_from[hash_point(next)] = curr;
push(&point_score_priority, next, previous_cost - heuristic(next, end));
}
}
}
}
return nil;
}
以下是辅助功能：
heuristic :: proc(curr, end: Point) -> f64 {
return math.sqrt(math.pow(cast(f64)(curr.x > end.x ? curr.x - end.x : end.x - curr.x), 2) +
math.pow(cast(f64)(curr.y > end.y ? curr.y - end.y : end.y - curr.y), 2));
}
neighbors :: proc(p: Point,
sizex, sizey: int) -> [4]Point {
return {Point{(p.x > 0 ? p.x - 1 : 0), p.y}, // Left (lower check)
Point{p.x, (p.y > 0 ? p.y - 1 : 0)}, // Up (lower check)
Point{(p.x < cast(u32)sizex - 1 ? p.x + 1 : cast(u32)sizex - 1), p.y}, // Right (upper check)
Point{p.x, (p.y < cast(u32)sizey - 1 ? p.y + 1 : cast(u32)sizey - 1)}}; // Down (upper check)
}
is_equal :: proc(curr, next: Point) -> bool {
return curr.x == next.x && curr.y == next.y;
}
// Created by Tetralux. Thanks, Tetra!
hash_point :: proc(p: Point) -> u64 {
hi := u64(p.x);
lo := u64(p.y);
k := (hi << 32) | lo;
return k;
}
以下是它试图重新创建路径的输出：
Printing point: Point{x = 3, y = 9}
Printing point: Point{x = 3, y = 8}
Printing point: Point{x = 4, y = 8}
Printing point: Point{x = 5, y = 8}
Printing point: Point{x = 5, y = 9}
Printing point: Point{x = 5, y = 10}
Printing point: Point{x = 6, y = 10}
Printing point: Point{x = 7, y = 10}
Printing point: Point{x = 7, y = 9}
Printing point: Point{x = 7, y = 8}
Printing point: Point{x = 7, y = 7}
Printing point: Point{x = 6, y = 7}
Printing point: Point{x = 6, y = 6}
Printing point: Point{x = 6, y = 5}
Printing point: Point{x = 6, y = 4}
Printing point: Point{x = 7, y = 4}
Printing point: Point{x = 8, y = 4}
Printing point: Point{x = 8, y = 3}
Printing point: Point{x = 8, y = 2}
Printing point: Point{x = 9, y = 2}
Printing point: Point{x = 9, y = 1}
Printing point: Point{x = 9, y = 0}
Printing point: Point{x = 8, y = 0}
Printing point: Point{x = 7, y = 0}
Printing point: Point{x = 6, y = 0}
Printing point: Point{x = 5, y = 0}
Printing point: Point{x = 5, y = 1}
Printing point: Point{x = 4, y = 1}
Printing point: Point{x = 4, y = 2}
Printing point: Point{x = 4, y = 3}
Printing point: Point{x = 4, y = 4}
Printing point: Point{x = 4, y = 5}
Printing point: Point{x = 3, y = 5}
Printing point: Point{x = 2, y = 5}
Printing point: Point{x = 2, y = 6}
Printing point: Point{x = 3, y = 6}
Printing point: Point{x = 3, y = 5}
Printing point: Point{x = 2, y = 5}
Printing point: Point{x = 2, y = 6}
Printing point: Point{x = 3, y = 6}
Printing point: Point{x = 3, y = 5}
Printing point: Point{x = 2, y = 5}
Printing point: Point{x = 2, y = 6}
Printing point: Point{x = 3, y = 6}
Printing point: Point{x = 3, y = 5}
Printing point: Point{x = 2, y = 5}
Printing point: Point{x = 2, y = 6}
Printing point: Point{x = 3, y = 6}
Printing point: Point{x = 3, y = 5}
...
我做错了什么？我想要一个直截了当的答案，因为我已经做了好几天了。我做错了什么？我需要改变什么才能让它发挥作用？
如果需要，我可以共享算法执行的每个步骤的转储，但它相当大。非常感谢你们。
好吧，多亏了trincot，我终于弄明白了！我需要检查该值是否已经在came_from中。这是我的最新版本：
astar :: proc(grid: []bool,
sizex, sizey: int,
start, end: Point) -> map[u64]Point {
// Initialize the "point_score_priority" priority queue
point_score_priority := Priority_Queue(Point, f64) {make([dynamic]Point),
make([dynamic]f64),
0};
push(&point_score_priority, start, 0 - heuristic(start, end));
came_from := make(map[u64]Point);
costs := make(map[u64]f64);
costs[hash_point(start)] = 0;
// Loop until point_score_priority is exhausted or we've reached the end
for {
if (point_score_priority.size == 0) {
break;
}
curr, curr_cost := pop(&point_score_priority);
if (curr.x == end.x && curr.y == end.y) {
return came_from;
}
for next in neighbors(curr, sizex, sizey) {
// If not the beginning and not blocked, proceed with heuristic
if (!grid[next.y * u32(sizex) + next.x]) {
overall_cost := curr_cost - heuristic(curr, next);
curr_g := costs[hash_point(curr)];
previous_cost, ok := costs[hash_point(next)];
previous_cost = ok ? previous_cost : 0;
if (overall_cost <= previous_cost && !is_equal(came_from[hash_point(curr)], next) && !is_equal(curr, next)) {
// Make the bigger heuristic values smaller for priority
costs[hash_point(next)] = overall_cost;
if (!(hash_point(next) in came_from)) {
came_from[hash_point(next)] = curr;
}
push(&point_score_priority, next, previous_cost - heuristic(next, end));
}
}
}
}
return nil;
}
注意新的检查：(它工作得很好！谢谢你，特林科特：(
1 2 3 4 5 6 7 8 9 10
///.........###///////////////
1/S/.........###///////////////
///.........###///////////////
///#########//////#########///
2///#########//////#########///
///#########//////#########///
///###...###///###...###//////
3///###...###///###...###//////
///###...###///###...###//////
///......###///###...###///###
4///......###///###...###///###
///......###///###...###///###
///###...###///###...//////...
5///###...###///###...//////...
///###...###///###...//////...
///////////////###//////###...
6///////////////###//////###...
///////////////###//////###...
###.........###...///######...
7###.........###...///######...
###.........###...///######...
############...###//////...###
8############...###//////...###
############...###//////...###
......###/////////###///###...
9......###/////////###///###...
......###/////////###///###...
###......///###///###///......
1###......///###///###///......
0###......///###///###///......
......###///###/////////###...
1......###/F/###/////////###...
1......###///###/////////###...