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