Какова хорошая стратегия для построения ориентированного графа для игровой карты (в Python)?

Question

Я занимаюсь разработкой процедурно-сгенерированного игрового мира на Python. Структура мира будет похожа на парадигму MUD / MUSH комнат и выходов, организованных в виде ориентированного графа (комнаты - это узлы, выходы - это ребра). (Обратите внимание, что это не обязательно ациклический граф, хотя я готов рассмотреть ациклические решения.)

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

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

Например, у меня будут комнаты такого рода:

side_street, main_street, plaza, bar, hotel, restaurant, shop, office

Наконец, вопрос: какова хорошая стратегия для создания и размещения этих комнат для создания графика, который может соответствовать заданным правилам?

Некоторые правила могут включать: одну площадь на 10 000 жителей; main_street подключается к plaza ; side_street подключается к main_street или side_street ; hotel поддерживает подключения main_street или plaza и соответственно получает дополнительные теги; и др.

Бонусные баллы, если предложенная стратегия позволит реализовать реализацию на основе данных.

Answer 1

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

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

Если вещи нерегулярны - и плотно упакованы - жизнь несколько сложнее.

Определите карту для размещения местоположений. Каждое местоположение имеет диапазон координат; если вы работаете с простыми прямоугольниками, то у каждого местоположения может быть (левый, верхний, правый, нижний) кортеж.

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

Затем вы можете выполнить это модульное тестирование с фиксированным набором местоположений, которые вы разработали, и которые все можно сбросить на карту и пройти некоторые базовые проверки работоспособности для неконфликтных, смежных и т. д.

<Ч>

Во-вторых, вам нужен своего рода "генератор лабиринтов". Односвязный лабиринт легко генерируется в виде древовидной структуры, которая складывается в заданное пространство.

Лабиринт / дерево имеет " корень " узел, который будет центром лабиринта. Не обязательно физический центр вашего пространства, но корневой узел будет серединой структуры лабиринта.

В идеале, одна ветвь этого узла содержит один " вход " на все пространство.

Другая ветвь этого узла содержит один " выход " со всего пространства.

Кто-то может пройтись от входа к выходу, посетив множество "тупиковых" сайтов. места по пути.

Выберите место для корневого узла. Поместите его в свое место на карте.

Это будет иметь 1 - n входов, каждый из которых является поддеревом с корневым узлом и 1 - n входами. Именно этот бизнес с несколькими входами делает дерево естественным образом подходящим для этой структуры. Кроме того, правильное дерево всегда хорошо связано тем, что у вас никогда не бывает изолированных разделов, которые недоступны.

Вы - рекурсивно - расправляетесь с корневым узлом, выбирая местоположения и помещая их в доступное пространство.

Модульное тестирование, чтобы убедиться, что оно достаточно хорошо заполняет пространство.

<Ч>

Остальные ваши требования - точная настройка того, как генератор лабиринта выбирает места.

Самое простое - иметь таблицу весов и случайный выбор. Выберите случайное число, сравните его с весами, чтобы увидеть, какой тип местоположения будет идентифицирован.

<Ч>

Ваше определение пространства может быть 2D или 3D - оба довольно рациональны. Для получения бонусного кредита подумайте, как бы вы реализовали 2D-пространство, выложенное плиткой с шестиугольниками вместо квадратов.

Эта " геометрия " может быть плагином Стратегии для различных алгоритмов. Если вы можете заменить квадратное 2D на шестиугольное 2D, вы хорошо поработали над OO Design.

Answer 2

Посмотрите обсуждения на MUD Connector - здесь есть несколько замечательных дискуссий о макете и генерации мира, и различные типы систем координат / навигации в «Расширенном кодировании и дизайне»; (или аналогичный) форум.