Single Fork Dataset Generator

[aaron-sandoval]

It would be useful to be able to easily generate datasets with a single fork (3-armed hallway -< ). The starting and ending positions would be constrained to lie at the ends of different arms.

[aaron-sandoval]

Possible quick and dirty algorithm:

1. Generate hallway maze
2. Delete one random entry in the adjacency list between c1 and c2 with the following constraints

• Neither c1 nor c2 may be a corner cell
• Both c1 and c2 must have at least one other neighbor which is not one of the hallway terminal cells.
• The order of c1 and c2 is arbitrary

3. Add an entry in the adjaceny list between c2 and some neighboring cell c3 with which no direct connection currently exists.
4. The resulting maze has a single fork with 3 terminal cells:

• The 2 original hallway terminal cells
• c1

Discussion

• This algorithm will fail for 3x3 mazes where one hallway terminal cell is in the center
• Seems like it should be pretty robust for 4x4 and larger mazes
• The simplicity is due to the restrictions in step 2 introducing some bias in the distribution to avoid corner terminal cells
  • If this bias is problematic, then I also have idea for a less biased but more complex algorithm