Maze Generation Algorithms - Little Rat

Understanding how the maze generator creates levels can help you predict its decisions, and prune off large time-wasting areas of the maze while playing the game.

Overall, the maze generator starts at the center of the maze (the goal, also called the origin) and randomly picks directions to create paths. When it runs into itself, and has no other paths to pick, it backtracks. Where it backtracks to is dependent on the maze’s parameters:

• Oldest: Backtracks to the earliest cell it visited.
• Newest: Backtracks to the latest cell it visited.
• Random: Backtracks to a random cell.

This results in what is known as a “perfect maze”. The maze has no loops and no inaccessible sections. Between any two points on the maze there is only one solution.

However, a perfect maze is not usually very exciting. This is because it can be solved easily with basic algorithms. You may have heard of “following the left wall” (or the right wall?). Due to this, the maze must be made imperfect.

A loop is when two cells have two different paths between them, allowing you to run in a circle without backtracking. This is achieved in the generator by punching holes in the perfect maze. It is not a flawless solution as its effectiveness is down to RNG, but it does throw the simplistic approaches to solving the maze into question.

Details of these processes can be found in these flowcharts: