Gridworld Mazes

posted by: Ms. Martin 29 March 2011 No Comment

Maze solving is a fun way to explore some deep ideas in computer science from recursion to graph theory.  The Gridworld infrastructure makes visualizing maze solving algorithms fairly straightforward — let’s take advantage of it!

You have some freedom in how you want to approach this.  Generating mazes is interesting and you may want to start there.  One way to generate mazes is to start with a maze in which all of the possible walls exist, then continue removing walls until all cells are reachable from the starting point by some path. The algorithm:

  • Mark the current cell as “visited.”
  • If the current cell has any adjacent cells that have not yet been visited…
    • Choose one of the unvisited adjacent cells at random. Randomness is important here, or your algorithm will always generate the same maze.
    • Remove the wall between the current cell and the cell you just chose.
    • Recursively call the algorithm, with the chosen cell becoming the current cell.

If you prefer, you can also read in existing mazes such as this one from a file.

Solving mazes can be done very similarly to the generation algorithm above.  There are several ways to approach it but the one most similar to the maze creation algorithm uses recursive backtracking, a broadly useful strategy.

Similar to recursive backtracking is an iterative strategy that uses an explicit Stack (rather than the call stack) to save next steps to explore.  Breadth-first search can be implemented similarly using a Queue and leads us to a shortest path.

I recommend creating a Maze class that keeps track of a maze structure separately from GridWorld.  I wrote mine to keep track of a two dimensional array of an Enum called Cell that consists of possible cell states: wall, visited, start, goal, open.  You could just use chars.  You will create a new type of World (MazeWorld) that generates a grid of the right size by looking at the Maze it is built on.

I created a Cell abstract class and subclasses Wall, Visited, Goal to populate my world.  I just gave the three subtypes different colors; you could use fancy images.  Read about displaying classes differently here.

One potential source of weird issues is that methods like getValidAdjacentLocations return up to 8 locations including diagonals.  Make sure you only look at the 4 cardinal directions.

1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 4.00 out of 5)
Loading ... Loading ...

Leave a comment

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>