Add Weights to Graph Edges
math.dist() function takes two points specified as sequences of coordinates. In this case, you provide tuples of the row and column indices of squares corresponding to the nodes. Note that you could define distance differently—for example, as the sum of absolute values of differences in the horizontal and vertical directions. You can update the function
make_graph() to use the new property.
Now, when you call
solve_all() on the Pac-Man maze, you’ll get two equivalent solutions, which lead you to the exit on the left. Clearly, both paths have the same length, so it shouldn’t matter which one you choose. However, notice that the upper path contains three extra nodes representing the intersections, including one with a chamber opening in the middle of the maze, while the lower path doesn’t.
02:19 Now you have weights in your graph, you can use other factors besides the distance to influence the algorithm’s decision. For example, you may want to favor paths with fewer enemies or more rewards, and you’ll find out how to do that in the next section of the course.
Become a Member to join the conversation.