Maize

About

A screenshot of a right follower on a DFS maze.

Maize is a maze generation and simulation program designed with Carl Ellis to illustrate concepts surrounding agent and model based AI to computer science undergrads. The basic premise is that one generates or loads a maze, and some custom bots, and then runs them against the clock (or against one other) to see which is best across various types of maze.

The program supports arbitrary sizes and types of maze, and comes bundled with a reasonable selection that will fox most simple solvers. It also comes with some trivial deterministic and nondeterminstic bots, heavily documented, along with some "stateful" and "stateless" examples to show how a world model can be constructed within the agent.

Features include:

Written in purest Java, it should run on any JDK after 1.6, and has been tested on Windows XP/7/8 and a few modern Linuxes. It comes with the fully documented source, and is released under a GPL license (which we will probably get around to formally bundling one day). Since it compiles and loads bots on the fly, you will need the JDK, not just the JVM.

The current version of the Maize program includes patches submitted by medavox, John Vidler, Ben Sherratt and tr00st. Many thanks for their contributions.

Download

Archives can be downloaded from the git summary page in various useful formats.

A presentation is also available giving a short introduction to mazes and AI. It comes bundled in the zip above, or is available separately in one page per slide and two slides with notes formats.

Using Maize

There are two main ways to use Maize: you can either run mazes and bots using the UI (runUI.bat or runUI.sh), or you can get to developing bots.

The JavaDoc is here. A guide to writing bots is available too!

Running Bots

To run a bot, start the UI by running runUI.sh or runUI.bat. You'll need to create or load a maze using the Maze menu item, and create or load at least one bot using the Bot menu item. It's possible to dynamically load bots and mazes from disk either in serialised format (to keep their state) or from source by compiling.

Switching to the Manage Bots tab will allow you to browse and inspect bots. Here you can see a unique identifer (in case they have nondeterminsitic initialisation values), a name, and a brief description for each of the bots.

To run a test, select the Run Tests tab. Highlight one or more bots from the lower-left list, and one maze from the right-han list and click New Test. This will create a new test, assign icons to your bots and set you up for a run. Click Start to start the test. Bots will turn green when they reach the end, and the list will show how many moves they take.

Developing new Bots

The bot API is fully documented in the release, so I won't dwell on it here. Each time tick, a method (nextMove()) is called in your bot (that must subclass Bot) which returns a single instruction to turn or move in a given direction. This re-entrant nature means people are free to write all the model and state management they see fit.

Also included is a stateful bot which may be subclassed to provide a slightly richer interface to those writing bots. This bot remembers only a few simple navigational hints, such as its direction, but comes with a higher level API built on this platform.

Developing new Maze Generators

When the Maize program loads up its generators it will look inside the maize package for all classes that implement the MazeFactory interface. So to create a maze generator of your own, you need to implement:

 
/** This method is implemented to create the maze data and return it encapsulated in a Maze instance.
  *  
  * @param    width       Width of the maze.
  * @param    height      Width of the maze.
  *
  * @return               Maze instance
  */
public Maze getMaze(int width, int height);

A maze object is pretty simple, it is essentially a boolean array of where the walls are and some data regarding measurements and entrance/exit points. The constructor looks like this:

 
/** Constructor to be used by MazeFactory only.
  * Encapsulates the maze data into an easy to use class.
  *
  * @param  data      Maze data
  * @param  width     Maze width
  * @param  height    Maze height
  * @param  entX      Entrance X coord
  * @param  entY      Entrance Y coord
  * @param  exiX      Exit X coord
  * @param  exiY      Exit Y coord
  */
public Maze(boolean[][] data, int width, int height, int entX, int entY, int exiX, int exiY);

So to summarise the maze building process, your maze generator has to implement a method which builds up a boolean map of a maze given a desired width and height. This can be done using a standard, or custom, algorithm (check out the example factories for the standard algorithms). Once you have your boolean array, choose a start and end point, then create your maze object.This will then get passed to the main UI to be tested against the mighty maze solving DaveBot. He'll solve anything. Eventually.