Общие принципы таковы: карта - это клетчатый прямоугольник, каждая клетка которого обладает некоторым состоянием. Все крайние клетки находятся в специальном состоянии "edge", которое не может быть изменено. Одна случайно выбранная некрайняя клетка находится в состоянии "floor", а все остальные - в состоянии "chaos".
Далее на каждом шаге происходит примерно следующее: клетка, находящаяся в состоянии "chaos", у которой хотя бы одна из соседних клеток находится в состоянии "floor", с некоторыми вероятностями может перейти либо в "floor", либо в "wall". Если у клетки есть соседи в состоянии "wall", переход в состояние "wall" более вероятен. Процесс продолжается, пока нам не надоест на некотором шаге состояния всех клеток не окажутся теми же, что и на предыдущем.
Даже такие простые правила (а в дальнейшем мы их несколько усложним) приводят к генерации достаточно интересного лабиринта. Его связность гарантирована (пол может появиться только рядом с полом), и он отличается определённой оригинальностью. Впрочем, нет гарантий, что лабиринт заполнит достаточное пространство - процесс может остановиться довольно скоро. В следующих версиях мы будем с этим бороться.
Посмотреть, как это работает, можно здесь: http://sirion.ho.ua/cell_maze/230813.html