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

Форум библиотеки BeaRLib

Модератор: Apromix

Аватара пользователя
Jesus05
Сообщения: 1840
Зарегистрирован: 02 дек 2009, 07:50
Откуда: Норильск, сейчас Санкт-петербург.
Контактная информация:

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

Сообщение Jesus05 » 08 фев 2016, 19:34

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

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

Аватара пользователя
kipar
Сообщения: 2120
Зарегистрирован: 10 мар 2010, 13:16
Откуда: Москва

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

Сообщение kipar » 08 фев 2016, 20:07

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

Аватара пользователя
Максим Кич
Администратор
Сообщения: 1642
Зарегистрирован: 03 дек 2006, 20:17
Откуда: Витебск, Беларусь
Контактная информация:

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

Сообщение Максим Кич » 08 фев 2016, 22:22

Я, честно говоря, вообще не понимаю, зачем в начале избыточно генерить комнаты, если нам, для триангуляции, по сути, нужен случайный набор разрозненных точек. А комнаты подходящего размера можно и потом к вершинам графа прилепить.
Dump the screen? [y/n]

Аватара пользователя
Jesus05
Сообщения: 1840
Зарегистрирован: 02 дек 2009, 07:50
Откуда: Норильск, сейчас Санкт-петербург.
Контактная информация:

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

Сообщение Jesus05 » 08 фев 2016, 22:30

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

Аватара пользователя
kipar
Сообщения: 2120
Зарегистрирован: 10 мар 2010, 13:16
Откуда: Москва

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

Сообщение kipar » 09 фев 2016, 05:47

Комнаты генерить чтобы гарантировать что точки будут достаточно далеко друг от друга.
----
Свой деланау не взлетел, поэтому я не стал разбираться и взял готовый отсюда http://paulbourke.net/papers/triangulate/
Untitled.png
Untitled.png (60 КБ) 5095 просмотров
Осталось остовное дерево и прочие шаги, ну и расталкивать наверное можно покрасивее - я решил обойтись без плавающих координат, в результате при расталкивании они иногда расталкиваются с зазором в один пиксель.

Аватара пользователя
Харука-тян
Мастер
Сообщения: 544
Зарегистрирован: 29 ноя 2006, 00:23
Контактная информация:

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

Сообщение Харука-тян » 09 фев 2016, 12:38

kipar писал(а):Свой деланау не взлетел, поэтому я не стал разбираться и взял готовый отсюда http://paulbourke.net/papers/triangulate/
Насколько я знаю, никто не делал свою триангуляцию Делоне при написании генератора по данному алгоритму, для всех языков есть готовые решения.
"Женщина верит, что дважды два будет пять, если хорошенько поплакать и устроить скандал" (© Дж. Элиот).
ИзображениеИзображение

Аватара пользователя
kipar
Сообщения: 2120
Зарегистрирован: 10 мар 2010, 13:16
Откуда: Москва

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

Сообщение kipar » 09 фев 2016, 12:49

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

Аватара пользователя
kipar
Сообщения: 2120
Зарегистрирован: 10 мар 2010, 13:16
Откуда: Москва

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

Сообщение kipar » 09 фев 2016, 22:10

В общем, демка готова.
В архиве ехе и исходники. Для красивой картинки можно убрать галочки с links и rooms, ну и жать Do All. Код ужасный, поэтому больше интересуют пожелания по самому алгоритму.
rel1.0.zip
(297.11 КБ) 144 скачивания
В длл оформлю завтра. Ну и чуть-чуть доработаю расталкивание, вдруг с вещественными координатами оно будет красивее работать.
Untitled.png
Untitled.png (47.9 КБ) 5081 просмотр
По-моему, основная проблемы:
- нестабильное число больших комнат. Может получится три, может 15. Из-за этого подземелье будет либо одним коридором либо огромной сетью. В настоящей диабле, очевидно, все не так, да и в обычных рогаликах для этого используют BSP или подобные методики.
Ну и пара мелких:
- большие комнаты могут оказаться впритык друг к другу, тогда получается двойная дверь да и вообще не очень красиво. Возможно, надо эти ребра удалять из триангуляции. Правда тогда комната может оказать изолированной.
- если использовать только минимальное дерево, все красиво, ну почти всегда. Но нет циклов. Когда добавляем случайные ребра - они могут образовывать кашу (большинство из них не создает большого "цикла", а просто добавляет к двум ребрам дерева третье образуя маленький треугольник). Возможно, надо добавлять их по каким-то правилам. А, да, я по рандому добавляю лишние ребра, возможно фиксированное число будет смотреться лучше.

Аватара пользователя
Максим Кич
Администратор
Сообщения: 1642
Зарегистрирован: 03 дек 2006, 20:17
Откуда: Витебск, Беларусь
Контактная информация:

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

Сообщение Максим Кич » 10 фев 2016, 06:06

Комнаты генерить чтобы гарантировать что точки будут достаточно далеко друг от друга.
Ну, это как бы здорово, но дальше:
большие комнаты могут оказаться впритык друг к другу
То есть алгоритм сам по себе этого не гарантирует. (мелькнула мысль «прикрутить box2d — «засыпать» окружностями разного радиуса — взять центры за вершины графа», но это порождение не до конца проснувшегося разума).
Dump the screen? [y/n]

Аватара пользователя
Jesus05
Сообщения: 1840
Зарегистрирован: 02 дек 2009, 07:50
Откуда: Норильск, сейчас Санкт-петербург.
Контактная информация:

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

Сообщение Jesus05 » 10 фев 2016, 06:19

Максим Кич писал(а):
большие комнаты могут оказаться впритык друг к другу
То есть алгоритм сам по себе этого не гарантирует. (мелькнула мысль «прикрутить box2d — «засыпать» окружностями разного радиуса — взять центры за вершины графа», но это порождение не до конца проснувшегося разума).
В гифке которая в описании алгоритма тоже часть больших комнат впритык друг к другу, но там больших комнат просто больше думаю поэтому он смотриться лучше, ну или как обычно :) для демонстрации взяли "красивую" генерацию, но как и любой другой алгоритм иногда получаются "не красивые" генерации.

Аватара пользователя
kipar
Сообщения: 2120
Зарегистрирован: 10 мар 2010, 13:16
Откуда: Москва

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

Сообщение kipar » 10 фев 2016, 08:25

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

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

Аватара пользователя
Харука-тян
Мастер
Сообщения: 544
Зарегистрирован: 29 ноя 2006, 00:23
Контактная информация:

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

Сообщение Харука-тян » 10 фев 2016, 10:15

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

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

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.
Осталось поправить критерий оценки больших комнат и будет очень круто. В Лазарусе у меня криво портировалось построение корридоров, поэтому скриншот без них.
Вложения
tinykeep.png
tinykeep.png (36.99 КБ) 5061 просмотр
"Женщина верит, что дважды два будет пять, если хорошенько поплакать и устроить скандал" (© Дж. Элиот).
ИзображениеИзображение

Аватара пользователя
kipar
Сообщения: 2120
Зарегистрирован: 10 мар 2010, 13:16
Откуда: Москва

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

Сообщение kipar » 10 фев 2016, 11:06

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

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

Аватара пользователя
Харука-тян
Мастер
Сообщения: 544
Зарегистрирован: 29 ноя 2006, 00:23
Контактная информация:

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

Сообщение Харука-тян » 10 фев 2016, 14:33

kipar писал(а):Дома попробую. Хотя с тем же успехом вместо модуля можно сделать RoomSizeMean=0, отрицательные размеры и так отсекутся.
Чтобы распределение было действительно нормальным, необходимо брать RoomSizeMean = 0.0, RoomSizeVariance = 1.0
"Женщина верит, что дважды два будет пять, если хорошенько поплакать и устроить скандал" (© Дж. Элиот).
ИзображениеИзображение

Аватара пользователя
kipar
Сообщения: 2120
Зарегистрирован: 10 мар 2010, 13:16
Откуда: Москва

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

Сообщение kipar » 10 фев 2016, 22:13

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

Ну и упаковал в библиотеку, интерфейс теперь двух типов - с использованием BearLibMap и через коллбеки. Вот новая версия исходников BearLibMG (все старые алгоритмы+ вот этот):
BeaRLibMG.zip
(15.27 КБ) 149 скачиваний
А вот демка, использующая сразу почти все библиотеки BearLib (FOV+Lighting(который пока не библиотека)+Map+MG+Terminal):
AllDemo.zip
(1.1 МБ) 140 скачиваний
Краткий хелп к ней:
- как и в demolighting цифрами гасить источники, нумпадом ходить.
- F1 - загрузить карту из map.txt
- F2 - перебирать алгоритмы из BearLibMG
- F3 - сразу последний алгоритм (NiceDungeon)
- F4 - выключить FOV чтобы увидеть всю карту.
Что пока не сделано:
- с размером 80*40 подземелье не такое уж крутое, надо сделать в демке прокрутку.
- интегрировано все "на соплях" - источники света никак с картой не связаны, из-за освещения все тайлы одинакового цвета, да и вообще в mapgen алгоритмы переплетены и прибиты к номерам тайлов, в общем еще пилить и пилить.
- как минимум для этого алгоритма надо дать возможность пользователю настраивать параметры на входе, ну и на выходе кроме массива тайлов возвращать граф связей и координаты комнат.
Untitled.png
Untitled.png (48.38 КБ) 5031 просмотр
Ну и на всякий случай исправленная предыдущая демка с графом и настройкой параметров.
rel1.1.zip
(297.33 КБ) 148 скачиваний
Последний раз редактировалось kipar 11 фев 2016, 07:04, всего редактировалось 1 раз.

Ответить

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и 13 гостей