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

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

Модератор: Apromix

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

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

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

kipar писал(а):А вот демка, использующая сразу почти все библиотеки BearLib (FOV+Lighting(который пока не библиотека)+Map+MG+Terminal)
А какой смысл разбивать это на 4 библиотеки? Терминал понятно, он и без карты обойтись может, но карту+свет+путь+зрение разве не логичнее упаковать в одну библиотеку?
Что замечено в AllDemo: Нашлась генерация с тремя комнатами. Никакого соединения между ними не произошло.
Комнаты все вытянуты по вертикали, нет вытянутых по горизонтали.
Комнаты часто упираются в край карты.
В rel 1.1 такого нет.
"Женщина верит, что дважды два будет пять, если хорошенько поплакать и устроить скандал" (© Дж. Элиот).
ИзображениеИзображение

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

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

Сообщение kipar » 11 фев 2016, 07:01

Харука-тян писал(а):В rel 1.1 такого нет.
Там надо поставить MapX=80, MapY=40. Хотя большинства проблем там таки нет.
Харука-тян писал(а):Комнаты часто упираются в край карты.
Исправлено.
Харука-тян писал(а):Комнаты все вытянуты по вертикали, нет вытянутых по горизонтали.
Это обман зрения! Просто в терминале клетки не квадратные а вытянуты по вертикали.
Харука-тян писал(а):Нашлась генерация с тремя комнатами. Никакого соединения между ними не произошло.
А с этим да, надо что-то делать - триангуляция иногда не работает, когда комнат мало. В rel1.1 это тоже есть. Причем если нет ни одной связи, то будет такая картина, а если при этом хоть одна связь все-таки будет, то программа упадет на составлении минимального дерева.
Самый простой путь, наверное, сделать "резервную триангуляцию", которая будет искать изолированные комнаты и присоединять их к ближайшим пока граф не станет связным.
Харука-тян писал(а):А какой смысл разбивать это на 4 библиотеки? Терминал понятно, он и без карты обойтись может, но карту+свет+путь+зрение разве не логичнее упаковать в одну библиотеку?
Ну, Apromix так сказал.
Конечно, часто может быть что человеку нужна карта и ее генерация, но не нужно освещение и поиск пути т.к. они у него свои. Или наоборот, нужно освещение и поиск пути, а карту он сам генерирует.
Но мне никогда не мешал подключать libtcod тот факт что больше половины ее возможностей я не использую.
Правда есть еще один довод - поиск пути и генерация карт написаны на паскале, FOV и Map на С++. В теории конечно можно на уровне линкера объединить в один dll, но это развлечение не для слабонервных.

Аватара пользователя
Cfyz
Сообщения: 776
Зарегистрирован: 30 ноя 2006, 10:03
Откуда: Санкт-Петербург
Контактная информация:

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

Сообщение Cfyz » 11 фев 2016, 17:29

kipar писал(а):Конечно, часто может быть что человеку нужна карта и ее генерация, но не нужно освещение и поиск пути т.к. они у него свои. Или наоборот, нужно освещение и поиск пути, а карту он сам генерирует.
Но мне никогда не мешал подключать libtcod тот факт что больше половины ее возможностей я не использую.
Правда есть еще один довод - поиск пути и генерация карт написаны на паскале, FOV и Map на С++. В теории конечно можно на уровне линкера объединить в один dll, но это развлечение не для слабонервных.
Занятно, но у libtcod как раз есть тикет по распиливанию библиотеки.

А вообще определенный резон в словах Харуки есть. Все крутится вокруг сущности "карта уровня", фактически набор методов генерации и обработки карты. Сюда нормально ложится и освещение, и другие гипотетические алгоритмы (например, постобработки типа удвоения толщины стен или проверки на отсутствие недостижимых зон -- вещи, которые могут оказаться полезны и сами по себе). Только вот простого представления карты для некоторых таких хотелок может не хватить =) например тому же освещению для полной автоматизации работы надо знать еще цвет и яркость источников.
Пытается раскуклиться

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

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

Сообщение kipar » 11 фев 2016, 18:02

Cfyz писал(а):Занятно, но у libtcod как раз есть тикет по распиливанию библиотеки.
В тикете как раз речь о
> where the former has generic roguelike features and the latter has the presentation features.
т.е. об отделении терминала от всего остального.

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

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

Сообщение kipar » 02 мар 2016, 23:01

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

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

Ну и наверное надо добавить в библиотеку возврат списка комнат с координатами и связей между ними, а в демке использовать это для расстановки источников света. Тогда и алгоритм генерации BSP можно добавить, который в том же формате будет комнаты возвращать.
Потому что этот результат этого алгоритма мне все-таки не очень нравится. Пробовал по нему еще клеточным автоматом пройтись чтобы коридоры понеровнее сделать, но тогда может связность потеряться.

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

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

Сообщение kipar » 03 мар 2016, 07:25

Вот теперь несоединенные комнаты исправлены.
графическая демо
rel1.2.zip
(299.15 КБ) 171 скачивание
текстовая
AllDemo.zip
(1.1 МБ) 154 скачивания
исходники для dll для текстовой
BeaRLibMG.zip
(16.58 КБ) 167 скачиваний
Как раз 7drl через два дня, осталось к этому генератору и освещению идею придумать.

Аватара пользователя
Cfyz
Сообщения: 776
Зарегистрирован: 30 ноя 2006, 10:03
Откуда: Санкт-Петербург
Контактная информация:

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

Сообщение Cfyz » 03 мар 2016, 11:38

kipar писал(а):Свой деланау не взлетел, поэтому я не стал разбираться и взял готовый отсюда http://paulbourke.net/papers/triangulate/
kipar писал(а):оказалось что используемое разбиение Делоне не работает когда точки находятся на одной прямой
Кажется зря вы с этой триангуляцией мучаетесь. Минимальное остовное дерево (которое можно построить на полносвязном графе исходных вершин) само по себе не будет иметь пересечений.
kipar писал(а):Но нет циклов. Когда добавляем случайные ребра - они могут образовывать кашу (большинство из них не создает большого "цикла", а просто добавляет к двум ребрам дерева третье образуя маленький треугольник). Возможно, надо добавлять их по каким-то правилам.
От построения минимального остовного дерева скорее всего останется сортированный список потенциальных ребер (ребер полносвязного графа). Можно взять из него минимальное ребро, вершины которого в остовном дереве находятся на случайном растоянии N > 2 друг от друга. При этом получаемый цикл будет иметь склонность замкнуть лежащие рядом куски пути, а не соединить края графа по диагонали через весь уровень. Правда, при этом отсутствие самопересечений гарантировать нельзя, так что придется либо проверять и выбрасывать, либо изначально отфильтровать список оставшихся ребер.
Пытается раскуклиться

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

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

Сообщение kipar » 03 мар 2016, 12:26

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

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

1   5--
|   |
|   |
2   |
|   |
3---4--
то алгоритм чаще соединяет 2 с 4 создавая скучный маленький треугольник, чем 1 с 5 создавая нетривиальный маршрут.
Хотя исходя из картинки наверное можно сделать шанс добавления зависящим от текущей длины пути от X к Y - чем больше тем лучше.


А в производительности узкое место в расталкивании комнат. Оно сделано в лоб (каждый такт каждую комнату с каждой) и при 2000 комнат занимает с минуту. Луашник то физдвижок не зря использовал.

Аватара пользователя
Cfyz
Сообщения: 776
Зарегистрирован: 30 ноя 2006, 10:03
Откуда: Санкт-Петербург
Контактная информация:

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

Сообщение Cfyz » 03 мар 2016, 13:00

kipar писал(а):Ну, раз она заработала, то жалко выкидывать. Вдруг еще какие-нибудь применения найдутся.
Как утилитарная функциональность в библиотеке -- да, наверняка стоит оставить. Но конкретно в этом алгоритме построения лабиринта триангуляция, выходит, просто лишняя.
kipar писал(а):алгоритм чаще соединяет 2 с 4 создавая скучный маленький треугольник, чем 1 с 5 создавая нетривиальный маршрут.
Именно поэтому я сказал "на случайном расстоянии N > 2". Треугольник получится только если между X и Y ровно N = 2 шага-ребра, дальше будет более длинный цикл.
kipar писал(а):А в производительности узкое место в расталкивании комнат. Оно сделано в лоб (каждый такт каждую комнату с каждой) и при 2000 комнат занимает с минуту. Луашник то физдвижок не зря использовал.
Вот тут у меня тоже большие сомнения. Максим Кич уже отмечал, что в итоге-то все равно выбирается только несколько комнат. Очевидно, что в этом случае проще раскидать несколько комнат обычным рандомом. Да, мелкие комнаты потом используются для выгрызания ниш в коридорах -- но не проще ли будет построить аккуратные коридоры, а потом пройтись по ним и отдельно накидать эти ниши? Причем можно будет использовать варианты "порченья" коридоров, чтобы они выглядели по-разному.
Пытается раскуклиться

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

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

Сообщение kipar » 03 мар 2016, 13:38

Cfyz писал(а):Как утилитарная функциональность в библиотеке -- да, наверняка стоит оставить. Но конкретно в этом алгоритме построения лабиринта триангуляция, выходит, просто лишняя.
Она нужна при добавлении новых ребер, чтобы не проверять их на пересечения.
Ну и если просто брать минимальные - боюсь что могут артефакты быть (ну т.е. если все комнаты скучены слева, то и большинство коротких ребер будет слева, а при триангуляции шанс проходов у всех комнат будет зависеть только от топологии графа а не от физического расположения).
Или например можно для какого-то "жилого комплекса" взять число дополнительных связей >0.5 и получить почти полную триангуляцию с ровными треугольниками. А если брать минимальные то я не знаю что получится, может и фигня.
Cfyz писал(а):Именно поэтому я сказал "на случайном расстоянии N > 2". Треугольник получится только если между X и Y ровно N = 2 шага-ребра, дальше будет более длинный цикл.
А, я думал в клетках расстояние. Ну да, как-то так.
Cfyz писал(а):Да, мелкие комнаты потом используются для выгрызания ниш в коридорах -- но не проще ли будет построить аккуратные коридоры, а потом пройтись по ним и отдельно накидать эти ниши? Причем можно будет использовать варианты "порченья" коридоров, чтобы они выглядели по-разному.
Теоретически, когда ниши раскиданы заранее они более упорядоченно смотрятся, ну т.е. границы часто (но не всегда) выровнены и упираются в настоящие комнаты или образуют прямоугольные дырки. Хотя на практике я этого не очень замечаю.
Ну и если переделывать то появляется много дополнительных параметров - подойдет ли случайное раскидывание или нужно постараться ближе к краям сделать, как коридоры корежить, в общем когда я начинаю наугад решения принимать обычно получается фигня.

С другой стороны, плюсом будет что можно будет заранее число комнат указать, а не боятся что при маленькой карте их окажется 1 или 2.
Хм, хотя и в текущей версии можно просто N самых больших комнат брать, а не на порог ориентироваться.

Аватара пользователя
Cfyz
Сообщения: 776
Зарегистрирован: 30 ноя 2006, 10:03
Откуда: Санкт-Петербург
Контактная информация:

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

Сообщение Cfyz » 03 мар 2016, 14:05

kipar писал(а):если все комнаты скучены слева, то и большинство коротких ребер будет слева, а при триангуляции шанс проходов у всех комнат будет зависеть только от топологии графа а не от физического расположения.
А можешь простенькую иллюстрацию нарисовать, а то я кажется не до конца понимаю как ты эту триангуляцию используешь? Ведь после комната все равно окажется соединена со всеми ближайшими, все равно короткие ребра будут. Или остовное дерево используется не минимальное?
Пытается раскуклиться

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

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

Сообщение kipar » 03 мар 2016, 14:23

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

1-3-----------8
|
2-4
|
5--6----------------7
Короткие ребра будут. Но на этой картинке шансов у ребра 6-8 или 7-8 появится нет, т.к. мы будем рисовать самые короткие, а ими будут 3-4, 4-6 ну или 3-6 если мы N побольше взяли. А если брать случайные ребра из полной триангуляции, то шансы у 7-8, 6-8 и 3-4 будут равны.

Остовное дерево минимальное. На моей картинке возможно не минимальное, но я не совсем понимаю на что это повлияет.

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

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

Сообщение kipar » 05 мар 2016, 18:25

Алгоритм генерации пока не трогал.

А вот интерфейс библиотеки доработан для настройки параметров генератора и для получения после генерации информации о положении комнат.
Теперь он выглядит так:
Скрытый текст: ПОКАЗАТЬ

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

type
    map_callback = procedure(x, y: Integer; Value: TCellType; opaque: Pointer); cdecl;
    TGeneratorParamsHandle = Pointer;
    TRoomsDataHandle = Pointer;


  procedure mg_generate(map_id, layer: Integer; Typ: TMapGenerator; Seed: Integer; GeneratorParams: TGeneratorParamsHandle; RoomsData: TRoomsDatahandle); cdecl;external bearlibmgLIB;
  procedure mg_generate_cb(SizeX, SizeY: Integer; Typ: TMapGenerator; Seed: Integer; callback: map_callback; opaque: Pointer; GeneratorParams: TGeneratorParamsHandle; RoomsData: TRoomsDatahandle); cdecl;external bearlibmgLIB;

  function mg_params_create(Typ: TMapGenerator): TGeneratorParamsHandle;cdecl;external bearlibmgLIB;
  procedure mg_params_delete(GeneratorParams: TGeneratorParamsHandle);cdecl;external bearlibmgLIB;
  procedure mg_params_set(GeneratorParams: TGeneratorParamsHandle; param: PAnsiChar; value: Integer);cdecl;external bearlibmgLIB;
  procedure mg_params_setf(GeneratorParams: TGeneratorParamsHandle; param: PAnsiChar; value: Single);cdecl;external bearlibmgLIB;
  function mg_params_get(GeneratorParams: TGeneratorParamsHandle; param: PAnsiChar): Integer;cdecl;external bearlibmgLIB;
  function mg_params_getf(GeneratorParams: TGeneratorParamsHandle; param: PAnsiChar): Single;cdecl;external bearlibmgLIB;
  procedure mg_params_setstr(GeneratorParams: TGeneratorParamsHandle; somestring: PAnsiChar);cdecl;external bearlibmgLIB;

  function mg_roomsdata_create: TRoomsDataHandle;cdecl;external bearlibmgLIB;
  procedure mg_roomsdata_delete(RoomsData: TRoomsDataHandle);cdecl;external bearlibmgLIB;
  function mg_roomsdata_count(RoomsData: TRoomsDataHandle): Integer;cdecl;external bearlibmgLIB;
  procedure mg_roomsdata_position(RoomsData: TRoomsDataHandle; RoomIndex: Integer; var ax0, ay0, awidth, aheight: Integer);cdecl;external bearlibmgLIB;
  function mg_roomsdata_linkscount(RoomsData: TRoomsDataHandle; RoomIndex: Integer): Integer;cdecl;external bearlibmgLIB;
  function mg_roomsdata_getlink(RoomsData: TRoomsDataHandle; RoomIndex, LinkIndex: Integer): Integer;cdecl;external bearlibmgLIB;
Что и демонстрируется в демке, в которой теперь источники света расставляются по центрам первых девяти комнат, а по нажатию F4 можно поменять один из параметров (порог при котором область считается комнатой).
Код в демке и библиотеке стал так себе, ну и организационная работа в планах - репозиторий запилить, байндинги к другим языкам по образцу BearlibTerminal, ну и добавить BSP чтобы с параметрами и информацией о комнатах было целых два алгоритма на выбор. А может и в старые алгоритмы новое API добавить - комнаты в некоторых из них есть, да и параметры наверняка можно найти.
AllDemo.zip
демо библиотеки
(1.11 МБ) 159 скачиваний
BeaRLibMG.zip
исходники библиотеки
(55.26 КБ) 161 скачивание

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

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

Сообщение Харука-тян » 09 мар 2016, 11:11

kipar писал(а):в планах - репозиторий запилить, байндинги к другим языкам по образцу BearlibTerminal, ну и добавить BSP чтобы с параметрами и информацией о комнатах было целых два алгоритма на выбор. А может и в старые алгоритмы новое API добавить - комнаты в некоторых из них есть, да и параметры наверняка можно найти.
Ждём с нетерпением
"Женщина верит, что дважды два будет пять, если хорошенько поплакать и устроить скандал" (© Дж. Элиот).
ИзображениеИзображение

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

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

Сообщение kipar » 17 мар 2016, 07:57

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

Ответить

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

Сейчас этот форум просматривают: Bing [Bot] и 20 гостей