Блог

Я занимался разработкой некоторых плагинов Minecraft Bukkit и в настоящее время работаю над чем-то, где мне нужно иметь возможность определять «объем» пространства и определять, когда объект (игрок) перемещается снаружи этого объема внутрь (или наоборот).

Если я ограничу «объем» полями, это должно быть просто. Структура данных может просто поддерживать целые числа, ограничивающие X / Y / Z (всего 6 целых чисел), и вычисление входа / выхода с учетом двух точек (перемещение из и перемещение в) должно быть просто вопросом определения, находятся ли А) все три значения To во всех трех диапазонах и Б) хотя бы одинЗначение From находится за пределами соответствующего диапазона.

(Хотя, если есть лучший, более эффективный способ хранения и вычисления этого, я весь внимание.)

Однако, что, если «объем» не является простым блоком? Предположим, у меня есть комната странной формы, и я хочу заключить объем этой комнаты. Я мог бы расположить несколько «томов» по отдельности, чтобы заполнить общее пространство, однако это привело бы к ложным срабатываниям при переходе объекта от одного к другому.

Раньше я не работал в игровых или 3D-движках, поэтому я не понимаю, как я мог бы структурировать что-то подобное. Но мне приходит в голову, что это, вероятно, проблема, которая была решена и имеет известные установленные шаблоны. По сути, я пытаюсь:

1. Определите структуру данных, которая может представлять объем пространства странной формы (хотя, по крайней мере, на основе координат блоков).
2. Определите алгоритм, который, учитывая источник и пункт назначения движения, может определить, пересекло ли движение границу определенного пространства.

Существуют ли установленные шаблоны и методы для этого?

Я не знаю, использовалось ли это раньше в каких-либо видеоиграх, но первое, что пришло на ум, — это классическая реализация сита Эратосфена, единственным изменением было бы сделать boolean массив 3D и использовать ключи в качестве координат. Очевидно, что, хотя x y значения as и могут быть огромными в Minecraft, вы, вероятно, захотите сэкономить место, сохранив смещение между мировой 0,0 позицией и вашим выбором, что-то вроде этого:

 class OddArea
{
    static final int MAX_SELECTION_SIZE = 64; //Or whatever

    public final int xOffset, yOffset;

    // 256 = Chunk height
    public final boolean[][][] squares = new boolean[MAX_SELECTION_SIZE][MAX_SELECTION_SIZE][256];

    OddArea()
    {
        this(0, 0);
    }

    OddArea(final int xOffset, final int yOffset)
    {
        this.xOffset = xOffset;
        this.yOffset = yOffset;
    }

    void addBlock(final int x, final int y, final int z)
    {
        this.squares[x - this.xOffset][y - this.yOffset][z] = true;
    }

    boolean isInsideArea(final int x, final int y, final int z)
    {
        return this.squares[x - this.xOffset][y - this.yOffset][z];
    }
}
 

z не требует смещения, поскольку мир Minecraft имеет высоту всего 256 блоков.

Единственная проблема, о которой я могу думать при этой настройке, заключается в том, что вам нужно знать наименьшие x y координаты, прежде чем начинать заполнять свой объект

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

Кстати, чтобы вычислить, пересекаются ли две сферы, проверьте, меньше ли расстояние между центрами суммы радиусов.