Lay the Groundwork

00:00 Lay the Groundwork for the Project.

00:04 The first step to writing any code starts on paper, so you’ll now take a step back to figure out the problem that you are solving and how you’re going to approach it.

00:13 The first step is to narrow down the design requirements of the maze.

00:19 Mazes come in different shapes and forms, but you’ll concentrate on one kind that you’d find in a typical maze-puzzle video game from the early 1980s, such as Boulder Dash or Sokoban.

00:32 The maze seen on-screen was inspired by the classic Pac-Man game. This maze is enclosed in a rectangle comprising a grid of square cells that form passages along straight lines. Therefore, parts in the maze will only be vertical or horizontal rather than diagonal or circular, and each cell will be one unit wide.

00:51 This will become important for calculating and comparing the distances later.

00:57 Note that you can give your maze any shape by surrounding it with empty squares marked as exterior to form an open space. However, you might want to align the maze’s edges with the enclosing rectangle to save some memory.

01:11 An additional restriction that you’ll impose on your maze is that it must have exactly one entrance and one exit, both of which should occupy distinct cells.

01:22 A few alternative paths can connect them, including paths with cycles that lead back to a place you’ve already visited. Solving the maze means finding a path leading from the entrance to the exit.

01:35 Each solution should include acyclic paths. In other words, a single path location should only be traversed once without backtracking. You also want to consider only the shortest paths while disregarding less optimal, meandering ones. However, defining the shortest distance is subject to interpretation, as you’ll find out in part two. In part two, you’ll also introduce enemies and rewards to the maze so that your hypothetical player can collect extra points and avoid obstacles.

02:05 But how do you actually find the way out of the maze? Mazes are a perfect example of graph theory in action. As it turns out, you can represent your maze with an undirected graph consisting of nodes and edges connecting them.

02:19 Each node or vertex is where two or more paths intersect, while edges are the connections between those intersections. Apart from the nodes representing the intersections and dead ends in the maze, there are a few extra nodes in the graph seen on-screen that capture the presence of enemies and rewards.

02:37 By associating numeric weights with edges that pass through them, you can influence the cost of the given connection. Later, you’ll add nodes for corners to make plotting the path from the entrance to the exit a little bit easier.

02:51 It’s worth noting that you can draw the same graph in different ways without changing its underlying structure. For example, you could draw all edges as straight lines, let them cross each other, or arrange the nodes in a certain pattern.

03:07 Mathematically, a graph is nothing more than a set of nodes and edges, which you can lay out in any order and locations that you want. This means that transforming the maze into a graph is an irreversible process resulting in losing some information about its visual features.

03:24 At the same time, a graph is a remarkably convenient representation for finding the shortest path in the maze. Finding the shortest path belongs in the second part of this course, but you won’t be implementing any of the graph traversal algorithms seen on-screen for finding it. Instead, you’ll be using the NetworkX library, which already implements these and more algorithms, to do the work for you.

03:49 Now that you’ve clarified the problem at hand, you can start thinking about how to approach it from a technical perspective. It’s time to lay the groundwork for some Python code, and that’s what you’ll be doing in the next section of the course.