java - 许多物体的碰撞检测

Question

我主要专注于图形方面来创建一个小的 2D 游戏。我看过/看过几个教程，但没有一个令人满意。我已经有一个玩家(一个方 block )在屏幕上移动并与其他方 block 发生碰撞。重力等也都搞定了。

如果只有屏幕上显示的那么多对象 (30*20)，则一切正常。但是，如果我将它增加到比方说 300*300，程序开始运行得非常慢，因为它必须检查如此多的对象。

我真的不明白像 Minecraft 这样的游戏如何处理所有这些 block ，我的程序已经放弃了 300*300 block 。

我已经尝试过仅在对象可见时检查碰撞，但这会导致程序检查每个对象的可见性，从而导致同样的问题。我究竟做错了什么？感谢帮助。

我将发布一些关于如何处理冲突的代码。

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

优化碰撞检测的常用方法是使用 space partition对您的对象进行分类/管理。

该方法的总体思路是构建一棵代表空间的树，并根据对象的位置将对象放入该树中。当您计算碰撞时，您遍历树。这样，与使用蛮力方法相比，您必须执行的计算要少得多，因为您将忽略分支中除您正在遍历的对象之外的所有对象。 Minecraft 和类似的可能使用 octrees用于碰撞(也可能用于渲染)。

最常见的空间分区结构是BSP-Trees , kd-Trees (一种特殊类型的 BSP 树)。更简单的方法是首先使用统一的空间分区 - 将空间分成轴对齐的两半。

我发现的关于碰撞的最佳资源是 this book .它应该澄清您关于该主题的所有问题。

如果你想做对的话。如果您想快速完成，您可以只对角色周围的颜色缓冲区进行采样，或者仅在移动方向上采样以确定障碍物是否靠近。