[Dip52]

Глобальная проблема, так это в том, что ячейки могут добавиться так, что вокруг будет уже занято, как квадрат.

Думаю, что для решения этой проблемы, потребуется знание количества добавляемых ячеек, которые и создают "случайную дорогу", потом какое-нибудь ограничение, например, 10, если есть свободных 10 ячеек, то добавляем в случайную сторону продолжение дороги, а если с какой-то стороны не будет, то в определённую сторону.