LINUX.ORG.RU

Алгоритм генерации игрового мира (дорОги)

 , ,


2

1

Пишем с детишками игру «Поездка». Там ездит машина.

В настоящий момент, игровая карта — это одномерный массив плиток разных типов (под каждый тип своя картинка). Можно и в двумерный превратить легко — у них есть «х» и «у» координаты.

Но, что-то очень лениво писать еще и конструктор карт. Вчера погуглил и нашлось куча вариантов, но всё что я нашел — это про ландшафты, острова, вобщем про природные неровности.

А надо чтобы в первую очередь генерировались дороги. Вот это я найти не смог.

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

На картинке пример генерации с помощью алгоритма «Diamond-Square», так, для прикола, чтобы тестировать покатушки было не скучно: https://pic4a.ru/88/N_F.png

Сама игра написана на канвасах (браузерка), без каких-либо библиотек, чистый JavaScript. Но учитывая специфику вопроса, я посчитал запоститься в девелопменте будет правильнее.

Да и машинка не проста — у неё переключаются скорости, есть нейтралочка, тормоз, разгон, инерция (что и видно на скрине по значению спидометра, чтобы сделать скрин газ я отпустил). Предполагается добавить в игру: умный рендер объектов (не дёргаем тех, кто не попал в вьюпорт), коллизии со слоем подстилки (по песку ехать труднее), другие автомобили с туповатым ИИ, коллизии с этими авто и прочими объектами типа дом, забор.

Заранее большой сяп тем кто откликнется и поможет!

★★★★★

Последнее исправление: cetjs2 (всего исправлений: 1)

Дороги, свершенно очевидно, пролегают по рельефу.

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

Einstok_Fair ★★☆
()
Ответ на: комментарий от Einstok_Fair

Рельеф предполагается совершенно ровным. Иначе дорогам не подойдет плиточное представление.

Иначе там будут кривые второго и третьего порядка. В принципе тоже вариант — рисовать кривые вместо того чтобы строить мир из клеточек.

Но сейчас выбран вариант с клетчками-дискретами.

deep-purple ★★★★★
() автор топика
Ответ на: комментарий от Harald

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

deep-purple ★★★★★
() автор топика
Ответ на: комментарий от deep-purple

А чем не угодили полигоны Вороного?

Дороги строй Брезенхамом по границам этих полигонов вот и получится карта.

timdorohin ★★★★
()
Ответ на: комментарий от timdorohin

Так это опять ты про кривые. Мне бы только дискретка — гориз, верт, и под 45 градусов. Еще ж картинки под это рисовать.

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

deep-purple ★★★★★
() автор топика
Ответ на: комментарий от deep-purple

ИМХО бери манхеттеновское растояние, так круче дороги

https://en.wikipedia.org/wiki/Voronoi_diagram#Illustration

И нет, я не про кривые а про двумерные карты тайлов.

timdorohin ★★★★
()
Последнее исправление: timdorohin (всего исправлений: 1)
Ответ на: комментарий от deep-purple

Это всё круто, только если у тебя плоский мир и препятствий нет, то рандомно (равномерно) набрасываешь точки «пунктов назначения» и объединяешь их дорогами.

Deleted
()
Ответ на: комментарий от timdorohin

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

deep-purple ★★★★★
() автор топика
Ответ на: комментарий от timdorohin

Да, манхетенское интересно. Но это представление тогда надо будет перевести в дискретку. Надо думать.

deep-purple ★★★★★
() автор топика
Последнее исправление: deep-purple (всего исправлений: 1)
Ответ на: комментарий от deep-purple

На самом деле в процедурной генерации ландшафтов до сих пор только две проблемы - дураки реки и дороги.

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

timdorohin ★★★★
()
Ответ на: комментарий от timdorohin

Наверное я возьму это: Алгоритм генерации игрового мира (дорОги) (комментарий)

Редактор карт писать придется, но хотябы протяженные дороги руками не надо будет прокладывать клеточками. Всеравно здания, заборы, вручную рассовывать. И фиксить какие-то дороги что не понравятся как сгенерилось.

deep-purple ★★★★★
() автор топика

Раскидай по карте некоторое количество прямоугольников разного размера, желательно довольно крупных, а потом случайным образом бери две точки и используя алгоритмы поиска пути(алгоритмы поиска минимальной стоимости), при этом дорогу тоже добавляй на карту и ставь стоимость прохода по ней меньше чем просто по территории, чтобы не было много паралелльных дорог.
Должно получится карта с норм объездами.

Tark ★★
()

надо чтобы в первую очередь генерировались дороги. Вот это я найти не смог.

плюсану рандом-генератор ключевых точек + A* (a-star) генератор дорог между ними.

Rastafarra ★★★★
()

сгенери холмистый ландшафт, накидай рандомом точки-города, и пусти между ними поиск пути

MyTrooName ★★★★★
()
Ответ на: комментарий от Einstok_Fair

Dwarf Fortress уже есть и он вроде как начинает с карты рельефа->осадков->рек и озёр->злобности окруения->цивилизаций->дорог.

peregrine ★★★★★
()
Ответ на: комментарий от Einstok_Fair

Будь она опенсорсная она не была бы такой упоротой в хорошем смысле слова.

peregrine ★★★★★
()
Ответ на: комментарий от deep-purple

напугал ежа голой жопой

Но... Может наоборот?

anonymous
()
Ответ на: комментарий от Einstok_Fair

высылая в изыскательские партии инженеров по 7 дворфов

Поправил

upcFrost ★★★★★
()

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

Napilnik ★★★★★
()
Ответ на: комментарий от Einstok_Fair

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

Napilnik ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.