Добавление циклов в минимальное связующее дерево без перемещения точек?

Я создаю макет подземелья для видеоигры. Я создал комнаты, разметил их, используя управление разделением, и создал полностью связанный взвешенный, ненаправленный граф комнат. Затем я рассчитал MST, используя алгоритм Прима, все с использованием GML (GameMaker Language). Я скучаю по Python.

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

Я включил изображение MST (линии соединяются с углами красных маркеров, даже если на изображении видно, что они быстро останавливаются)

Изображение


algorithm geometry graph-theory game-maker-studio-2 game-maker-language
person Timothy Mitcheson    schedule 24.05.2020    source источник
comment
Это MST внедрен? (Есть ли узел, где можно сказать, что это начало)?   -  person Yonlif    schedule 25.05.2020
comment
@Yonlif Да, корневой узел всегда ближайший к центру (круга, окружающего все узлы)   -  person Timothy Mitcheson    schedule 25.05.2020
comment
Прохладный. Как насчет добавления двух номеров метаданных в узлы - сначала расстояние от центра. Второй для каждого слоя (с равным расстоянием от центра) проиндексируйте их. Затем разрешите проходы случайным образом только между узлами с одинаковым расстоянием от центра и последовательными индексами. Вы можете выбрать сколько, но таким образом можете обещать, что пересечений не будет.   -  person Yonlif    schedule 25.05.2020

Ответы (1)


arrow_upward
0
arrow_downward

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

Чтобы проверить, можете ли вы соединить два узла, node1 и node2, вы можете перебрать все существующие ребра и посмотреть, пересечет ли линейный сегмент node1 --- node2 линейный сегмент edge.endpoint1 - - edge.endpoint2. Ключевая функция, которая проверяет, пересекаются ли два отрезка линии, может быть реализована с помощью любого из решений, найденных здесь: Как я могу проверить, пересекаются ли два сегмента?.

Это займет O (E) времени и будет выглядеть примерно так

def canAddEdge(node1, node2):
    canAdd = True
    for edge in graph:
        canAdd = canAdd and not doesIntersect([node1.location(),
          node2.location(), edge.endpoint1.location(), edge.endpoint2.location()])

И вы можете получить список допустимых ребер для добавления в O (EV ^ 2) с чем-то вроде

def getListOfValidEdges(graph):
    validEdges = []
    for index,firstEndpointNode in enumerate(graph.nodes()):
        for secondEndpointNode in graph.nodes()[index:]:
            if (canAddEdge(firstEndpointNode, secondEndpointNode)):
                validEdges.append([firstEndpointNode, secondEndpointNode])
    return validEdges

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

person Cjp    schedule 12.11.2020