Maze generation is a fascinating topic. There are many ways to generate mazes and each one of them generates mazes with its own unique properties. In this blog post, I look some of the ways in which we can generate mazes. Before we can get into any of these algorithms, we must first figure out how our maze is modeled and stored inside our program. Modelling the maze To get started, we can think of our maze a n by n grid of cells where a cell contains information about its index in the grid. Note: The cell can also contain references to its neighbors. This is helpful when you want to solve the maze using state space search algorithms like Depth First Search, Breadth First Search, etc. Next, we need to be able to store which cells are connected, i.e., which cells do not have a wall separating them. For this we use what is known as an adjacency matrix. The adjacency matrix is a m by m grid where m is the number of cells in our maze = n 2 . In the matrix the value at row i and column j
State space search is a process which is used to create simple artificial intelligence. It can be used when the problem can be represented as a set of simple states and the player / agent is the only one who can affect the environment. It allows us to generate a path from the initial state to the goal state (of which there can be many depending on the problem). 8-Puzzle / Sliding Puzzle , N-queens and Route Finding are some of the various problems which can be solved using state space search. Let us explore the process of solving the 8-Puzzle problem using various path finding algorithms and comparing how effective each of them is. To get started, we need to start by creating the 8-Puzzle game itself. First, we need a simple way to represent different states of the puzzle. A good way to do this is to store the state as a string. For example: Next up, we need a way to generate the actions that are possible from a particular state. We can think of it as moving the empty space itself