Цель этой статьи познакомить новичков с геометрией в игре. Так что не ждите здесь пересечений параллельных прямых и прочих интересных вещей. Здесь будут только базовые знания немного посыпанные формулами и объяснениями на уровне первого класса особо одарённых учеников. Так что заварите себе чаю, возьмите в зубы карандаш для умного вида и погнали.
Когда речь заходит о позиционировании, первым делом необходимо определить точку отсчёта. Игра использует прямоугольную систему координат, которую можно легко понять даже если вы плохо учились в школе.
Зелёные линии это оси. Горизонтальная именуется X или ось абсцисс, вертикальная соответственно Y или ось ординат. В их пересечении располагается точка ноль.
Учтите, что точка ноль не всегда находится в середине карты. При определённой криворукости, она вообще может оказаться за её пределами вследствие того, что при изменении границ карты координаты не сдвигаются относительно рельефа.
Когда речь заходит о расстоянии, то первым на ум приходит расстояние между двумя точками. Но мы не будем сходу окунаться в двумерное пространство, а ограничимся одним измерением, то бишь точками на координатной прямой.
Для того, чтобы вычислить расстояние между двумя точками на координатной прямой необходимо вычислить абсолютную величину разности двух координат.
Говоря проще, необходимо отнять от одной координаты другую и выбросить минус, если он есть. Притом абсолютно не важно, какую координату из какой вычитать. Убедиться в этом вы можете на интерактивной демонстрации.
Как вы могли заметить, формула прекрасно работает вне зависимости от направления оси. Теперь можно воспользоваться теоремой Пифагора и найти расстояние между точками на плоскости.
Если вы не понимаете, при чём здесь треугольники, то эта интерактивная демонстрация вам всё пояснит.
Как видите, у нас всегда получается треугольник ABC, где AB является гипотенузой. Её длину несложно вычислить по теореме Пифагора: AB2 = AC2 + BC2.
В файле blizzard.j находится специально обученная функция:
function DistanceBetweenPoints takes location locA, location locB returns real
local real dx = GetLocationX(locB) - GetLocationX(locA)
local real dy = GetLocationY(locB) - GetLocationY(locA)
return SquareRoot(dx * dx + dy * dy)
endfunction
Если же вы являетесь счастливым обладателем UjAPI, то можете воспользоваться следующими нативками:
native MathDistanceBetweenPoints takes real fromX, real fromY, real toX, real toY returns real native MathDistanceBetweenLocations takes location fromLoc, location toLoc returns real
Когда речь заходит про измерение углов, те, кто учился в школе сразу вспоминают транспортир и разметку от нуля до 360. Это всё прекрасно работает в своей области применения, но когда дело доходит до программирования то все культурные люди переходят на радианы. Они имеют много интересных и полезных геометрических свойств из-за чего в большинстве языков программирования геометрические функции принимают на вход именно радианы.
Для простоты понимания, по сложившейся традиции, наша команда подготовила интерактивную демонстрацию.
Чтобы не запутаться в единицах измерения будет очень полезно запомнить их обозначения:
В ваниле получить угол можно только у юнита:
constant native GetUnitFacing takes unit whichUnit returns real
В UjAPI, естественно, функций будет немного больше:
constant native GetUnitFacing takes unit whichUnit returns real native GetDoodadFacing takes doodad whichDoodad returns real native GetSpecialEffectFacing takes effect whichEffect returns real native GetTrackableFacing takes trackable whichTrackable returns real native GetWidgetFacing takes widget whichWidget returns real native GetDestructableFacing takes destructable whichDestructable returns real native GetItemFacing takes item whichItem returns real native GetProjectileFacing takes projectile whichProjectile returns real native GetFrameSpriteFacing takes framehandle whichFrame returns real
Все эти функции возвращают угол в градусах в диапазоне 0 ... 360. Чтобы перевести их в радианы, можете просто умножить их на константу bj_DEGTORAD или воспользоваться следующей нативкой из UjAPI:
native Deg2Rad takes real degrees returns real
Как вы наверное догадались, у точек нет такого свойства как угол. Под этим обычно понимают минимальный угол между векторами. Если быть точнее, то минимальный угол, на который нужно повернуть вектор, чтоб он был сонаправлен с осью X. Звучит конечно слишком умно, поэтому смотрите на интерактивную демонстрацию и читайте объяснение ниже.
Попытаемся вычислить угол AB, то бишь найти минимальный угол, на который необходимо повернуть точку B вокруг точки A так, чтобы AB совпал с AB2.
Сместим AB таким образом, чтоб A совпала с началом координат. Это несложно. Просто разместим там точку A1.
Разместим точку B1 относительно A1 таким же образом, как и
B находится относительно A. Если вы внимательно посмотрите на
интерактивный пример то быстро догадаетесь как это сделать:
Ну и в завершении, нам нужно вычислить арктангенс с помощью функции Atan2.
Арктангенс это угол между осью X и линией, проведенной из начала координат 0, 0 в точку с координатами x, y. Угол определяется в радианах в диапазоне от -π до π, исключая -π.
Так, как мы уже переместили A в 0, 0, то нам остаётся только передать координаты B1 в функцию:
В файле blizzard.j есть специально обученная функция.
function AngleBetweenPoints takes location locA, location locB returns real
return bj_RADTODEG * Atan2(GetLocationY(locB) - GetLocationY(locA), GetLocationX(locB) - GetLocationX(locA))
endfunction
Для счастливых обладателей UjAPI были добавлены следующие нативки.
native MathAngleBetweenPoints takes real fromX, real fromY, real toX, real toY returns real native MathAngleBetweenLocations takes location fromLoc, location toLoc returns real
Все вышеперечисленные функции возвращают угол в градусах в диапазоне -180 ... 180, с чем не очень удобно работать. Поэтому напишем свою функцию:
function AngleBetweenXY takes real xa, real ya, real xb, real yb returns real
return Atan2(by - ay, bx - ax)
endfunction
Полярная система координат не так сложна в понимании. В отличие от прямоугольной системы координат, точка обозначается не через две координаты, а через расстояние и угол.
Из всех возможных применений такой системы мы рассмотрим только полярное смещение. То бишь способ, как сместить точку на определённое расстояние под определённым углом.
Для лучшего понимания интерактивная демонстрация к вашим услугам.
Чтоб лишний раз не повторяться допустим, что расстояние (len) и угол (rad) AB мы уже вычислили и наша задача сместить точку B в точку B2 на то же расстояние под тем же углом.
Здесь нам опять понадобится смещение A в 0, 0. Можно воспользоваться способом, который мы применяли при вычислении углов:
B1x = Bx - Ax B1y = By - Ay
Хоть этот способ и прост, но он не позволяет нам изменять угол. Вот здесь на помощь приходит полярная система координат. Чтоб найти точку, лежащую на расстоянии (len) под углом (rad) от точки 0, 0 нужно воспользоваться формулой:
B1x = Cos(rad) * len B1y = Sin(rad) * len
Чтоб нить разговора не потерялась, напомню, что мы смещаем точку B в точку B2 на расстояние len под углом rad. На данный момент мы получили точку B1, которая находится на расстоянии len под углом rad от 0, 0. И если прибавить к точке B1 координаты B, то мы получим точку B2, которая находится на расстоянии len под углом rad от B.
Запишем итоговую формулу:
B2x = Cos(rad) * len + Bx B2y = Sin(rad) * len + By
В файле blizzard.j вы можете найти функцию:
function PolarProjectionBJ takes location source, real dist, real angle returns location
local real x = GetLocationX(source) + dist * Cos(angle * bj_DEGTORAD)
local real y = GetLocationY(source) + dist * Sin(angle * bj_DEGTORAD)
return Location(x, y)
endfunction
Она принимает угол в градусах, и создаёт Location, который нужно потом уничтожать во избежание утечек.
В UjAPI тоже есть функции:
native MathPointProjectionX takes real x, real angle, real distance returns real native MathPointProjectionY takes real y, real angle, real distance returns real
Но они так же принимают угол в градусах, что не очень хорошо для ментального здоровья. Посему мы напишем собственные функции с блэкджеком и радианами:
function PolarProjectionX takes real x, real dist, real angle returns real
return Cos(angle) * dist + x
endfunction
function PolarProjectionY takes real y, real dist, real angle returns real
return Sin(angle) * dist + y
endfunction
В нашем случае нормализация это приведение любого значения угла в диапазон от -π до π, исключая -π. Используется редко, но именно здесь логичней всего о ней рассказать пока не забылись знания о полярном смещении.
Рассмотрим бытовую ситуацию - вам нужно нарисовать пентаграмму с центром в точке A и одним из лучей в точке B. Простейшим решением будет найти угол между лучами, в нашем случае это 2π/5, и с помощью полярного смещения нарисовать остальные лучи.
Так как мы уже умеем вычислять расстояние, то осталось только посчитать углы:
Как видите, у некоторых углов значение превышает 2π, то есть полный угол. Для расположений точки на плоскости такой угол вполне годится. Но, когда дело коснётся оборотов, то можно ступить ногами в жир.
Нормализуем все углы и обрамим нашу пентаграмму пятиугольником. Для краткости, обозначим функцию нормализации как N:
Для нормализации угла функций никто не завёз, поэтому мы напишем её руками:
function AngleNormalize takes real angle returns real
if angle > -bj_PI and angle <= bj_PI then
return angle
endif
set angle = ModuloReal(angle + bj_PI, bj_PI * 2)
if angle < 0 then
return angle + bj_PI
else
return angle - bj_PI
endif
endfunction
Угол поворота — это минимальный угол, на который нужно повернуть луч, исходящий из точки O, чтобы он совпал с другим лучом, исходящим из этой же точки.
Мы уже сталкивались с этим при вычислении угла между двумя точками. Только там в роли второго угла выступало положительное направление оси X, здесь же это будет произвольный угол.
Из точки A исходят два луча: AB и AC. Углом поворота D для угла AB по отношению к AC будет такое значение, при котором AB + D = AC.
Можно наивно вычислить D из уравнения AB + D = AC:
Если подвигать точки на интерактивной демонстрации, то можно заметить, что в некоторых случаях абсолютное значение D больше чем π. Это значит, что существует угол, с меньшим абсолютным значением и противоположным знаком. Необходимо только его вычислить:
Для проверки разместим точку E таким образом, что угол AE = AB + D:
Как видите, на интерактивной демонстрации угол AE всегда совпадает с углом AC, но их численные значения не всегда одинаковы.
Напрашивается вопрос, а зачем же это всё нужно? Всё просто:
Как обычно, функций для работы с углами не завезли, поэтому пользуемся собственной функцией:
function AngleOfRotation takes real a, real b returns real
local real d = b - a
if d > bj_PI then
return d - 2 * bj_PI
elseif d < -bj_PI then
return d + 2 * bj_PI
endif
return d
endfunction
Он же наклон прямой численно равен тангенсу угла между положительным направлением оси абсцисс и данной прямой.
Если упростить, то зачастую нужно работать не с двумя точками, а с прямой, проходящей через них. Если вычислять угол между точками, то важен порядок точек, что не применимо в случае прямой. Посему требуется универсальное число, обозначающее наклон прямой.
Вычисляется наклон довольно просто:
k = Δy / Δx
Если вы не знакомы с дельтой, то вкратце, это разница между чем либо. В нашем случае между координатами:
Если вы беспокоитесь о порядке точек, то легко можно убедиться, что он не важен:
Учтите, что параллельная оси Y прямая имеет наклон равный бесконечности. В языках которые её не поддерживают это может грозить многими печалями.
На интерактивной демонстрации выше вы можете наблюдать две прямые: AB и AC и их наклон обозначенный соответственно kAB и kCD. У него есть довольно интересные свойства.
Прямые перпендикулярны при:
kAB * kCD = -1
Прямые параллельны при:
kAB - kCD = 0
В голом виде здесь вычислять ничего не требуется. Наклон необходим для дальнейших вычислений всякого. Но если вам вдруг понадобится вычисление параллельности/перпендикулярности прямых, то вы всегда можете написать об этом.
Для всевозможных кастов по прямой зачастую используют всевозможные алгоритмы разной степени унылости. Пора прекратить это безобразие.
В данном примере у нас есть прямая, заданная двумя точками A, B и точка С. Функция, приведённая ниже вычислит точку С1, которая является кратчайшим расстоянием от прямой AB до точки C.
Как вы уже наверно догадались, разработчикам абсолютно наплевать на геометрию и функции придётся писать руками:
globals
real LinePointPerpendicularX = 0
real LinePointPerpendicularY = 0
endglobals
function LinePointPerpendicular takes real xa, real ya, real xb, real yb, real px, real py returns nothing
local real m
local real c
local real mPerpendicular
local real cPerpendicular
// Прямая, параллельная оси X
if ya == yb then
set LinePointPerpendicularX = px
set LinePointPerpendicularY = ya
return
endif
// Прямая, параллельная оси Y
if xa == xb then
set LinePointPerpendicularX = xa
set LinePointPerpendicularY = py
return
endif
set m = (yb - ya) / (xb - xa) // Находим угловой коэффициент прямой AB
set c = ya - m * xa // Находим свободный член c уравнения прямой AB
set mPerpendicular = -1 / m // Находим угловой коэффициент перпендикулярной прямой
set cPerpendicular = py - mPerpendicular * px // Находим свободный член c уравнения перпендикулярной прямой, проходящей через точку (x, y)
// Находим точку пересечения перпендикулярной прямой с прямой AB
set LinePointPerpendicularX = (cPerpendicular - c) / (m - mPerpendicular)
set LinePointPerpendicularY = m * LinePointPerpendicularX + c
endfunction
Данная функция принимает координаты двух точек, обозначающих прямую xa, ya, xb, yb, координаты точки px, py и устанавливает в глобальных переменных координаты искомой точки.
Далее вы можете воспользоваться нативкой, которая учитывает коллизию юнита:
constant native IsUnitInRangeXY takes unit whichUnit, real x, real y, real distance returns boolean
Или же просто вычислить расстояние и использовать его в своих целях. Только не забывайте, что прямая бесконечна и вам может понадобиться угол поворота.
Для работы с молниями, и прочими прямыми, может понадобиться найти их пересечения чтоб заклинания не выглядели уныло.
Чем дальше в лес, тем толще партизаны и всё яростней разработчики доказывают, что функции для работы с геометрией придётся писать руками:
globals
real LineSegmentIntersectX = 0
real LineSegmentIntersectY = 0
boolean LineSegmentIntersectA = false
boolean LineSegmentIntersectB = false
endglobals
function LineSegmentIntersect takes real ax, real ay, real bx, real by, real cx, real cy, real dx, real dy returns boolean
local real a
local real b
local real na
local real nb
local real d = (dy - cy) * (bx - ax) - (dx - cx) * (by - ay)
set LineSegmentIntersectX = 0
set LineSegmentIntersectY = 0
set LineSegmentIntersectA = false
set LineSegmentIntersectB = false
if d == 0 then
return false
endif
set a = ay - cy
set b = ax - cx
set na = (dx - cx) * a - (dy - cy) * b
set nb = (bx - ax) * a - (by - ay) * b
set a = na / d
set b = nb / d
set LineSegmentIntersectX = ax + a * (bx - ax)
set LineSegmentIntersectY = ay + a * (by - ay)
set LineSegmentIntersectA = a > 0 and a < 1 // Находится ли точка пересечения на первом отрезке
set LineSegmentIntersectB = b > 0 and b < 1 // Находится ли точка пересечения на втором отрезке
return true
endfunction
Функция принимает восемь аргументов с координатами четырёх точек задающих два отрезка и возвращает логическую, указывающую пересекаются ли прямые в одной и только одной точке. При этом в глобалках устанавливаются точка пересечения и находится ли точка пересечения на каждом отрезке.
Подозреваю, что вы можете запутаться, в каком порядке передавать аргументы. Посему объясню на примере точек из кропотливо сделанной интерактивной демонстрации:
Ax Ay Bx By Cx Cy Dx Dy
В таком случае LineSegmentIntersectA будет указывать, лежит ли точка пересечения на отрезке AB и соответственно LineSegmentIntersectB на CD.
Зачастую стандартных прямоугольников не хватает и хочется чего-то более интересного. Например, произвольных многоугольников. Для этого нам необходимо решить задачу о принадлежности точки многоугольнику, которая имеет несколько решений в зависимости от требуемого поведения при работе с самопересекающимися многоугольниками.
Мы выбрали решение, требующее меньше всего вычислений. Пускаем из искомой точки луч параллельно оси X и считаем количество пересечений с рёбрами. Если это количество чётное, то точка находится снаружи. Если нечётное, то внутри.
Так же мы добавили дополнительную проверку, принадлежит ли точка ребру, чтоб избежать неопределённого поведения в отдельных случаях.
Так как волшебный JASS не даёт передавать массивы в функцию, то мы заморочимся и напишем свой менеджер многоугольников на хэштаблицах:
globals
hashtable PolygonHT = InitHashtable()
endglobals
function PolygonDestroy takes integer index returns nothing
call FlushChildHashtable(PolygonHT, index)
endfunction
function PolygonAddPoint takes integer index, real x, real y returns nothing
local integer cursor
local integer idx
if HaveSavedInteger(PolygonHT, index, 0) then
set cursor = LoadInteger(PolygonHT, index, 0)
else
set cursor = -1
endif
set cursor = cursor + 1
set idx = cursor * 2
call SaveReal(PolygonHT, index, idx, x)
call SaveReal(PolygonHT, index, idx + 1, y)
call SaveInteger(PolygonHT, index, 0, cursor)
endfunction
function PolygonCountPoint takes integer index returns integer
if HaveSavedInteger(PolygonHT, index, 0) then
return LoadInteger(PolygonHT, index, 0) + 1
else
return 0
endif
endfunction
function PolygonEdgeContainPoint takes real ax, real ay, real bx, real by, real px, real py returns boolean
if (py - ay) * (bx - ax) - (px - ax) * (by - ay) != 0 then
return false
endif
return RMinBJ(ax, bx) <= px and px <= RMaxBJ(ax, bx) and RMinBJ(ay, by) <= py and py <= RMaxBJ(ay, by)
endfunction
function PolygonContainPoint takes integer index, real x, real y returns boolean
local integer count = PolygonCountPoint(index)
local boolean inside = false
local integer i = 0
local integer j = count - 1
local real ax
local real ay
local real bx
local real by
if count < 3 then
return false
endif
loop
exitwhen i >= count
set ax = LoadReal(PolygonHT, index, i * 2)
set ay = LoadReal(PolygonHT, index, i * 2 + 1)
set bx = LoadReal(PolygonHT, index, j * 2)
set by = LoadReal(PolygonHT, index, j * 2 + 1)
// Дополнительная проверка на пересечение с ребром.
// Можно безболезненно удалить для повышения производительности.
if PolygonEdgeContainPoint(ax, ay, bx, by, x, y) then
return true
endif
if (ay > y) != (by > y) and x < ((bx - ax) * (y - ay)) / (by - ay) + ax then
set inside = not inside
endif
set j = i
set i = i + 1
endloop
return inside
endfunction
Прекрасное определение выпуклой оболочке дано в википедии, им мы и воспользуемся:
Представьте себе доску, в которую вбито — но не по самую шляпку — много гвоздей. Возьмите верёвку, свяжите на ней скользящую петлю (лассо) и набросьте её на доску, а потом затяните. Верёвка окружает все гвозди, но касается она только некоторых, самых внешних. В таком положении петля и окружённая ей область доски являются выпуклой оболочкой для всей группы гвоздей.
Для построения воспользуемся алгоритмом Quickhull, или, говоря по-русски, алгоритмом быстрой оболочки.
Подробнее можете почитать на официальном сайте алгоритма, нам важна только его сложность: O(N log N).
Так как волшебный JASS не даёт передавать массивы в функцию, то мы заморочимся и напишем свой менеджер точек на массивах:
globals
real array ConvexHullInputX
real array ConvexHullInputY
integer array ConvexHullInputIndex
integer ConvexHullInputCursor = -1
real array ConvexHullX
real array ConvexHullY
integer ConvexHullCursor = -1
endglobals
function ConvexHullInputAdd takes real x, real y returns nothing
set ConvexHullInputCursor = ConvexHullInputCursor + 1
set ConvexHullInputIndex[ConvexHullInputCursor] = ConvexHullInputCursor
set ConvexHullInputX[ConvexHullInputCursor] = x
set ConvexHullInputY[ConvexHullInputCursor] = y
endfunction
function ConvexHullInputSortSwap takes integer i, integer j returns nothing
local integer temp = ConvexHullInputIndex[i]
set ConvexHullInputIndex[i] = ConvexHullInputIndex[j]
set ConvexHullInputIndex[j] = temp
endfunction
function ConvexHullInputSort takes integer low, integer high returns nothing
local integer i = low - 1
local integer j = low
local integer ji
local real jx
local real jy
local integer pi
local real px
local real py
if low >= high then
return
endif
loop
exitwhen j >= high
set ji = ConvexHullInputIndex[j]
set jx = ConvexHullInputX[ji]
set jy = ConvexHullInputY[ji]
set pi = ConvexHullInputIndex[high]
set px = ConvexHullInputX[pi]
set py = ConvexHullInputY[pi]
if jx < px or jx == px and jy < py then
set i = i + 1
call ConvexHullInputSortSwap(i, j)
endif
set j = j + 1
endloop
call ConvexHullInputSortSwap(i + 1, high)
call ConvexHullInputSort(low, i)
call ConvexHullInputSort(i + 2, high)
endfunction
function ConvexHullRemoveMiddle takes real cx, real cy returns boolean
local real ax = ConvexHullX[ConvexHullCursor - 1]
local real ay = ConvexHullY[ConvexHullCursor - 1]
local real bx = ConvexHullX[ConvexHullCursor]
local real by = ConvexHullY[ConvexHullCursor]
local real abx = ax - bx
local real aby = ay - by
local real cbx = cx - bx
local real cby = cy - by
local real cross = abx * cby - aby * cbx
return cross < 0 or cross == 0 and abx * cbx + aby * cby <= 0
endfunction
function ConvexHull takes nothing returns nothing
local real n = ConvexHullInputCursor + 1
local integer i = 0
local integer j
local integer ji
local real jx
local real jy
call ConvexHullInputSort(0, ConvexHullInputCursor)
set ConvexHullCursor = -1
loop
exitwhen i >= 2 * n
if i < n then
set j = i
else
set j = 2 * n - 1 - i
endif
set ji = ConvexHullInputIndex[j]
set jx = ConvexHullInputX[ji]
set jy = ConvexHullInputY[ji]
loop
exitwhen ConvexHullCursor < 1 or not ConvexHullRemoveMiddle(jx, jy)
set ConvexHullCursor = ConvexHullCursor - 1
endloop
set ConvexHullCursor = ConvexHullCursor + 1
set ConvexHullX[ConvexHullCursor] = jx
set ConvexHullY[ConvexHullCursor] = jy
set i = i + 1
endloop
set ConvexHullCursor = ConvexHullCursor - 1
endfunction