forum.boolean.name - Пишем свой LinePick для своего Minecraft

Привет форумчане, спешу поделится полезным опытом. Недавно пытался написать алгоритм собственного пика(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-зад :-D
(пока что делаем это только в уме).
При помощи If Then Else делаем весьма сложное разветвление.

PHP код:


		
			
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-процентного конца обновлю код.

В математической стороне реализации мне помог друг (с)Мостепанюк Вова