algorithm - A* 在路径重建上无限递归
问题描述
每个人！我的 A* 算法一直有问题。它能够走到尽头并解决迷宫，但在重建路径时，它最终会在几个点之间无限循环。我已经在这上面花了几天时间，所以这可能只是一个我看不到的愚蠢错误。
解释非常快：网格是一个二维数组，分布在一维上（Odin 没有 nD 数组），表示一个点是否被阻塞，Point 是一个整数 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......###///###/////////###...
推荐阅读
- php - WooCommerce 根据购买的产品 ID 和数量删除运输方式
- python - 标准化特征以计算方差膨胀因子
- docker - 用于网站的单个 Nginx Docker 与多个 Nginx Docker
- azure-managed-app - 如何使用新的包版本更新现有的 Azure 托管应用程序？
- javascript - 如何使用 vanilla JavaScript 在列表中获取 span 的值？
- java - 将文件保存在谷歌驱动器上
- android - 从 expo 客户端构建应用程序 apk 时获取“keystore.keyAlias”不允许为空错误
- python - 确定一个列表中的元素是否小于另一个列表中的元素
- javascript - Is there a way to copy validation from one input to another with JavaScript?
- .htaccess - 如何对主域强制执行 https 连接，同时对子域强制执行 http？