Как мне найти кратчайший путь в лабиринте?

Мой лабиринт представляет собой массив с двумя измерениями, 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;
}

0

Решение

Я бы порекомендовал Поиск алгоритм.

ПСЕВДОКОД:

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
4

Другие решения

Если мы предполагаем, что ваш лабиринт является сеткой, а стены помечены как недоступные пространства сетки, то поиск точек перехода A * в настоящее время является самым быстрым оптимальным алгоритмом для этого пространства поиска.

0

По вопросам рекламы [email protected]