Триъгълните мрежи в игрите

Оригиналът е на Boris the Brave

1
1716

Да, триъгълните мрежи… Квадратните мрежи например се използват навсякъде – от пикселите в изображенията до разположението на сградите в един квартал. Шестоъгълните мрежи също се използват много широко, особено в десктоп игрите. Но триъгълните мрежи, които всъщност са равномерно запълнени 2D плоскости с равностранни триъгълници, кой знае защо вече не са особено популярни. Срещал съм мнения, че те са на практика безполезни или че тяхната математика е твърде сложна. С тази статия ще се опитам да докажа, че тези две изявления са напълно погрешни и всъщност изчисленията при триъгълните мрежи са по-лесни в сравнение с шестоъгълните и освен това триъгълните мрежи имат редица преимущества пред другите.

Кодът за извършването на необходимите изчисления в триъгълни мрежи качих в своята GitHub страница, но считам, че трябва да обясня, как и защо е необходимо използването на подобни мрежи.

Какво всъщност са триъгълните мрежи

Когато говоря за триъгълна мрежа, то аз имам предвид тайлова карта, в която всички тайлове (плочки) са подредени във вид на редове и колони.

Почти всички софтуерни пакети за работа с графика и хардуерните устройства могат да работят по-ефективно с триъгълници, групирани в мрежи, отколкото на подобен брой триъгълници, които са представени поотделно. Това обикновено е така, защото компютърната графика извършва операции с върховете в ъглите на триъгълниците.  С отделните триъгълници системата трябва да работи с по три върха за всеки триъгълник. В една по-голяма мрежа може да има осем или повече триъгълника, които се срещат в един връх – чрез обработка на тези върхове само веднъж, е възможно да се постигне идентичен ефект

Най-важният момент в една триъгълна мрежа е, че всяка клетка има точно три съседа. Можем да видим игри, в които е нарисувана една триъгълна мрежа, но в същност фигурите са разположени в ъглите на триъгълниците. Всеки ъгъл се сравнява с шест други и всъщност това не е триъгълна, а шестоъгълна мрежа.

Популярната китайска игра Халма се играе на шестоъгълна мрежа, въпреки че там се виждат само триъгълници.

И обратното: ако в дадена игра се използват ъглите на шестоъгълна мрежа, то това на практика е триъгълна мрежа. Заради тези свойства равномерните шестоъгълни и триъгълни мрежи се наричат двойни.

Защо да се използва триъгълна мрежа

Триъгълниците имат три потресаващи свойства:

  1. Те са винаги планарни
  2. Те са съвсем опростени
  3. Тяхната геометрия е по-удобна в сравнение с всичко друго
Планарността

Ако изберем произволни три точки в триизмерното пространство, то през тях винаги може да премине една равнина. Тоест, имайки три точки, винаги може да се нарисува триъгълник на повърхността на тази равнина. За многоъгълниците с повече върхове това невинаги е вярно. Ако вземем четири 3D върха, то тяхното съединяване във вид на многоъгълник с четири върха става сложно. Многоъгълниците с подобни проблеми се наричат непланарни и могат да създадат сериозни проблеми в компютърната графика, понеже почти всичката графика, която се генерира и обработва в реално време, преобразува абсолютно всички обекти в триъгълници.

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

В Sim City 2000 се използват квадратни мрежи плюс карти на височините. Обърнете внимание че много от наклонените тайлове са разделени на двойки триъгълници, понеже този тайл е непланарен.

Няма никакви проблеми с върховете при триъгълните мрежи.

Простотата

Математически е съвсем разбираемо, че 3 е по-малко от 4 или 6. Това е най-малкият брой върхове, които може да има един многоъгълник и именно затова триъгълниците са най-добрата геометрична фигура за всеки алгоритъм, на който се налага да бъде мащабиран в зависимост от броя на точките или ребрата.

Така например, в моя учебник по Marching Cubes обяснявам, че за да се вземат предвид всички случаи при четириъгълниците в 2D е необходимо да се бъдат създадени 24=16 различни тайлове. Триъгълниците имат два варианта – обърнат нагоре или обърнат надолу и са необходими 23=8 различни тайла. Тоест, и в двата случая получаваме 16 тайла.

Обърнете внимание, че при триъгълниците няма противоречиви случай.

Но това е най опростеният случай. Ако допуснем възможността за завъртане на тайловете, то вариантите при триъгълниците са по-малко – 4 срещу 6. Ако са необходими повече от две възможни значения на всеки от ъглите, то ще имаме 54 срещу 81 или 10 срещу 21 със завъртанията и отраженията.

Тайловете със завъртане, необходими за marching cubes

Освен това, триъгълниците са много добри за линейни интерполации. Трите значения на триъгълника могат лесно да бъдат интерполирани с помощта на барицентричните координати на точките, докато при квадратите се налага използването на билинейна интерполация, която е доста по-сложна. Именно заради тази разлика бе измислен симплекс шума, който замени шума на Перлин. По принцип резултатът от тяхната работа е еднакъв, но при симплекс шума се използва 2D триъгълна мрежа, при която изчисленията са по-леки и хардуерът не се натоварвам много.

Тяхната геометрия е по-добра от тази на шестоъгълниците

Когато работиш с шестоъгълници бързо разбираш, че големи неудобства създават техните ребра, които просто не могат да изградят права линия. Заради тази особеност е невъзможно шестоъгълната мрежа да бъде разделена на редове или колони. И още, не може да се сглоби голям шестоъгълник от няколко по-малки.

Как се използва триъгълната мрежа

Нека да уточним, че има много начини за работа с триъгълните мрежи. Тук ще опиша метода, който лично аз смятам за най-добър. Той е лесен за разбиране и всички негови действия се описват по разбираем начин. Ще използвам триъгълници, които са подредени в редове – единият триъгълник е обърнат нагоре, съседният надолу и т.н. Характерна особеност на този подход е, че дори една подобна триъгълна мрежа да бъде завъртяна на 90 градуса, всичко си остава същото.

Хитрото тук е, че тази триъгълна мрежа да бъде разглеждана като зададена с помощта на три множества равномерно разположени паралелни линии, които са наложени една върху друга:

Пространството между всяка една от тези паралелни линии се наричат ленти (на някои места ивици). Нека да обозначим тези три направление от ленти като a, b и c, а на самите ленти да дадем последователни номера:

По този начин координатите на всеки един триъгълник ще бъдат трите цели числа a, b и c, които ще определят в кои ивици се намира съответния триъгълник. Всичко е наистина съвсем лесно!

Вероятно си задавате въпроса, защо използваме три числа, за да опишем клетка в една 2D мрежа. Просто така ще ни е по-удобно да работим. Ако се опитаме да създадем координатна система от две числа, то в крайна сметка ще ни се наложи да добавим повече изключения за четните и нечетните координати, както и за някои други аспекти. Нещо подобно се използва при работа с шестоъгълните мрежи. Между другото, третата координата е почти излишна, понеже в тази система a + b + c винаги е равно на 1 или 2. Ето защо можем просто да я съхраняваме във вид на булева променлива.

Да допълня, че в тази система няма триъгълник с координати (0, 0, 0) понеже дадох последователни номера на лентите по такъв начин, че точката на началото на координатите е връх, заобиколен от 6 триъгълника в ивиците 0 и 1. Но и при другите начини за номериране на ивиците системата работи по същия начин.

Съседите

Когато се прехвърляме от един триъгълник към друг, то ние пресичаме една от линиите, разделящи лентите. Направих тази система по такъв начин, че при придвижване от триъгълника с върха надолу, ние добавяме към координатите единица. А при излизането от триъгълник с върха нагоре изваждаме единица.

def tri_neighbours(a, b, c):
    """Returns the tris that share an edge with the given tri"""
    points_up = a + b + c == 2
    if points_up:
        return [
            (a - 1, b    , c    ),
            (a    , b - 1, c    ),
            (a    , b    , c - 1),
        ]
    else:
        return [
            (a + 1, b    , c    ),
            (a    , b + 1, c    ),
            (a    , b    , c + 1),
        ]

Центърът на триъгълника

Тъй като преместването към съседния триъгълник винаги е стъпка с точно зададен размер по една от трите ивици, даден триъгълник може бързо да бъде намерен чрез обикновено сумиране на всички стъпки направени в трите направления:

def tri_center(a, b, c):
    """Returns the center of a given triangle in cartesian co-ordinates"""
    return ((       0.5 * a +                      -0.5 * c) * edge_length,
            (-sqrt3 / 6 * a + sqrt3 / 3 * b - sqrt3 / 6 * c) * edge_length)

Разстоянието между триъгълниците

Тъй като всяка стъпка променя координатите с единица, формулата за разстоянието е просто разликата във всяка една от тези координати:

def tri_dist(a1, b1, c1, a2, b2, c2):
    """Returns how many steps one tri is from another"""
    return abs(a1 - a2) + abs(b1 - b2) + abs(c1 - c2)

В кой триъгълник се намира точката

За да се намери триъгълникът, съдържащ зададена точка, необходимо е просто да се определи в кои три ивици се намира триъгълника. Това може да се направи чрез измерване на разстоянието перпендикулярно на лентата от точката на началото на координатите, което също лесно се изчислява с помощта на скаларно произведение и закръгляне на резултата до цяло число:

def pick_tri(x, y):
    """Returns the triangle that contains a given cartesian co-ordinate point"""
    return (
        ceil(( 1 * x - sqrt3 / 3 * y) / edge_length),
        floor((    sqrt3 * 2 / 3 * y) / edge_length) + 1,
        ceil((-1 * x - sqrt3 / 3 * y) / edge_length),
    )

Да напомним, че ceil закръгля дадено число нагоре, а floor закръгля надолу. Не можем просто да закръглим всичките три ленти в едно и също направление, понеже ще възникнат усложнения, например при точката с координати (0, 0), която се намира в ъгъла на шест различни триъгълника.

Други операции

С триъгълните мрежи могат да се правят редица други операции, като например да се измерват разстояния, да се рисуват линии и да се правят завъртания. Всичко е съвсем подробно описано в моя проект в GitHub, който е подробно документиран.

Можете да го сравните с реализацията на същите обекти, но когато се използва шестоъгълна мрежа. Да се работи с триъгълниците е много по-лесно и по-просто в сравнение с шестоъгълниците и това е причината да реализирам много от операциите с шестоъгълници, които преобразувам в триъгълници, пресмятам каквото е необходимо и след това отново ги преобразувам в шестоъгълници.

Надявам се да съм ви убедил, че триъгълната мрежа е един твърде недооценен инструмент.

Процедурно генериране на триъгълна мрежа, извършено от Tessera

 

4 13 гласа
Оценете статията
Абонирай се
Извести ме за
guest
1 Коментар
стари
нови оценка
Отзиви
Всички коментари