检测多个物体之间的碰撞问题

Question

我主要专注于图形方面，创建了一个简单的2D游戏。我观看/查看了几个教程，但没有一个让我满意的。我已经有一个玩家（一个正方形）在屏幕上移动并与其他正方形发生碰撞。包括重力等都已经完成。

如果只有那么少量的对象出现在屏幕上（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++;
            }
        }
    }

- Gjallar

---

这里有一些缺失的代码。Map.tileAmount是什么？你是否检查了离问题对象太远的地方？碰撞检测实际上是如何工作的？你是否尽可能跳过了网格位置之间的空间？ - Dave Newton

Map.tileAmount只是地图的WIDTH(30)*HEIGHT(20)，因此是地图上物体（正方形）的数量。碰撞检测通过矩形之间的.intersectes工作。我有四个这样的矩形，分别在玩家的上方、下方、左侧和右侧，以检查与墙壁的碰撞发生在哪里（例如，如果上方的一个与墙壁碰撞，则重力设置为0）。将对象创建代码添加到问题中。 - Gjallar

我不清楚你的策略：你应该有一个对象集合；你不需要遍历整个地图。对于当前有效对象的列表，你将拥有它们的位置。从它们的位置，你可以检查地图上周围的网格位置是否被占用。无论如何，在网上有大量的碰撞检测算法--哪一个最适合可能取决于你的游戏世界实现。 - Dave Newton

相关视频：https://www.youtube.com/watch?v=eED4bSkYCB8 - Ronald C

Answer 1

通常优化碰撞检测的方法是使用空间划分来分类/管理你的对象。

这种方法的一般思路是构建一个表示空间的树，并根据它们的位置将对象放入该树中。当计算碰撞时，遍历该树。这样，与使用暴力方法相比，您将只需要执行显著少的计算，因为您将忽略除正在遍历的分支之外的所有对象。Minecraft和类似游戏可能会在碰撞（也可能在渲染）方面使用八叉树。

最常见的空间划分结构是BSP-树，kd-树（BSP-树的一种特殊类型）。更简单的方法是从开始时使用均匀的空间划分-将您的空间分成轴对齐的两半。

我发现的关于碰撞的最佳资源是这本书。它应该澄清您对该主题的所有问题。

如果您想正确地完成此操作，那么以上是正确的方法。如果您想快速完成，则可以仅在角色周围或运动方向上对颜色缓冲区进行采样，以确定是否靠近障碍物。

- kostja

Answer 2

如Kostja所提到的，将空间划分为区块会很有用。然而，由于您只处于二维状态，因此需要使用QuadTrees而不是Octrees。 这里有一篇不错的文章可以帮助您入门QuadTrees。

- GETah

---

我很乐意这样做，但我需要15个声望才能这样做:/ - Gjallar

Answer 3

您可以通过这种方式将开销降低4倍：计算两个物体的相对位置，而不是根据上/下/左/右进行碰撞计算，以此来确定是否撞到地板、墙壁或天花板。还有一个好主意是只关注附近的物体 - 可以每0.25秒钟列出所有可能在接下来的0.25秒内与之碰撞的物体列表。

- Toomai