Python a-Maze-ing Challenge

You have a choice of two maze types:

1. Rectangular
   • The maze is an M x N rectangular grid.
   • The robot may move North, South, East, or West. No diagonal moves are allowed.
2. Hexagonal
   • The maze is a regular hexagonal grid.
   • The robot may move in one of six directions.

For each of the maze types, there are the following rules:

1. Each cell is either a wall or free.
2. One free cell is the start.
3. One free cell is the goal.
4. The robot may only occupy a free cell.

You can implement one of the following solving methods:

1. Wavefront Planner
   • Breadth-first search approach
   • Start at the goal
   • Advance one square in every direction and mark with a 1.
   • From each 1, advance to every open square and mark with a 2
   • From each \(n-1\) square advance to every open square and mark with an \(n\)
   • Stop when there are no more squares to explore
   • From any starting point, move to the adjacent cell with the lowest number
   • Stop at the goal
   • This finds the shortest path to a given goal from every starting point, but it requires full knowledge of the maze
2. Recursive Backtracking
   • Depth-first search approach
   • Start at the start
   • For each neighboring cell, find a path to the goal
   • When finding a path to the goal:
     • If you are at the goal, return true, you are done
     • If you are at a wall, return false, this is not the path
     • Otherwise find a path from each neighboring cell
   • Mark each cell when exploring it as part of the path
   • Unmark each cell when you've searched all its neighbors without finding the goal
   • Does not find the shortest path, but it will find a path if it exists

   • Does not require full knowledge of the maze (because exploration starts at the start, the robot could physically follow each step in the search).

     

3. Belief State Planner
   • The maze and the goal are known, but the robot does not know where it is in the maze.
   • When commanded to move in a direction, the robot will either:
     1. Move to the next cell, if it is free
     2. Stay in the current cell if the next cell is occupied.
   • The purpose of the planner is to develop a sequence of moves that will cause the robot to reach the goal no matter where it started
   • At first, the robot considers itself to be at any position
     • With each move to a different neighbor, some positions are ruled out (i.e., if you move EAST, the WEST-most cells that have a free cell to their EAST will all be unoccupied)

1. Manual
   • Make a maze by hand
   • The input format of the maze should be easy to type
   • Establish this type of maze generation first

2. Randomized Prim's Algorithm There are two commonly used maze representations:

   1. A cell is either free or blocked (what we are using)
   2. Each cell has associated walls and passages (e.g. North can be either free or blocked). This representation is used by the description linked above.

   The pseudocode below uses our representation

   All cells are walls.
   Randomly choose a cell Q and mark it as free.
   Add cell Q's neighbors to the wall list.
   While the wall list is not empty:
       Randomly choose a wall W from the wall list
       If wall W is adjacent to exactly one free cell
          Let F be the free cell that wall W is adjacent to
          W is to a direction DIR (either North, South, East, or West) of F.
          Let A be the cell to the direction DIR of W
          Make W free
          Make A free
          Add the walls of A to the wall list
       Remove W from the wall list
   

3. When Prim's algorithm is successful you should achieve a "perfect" maze, that is a Maze without any loops or any inaccessible areas.

• Print the state of the maze to the terminal.
• The display should include the walls, free cells, start position, goal position, and robot position
• Each time the maze changes, you can just print a new one to the screen
• You should have a mode to display some debugging output (such as whether an algorithm has marked a cell).
• You should be able to draw a path through the maze

• Track the state of the maze and determine if a grid square is a wall, free, the goal, the start
• Be able to find the 1-hop and 2-hop neighbors of a cell
• Other state may need to be tracked depending on the algorithm (such as marking cells as visited)

• Implement one of the maze solving algorithms
• The display should be able to print your solution

• Although it may seem counterintuitive, I recommend starting with a manual maze, then working through some other issues before trying a maze generation algorithm.
• Determine a format for saving and loading a maze, so that custom mazes can be designed
• Implement the randomized Prim's maze generation algorithm

• Allow a maze to be loaded from a file
• Allow a user to specify the start and end positions
• Interactive mode for a user to manually control a robot in the maze