Обнаружение столкновений с МНОГИМИ объектами

В основном я сосредоточился на аспектах Graphics, чтобы создать немного 2DGame. Я смотрел/смотрел несколько учебников, но ни один из них не нравился. У меня уже есть игрок (квадрат), который перемещается и сталкивается с другими квадратами на экране. Гравитация и т.д. Также выполняются.

Если на экране есть только много объектов (30 * 20), все работает отлично. Но если я увеличу его, чтобы сказать 300 * 300, программа начнет работать очень медленно, так как она должна проверять столько объектов.

Я действительно не понимаю, как игры, такие как Minecraft, могут работать со всеми блоками ALL THOSE, и моя программа уже отдает 300 * 300 блоков.

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

Я отправлю код о том, как я обрабатываю столкновений.

player.collision(player, wall);

public void collision(Tile object1, Tile[] object2){
    collisionCheckUp(object1, object2);
    collisionCheckDown(object1, object2);
    collisionCheckLeft(object1, object2);
    collisionCheckRight(object1, object2);  
}

public void collisionCheckDown(Tile object1, Tile[] object2){

    for (int i = 0; i < Map.tileAmount; i++){
        if(object2[i] != null && object2[i].visible)
        {
            if(object1.isCollidingDown(object2[i])){
                object1.collisionDown = true;
                return;
            }

        }
    }       
    object1.collisionDown = false;
}

public void compileHullDown(){

     collisionHull = new Rectangle((int)x+3, (int)y+3, width-6, height);
}

int wallCount = 0;
    for (int x=0;x<Map.WIDTH;x++) {
        for (int y=0;y<Map.HEIGHT;y++) {

            if (Map.data[x][y] == Map.BLOCKED) {
                wall[wallCount] = new Tile(x * Map.TILE_SIZE, y *  Map.TILE_SIZE);
                wallCount++;
            }
        }
    }

Ответы

Ответ 1

Обычный подход для оптимизации обнаружения столкновений заключается в использовании раздела space для классификации/управления вашими объектами.

Общая идея подхода заключается в том, что вы создаете дерево, представляющее пространство, и помещаете свои объекты в это дерево в соответствии с их позициями. Когда вы вычисляете столкновения, вы пересекаете дерево. Таким образом, вам придется выполнять значительно меньше вычислений, чем использовать подход грубой силы, потому что вы будете игнорировать все объекты в ветвях, отличных от того, который вы просматриваете. Minecraft и т.д., Вероятно, используют octrees для столкновения (и, возможно, для рендеринга тоже).

Наиболее распространенными структурами пространственного раздела являются BSP-Trees, kd-Trees (особый тип BSP-деревья). Более простой подход состоял бы в том, чтобы использовать единое пространственное разделение для начала - разделите ваше пространство на половину по оси.

Лучший ресурс при столкновении, который я обнаружил, - в этой книге. Он должен прояснить все ваши вопросы по этой теме.

Это, если вы хотите сделать это правильно. Если вы хотите сделать это быстро, вы можете просто выбрать цветовой буфер вокруг своего персонажа или только в направлении движения, чтобы определить, близко ли препятствие.

Ответ 2

Как сказал Костя, вам будет полезно разбить ваше пространство. Однако вам нужно будет использовать QuadTrees вместо Octrees, поскольку вы находитесь только в 2D не 3D. Вот хорошая статья чтобы начать работу с QuadTrees.

Ответ 3

Вы можете сократить свои накладные расходы в 4 раза, вместо вычисления коллизий для вверх/вниз/влево/вправо, вычисляя коллизии один раз и используя относительные позиции двух объектов, чтобы узнать, попали ли вы в пол, стена, или потолок. Еще одна хорошая идея - обратить внимание только на объекты, которые находятся поблизости - может быть, каждые 0,25 секунды составляют список всех объектов, которые, вероятно, достаточно близки, чтобы столкнуться в следующие 0,25 секунды?