BeaRLibMG - генератор карт

[Jesus05]

Да, Деланау и потом остовное дерево выглядит самыми мозголомным моментами. С другой стороны, это же генерация лабиринта, комнат будет немного, можно не гнаться за оптимальностью алгоритмов.
Попробую запилить.

Правда результат каким-то очень специфичным выглядит, слишком много комнат и мало коридоров. Для диаблоподобного рогалика нормально, для более традиционных - не очень.
Конечно, можно просто не включать синие комнаты, но тогда по-моему суть потеряется, красные комнаты можно было бы накидать и без расталкивания в стороны.

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

[kipar]

Куда передвигать? Дальше (начиная с триангуляции) они вроде не двигаются, только удаляются.

[Максим Кич]

Я, честно говоря, вообще не понимаю, зачем в начале избыточно генерить комнаты, если нам, для триангуляции, по сути, нужен случайный набор разрозненных точек. А комнаты подходящего размера можно и потом к вершинам графа прилепить.

[Jesus05]

Куда передвигать? Дальше (начиная с триангуляции) они вроде не двигаются, только удаляются.

виноват. мне показалось что на последнем шаге мелкие комнаты еще раз передвигаются.

[kipar]

Комнаты генерить чтобы гарантировать что точки будут достаточно далеко друг от друга.
----
Свой деланау не взлетел, поэтому я не стал разбираться и взял готовый отсюда http://paulbourke.net/papers/triangulate/

Untitled.png (60 КБ) 5057 просмотров

Осталось остовное дерево и прочие шаги, ну и расталкивать наверное можно покрасивее - я решил обойтись без плавающих координат, в результате при расталкивании они иногда расталкиваются с зазором в один пиксель.

[Харука-тян]

Свой деланау не взлетел, поэтому я не стал разбираться и взял готовый отсюда http://paulbourke.net/papers/triangulate/

Насколько я знаю, никто не делал свою триангуляцию Делоне при написании генератора по данному алгоритму, для всех языков есть готовые решения.

[kipar]

Ну, я как-то привык что для паскаля может и не оказаться реализации с открытыми исходниками, а вместо нее у каждого свой велосипед.
Ну и да, реализаторы из комментов к статьям тоже еще те ребята - один, питонист, вообще Делоне не осилил, честно сказал что его программа иногда генерит несвязанные острова. Второй, луашник, к первой части творчески подошел, физдвижок задействовал.

[kipar]

В общем, демка готова.
В архиве ехе и исходники. Для красивой картинки можно убрать галочки с links и rooms, ну и жать Do All. Код ужасный, поэтому больше интересуют пожелания по самому алгоритму.

rel1.0.zip

(297.11 КБ) 141 скачивание

В длл оформлю завтра. Ну и чуть-чуть доработаю расталкивание, вдруг с вещественными координатами оно будет красивее работать.

Untitled.png (47.9 КБ) 5043 просмотра

По-моему, основная проблемы:
- нестабильное число больших комнат. Может получится три, может 15. Из-за этого подземелье будет либо одним коридором либо огромной сетью. В настоящей диабле, очевидно, все не так, да и в обычных рогаликах для этого используют BSP или подобные методики.
Ну и пара мелких:
- большие комнаты могут оказаться впритык друг к другу, тогда получается двойная дверь да и вообще не очень красиво. Возможно, надо эти ребра удалять из триангуляции. Правда тогда комната может оказать изолированной.
- если использовать только минимальное дерево, все красиво, ну почти всегда. Но нет циклов. Когда добавляем случайные ребра - они могут образовывать кашу (большинство из них не создает большого "цикла", а просто добавляет к двум ребрам дерева третье образуя маленький треугольник). Возможно, надо добавлять их по каким-то правилам. А, да, я по рандому добавляю лишние ребра, возможно фиксированное число будет смотреться лучше.

[Максим Кич]

Комнаты генерить чтобы гарантировать что точки будут достаточно далеко друг от друга.

Ну, это как бы здорово, но дальше:

большие комнаты могут оказаться впритык друг к другу

То есть алгоритм сам по себе этого не гарантирует. (мелькнула мысль «прикрутить box2d — «засыпать» окружностями разного радиуса — взять центры за вершины графа», но это порождение не до конца проснувшегося разума).

[Jesus05]

большие комнаты могут оказаться впритык друг к другу

То есть алгоритм сам по себе этого не гарантирует. (мелькнула мысль «прикрутить box2d — «засыпать» окружностями разного радиуса — взять центры за вершины графа», но это порождение не до конца проснувшегося разума).

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

[kipar]

То есть алгоритм сам по себе этого не гарантирует. (мелькнула мысль «прикрутить box2d — «засыпать» окружностями разного радиуса — взять центры за вершины графа», но это порождение не до конца проснувшегося разума).

Он гарантирует что они не будут пересекаться. В принципе можно расталкивать не комнаты как сейчас, а круги или даже прямоугольники, просто большего размера. Но тогда придется отказаться от синих комнат, т.к. их тоже вытолкнет.

В оригинале статьи есть ссылка на онлайн-генератор: http://tinykeep.com/dungen/
Там результаты все-таки более-менее ровные, и да, комнат больше.
В общем, можно с параметрами поиграться. Например если RoomSizeMean сделать=0.05 то комнат станет намного больше, а если еще PickRatio=0.5, то получается довольно похоже на статью.
В общем, добавил еще один параметр (соотношение сторон)

Проблема еще что в статье дверей нет. Сейчас я рисую дверь когда коридор пересекается со стеной красной комнаты, но возможна ситуация когда коридор пройдет строго по стене посторонней комнаты и тогда она вся превратится в линию дверей. Можно конечно игнорировать посторонние комнаты, но тогда будут коридоры уходящие в стену. Видимо надо просто для каждого коридора делать не больше одной двери в комнату.

[Харука-тян]

Подумай над этим куском (так лучше работает):

Код: Выделить всё

function normalize( a, b, c : Double ) : Double;
begin
  Result := ( a - b) / ( c - b);
end;

function Clampf( a, b, c : Double ) : Double;
begin
  Result := Max( a, b );
  Result := Min( Result, c);
end;

procedure TDungeon.GenerateRooms;
var
  I: Integer;
  rx,ry,rw,rh, t,u,r: Single;

begin
  for I := 0 to NRooms - 1 do
  begin
    t := 2*Pi*Random;
    u := Random+Random;
    if u > 1 then
      r := 2-u
    else
      r := u;
    rX := MapX*Params.InitialRadius*r*cos(t) + MapX/2;
    ry := MapY*Params.InitialRadius*r*sin(t) + MapY/2;

    repeat
      rh := Round( Clampf( normalize( Abs(RandG(0.0, 1.0)), 0, 3 ), 0, 1 ) * 9 ) + 2; //min_room_size = 2, max_room_size = 11, STANDARD_NORMAL_CAP = 3
    until (rh > 3) and (ry+rh < MapY-1);
    repeat
      rw := Round( Clampf( normalize( Abs(RandG(0.0, 1.0)), 0, 3 ), 0, 1 ) * 9 ) + 2;
    until (rw > 3) and (rx+rw < MapX-1) and (rw/rh < 1.8) and (rh/rw < 1.8); // w/h ratio = 1.8

    Rooms[I].X := Round(rx);
    Rooms[I].Y := Round(ry);
    Rooms[I].H := Round(rw);
    Rooms[I].W := Round(rh);
    Rooms[I].RoomType := SmallRoom;
  end;
end;

Что изменилось : разброс размеров комнат пропорционален разбросу модуля нормального случайного числа в диапазоне 0-3.
Осталось поправить критерий оценки больших комнат и будет очень круто. В Лазарусе у меня криво портировалось построение корридоров, поэтому скриншот без них.

[kipar]

Хм, да, модуль я не догадался попробовать, с ним маленьких комнат будет больше, ну и слишком большие отсекать.
Дома попробую. Хотя с тем же успехом вместо модуля можно сделать RoomSizeMean=0, отрицательные размеры и так отсекутся. В любом случае твоя версия выглядит лучше и даже свободное место по углам есть.

А с критерием что? Он вроде такой же как и во всех источниках, задается с помощью PickRatio.
Если ты имеешь в виду что надо просто выражать его, как и остальные параметры в клетках то согласен. К размеру карты не было никакого смысла привязываться.
Ну и можно вместо этого просто брать Н самых больших комнат, но тогда боюсь получится слишком предсказуемое подземелье.

[Харука-тян]

Дома попробую. Хотя с тем же успехом вместо модуля можно сделать RoomSizeMean=0, отрицательные размеры и так отсекутся.

Чтобы распределение было действительно нормальным, необходимо брать RoomSizeMean = 0.0, RoomSizeVariance = 1.0

[kipar]

Мда, обнаружилась еще одна проблема. Если больших комнат мало (порядка 4-5), то иногда разбиение деланау косячит и оставляет одну из комнат несоединенной. Возможно из-за того что три точки оказываются на одной прямой, но при большом числе комнат я не встретил такого ни разу.
После этого программа падает при построении минимального дерева. Надо будет какой-нибудь костыль на этот случай приделать.

Ну и упаковал в библиотеку, интерфейс теперь двух типов - с использованием BearLibMap и через коллбеки. Вот новая версия исходников BearLibMG (все старые алгоритмы+ вот этот):

BeaRLibMG.zip

(15.27 КБ) 148 скачиваний

А вот демка, использующая сразу почти все библиотеки BearLib (FOV+Lighting(который пока не библиотека)+Map+MG+Terminal):

AllDemo.zip

(1.1 МБ) 137 скачиваний

Краткий хелп к ней:
- как и в demolighting цифрами гасить источники, нумпадом ходить.
- F1 - загрузить карту из map.txt
- F2 - перебирать алгоритмы из BearLibMG
- F3 - сразу последний алгоритм (NiceDungeon)
- F4 - выключить FOV чтобы увидеть всю карту.
Что пока не сделано:
- с размером 80*40 подземелье не такое уж крутое, надо сделать в демке прокрутку.
- интегрировано все "на соплях" - источники света никак с картой не связаны, из-за освещения все тайлы одинакового цвета, да и вообще в mapgen алгоритмы переплетены и прибиты к номерам тайлов, в общем еще пилить и пилить.
- как минимум для этого алгоритма надо дать возможность пользователю настраивать параметры на входе, ну и на выходе кроме массива тайлов возвращать граф связей и координаты комнат.

Untitled.png (48.38 КБ) 4993 просмотра

Ну и на всякий случай исправленная предыдущая демка с графом и настройкой параметров.

rel1.1.zip

(297.33 КБ) 144 скачивания