Code the A* algorithm in Python - Python Tutorial

- [Instructor] We're now going to code a python implementation of the a_star algorithm. The basic approach should now be quite familiar from the implementations of depth first search and breadth first search. So this is chapter 803. If we go to a_star.py, there's a little bit of template here, so we've got a comment telling us that the priority queue contains f-values and (i,j) tuples that's row column tuples. We have some imports on line nine, including the priority_queue class that we just wrote. And then on line 13 we have a heuristic, which basically just calculates the Manhattan distance by calculating a difference of the x-coordinates and adding it to the difference of the y-coordinates. And we use the absolute value there in case we end up with a negative value, and we are only interested in the positive value. The tests going from 926 onwards are exactly the same as we had for BFS. In fact, even the maze that we're using line 35 for example, is using the same maze. So let's start coding our algorithm. The initial setup is we have a Priority Queue. I'm going to call pq and it's equal to a Priority Queue. PyCharm has kindly suggested that that's what I want there. And then we put onto our queue, our start position, and we give it a priority of zero. And I just want to spend a minute talking about this line 24, because in the previous video, I said that the f-value for the initial cell should be equivalent to its h-value because the g-value is zero, which means the distance from the start to the start is zero. But the f-value wants to be the sum of the distance from the start to the current cell, plus the heuristic distance. So technically line 24 should have the heuristic distance. However, it would be extra work to calculate that, and it's not actually needed because there's only going to be one item on the queue at this point, therefore it's automatically going to have the highest priority. So for the implementation, zero is fine here. Then we have our predecessors, and that's equal to a dictionary, which has a start and none as it's only key value pair. And then we have g_values, which is equal to a dictionary containing start, which has a g_value of zero. So that's the initial setup. And then the main part of the algorithm, very similar to what we've done so far. We have a while loop. While not pq. is empty, then we get our current cell, which is equal to pq.get and we say if our current cell, is equal to our goal, then we're done. So at that point we return. And we want to return the path. So return and get path for the predecessors and the start and the goal. Now start and goal they're on line 31 are the same arguments as were passed in on line 22. However, if we've not found the destination, then we have to go through the direction. So for direction in, and then we have a list of directions so that's up, right, down and left. For each of those directions, we get an offset. So row_offset, and col_offset are equal to offset. Now offsets is in our helper file, offsets for this direction. Then we find our neighbor, so that is n-e-i-g-h-b-o-u-r, in England anyway, is equal to current_cell zero. So that's the i position of the row plus the row offset. So that's the first coordinate there is the, i of the current plus the offset. And then the second coordinator is going to be current_cell one, that's the j coordinate plus the col_offset. And so that's the coordinates of the neighboring cell. Then if is legal pos, so if it's a legal position within the current maze, for that neighbour, and also if the neighbour is not in the g_values. Now what that means is it's undiscovered. Okay. So try and relate this back to the grid tracer app that we've looked at. So you only put onto the queue sales, which have not yet been put onto the queue. Otherwise it would be very inefficient. So if it's not in the g_values, that means it's undiscovered. So at that point, we can say the new_cost, is equal to the g_values, the current_cell, or the g_value of the current_cell plus one. Now the reason we can be sure that it's plus one is because in our particular representation of these mazes, we have cells connected by edges and the weight of each edge is just a one. So we're not dealing with a weighted graph here. So we can guarantee that the new_cost is just going to be one more than the previous cost. Then g_values, for this neighbour. Now remember we're going to do this for all of the neighbours that are applicable in all four directions. So g_values for this particular neighbour is equal to the new_cost. So putting it in g_values and in predecessors are both equivalent to saying we've discovered this. So we'll put it into predecessors in a minute as well. But let's do the f_value. Now the f_value is equal to the new_cost plus the heuristic. This is where the magic happens, ready? The heuristic of goal and neighbour. And then we can do pq. put. So we then add it onto our queue. Finally, now that we've got our f_values, we put the neighbor and the f_value here. And then we also have to update our predecessors. I've used a hyphen instead of an underscore there. Have to update our predecessors. So the predecessor for that neighbor, is equal to the current_cell. And then finally, if none of that worked, so we haven't managed to find a destination, then at that point we return none. And I'm just going to get rid of a couple of plain lines and also make sure there's nothing else that's badly formatted. And we're good to go. So let's test it. Even though it looks like absolutely nothing happened, remember that's how assertions work. So on line 50, I asserted that the result of running that algorithm within this empty maze, is going to be this path here, that is, 0,0, 0,1, 0,2, 1,2, 2,2 I then asserted that within this maze on line 53, the path would be 0,0, 1,0, 1,1, 1,2, 2,2 and it didn't throw an error, so the algorithm came up with that correct result. And likewise for the test three, starting on line 61, this goal was unreachable because it was off outside of the dimensions of our maze, so it returned none as expected. So there we have it. The a_star algorithm implemented in Python for a amaze represented inside a TD list.