A * бесконечно повторяющийся на реконструкции пути

Question

все! У меня была проблема с моим алгоритмом A *. Он способен дойти до конца и решить лабиринт, но при реконструкции пути он в конечном итоге бесконечно идет по кругу между несколькими точками. Я потратил несколько дней на это, поэтому это может быть просто глупая ошибка, которую я не могу увидеть.

Объяснение очень быстрое: сетка представляет собой двумерный массив, растянутый по одному измерению (У него нет массивов 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}
...

Чтоя делаю не так? Я хотел бы получить прямой ответ, пожалуйста, так как я работал над этим в течение нескольких дней. Что я сделал не так и что мне нужно изменить, чтобы заставить его работать?

При необходимости я могу поделиться дампом каждого отдельного шага, который делает алгоритм, но он довольно большой. Большое спасибо, ребята.

Answer 1

Хорошо, мне удалось выяснить это благодаря 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;
}

Обратите внимание на новую проверку :) Она отлично работает! Спасибо, Trincot:)

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