У меня провы сейчас генерируются так:
Сначала карта "засевается", каждая провинция состоит из одной ячейки.

Затем пробегаем по карте несколько раз и ячейки, граничащие с провинциями, с определённой вероятностью передают в эти провинции.