Raycast на кубической сетке?
В настоящее время я пишу клон Minecraft в Unity в качестве своего любимого проекта и пытаюсь реализовать для него raycasts, чтобы знать, на какой блок смотрит игрок (я буду использовать raycasts и для других целей). Мир игры представляет собой трехмерную сетку идеальных единичных кубов. Каждый элемент сетки либо сплошной, либо нет. Я хочу иметь возможность выстрелить лучом из любой точки моего мира и получить точку, в которой этот луч попадает на поверхность первого сплошного блока на своем пути.
Вот псевдокод С# того, как примерно выглядит моя игра:
// An aproximation of what Unity's Vector3 looks like.
public struct Vector3
{
public float x, y, z;
}
public class World
{
public bool[,,] blocks;
public bool IsSolid(Vector3 pos) // i.e. if pos is inside a solid block
{
return blocks[Math.Floor(pos.x), Math.Floor(pos.y), Math.Floor(pos.z)]
}
public Vector3 Raycast(Vector3 origin, Vector3 direction)
{
// some algorithm, that returns the point at which ray hits a solid block
}
}
Обратите внимание, что координаты любого Vector3 не могут быть целыми числами, вполне возможно, что лучи начинаются (или заканчиваются) с дробными координатами. Для простоты вы можете (или не можете) предположить, что мир бесконечен и луч всегда в конце концов попадет в какой-то блок. Помните, что Raycast() должна возвращать точку, в которой луч попадает на поверхность куба.
Какой лучший алгоритм я могу использовать для этого? Мои приоритеты (по порядку):
- Скорость — создание рейкаста должно быть быстрым
- Элегантность — алгоритм должен быть достаточно простым и лаконичным.
- Универсальность — алгоритм должен легко модифицироваться (т. е. добавлять к нему дополнительную функциональность).
Вот Q / A для некоторых возможных вопросов:
В: Почему бы не использовать нативные коллайдеры и рейкасты Unity?
A: Коллайдеры и raycast Unity слишком медленные и не оптимизированы для моих нужд, более того, это ни в коем случае не элегантно или универсально.
В: Вам нужна реализация алгоритма или просто основная концепция?
О: Меня вполне устраивает простое понимание основ аглоритма, но я был бы очень признателен за его реализацию (желательно на C#).
Вероятно, вам нужен не более быстрый генератор лучей, а лучшая структура данных, такая как дерево октябрей, чтобы сократить количество тестов пересечения.
@ MrSmith42 Ну, это довольно сложно. У меня есть рабочее решение, но оно довольно запутанное и сложное для понимания. Делиться этим только запутает всех, так что я бы предпочел этого не делать,
@rotgers Я не очень понимаю, что именно вы имеете в виду, не могли бы вы рассказать мне об этом подробнее, пожалуйста?
Tbh, если бы у вас были твердые и нетвердые слои и raycast только на сплошных слоях. Затем хит говорит вам, что и где он попал. Зачем изобретать велосипед
Ответы 1
Вот несколько основных принципов. Вам нужно будет достаточно хорошо разбираться в линейной алгебре, чтобы хотя бы попытаться это сделать, а также прочитать и понять, как работает пересечение луча и плоскости .
Ваш луч начнется внутри куба и попадет на одну из 6 граней на пути из куба. В обычных случаях мы можем быстро исключить три грани, просто проверив, указывает ли направление луча в том же направлении, что и грань куба. Это делается путем проверки знака скалярного произведения между векторами. Чтобы найти первое попадание из трех оставшихся граней, мы проводим тест пересечения с соответствующей плоскостью и выбираем ближайшую. Если вы знаете грань попадания, вы знаете, в какой куб она попала. Если этот куб пуст, вы повторяете процесс, пока не найдете непустой куб. Вы также можете добавить некоторые проверки, чтобы избежать крайних случаев, например, исключить все плоскости, параллельные вашему лучу, как можно раньше.
Однако, чтобы получить реальную скорость, вам действительно нужна какая-то древовидная структура, чтобы уменьшить количество выполняемых проверок. Есть много альтернатив, kd-деревья, r-деревья и т. д., но в этом конкретном случае я, вероятно, рассмотрю разреженное октодерево. Это означает, что ваши кубы будут частью более крупных секций 2x2x2, где вся секция может быть помечена как пустая, заполненная, частично заполненная и т. д. Эти секции также будут сгруппированы в более крупные секции 2x2x2 и так далее, пока вы не достигнете максимального размера, который либо содержит всю вашу игровую зону или одну независимо загружаемую единицу вашей игровой области и имеет некоторую логику для тестирования нескольких единиц, если это необходимо.
Рейкастинг выполняется более или менее так же, как и в октодереве, как и в простом случае, за исключением того, что теперь у вас есть кубы переменного размера. И когда вы попадаете в лицо, вам нужно пройти по дереву, чтобы найти следующий куб для проверки.
Но чтобы действительно сделать хорошо оптимизированную реализацию этого, требуется немало опыта, как в задействованных концепциях, так и в языке и аппаратном обеспечении. Вам также может понадобиться понимание структуры вашего реального игрового мира, поскольку могут быть неочевидные ярлыки, которые вы можете использовать, чтобы значительно повысить производительность. Таким образом, не гарантируется, что ваша реализация будет быстрее, чем встроенные единства.
Это отличный ответ, спасибо!
Что вы пробовали / исследовали до сих пор? Поделитесь своими идеями/находками/кодом.