Структура данных для случайного мира

Question

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

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

Есть идеи о том, какая структура данных может быть наиболее эффективной в такой ситуации?Или я делаю что-то действительно глупое с моим случайным поколением мира?

Любая помощь будет принята с благодарностью.Спасибо, Крис

Answer 1

Рекомендую прочитать о графиках.Это как раз приложение генерации случайных графов.Вместо «ячейка» и «выход» вы описываете «узел» и «ребро».

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

Это поможет вам понять узлы и ребра:

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

Удачи!

-Брайан Дж. Стирн-

Answer 2

A map< pair<int,int>, cell>, вероятно, будет работать хорошо; пара будет представлять координаты x, y. Если в этих координатах на карте нет ячейки, создайте новую ячейку. Если вы хотите сделать его действительно бесконечным, вы можете заменить целые числа целочисленным классом произвольной длины, который вы должны будете предоставить (например, bigint)

Answer 3

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

Answer 4

Не могли бы вы иметь хэш (или набор STL), в котором хранится коллекция всех координат сетки, содержащих занятые ячейки?

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

(если бы у вас было ограниченное пространство, вы могли бы использовать 2d-массив - я думаю, что я видел это в статье в журнале Byte в 1980-х годах, но если я правильно понимаю, вам нужен мир, который может бесконечно расширяться)