与MANY对象的碰撞检测

Question

我主要专注于Graphics方面来创建一个2DGame.我看过/看过几个教程,但没有一个是令人高兴的.我已经有一个玩家(一个正方形)移动并与屏幕上的其他方块相撞.重力等也完成了.

如果屏幕上只有那么多的物体(30*20),一切都很好.但是,如果我将它增加到300*300,那么程序开始运行非常慢,因为它必须检查这么多对象.

我真的不知道像Minecraft这样的游戏如何与所有这些块一起工作,我的程序已经放弃了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++;
            }
        }
    }

Answer 1

优化碰撞检测的常用方法是使用空间分区来对对象进行分类/管理.

该方法的一般思想是,您构建一个表示空间的树,并根据其位置将您的对象放入该树中.计算碰撞时,您将遍历树.这样,您将不得不执行比使用强力方法少得多的计算,因为您将忽略除了您正在遍历的分支之外的所有对象.Minecraft和类似的可能使用八叉树进行碰撞(也可能用于渲染).

最常见的空间分区结构是BSP-Trees,kd-Trees(一种特殊类型的BSP树).更简单的方法是使用统一的空间分区作为开始 - 以轴对齐的一半分割您的空间.

我发现的最好的碰撞资源就是这本书.它应该澄清您对该主题的所有问题.

如果你想做得对,那就是这样.如果你想快速做,你可以只是在你的角色周围采样颜色缓冲区,或者只在运动方向上采样,以确定障碍物是否接近.

Answer 2

正如 Kostja 提到的，对空间进行分区将会很有用。但是，您将需要使用四叉树而不是八叉树，因为您仅处于 2D 而不是 3D。这是一篇很好的文章，可以帮助您开始使用四叉树。