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.
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
.intersection, and a
.dead_end, while the
Role model will tell you whether the associated square has some special function in the maze.
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
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.
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.
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.
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
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.
Become a Member to join the conversation.