Как я могу создать (относительно) линейный путь подземелья?

8

Мы разрабатываем концепцию экшн-скроллера. Нам нужен способ создания (относительно) прямой карты. Под этим я подразумеваю что-то вроде ...

введите описание изображения здесь

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

Здесь мы зашли в тупик. Мы изучаем несколько вариантов, но пока не достигли прогресса. Какой подход мы могли бы использовать для генерации такого рода пути? Мы не связаны языками программирования, поскольку до сих пор мы экспериментировали с Java, C # и C ++. Точно так же у нас нет текущих зависимостей от конкретных игровых движков.

user2444503
источник
11
Я бы добавил, что не ясно, какой конечный результат вы ищете. «Карта», которую вы показываете, представляет собой вид сверху на регион. Вы разрабатываете 2-й боковой скроллер. Как связаны 2?
Vaillancourt
Я удалил «лучшую» фразу из вашего вопроса, так как она не очень полезна. Я также удалил три предложенных вами подхода, которые являются потенциально верными ответами. Как правило, лучше не включать потенциальные решения в свой вопрос, так как сравнение предоставленных решений, как правило, не является вопросом, который мы рассматриваем здесь по теме (но обычно возникает вопрос, как решить проблему в отсутствие существующего отклонения решения). Я также убрал некоторые из комментариев, которые, как мне кажется, устранены изменениями.
1
Эта линия выглядит почти так же, как то, что я получил, когда начал с прямой линии и добавил к ней перлин (или симплекс) шум (несколько октав). Может быть, область для исследования (я создавал динамическое освещение, меняющееся во времени)
Ричард Тингл

Ответы:

15

Требования

  1. Вы хотите несколько путей от А до Б.
  2. Вы хотите работать в пространстве сетки, вероятно, это пространство листов для вашей боковой прокрутки.
  3. Вы не хотите, чтобы пути пересекались, иначе это может испортить ход игры.
  4. Вы хотите, чтобы пути выглядели достаточно органично.

Диаграммы Вороного

Диаграммы Вороного - это заполняющие пространство плоские графы:

введите описание изображения здесь

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

Как создать диаграмму Вороного для использования с системой на основе плиток

Создайте карту разумного размера, скажем, 128x128. Генерация nслучайных координат сетки (x, y) на карте и заполнение каждого уникальным идентификатором / цветом. Создайте список для этого цвета и добавьте в него начальную ячейку; сделать это для каждого цвета.

Теперь у вас есть эти уникальные цветные точки, плавающие в пустоте, но вам нужно создать целые островки цвета вокруг них, чтобы конечный результат выглядел так:

введите описание изображения здесь

Для этого нам нужно увидеть, какой цвет принадлежит каждой ячейке на карте (ячейка = пиксель на изображении выше). Мы пробегаем каждую ячейку на карте, проверяя, какая из наших nначальных цветовых точек ближе всего к ней (через Пифагора). Эта ячейка попадает в список, связанный с этим уникальным идентификатором / цветом ... далее называемые островками AKA Voronoi (на приведенной выше диаграмме группы пикселей одного цвета).

Теперь у вас должна быть квантовая диаграмма Вороного. Следующим шагом является анализ смежности каждого острова с другими островами. Установите простой узел и структуру ребер, чтобы вы могли хранить график (узел - это просто идентификатор, список для этого идентификатора и пустой список ребер; ребро - это только начальный и конечный узел). Для каждого острова с уникальным идентификатором создайте узел и добавьте ребра, чтобы связать его с каждым островом, к которому он прилегает.

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

Например - красный - это путь 1, синий - это путь 2, пурпурный - оба:

введите описание изображения здесь

Вы можете использовать любые существующие графовые алгоритмы (включая A *) для генерации путей от начала до конца. Получение извилистого пути - это случай, когда не всегда используется оптимальный шаг к острову цели.

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

Необязательный, последний шаг для поиска пути

Либо вы можете использовать график высокого уровня, который вы построили в сочетании с нижележащими ячейками / тайлами, для выполнения времени выполнения A *, либо вы можете совершать восхождение на холм на нижележащие ячейки / тайлы для лучшего движения:

В центральной (или любой) координате острова цели вы можете разместить ячейку влияния. Это влияние может накачивать «запах», как в Collaborative Diffusion . Этот аромат будет распространяться вниз по пути обратно к тому, что было начальным островом, становясь все слабее и слабее. Теперь для существа в начале мы просто поднимаемся от клетки с более низким ароматом к ячейке с более высоким ароматом, каждый раз приближая вас к цели - так же, как действует собака. Каждый путь является примерно линейным, что позволяет избежать использования A * во время выполнения. Или вы можете сделать то же самое с графиком островов, но этот способ немного сложнее, потому что вы, вероятно, захотите перемещаться по своим сущностям на уровне плиток. Так что первый способ, возможно, лучше. В любом случае вы сможете перейти к цели при низких затратах на обработку.

инженер
источник
Я сделал генератор карт, используя Voronoi и Perlin Noise в Java, возможно, он может быть вам полезен в качестве отправной точки: github.com/dragondgold/Map-Generator
Andres