Доброго времени суток. Работаем над генератором карт для tile-based игры. Интересуют алгоритмы генерации пятен (озер) случайной формы. Собственно в общем случае интересует генерация многоугольников (причем они могут быть невыпуклыми и иметь нестандартные пропорции).

Если не очень быстрый алгоритм устроит, то я бы сделал так.

На первом этапе создаем пятно с некрасивыми краями.

1) Наносим случайным образом точку на карте. Это зародыш пятна.
2) Обходим пятно по периметру случайным образом добавляя точки.
3) Возврящаемся к п.2 случайное число раз.

На этом этапе важно правильно задать вероятности и критерий выхода из цикла. Можно, например, задать функцию уменьшения вероятности добавления новой точки по мере увеличения счетчика цикла и выходить из цикла если за проход не добавлено ни одной точки. Чем быстрее убывает такая вероятность - тем меньше получится озеро.

Далее - сглаживаем края. Это можно сделать стандартным алгоритмом увеличения-уменьшения пятна. Сначала увеличиваем полученное пятно на N пикселей. Потом уменьшаем на то же число. Края при такой процедуре всегда сглаживаются. Чем больше N, тем глаже результат. Остнова в озере такие операции тоже убирают, если острова не очень большие. К сожалению я не помню названия этих операций увеличения-уменьшения. А книжка нужная на работе. А на работу я попаду в лучшем случае на той неделе.

А натыкать рандомно точек и обойти по ним, исключая некоторые (слишком крутые изгибы) ? Не?

Создается по N точкам правильный многоугольник, затем в нем выбирается пара вершин, которые соединяются прямой, отсекая фигуру. Если выбирать не слишком далекие друг от друга вершины - можно добиться нормальных результатов.
Ну естественно без сглаживания никак

Посмотрите на тему активатор-ингибитор (Meinhardt-Gierer, Тьюринг).
Например: How the Leopard Gets Its Spots