altmax писал(а): ↑15 июл 2017, 12:09
4. Ну а теперь находим комнаты и связываем их между собой. Самая ресурсоемкая часть алгоритма. Если делать данж 128х40 с одним усреднением, то получается примерно 30-35 комнат, и чтобы их все связать, уходит 1-2 секунды реального времени - не много, но уже заметно при генерации следующего уровня. Но я связываю первую со второй, потом опять ищу отдельные комнаты, снова связываю первую со второй и так до тех пор, пока не останется одна. А если комнат много, то можно связывать сразу 5-10 пар и потом проверять, так гораздо быстрее будет.
Ну и результат на скринах - 1-4 усреднения (файлы добавились почему-то в обратном порядке, потому наоборот, 4-1 усреднения
)
по поводу соединения комнат - недавно с этой темой воевал. Копаться лень, поэтому сделал "велосипед", на карте 250х250, с порядка 500-700 изолированными комнатами работает относительно шустро, те же секунда-две (не замерял) в дебаг режиме.
До ума алгоритм не довёл, лень (и так работает), но задача решается в лоб:
1 - находим первый попавшийся проход
2 - распространяем волну по проходу, пока можем. При этом в отдельный фронт волны сохраняем пограничные тайлы - те, что видны, но уже не проходимые.
3 - когда идти дальше некуда, переключаемся в режим прохода по стенам,
4- берём пограничную волну и - до первой встречи с "неизведанным" проходом.
5 - соединяем проход с нашим кошерным подземельем, используя волну.
дальше интересней. Сперва у меня был просто вызов этой всей процедуры в цикле, пока оставались свободные комнаты. в мелкой карте работает отлично, но в больших отмороженных картах тормозит. Поэтому дописал основной алгоритм:
6 - из последней точки прохода быстренько пробегаемся по вновь присоединённой "комнате", заполняя её волной - и добавляя в пограничную волну обязательно тоже.
7 - возвращаемся в пункт 4 (примерно)
код есть, если что. (Улучшить алгоритм явно можно, например, избежать шагов 1-3 и переключения режимов прохода, просто начиная с шага 6)