Generating Random Mazes
A variety of random mazes can be constructed using RRTs. For the
example shown below, four possible inputs (directions of motion) are
allowed (up, down, left right). The initial state is in the center of
a square region. Each RRT edge has length 1, and the square has
dimensions 20x20. Excluding the boundary, the walls are simply
connected (i.e. no loops are formed by walls). The resulting maze is
also simply connected (removing the boundary).
If the edge length is reduced to 0.5, as opposed to 1, a
finer-resolution maze is obtained, such as the one shown below.
By changing the set of inputs, a maze that is not rectilinear can be
obtained. The maze below was obtained by using only three inputs,
which generate motions in the 0, 120, and 240-degree directions.
Return to RRT Gallery page
Return to main RRT page
Web page maintained by Steve LaValle