0

int maze[][]私の迷路は、を含む2次元のint配列0,1,START(2),GOAL(3)です。最短経路を印刷したい。

関数がありますが、最短パスではなく、最後まで1つのパスが表示されます。

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;
}
4

2 に答える 2

4

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
于 2013-01-26T16:36:30.017 に答える
0

迷路がグリッドであり、壁がアクセスできないグリッド スペースとしてマークされていると仮定すると、A* ジャンプ ポイント検索が現在、この検索スペースに最適な最速のアルゴリズムです。

于 2013-01-26T16:46:12.997 に答える