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......###...###.........###...

这是我的代码(Odin):

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}
...

我究竟做错了什么? 请问一个直接的答案,因为我已经为此工作了几天。 我做错了什么,我需要进行哪些更改才能使其正常工作?

如果需要,我可以共享该算法正在执行的每个步骤的转储,但是它很大。 谢谢你们

好了,我通过小装饰弄清楚了! 我需要检查值是否已经在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......###///###/////////###...

转载请注明来自askonline.tech,本文标题:algorithm - A *在重构路径上无限递归


 Top