Я делаю генератор случайных карт для космической игры 4X.
Каждый узел в игре находится в произвольной (x, y) координате на двумерной сетке. Узел может иметь один или несколько двунаправленных ребер для другого узла (представляющих червоточины). Все узлы должны иметь хотя бы одну червоточину, и все узлы должны принадлежать одному графику.
В идеале, червоточина не должна превышать максимальную длину, и, если возможно, червоточины не должны пересекаться друг с другом.
Моя наивная реализация состоит в том, чтобы перебрать все узлы и привязать узел к ближайшим 3 узлам. Тем не менее, я в конечном итоге с многочисленными подпрограммами. Какой хороший метод для создания ребер для узлов?
random
graph-theory
Extrakun
источник
источник
Ответы:
Вот хороший ответ на аналогичный вопрос.
Сначала создайте связанный граф, возможно, используя минимальное связующее дерево, как в ссылке выше. Он предлагает использовать случайные веса ребер, чтобы сделать «минимальное» дерево случайным. Тогда вы можете случайным образом добавить больше ребер, чтобы это было не просто минимальное дерево. Как именно вы добавляете случайные ребра, зависит от того, какой граф вы хотите.
На самом деле, если проблема заключается только в том, чтобы убедиться, что все узлы принадлежат одному и тому же графу, вы можете воспользоваться вашим текущим методом случайной генерации (или любым другим) и применить алгоритм Прима поверх него. Если вы хотите внести минимальные изменения в график, просто чтобы убедиться, что все подграфы связаны, вы можете установить стоимость ребра равной 0 для ребер, которые уже есть.
источник
Основные ограничения вашей проблемы двояки: создание односвязного графа; и создавая его с проксимальными связями. Ответ Филиппа, хотя и несколько ценный, не затрагивает все ограничения вашей проблемы
Когда вы наивно соединяете точки в облаке, вы рискуете (и к тому же высок), что эти условия не будут выполнены.
Итак, вы видите, проблема не столько в связанности, сколько в близости этих соединений. Соединить каждый узел графа с любым другим узлом тривиально, но соединить только те, которые находятся ближе всего при сохранении односвязности всего графа, немного сложнее.
Это то, что создает триангуляция Делоне в n измерениях. Первая причина использования триангуляции Делоне состоит в том, что она выполняет оба эти условия неявно. Вторая причина в том, что намного проще работать в обратном направлении от такого графа (вычитая ненужные ребра и вершины), чем пытаться создать его другими способами.
Важно видеть, что это иерархический процесс. Первый уровень связан с подключением червоточины; вторая касается расстояний, по-видимому, пройденных с использованием стандартного корабля. Вы можете применить Делоне на одном или обоих уровнях, чтобы удовлетворить ваши ограничения.
Выполнение этого чисто топологически оставит вас с червоточинами, которые не имеют смысла, поскольку они могут соединить одну сторону галактики с другой, несмотря на высокую плотность звезд между ними (и, возможно, даже падение на прямой маршрут червоточины). Топология не топография; последнее является соображением сверх первого. Вы обеспокоены близостью и, следовательно, топографией.
источник