Сферическое представление карты

19

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

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

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

В игре есть элементы RTS, поэтому я буду хранить такие вещи, как карты влияния и выполнение A * поиска пути и свертки, поэтому представление должно быть эффективным.

DaleyPaley
источник
Насколько важна точная топология карты, а не просто позволить актерам двигаться в одном направлении и в конечном итоге оказаться там, где они начали? Самым простым и эффективным представлением был бы тор / пончик.
congusbongus
1
Да, я упомянул сферическое отображение и проблемы, которые оно имеет с полюсами. Я хочу хранить значения вокруг поверхности, поэтому мне нужно сопоставить точку 3D-поверхности с индексом массива с минимальным растяжением.
DaleyPaley
Вы можете попытаться разделить тетраэдон, чтобы создать сферу. Он состоит из треугольников одинакового размера и распределенных.
thalador
1
@thalador Спасибо за предложение. Не уверен, но я думаю, что икосаэдры лучше, чем тетраэдры, если я пойду по треугольному маршруту. Но в любом случае тесселяция не является проблемой. Меня беспокоит эффективная индексация массива.
DaleyPaley
Дополнительное чтение: gamedev.stackexchange.com/questions/10249/…
Кромстер говорит, что поддерживает Монику

Ответы:

12

Хорошо, для тех, кто интересуется этой темой, я сейчас подробно опишу решение, которое я выбрал. Спасибо всем, кто ответил и дал мне идеи.

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

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

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

Редактировать:

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

Я могу сделать несколько итераций расслабления, чтобы сделать области клеток еще более однородными.

подразделение икосаэдра

DaleyPaley
источник
7

Есть способ сделать это довольно изящно, основанный на подразделении икосаэдра, как вы предложили в своем вопросе. Икосаэдр состоит из 20 равносторонних треугольников, и эти треугольники можно сгруппировать в 5 наборов, где 4 треугольника в наборе образуют форму параллелограмма:

введите описание изображения здесь

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

Если эти треугольники подразделяются на более мелкие треугольники, весь параллелограмм можно индексировать, как прямоугольный массив n на 4n (в данном примере n = 4):

введите описание изображения здесь

Числа в каждой ячейке являются номерами столбцов прямоугольного массива. Правила поиска соседей в массиве довольно просты: горизонтальные соседи - это столбец плюс или минус 1, а вертикальный сосед - либо минус одна строка и плюс один столбец, либо плюс одна строка и минус один столбец, в зависимости от того, Номер столбца является четным или нечетным, соответственно.

Тем не менее, вам все равно придется написать специальный код для поиска соседей, которые пересекают границу от одного параллелограмма к следующему. Это немного сложно, так как в некоторых местах верх или низ одного параллелограмма будет связан со стороной другого, или верх и низ будут связаны с горизонтальным смещением между ними и т. Д. Возможно, структура с половиной края или подобное для параллелограммов было бы здесь полезно. Тем не менее, по крайней мере, отношения являются симметричными среди всех 5 параллелограммов: все они следуют той же схеме, в которой сторона связана с другой стороной своих соседей.

Натан Рид
источник
Это действительно очень хорошее представление. Моей основной заботой о треугольных методах было поддержание треугольных массивов и всех строчек. Здесь все еще есть небольшая строчка, но массивы прямоугольные. Спасибо, очень приятно знать
DaleyPaley
3

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

Если вы хотите, чтобы плитки были плоскими и однородными, вы правы в том, что икосаэдр, в частности усеченный икосаэдр, довольно распространен

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

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

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

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

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

Это на самом деле довольно легко сделать недетерминированным способом. Сначала выберите N случайных точек равномерно вокруг поверхности. Удостоверьтесь, что эти точки фактически одинаковы (см. Выбор точек сферы , формулы 9-11). На втором этапе мы делаем эти точки менее случайными и более однородными: предположим, что все эти точки имеют отрицательный электрический заряд, чтобы они отталкивали друг друга. Смоделируйте движение точек за несколько шагов, пока они не сойдутся в состояние равновесия. Эта окончательная конфигурация точек даст вам сетку, которая почти равномерно распределена по поверхности сферы.

паша
источник
1
Я никогда не слышал о теории волосатых шаров, это довольно интересно. Нужно помешать себе шутить. Раньше я так распределял точки по сферам, но проблема в том, что полигонизировать их гораздо медленнее, чем подразделять многогранник. Кроме того, формы и валентность клеток будут слишком неоднородными, на мой взгляд. Но все равно спасибо.
DaleyPaley