<-- Back to the main page

GridWorld version of maze solver

Screenshot of GridWorld solution (click for full-size) I don't teach in a high school, but I'm aware how large the case study looms in an AP class; I haven't rewritten the handout materials but I did put together a sort of proof-of-concept solution to my CS2 assignment using GridWorld as the underlying framework instead of AWT and applets and 2D arrays, and removing the enumerated types. I also simplified it to assume a queue-based agenda, removing another layer of complexity from the problem. As such, I'd say it now sits somewhat earlier, difficulty-wise, although still on the AB (CS2) end of things: you could do this assignment pretty much as soon as they've seen either a queue or a stack.

With respect to the CS2 version of the project, the three preliminary assignments are modified as follows. Agenda simply goes away; reading from a file into a 2D array is mostly the same, except you're reading into a Grid; and instead of making a Square enum, you'll need some other representation (I used an abstract Square class with concrete subclasses Wall, Finish, Explored, and so on). In the main project, you then skip straight to the "The maze solver" portion.

Above is a sample screenshot of a my implementation, with the maze solution in progress. (Click it for a full-size version.) Here the start point is in the lower-left, and the grey circles represent a square that has been explored. The target marks the finish.

A few implementation notes

If you want to read in mazes from files, and have the size of the maze declared in the file (as in the CS2 version of the assignment), you have a slight problem: to inherit from BoundedGrid, you need to know at the start of construction (when super(...) is called) what the bounds are. In my implementation, I inherited from UnboundedGrid instead, but that's a little icky. Alternatives include requiring all mazes to have the same dimensions, or requiring the dimensions to be specified on the command line in addition to or instead of in the file. Also not optimal.

Because the World GUI provides a pre-determined set of buttons, the interface has to be simpler than the CS2 version gives. In particular, there's no easy way to input a filename here, which is why I put it on the command line. Also, there's no easy way inside the GUI to swap a stack for a queue, so that'll require a recompile (or you could do it as a command-line option).

There are many ways to implement Square or its equivalent. I define Square as an abstract type with concrete subclasses Wall, Finish, and so on, which lets me make use of GridWorld's ability to automatically take a GIF (it should be PNG! Boo!) of the same name as the class as its icon.


This page is too easily googlable, so I don't want to post it here, but I'm happy to email the solution to any CS teacher. Just email me at dblaheta@knox.edu. Preferably, email from your school email account, and if possible include a link to some official school website that includes your name on faculty/staff (so I can verify that this is on the up-and-up).