Transform the Maze Into a Graph

00:01 Transform the Maze into a Graph. To create a graph, you’ll need to provide nodes and edges that connect them. You’ve already established that your maze consists of nodes that represent path intersections, dead ends, and special squares, such as enemies or the entrance.

00:17 However, if you connect them directly without taking the corners into account, then you won’t be able to follow the maze’s horizontal and vertical pathways.

00:26 The image on the left depicts six color-coded nodes, including two intersections in blue, two dead ends in red, as well as the entrance and the exit in green.

00:37 The image on the right is almost the same, but it adds four corners in yellow, which allow you to preserve the maze’s layout. Your Border model can already identify a .corner, an .intersection, and a .dead_end, while the Role model will tell you whether the associated square has some special function in the maze.

00:59 You can treat the square as a synonym for a graph node because NetworkX lets you use any object as a node, as long as it’s hashable. The Square class is hashable out of the box because it was implemented as an immutable, frozen data class. To use consistent terminology, you’ll define a type alias for the Square class so that you can refer to it as a Node in your code. Once you’ve done this, you’ll model the edge as a pair of two nodes, which you can implement as a named tuple.

01:48 It’s possible to represent edges of directed graphs with this class because it’s an ordered pair. But for now, you’ll only consider undirected graphs with two-way connections between their nodes.

02:03 Now that you have a representation for nodes and edges, you can start transforming your maze into a graph by first getting a collection of nodes from it. The simple way would be to turn all squares into nodes.

02:15 However, capturing only intersections, corners, and dead ends as nodes can lead to a more efficient and accurate solution for solving mazes. You can identify these nodes by checking the role and border pattern of each square in the maze. If

02:59 a square is marked as either a wall or exterior, then it’s definitely not part of the graph, so you skip it with a continue statement. Otherwise, if the square has some special role other than None, then you record it as a graph node.

03:18 Finally, regardless of the square’s role, you take note of intersections, dead ends, and corners.

03:34 Thanks to using a Python set, you don’t have to worry about adding the same square more than once when, for example, a reward happens to be placed at an intersection.

03:43 That’s because sets filter out duplicates. Next, you’ll need to connect your nodes with edges. To do that, you’ll take advantage of the fact that the maze is a rectangular grid.

03:56 That means you can loop through the nodes you just identified, checking to the right and down for any adjacent nodes in the maze and stopping once you reach a wall.

04:07 You look for the immediate neighbors of each node supplied to the function. In this case, you will move east and south in the maze, but you could just as well follow the opposite directions, remembering to change the loop indexing and wall detection accordingly.

04:53 First, you check to the east. You use the bitwise AND operator (&) to check if a border around the current square has a right side, indicating a wall that terminates the search in that direction.

05:07 If it does, then you break out of the loop. On the other hand, if you find a square located in the same row as your source node is also present in the set of nodes, and there’s no wall between them, then you create an Edge instance. You

05:29 then perform a similar check, but looking south, checking for bottom walls and checking for nodes in the same column, adding an edge as before.

06:08 Knowing the edges is sufficient to define a new NetworkX graph object.

06:31 The initializer method of nx.Graph can optionally take various graph data types, including a collection of edges. Normally, you should create an instance of nx.MultiGraph to account for parallel edges that might appear in one of your mazes. However, the extra corners that you added before make each parallel connection unique, so there’s no need to use a multigraph in this case.

06:58 In the next section, you’ll use NetworkX to find the shortest path from the entrance to the exit of the maze.