c++ A* pathfinding/BFS algorithm

[Neon92]

Hi all,

I am confused how it is able to loop through and find all its neighbor and get the optimized path to the goal

 

[davidktw]

Hi all,

I am confused how it is able to loop through and find all its neighbor and get the optimized path to the goal

It's the heuristic function that helps to compute a possible optimised path. It is not necessarily the most optimised, but often close enough, depending on how good your heuristic function is.

http://www.raywenderlich.com/4946/introduction-to-a-pathfinding

 

[Neon92]

in terms of code how does it get its neighbor?

 

[davidktw]

in terms of code how does it get its neighbor?

Lets me see if this is what you understand.

Assuming we are talking about a map that is divided into a 2D array. Then when you start off at Point (X, Y), your neighbours are P(X-1,Y-1), P(X-1,Y), P(X-1,Y+1), ...., P(X+1,Y+1), a total of 8 neighbours unless some are walls, or boundaries of your map, or already visited.

The idea is you want to find a neighbour that you believe will get you the optimal path to the destination.

Reading the wikipedia algorithm, you will be assessing for each node in the openset, starting from the one with the lowest cost (actual + heuristic), meaning the most potential candidate. The search will be in a way similar to breadth first search(BFS), except it is a more targeted search with the guidance of the cost function, instead of just going uniformly expanding the search layer by layer.

 

[Neon92]

I dont know whether this thinking is correct

So i need to loop to find its neighbor

[x-1][y-1] [x][y-1] [x+1][y-1]
[x-1][y] [x+1][y]
[x-1][y+1] [x][y+1] [x+1][y+1]

(assuming i dont hit a null object)
if there is obstacle i just take out that square

then take the target minus each of those coordinates to find the H of each square

After that add G + H to find F with G++

if that square F is less than other F, i move to that square

And then i will repeat to the desired path?

 

[davidktw]

I dont know whether this thinking is correct

So i need to loop to find its neighbor

[x-1][y-1] [x][y-1] [x+1][y-1]
[x-1][y] [x+1][y]
[x-1][y+1] [x][y+1] [x+1][y+1]

(assuming i dont hit a null object)
if there is obstacle i just take out that square

then take the target minus each of those coordinates to find the H of each square

After that add G + H to find F with G++

if that square F is less than other F, i move to that square

And then i will repeat to the desired path?

For all position candidates, you have to insert into a min heap.

Look at the pseudo code below, observe those in RED, see how possible candidates for traversing is always inserted into "openset". Then read the line in BLUE, see that you need to take out the node with the minimum "F" cost. This is a good indication that "openset" is a min heap using the "F" as the weigh function. You don't move to any square YET even if you know it has a lower "F" than what you have discovered so far. Because your F is a combination of a heuristic function, as you traverse further and further away, it cost can add up to INFINITELY HIGH to indicate a BLOCK. You add all your neighbouring candidates into the "openset", then you select the best you have discovered so far, with the least "F" cost, and you keep exploring.

Read the pseudocode.

function A*(start,goal)
    ClosedSet := {}    	  // The set of nodes already evaluated.
    [COLOR="Red"]OpenSet := {start}[/COLOR]    // 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 := map with default value of Infinity
    g_score[start] := 0    // Cost from start along best known path.
    // Estimated total cost from start to goal through y.
    f_score := map with default value of Infinity
    f_score[start] := heuristic_cost_estimate(start, goal)

    [COLOR="red"]while OpenSet is not empty[/COLOR]
        [COLOR="Blue"]current := the node in OpenSet having the lowest f_score[] value[/COLOR]
        if current = goal
            return reconstruct_path(Came_From, goal)

        OpenSet.Remove(current)
        ClosedSet.Add(current)
        for each neighbor of current
            if neighbor in ClosedSet
                continue		// Ignore the neighbor which is already evaluated.
            tentative_g_score := g_score[current] + dist_between(current,neighbor) // length of this path.
            if neighbor not in OpenSet	// Discover a new node
                [COLOR="red"]OpenSet.Add(neighbor)[/COLOR]
            else if tentative_g_score >= g_score[neighbor]
                continue		// This is not a better path.

            // This path is the best until now. Record it!
            Came_From[neighbor] := current
            g_score[neighbor] := tentative_g_score
            f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)

    return failure

function reconstruct_path(Came_From,current)
    total_path := [current]
    while current in Came_From.Keys:
        current := Came_From[current]
        total_path.append(current)
    return total_path

 

[Neon92]

so if there is a wall or blockage, it is calculated at the neighbor?

if neighbor in ClosedSet
continue

Can i create an array of the desired path?

 

[davidktw]

so if there is a wall or blockage, it is calculated at the neighbor?

if neighbor in ClosedSet
continue

Can i create an array of the desired path?

That is how can decide to write your COST function. You can either do not include it into the openset, or you can insert it in and let the COST function assign a ridiculously high COST which makes it never a desirable solution. Imagine a map with 9x9=81 squares, if I assign any blockage candidate with a cost of 100, do you think there will actually be any possible routes sensible on a map with only 81 squares ? You can also double use the "ClosedSet" for not only visited nodes, but also nodes that are impossible to traverse, its work the same since the ClosedSet is just a container to identify nodes that are no longer a viable part of a route or already part of a route.

You mean tracking the path ? Yes of course, that's what the "Came_From" data structure is storing right ? It store for all neighbour nodes, where is the next best path to the next node.

 

[Neon92]

thanks for the info