Как я могу постепенно генерировать график?

8

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

Предполагая, что я правильно определил терминологию, мои требования таковы:

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

У меня были некоторые идеи (которые я еще не пытался реализовать) относительно использования локальных максимумов двумерного перлин-шума в качестве вершин (входные данные x и y могли бы использоваться в качестве его метки), но это кажется неуклюжим и слишком сложным.

Есть ли лучший способ для создания такого графика? Я занимаюсь разработкой на Python 2.6 с использованием Panda3D и numpy, и, конечно, хотел бы посмотреть на включение других библиотек, если они помогут с этой проблемой!

редактировать

Я думаю, что плохо справился с объяснением некоторых моих требований, так что пришло время иллюстрации! Надеюсь, это прояснит ситуацию.

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

Граф мира игрока А

Хороший друг Игрока A Игрок B - фанат кошек, поэтому он хочет показать это ей. Он дает ей корневое семя для своего мира и направления по более короткому маршруту на интересующую гору. Ее игра теперь должна выглядеть так:

Граф мира игрока B

Проблема, с которой я в настоящее время сталкиваюсь больше всего, заключается в том, «Как создать те же семена для Игрока B, если ее исследование не пошло по тому же пути?» Вот что привело меня к идее использования шума Перлина - пока используется один и тот же начальный корень, максимумы не будут двигаться, поэтому их координаты могут использоваться в качестве стабильных начальных вершин.

Бен Бланк
источник
Почему связный граф не подходит для этого? mathworld.wolfram.com/ConnectedGraph.html Возможно, я упускаю суть. Если пользователь хочет перейти из одного местоположения в другое, и все они связаны, предоставьте им список местоположений и переместите их положение на карте мира в новое местоположение.
Брэндон
@brandon - «Подключено» - это второе свойство, которое я перечисляю. :-)
Бен Бланк
моя точка зрения, если вы можете перейти от одного узла к любому другому. Когда они посещают телепорт, дайте им список всех узлов, которые они посетили, кроме этого. Нет необходимости иметь график, вы ведете список всех посещенных узлов и их местоположений, и вы просто телепортируетесь в выбранное место. Я неправильно понимаю?
Брэндон
почти все ваши описания этих терминов являются правильными, за исключением «циклического» и «локально конечного». Первый ограничивает ваши графики тем, что они звучат - кругом. Термин, который вы можете использовать для требования о наличии более одного пути от одной вершины к другой, является «2-связным». «Локально конечный» просто означает, что каждая вершина имеет конечное число ребер.
Гарри Стерн
@ Гарри Стерн - Насколько я понимаю, циклические графы - это графы, содержащие как минимум один цикл графов . Похоже, вы говорите о графе циклов , который представляет собой граф, состоящий из одного цикла графа и ничего больше. Я специально не ищу графики, которые являются «2-связными» (см. «Простой»). И да, это то, что я имел в виду под «локально конечным».
Бен Бланк

Ответы:

6

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

Вы должны быть очень осторожны, когда говорите о «крайних вершинах». Граф - это набор вершин, набор ребер и функция, которая связывает их. Не существует заданной геометрической интерпретации, если вы не примените ее. Например: обе эти картинки показывают один и тот же график. На первом изображении вершина 2 может рассматриваться как «самая внешняя» вершина, но во втором изображении вершина 2 не будет считаться «самой внешней». Если бы вы рассматривали три измерения, вы могли бы сказать, что все вершины являются «внешними».

График 1 График 2

Это означает, что у вас должна быть какая-то другая информация, чтобы вы могли знать, что такое «самая внешняя» вершина. Вы можете использовать (x, y) пары, так как это даст вам возможность легко визуализировать геометрическое представление, однако я не думаю, что вам нужно заходить так далеко. Из того, что вы говорите, все, что вам нужно знать, это то, какие вершины уже есть в графе.

Если вы запускаете это каждый раз, когда посещаете вершину:

if(this.needsNeighbours)
{
    List<int> connections = genRandomNumbers(n);
    foreach (int connection in connections)
    {
        //Simple graph
        if(connection == this.seed || this.hasNeighbour(connection))
        {
            continue;
        }
        //Connections to already existing, unvisited vertices
        else if(nodeMap.containsKey(connection) && 
                nodeMap.getByKey(connection).needsNeighbours)
        {
            nodeMap.getByKey(connection).addNeighbour(this.seed);
            this.addNeighbour(connection);
        }
        //Grow graph with new vertices
        else
        {
            nodeMap.add(connection, new Node(connection));
            nodeMap.getByKey(connection).addNeighbour(this.seed);
            this.addNeighbour(connection);
        }
    }
    this.needsNeighbours = false;
}

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

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

Чуви Гамбол
источник
Вы понимаете именно то, что я имел в виду под «бесконечным», и ваша точка зрения о «внешнем» хорошо принята - я подправил словоблудие в своем вопросе. Тем не менее, либо я неправильно понимаю ваш генератор, либо я плохо объяснил свои потребности, так как это выглядит так, как будто это не будет генерировать одни и те же семена для разных путей к одной и той же вершине. Я добавил несколько иллюстраций к своему вопросу, которые, надеюсь, прояснят то, что я пытаюсь достичь. :-)
Бен Бланк
Теперь я понимаю, что вы имеете в виду. Это немного сложнее. Что вам нужно сделать, это изменить вызов genRandomNumbers на функцию, которая всегда возвращает один и тот же набор чисел для своего ввода, и использовать семя узла в качестве аргумента. Это гарантирует, что вы получите те же соединения и семена независимо от того, какой путь вы выберете или с какого узла вы начинаете. Вы должны быть осторожны, чтобы набор чисел для узла B, к которому подключается A, также содержал A, чтобы вы получили свойство неориентированного графа. Если вы этого не сделаете, вы получите ориентированный граф.
Chewy Gumball
1

Один метод:

init:
  root = generateLocation using random seed
  store root's seed
  place player in root location

when the player enters a new location:
  release the memory used by locations that are further than 1 edge away, but keep their seeds
  generate some neighbors for the new location. for every neighbor n:
    gen.seed(getSeed(n))
    n = generateLocation using n's random seed
    numCyclicEdges = gen.randint(0, 1)
    create numCycleEdges edges to existing locations

getSeed(n):
  if(n already has a seed) return n's seed
  else return randomSeed()

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

Цзяхуа Ван
источник