Привет форумчане, спешу поделится полезным опытом. Недавно пытался написать алгоритм собственного пика(Camera Pick) для игры похожей на Майнкрафт. Оказалось это сложней чем я рассчитывал, но все же это вышло. Поэтому хочу описать свой метод для посторонних людей с похожими целями. Также хочу добавить моя статья написана с целью помочь разобраться тем, кто не знает как это реализовать, если у вас есть лучшие методы, то я жду от вас либо конструктивной критики, либо помощи в улучшении моей статейки, либо свою собственную статью.
К читающему есть пара требований. Элементарное понимание функций среды программирования, что такое вектор и хоть немного тригонометрии.
И так. Начнем с теории. В моем случае мир 3-х мерный и каждый кубик имеет размер 1х1х1 то есть каждый персонаж имеет координаты X#,Y#,Z# - и все они с типа Float с плавающей запятой. Сделав для координат позиции: Floor(X#),Floor(Y#),Floor(Z#) - мы отбрасываем дробовую часть и узнаем адрес клетки в мире. Поэтому все у кого масштаб кубика не ровен 1х1х1 обрели себя на вечный гемор, и советую перейти на единичные размеры кубика, в случае если это не будет перечить каким либо вашим собственным идеям, или задумкам. Также есть следующее. В меру ограниченности моей карты мне весьма удобно держать все кубики не в октодереве, а в массиве размеры которого равны размерам карты. То есть скорей всего в этих методах у нас с вами может быть различие, но всегда вы сможете подумать и модернизировать свой алгоритм под свою ситуацию. А я постараюсь описать саму логику алгоритма а не его код для копипаста. Поэтому не пытайтесь скопировать какой либо код, без должного понимания у вас ничего не получится. Я же в свою очередь попробую как можно нагляднее изобразить принцип алгоритма. Что б было проще соображать, для начала попробуем рассматривать ситуацию как 2д сетку, а потом переведем все в 3д.
Допустим есть у нас такая вот ситуация в игре, типочек смотрит на камень и пытается его копнуть: (важные точки для алгоритма отмечены)
Важно помнить что на самом деле у каждой точки по 3 координаты. Я для схематики и простоты наглядного примера я использую только 2.
Теперь опишу нужные точки:
Source(x1#,z1#)-Точная позиция начальной точки, в нашем случае это точная точка камеры.
Dest(x2#,z2#)-Точка которая находится на расстоянии на которое персонаж может копать (DiggingRange)
p1(p1x%,P1z%)-Теперь несколько важных точек которые мы можем узнать так: p1x%=Floor(X1#) P1z%=Ceil(Z1#)
p2(p2x%,P2z%)-p2x%=Ceil(x1#) P2z%=Ceil(Z1#)
p3(p3x%,P3z%)-p3x%=Ceil(x1#) P3z%=Floor(Z1#)
p4(p4x%,P4z%)-p4x%=Floor(X1#) P4z%=Floor(Z1#)
p5(p5x#,p5z#)-неизвестная нам пока точка, которая находится в месте на которое мы ткнули мышкой.
Координаты этой точки должны быть аналогом блицевским PickedX#(),PickedY#(),PickedZ#()
Как я и говорил, в случае если ваш стандарт кубика не 1х1х1 - нужно будит все переделывать под свой масштаб(просто вызовом Floor(X1#) мы не получим координаты нужной точки, как в прочем и другими такими вызовами), и код будет другим, но думаю написать это не должно составить труда. А точки Source(x1#,z1#) и Dest(x2#,z2#) образуют собой вектор Vector(Vx#,Vz#) где:
Vx#=x2#-x1#
Vz#=z2#-z1#
Сразу опишу функцию, что б было понятно какие данные являются входными: Function Pick%(X1#,Z1#,Vx#,Vz#) - другими словами аналог блицовскому LinePick. Располагая данными выше опишу сам алгоритм по шагам опираясь на этот рисунок:
Проверить блок под номером 1 - проще простого, мы на нем стоим и знаем его координаты, делаем адрес блока: Floor(X#),Floor(Y#),Floor(Z#) и если он пуст - продолжаем работу. Методом перебора 2, 3 и т.д. кубов и постоянно сверяемся пустые ли они, а если нет, возвращаем их оканчивая работу функции. Вся соль заключается в том, как располагая точками выше определить какие кубы проткнул вектор?
Начнем с того, что б узнать какую из сторон куба номер 1 проткнул вектор. Есть 4 варианта левую, правую, переднюю, заднюю (вид сверху, поэтому верхнюю и нижнюю пока что игнорим) присваиваем сторонам соответственные индексы:
1-лево
2-право
3-перед
4-зад
(пока что делаем это только в уме).
При помощи If Then Else делаем весьма сложное разветвление.
If VZ>0
If VX>0
;В этой ситуации теоретически возможны 2 варианта.
;Вектор проткнет либо перед, либо право
Else
If VX=0
;Тут он точно проткнет только перед
Else
;Перед, или лево
EndIf
EndIf
Else
If VZ=0
If VX>0
;Точно только право
Else
If VX=0
;Ничего не проткнет
Else
;Точно только лево
EndIf
EndIf
Else
If VX>0
;Право, или низ
Else
If VX=0
;Только низ
Else
;Лево, или низ.
EndIf
EndIf
EndIf
EndIf
Теперь мы сделали все возможные варианты (кроме верхней и нижней сторон, но пока отложим их). Теперь стоя в этом тупике, на нужно определить намного меньше чем раньше, какую из ДВУХ сторон проткнет вектор, а не из ЧЕТЫРЕХ возможных. Вот теперь нам на помощь и приходят точки:
p1(p1x%,P1z%) где p1x%=Floor(X1#) P1z%=Ceil(Z1#)
p2(p2x%,P2z%) где p2x%=Ceil(x1#) P2z%=Ceil(Z1#)
p3(p3x%,P3z%) где p3x%=Ceil(x1#) P3z%=Floor(Z1#)
p4(p4x%,P4z%) где p4x%=Floor(X1#) P4z%=Floor(Z1#)
В каждой из выше возможных ситуаций нам нужна лишь 1 из 4-х точек. И каждый раз эта точка будет той, что стоит между 2 теоретически возможными сторонами. Пример:
Возможно вектор проткнет либо перед, либо право - нужна верхняя правая точка что соответствует точке p2(p2x%,P2z%)
п.с. В нашем случае как на рисунках нам именно эта точка и нужна. Переменные и Vx#>0, и Vz#>0
Теперь располагая информацией выше можем свести алгоритм до использования только этих переменных
Source(x1#,z1#)
Vector(Vx#,Vz#)
p2(p2x%,P2z%)
Попробую изобразить рисунком данный пример:
Серым цветом закрашена зона где вектор не когда не окажется при Vx#>0 и Vz#>0
Вы должны понимать, что в ситуации, когда вектор проткнет либо зад, либо лево (Vx#<0 и Vz#<0) - ситуация будет другой, и нужна будет уже точка не p2(p2x%,P2z%), а точка p4(p4x%,P4z%). Другими словами в точке Source(x1#,z1#) пространство делится на 4 области двумя перпендикулярами какие проходят параллельно осям OX и OZ. Отсюда и строятся предположения, какие возможные стороны будут проткнуты.
Далее превращаем Source(x1#,z1#) и p2(p2x%,P2z%) в новый вектор EdgeVector(eVx#,eVz#)
eVx#=p2x%-x1#
eVz#=P2z%-z1#
И смотрим:
Что б узнать наверняка, какую сторону проткнет вектор, нужно узнать косинус угла вектора. Попробую сделать сложный рисунок. Надеюсь вы его поймете:
Теперь прокомментирую происходящее.
У нас есть 3 точки Source(x1#,z1#) p2(p2x%,P2z%) Dest(x2#,z2#)
Которые создали 2 вектора Vector(Vx#,Vz#) и EdgeVector(eVx#,eVz#)
В математике есть кроме Декартовой сис-мы координат еще и полярная. В ней каждая точка имеет 2 компонента. Пример: Point(Lenght,Angle) Lenght-длинна вектора который соединяет точку с началом координат (0,0) Angle-угол, на который повернут вектор. У нас в алгоритме будет использовано нечто подобное. Как видно я на круге отложил 2 точки. Эти точки показывают угол на который повернут каждый вектор. Осталось найти косинус угла каждого вектора. Если косинус Vector(Vx#,Vz#) больший за косинус EdgeVector(eVx#,eVz#), значит вектор проткнет правую сторону. Если наоборот, то переднюю. Формула что б узнать косинус угла вектора:
п.с. Не знаю как по русски сказать "Скалярный" короче когда вектор множишь на вектор и выходит одно число.
Скалярное воспроизведении векторов разделено на воспроизведение их модулей равно косинусу угла между ними. За этой формулой находим косинус угла между векторами и сравниваем их.
Вот необходимые данные:
Вот решение:
Вот попробую анимационно изобразить роботу этой части алгоритма:
Думаю все логично и понятно. Теперь когда мы знаем сторону куба которую проткнет вектор мы сможем вычислить нашу загадочную точку p5(p5x#,p5z#), которая как я говорил имеет координаты служащие аналогом блицевским PickedX#(),PickedY#(),PickedZ#(). Найти мы ее можем потому, что она лежит на прямой концом и началом которой являются точки Source(x1#,z1#) и Dest(x2#,z2#), а зная какой стороне куба принадлежит эта точка мы будем знать одну из координат этой точки.
Если пробита правая сторона куба Известная координата будет p5x#=p2x%
Если пробита верхняя сторона куба известная координата будет p5z#=P2z%
Найти недостающие координаты мы можем при помощи не сложных уравнений:
Тут и пригодится элементарные знания математики, что б вывести из следующих формул необходимые:
(X2-X1)/Vx=(Y2-Y1)/Vy
(X2-X1)/Vx=(Z2-Z1)/Vz
(Y2-Y1)/Vy=(Z2-Z1)/Vz
Например нам известно, что вектор проткнул правую сторону. Формулы должны выглядеть так:
p5x#=p2x%
p5y#=VY*(p5x-X1)/VX+Y1
p5Z#=VZ*(p5y-Y1)/VY+Z1
Вот теперь почти все готово. Единственное про что мы забыли это посчитать это не протыкает ли вектор верх, или низ куба. Делается это примерно также как и с другими сторонами. После этого мы зацикливаем функцию, и делаем в нужный момент выход из нее.
Излагаю свой код функции, но он еще не на 100% отлажен. Хотя пробовал в деле, кубики в моей игре он уже рубать способен, отладка идет в сторону, что б при ее помощи вычислять передвижение персонажа по локации.
п.с. Когда доделаю до 100-процентного конца обновлю код.
;Описываем переменные, какие мы будем использовать вне функции
Global PickX#
Global PickY#
Global PickZ#
Global PickVx#
Global PickVy#
Global PickVz#
Function Pick%(PointX#,PointY#,PointZ#,VectorX#=0,VectorY#=0,VectorZ#=0)
Local CosAngle#,CosEdgeVector#
Local PointVectorX#,PointVectorZ#,PointVectorY#
Local Side=0
Local X2#,Y2#,Z2#
Local X#=PointX
Local Y#=PointY
Local Z#=PointZ
Local VX#=VectorX
Local VY#=VectorY
Local VZ#=VectorZ
Repeat
:Если вектор вообще не выходит из куба (слишком короткий) - выходим из функции.
If Floor(X+VX)=Floor(X) And Floor(Y+VY)=Floor(Y) And Floor(Z+VZ)=Floor(Z)
PickX=X+VX
PickY=Y+VY
PickZ=Z+VZ
PickVx=VX
PickVy=VY
PickVz=VZ
Return World(Floor(X),Floor(Y),Floor(Z))
EndIf
If VZ>0
If VX>0
CosAngle=VX/(Sqr(VX^2+VZ^2)*1.0)
PointVectorX=Ceil(X)-X
PointVectorZ=Ceil(Z)-Z
CosEdgeVector=PointVectorX/(Sqr(PointVectorX^2+PointVectorZ^2))
If CosAngle>CosEdgeVector
;=========================================================================Right side
Side=2
Else
;=========================================================================Front side
Side=5
EndIf
Else
If VX=0
;=========================================================================Front side
Side=5
Else
CosAngle=VX/(Sqr(VX^2+VZ^2)*1.0)
PointVectorX=Floor(X)-X
PointVectorZ=Ceil(Z)-Z
CosEdgeVector=PointVectorX/(Sqr(PointVectorX^2+PointVectorZ^2))
If CosAngle<CosEdgeVector
;=========================================================================Left side
Side=1
Else
;=========================================================================Front side
Side=5
EndIf
EndIf
EndIf
Else
If VZ=0
If VX>0
;=========================================================================Right side
Side=2
Else
If VX=0
Side=0
Else
;=========================================================================Left side
Side=1
EndIf
EndIf
Else
If VX>0
CosAngle=VX/(Sqr(VX^2+VZ^2)*1.0)
PointVectorX=Ceil(X)-X
PointVectorZ=Floor(Z)-Z
CosEdgeVector=PointVectorX/(Sqr(PointVectorX^2+PointVectorZ^2))
If CosAngle>CosEdgeVector
;=========================================================================Right side
Side=2
Else
;=========================================================================Back side
Side=6
EndIf
Else
If VX=0
;=========================================================================Back side
Side=6
Else
CosAngle=VX/(Sqr(VX^2+VZ^2)*1.0)
PointVectorX=Floor(X)-X
PointVectorZ=Floor(Z)-Z
CosEdgeVector=PointVectorX/(Sqr(PointVectorX^2+PointVectorZ^2))
If CosAngle<CosEdgeVector
;=========================================================================Left side
Side=1
Else
;=========================================================================Back side
Side=6
EndIf
EndIf
EndIf
EndIf
EndIf
;Теперь, когда мы определили какую сторону пробивает вектор, определим, не пробивает ли он верх или низ?
If VY<>0
If VY>0
Select True
Case Side=1 Or Side=2
CosAngle=VX/(Sqr(VX^2+VY^2)*1.0)
PointVectorY=Ceil(Y)-Y
If Side=1
PointVectorX=Floor(X)-X
CosEdgeVector=PointVectorX/(Sqr(PointVectorX^2+PointVectorY^2)*1.0)
If CosAngle>CosEdgeVector
;=========================================================================Up side
Side=3
EndIf
Else
PointVectorX=Ceil(X)-X
CosEdgeVector=PointVectorX/(Sqr(PointVectorX^2+PointVectorY^2)*1.0)
If CosAngle<CosEdgeVector
;=========================================================================Up side
Side=3
EndIf
EndIf
Case Side=5 Or Side=6
CosAngle=VZ/(Sqr(VZ^2+VY^2)*1.0)
PointVectorY=Ceil(Y)-Y
If Side=5
PointVectorZ=Ceil(Z)-Z
CosEdgeVector=PointVectorZ/(Sqr(PointVectorZ^2+PointVectorY^2)*1.0)
If CosAngle<CosEdgeVector
;=========================================================================Up side
Side=3
EndIf
Else
PointVectorZ=Floor(Z)-Z
CosEdgeVector=PointVectorZ/(Sqr(PointVectorZ^2+PointVectorY^2)*1.0)
If CosAngle>CosEdgeVector
;=========================================================================Up side
Side=3
EndIf
EndIf
Case Side=0
;=========================================================================Up side
Side=3
End Select
Else
Select True
Case Side=1 Or Side=2
CosAngle=VX/(Sqr(VX^2+VY^2)*1.0)
PointVectorY=Floor(Y)-Y
If Side=1
PointVectorX=Floor(X)-X
CosEdgeVector=PointVectorX/(Sqr(PointVectorX^2+PointVectorY^2)*1.0)
If CosAngle>CosEdgeVector
;=========================================================================Down side
Side=4
EndIf
Else
PointVectorX=Ceil(X)-X
CosEdgeVector=PointVectorX/(Sqr(PointVectorX^2+PointVectorY^2)*1.0)
If CosAngle<CosEdgeVector
;=========================================================================Down side
Side=4
EndIf
EndIf
Case Side=5 Or Side=6
CosAngle=VZ/(Sqr(VZ^2+VY^2)*1.0)
PointVectorY=Floor(Y)-Y
If Side=5
PointVectorX=Ceil(Z)-Z
CosEdgeVector=PointVectorZ/(Sqr(PointVectorZ^2+PointVectorY^2)*1.0)
If CosAngle<CosEdgeVector
;=========================================================================Down side
Side=4
EndIf
Else
PointVectorX=Floor(Z)-Z
CosEdgeVector=PointVectorZ/(Sqr(PointVectorZ^2+PointVectorY^2)*1.0)
If CosAngle>CosEdgeVector
;=========================================================================Down side
Side=4
EndIf
EndIf
Case Side=0
;=========================================================================Down side
Side=4
End Select
EndIf
Else
If Side=0 Return 0
EndIf
;Зная точную сторону вычисляем точку пика
Select Side
Case 1
X2=Floor(X)-.001
Y2=VY*(X2-X)/VX+Y
Z2=VZ*(Y2-Y)/VY+Z
VX=VX-(X2-X)
VY=VY-(Y2-Y)
VZ=VZ-(Z2-Z)
X=X2
Y=Y2
Z=Z2
Case 2
X2=Ceil(X)+.001
Y2=VY*(X2-X)/VX+Y
Z2=VZ*(Y2-Y)/VY+Z
VX=VX-(X2-X)
VY=VY-(Y2-Y)
VZ=VZ-(Z2-Z)
X=X2
Y=Y2
Z=Z2
Case 3
Y2=Ceil(Y)+.001
Z2=VZ*(Y2-Y)/VY+Z
X2=VX*(Z2-Z)/VZ+X
VX=VX-(X2-X)
VY=VY-(Y2-Y)
VZ=VZ-(Z2-Z)
X=X2
Y=Y2
Z=Z2
Case 4
Y2=Floor(Y)-.001
Z2=VZ*(Y2-Y)/VY+Z
X2=VX*(Z2-Z)/VZ+X
VX=VX-(X2-X)
VY=VY-(Y2-Y)
VZ=VZ-(Z2-Z)
X=X2
Y=Y2
Z=Z2
Case 5
Z2=Ceil(Z)+.001
X2=VX*(Z2-Z)/VZ+X
Y2=VY*(X2-X)/VX+Y
VX=VX-(X2-X)
VY=VY-(Y2-Y)
VZ=VZ-(Z2-Z)
X=X2
Y=Y2
Z=Z2
Case 6
Z2=Floor(Z)-.001
X2=VX*(Z2-Z)/VZ+X
Y2=VY*(X2-X)/VX+Y
VX=VX-(X2-X)
VY=VY-(Y2-Y)
VZ=VZ-(Z2-Z)
X=X2
Y=Y2
Z=Z2
Default
RuntimeError "Something wrong!!!"
End Select
;Если наткнулись на твердую породу или чтото еще - выходим из функции.
If World(Floor(X),Floor(Y),Floor(Z))<>0
PickX=X
PickY=Y
PickZ=Z
PickVx=X-PointX
PickVy=Y-PointY
PickVz=Z-PointZ
Return World(Floor(X),Floor(Y),Floor(Z))
EndIf
Forever
End Function
В математической стороне реализации мне помог друг (с)Мостепанюк Вова