How can we find a way through a maze fast and efficiently?

Let's make a fast summary. The algorithm:

- walks through the foundation layout in a random way
- at each step it decides if the wall that separates cells can be removed

```
walk_layout( x, y )
{
if ( visited( x, y ) ) return;
create_random_permutation( p )_of_a_set_0_3
call_with_the_sequence_determined_by_p
{
walk_layout( x-1, y );
walk_layout( x+1, y );
walk_layout( x, y-1 );
walk_layout( x, y+1 );
}
}
```

This, alas, will not work for big foundations because the stack is limited. In practice, with C# I failed
to create a 64x64 maze because I got an obvious exception "Stack overflow".
I solved this problem with iterative version of this algorithm. It required to implement a stack that would be used while walking to store the current position and a value saying which directions had been already tried.

For example, if we are in cell (4, 5) and we walk to cell (4, 6) then we push to stack (4, 5, directions | direction.E).

If we reach a cell and we see that all directions were already checked, we just pop the state from the stack and try different ways for this state.

In practice this is not so simple to check if there is already a path between two cells. Naive implementation would analyze whole maze generated to this moment!

I've decided to use a version of an algorithm said to be by Robert E. Tarjan. I found a paper about it but it still looked quite messy and unnecessary complicated. I've decided to simplify it.

This is the idea: in addidional table (called

- the number -1 - means that the cell is a tail of a chain of connected cells
- positive number - means a pointer, a number of next cell in a chain you have to refer

[0] : -1 [1] : 0 [2] : 1 ...To compute the

```
int base_cell( int tIndex )
{
int index = tIndex;
while ( maze_base[ index ] >= 0 )
{
index = maze_base[ index ];
}
return index;
}
```

Then if we would like to check if two cells C1 i C2 are conencted we just compute thier base cells.
If base cells are equal then C1 and C2 are in the same chain.
This is because two separated chains can be merged together to form a new chain. We do this
by changing the base pointer of one chain:
```
void merge( int index1, int index2 )
{
// merge both lists
int base1 = base_cell( index1 );
int base2 = base_cell( index2 );
maze_base[ base2 ] = base1;
}
```

For example two separated chains
[0] : -1 [1] : 0 [2] : 1 and [3] : -1 [4] : 3 [5] : 4will be merged as:

[0] : -1 [1] : 0 [2] : 1 [3] : 0 [4] : 3 [5] : 4Notice that base_cell() for each cell in this chain is equal to 0 and this means that all cells are in one chain.

There are a lot of tricky algorithms for path finding in mazes. I will present one of the most reliable but quite memory demanding (it requires a temporary table as big as the maze)

The algorithm is quite simple. I will provide an example:

In that temporary tablie (let's call it-1 | -1 | -1 | -1 |

-1 | -1 | -1 | -1 |

-1 | -1 | -1 | -1 |

-1 | -1 | -1 | -1 |

We start by putting the value of 0 into the source point.

0 | -1 | -1 | -1 |

-1 | -1 | -1 | -1 |

-1 | -1 | -1 | -1 |

-1 | -1 | -1 | -1 |

Then we do an *i*-step until we reach the destination point:

- all points that are neighbours to points filled in previous step
and are not filled yet should be filled with the value of
*i*only if we follow the maze (we are not allowed to go through the walls)

0 | 1 | -1 | -1 |

-1 | -1 | -1 | -1 |

-1 | -1 | -1 | -1 |

-1 | -1 | -1 | -1 |

0 | 1 | -1 | -1 |

-1 | 2 | -1 | -1 |

-1 | -1 | -1 | -1 |

-1 | -1 | -1 | -1 |

0 | 1 | -1 | -1 |

3 | 2 | 3 | -1 |

-1 | 3 | -1 | -1 |

-1 | -1 | -1 | -1 |

...

0 | 1 | -1 | -1 |

3 | 2 | 3 | -1 |

4 | 3 | 8 | -1 |

5 | 6 | 7 | 8 |

At this time the first part of the algorithm is finished. The only thing that we have to do is to build the path. To do it we follow the consecutive numbers from 8 to 0, starting at the destination point and ending at start point. The path is ready.

All the details of the implementation can be found in the source of