A maze is a grid of locations used to test pathfinding. Each cell is empty or blocked; a search starts at one location and tries to reach a goal. A randomly generated maze replaces some empty cells with walls according to a sparseness setting, but a path is not guaranteed. section 2.2
func successorsForMaze(_ maze: Maze) -> (MazeLocation) -> [MazeLocation] {
func successors(ml: MazeLocation) -> [MazeLocation] { //no diagonals
var newMLs: [MazeLocation] = [MazeLocation]()
if (ml.row + 1 < maze.count) && (maze[ml.row + 1][ml.col] != .Blocked) {
newMLs.append(MazeLocation(row: ml.row + 1, col: ml.col))
}
if (ml.row - 1 >= 0) && (maze[ml.row - 1][ml.col] != .Blocked) {
newMLs.append(MazeLocation(row: ml.row - 1, col: ml.col))
}
if (ml.col + 1 < maze[0].count) && (maze[ml.row][ml.col + 1] != .Blocked) {
newMLs.append(MazeLocation(row: ml.row, col: ml.col + 1))
}
if (ml.col - 1 >= 0) && (maze[ml.row][ml.col - 1] != .Blocked) {
newMLs.append(MazeLocation(row: ml.row, col: ml.col - 1))
}
return newMLs
}
return successors
}
The successor function turns the grid into a search problem: from a location, it returns unblocked neighbors one step up, down, left, or right, without crossing the grid boundary. section 2.2
A location stores its row and column and is hashable so search algorithms can track visited places. Depth-first search follows a path until it must backtrack; breadth-first search explores nearer locations first. A* can use Manhattan distance to guide movement toward the goal. Once a search finds the goal, parent links reconstruct the path for marking on the printed maze. section 2.2
Try a small maze
Generate a 10-by-10 grid with sparseness 0.2. Search from (0, 0) to (9, 9); if a solution exists, mark its route with P, its start with S, and its goal with G. section 2.2
