The algorithm is as follows:
- Pick a random point on a filled grid and mark it empty.
- Choose a random cardinal direction (N, E, S, W).
- Move in that direction, and mark it empty unless it already was.
- Repeat steps 2-3, until you have emptied as many grids as desired.
The Drunkard Walk guarantees connectivity from the first grid picked, and you can also guarantee that a set percentage of the grid has been carved out. Unless the grid is large, you should bias the direction chosen towards the centre of the grid as the drunkard walk may end up butting up against the edges unnaturally. You may also choose to bias the drunkard walk to choose the last direction it travelled to create longer corridors.