Структура данных для представления связей между странами на карте

9

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

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

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

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

maps efficiency Мэтью Фредерик
источник
Если я должен спросить об этом на GameDev.StackExchange, просто дайте мне знать. Я спрашиваю здесь, потому что я уверен, что такого рода вещи нужны для всех видов проблем разработки, и мне не нужна помощь с «игровой» стороной, по сути, только с частью планирования маршрута.
Мэтью Фредерик
Вам нужен либо график, либо матрица связности (что удобно, потому что замыкание легко вычислить). Возможно, вам нужны оба. Ищите их.
2
Посмотрите на структуры и алгоритмы графовых данных: en.wikipedia.org/wiki/Graph_%28data_structure%29
1
Это не выглядит по теме для меня. Это должно быть либо на GameDev, либо на Stack Overflow, так как здесь слишком объективная тема.

Ответы:

6

Определенно График. Проверьте это здесь в теории графов , в основном у вас есть узлы и ребра. Узел может содержать 0 или более ребер для других узлов.

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

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


источник
Отлично, спасибо. У вас есть предложения, где найти такие алгоритмы? Мне так не нужен кратчайший путь, но такие вещи, как проверка кругов и т. Д., Были бы очень полезны.
Мэтью Фредерик
2

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

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

Есть также несколько хороших книг об игре ai: Game AI на примере Мэта Бакленда http://www.ai-junkie.com/books/toc_pgaibe.html

или серия Мудрости программирования игр AI. http://www.aiwisdom.com/ Первая книга состоит из нескольких глав о поиске пути.

Стивен
источник
Отлично, спасибо за указатели книг. Кажется, есть тонна книг по искусственному интеллекту, и личные рекомендации намного лучше, чем широкие результаты, которые я получаю при поиске.
Мэтью Фредерик