Создание карты территории

Question

Существует ли тривиальный или, по крайней мере, умеренно простой способ создания карт территорий (например, Риск)?

Я смотрел в прошлое, и лучшее, что я мог найти, были расплывчатые ссылки на диаграммы Вороного. Пример диаграммы Вороного таков:

.

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

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

Любой совет будет высоко ценится.

Answer 1

Лучшая ссылка, которую я видел на них, - Вычислительная геометрия: алгоритмы и приложения , которая охватывает диаграммы Вороного, триангуляции Делоне (аналогично диаграммам Вороного, и каждая из них может быть преобразована в другую) и другие. похожие структуры данных.

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

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

Answer 2

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

Answer 3

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

Страница Пола Бурка в UWA, с его работой 1989 года по Делоне и рядом ссылок на реализацию.

A отличное объяснение псевдокода и визуальное выполнение Делоне на codeGuru.com.

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

Answer 4

CGAL - это библиотека C ++, которая имеет структуры данных и алгоритмы, используемые в вычислительной геометрии.