c++ - 如何在迷宫中找到最短路径？

Question

我的迷宫是一个具有二维的 int 数组，int maze[][]包含0,1,START(2),GOAL(3). 我想打印最短路径。

我有一个功能，但它不显示最短路径，而是一条到最后的路径：

bool RenderThread::find_path(int x, int y)
{
    int maze_size=mmaze->size*2;

    if ( x < 0 || x > maze_size  || y < 0 || y > maze_size  ) return FALSE;

    if ( toSolve1->maze_data[y][x] == G ) return TRUE;

    if ( toSolve1->maze_data[y][x] != PATH && toSolve1->maze_data[y][x] != S ) return FALSE;

    toSolve1->setRed(y,x);


    if ( find_path(x, y - 1) == TRUE ) return TRUE;

    if ( find_path(x + 1, y) == TRUE ) return TRUE;

    if ( find_path(x, y + 1) == TRUE ) return TRUE;

    if ( find_path(x - 1, y) == TRUE ) return TRUE;

    toSolve1->setPath(y,x);

    return FALSE;
}

Answer 1

我会推荐A* 搜索算法。

伪代码：

function A*(start,goal)
    closedset := the empty set    // The set of nodes already evaluated.
    openset := {start}    // The set of tentative nodes to be evaluated, initially containing the start node
    came_from := the empty map    // The map of navigated nodes.

    g_score[start] := 0    // Cost from start along best known path.
    // Estimated total cost from start to goal through y.
    f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal)

    while openset is not empty
        current := the node in openset having the lowest f_score[] value
        if current = goal
            return reconstruct_path(came_from, goal)

        remove current from openset
        add current to closedset
        for each neighbor in neighbor_nodes(current)
            if neighbor in closedset
                continue
            tentative_g_score := g_score[current] + dist_between(current,neighbor)

            if neighbor not in openset or tentative_g_score <= g_score[neighbor] 
                came_from[neighbor] := current
                g_score[neighbor] := tentative_g_score
                f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)
                if neighbor not in openset
                    add neighbor to openset

    return failure

function reconstruct_path(came_from, current_node)
    if came_from[current_node] in set
        p := reconstruct_path(came_from, came_from[current_node])
        return (p + current_node)
    else
        return current_node

Answer 2

如果我们假设你的迷宫是一个网格，并且墙壁被标记为不可访问的网格空间，那么 A* Jump Point Search 是目前这个搜索空间最快的最优算法。