c实现二维平铺世界的碰撞检测与处理

Question

我使用SFML 2.1进行图形，我的游戏结构非常严格地遵循SFML书（SceneGraph实现等）我的世界主要由角色（大约1-400，四处移动）和瓷砖（3600，静止）组成，每次移动时我都会检查碰撞

在最坏的情况下，大约400个字符移动，大约3600个平铺，我有4000个可能的实体，每帧有800个冲突检查调用（单独的X和Y移动）-

几乎我所有的实体都有16x16像素的大小，我一直在考虑实现四叉树或更简单的网格来进行碰撞检测，这将大大减少碰撞检查的数量。我是说网格http://conkerjo.wordpress.com/2009/06/13/spatial-hashing-implementation-for-fast-2d-collisions/

但是我不知道我应该如何实现简单的网格。欢迎所有的帮助。可能还有很多更好的方法来强制执行它。

实体更新步骤。我分别做X/Y轴运动。因为我想在对角碰撞时靠着实体滑动。

>

水平移动实体

检查和处理冲突

垂直移动实体

检查和处理冲突

对所有实体重复 1-4

。

void Entity::updateCurrent(sf::Time dt, CommandQueue& commands)
{
    setPreviousPosition(getPosition());
    move(sf::Vector2f(mVelocity.x, 0) * dt.asSeconds());
    handleCollision();
    setPreviousPosition(getPosition());
    move(sf::Vector2f(0, mVelocity.y) * dt.asSeconds());
    handleCollision();
}

我不知道碰撞后是否应该重置X或Y位置。

碰撞处理。我将只在实体移动时处理碰撞(目前只有角色实体，后来的投射物和一些特殊的贴图)

>

如果实体是磁贴 -

如果实体是字符 -

。

void Entity::handleCollision()
{
    if (getCategory() & Category::Tile)
        return;
    if (getCategory() & Category::Character)
    {
        std::set<SceneNode::Pair> collisionPairs;
        checkCollision(*mSceneGraph, collisionPairs);

        for (SceneNode::Pair pair : collisionPairs)
        {
            if (matchesCategories(pair, Category::Character, Category::NonPassableCharacterOrTile))
            {
                resetPreviousPosition();
                break;
            }
        }
    }
}

我将使用SFML的相交函数简单地检查碰撞。这可能对这个足够好了吗？

bool collision(const SceneNode& l, const SceneNode& r)
{
    return l.getBoundingRect().intersects(r.getBoundingRect());
}

如果我要实现网格或四叉树以进行碰撞检测，我应该何时填充它，何时更新？我应该在每次移动一个实体时更新它，还是应该尝试一次移动所有实体，然后构建网格/四叉树，只有在这之后才尝试处理所有冲突。

所以我的问题是：（1）在这种情况下，我应该如何以及何时进行冲突处理？我目前的实现工作正常，但我认为我这样做太频繁了，我查看网格/四叉树的所有示例都假设我首先进行所有移动，然后进行冲突检测和处理。

以及(2)何时清除/填充/更新我的网格/四叉树。例如，如果我有3600块瓷砖和3个移动的角色。每次在网格中移动时，我应该寻找实体并尝试将其移动到不同的网格单元/树分支吗？

编辑：

除非有人给出更好的建议，否则我接下来可能会尝试什么

更新了更新步骤。这是明智的还是以合理的方式做到这一点？

> < li>

从网格/四叉树中删除实体

水平移动实体

将实体添加到网格/四叉树

检查和处理冲突

从网格/四叉树中删除实体

垂直移动实体

将实体添加到网格/四叉树

检查和处理冲突

对所有实体重复1-8

。

Entity::move()
{
    grid.getCell(getPosition()).remove(this);
    ... move x
    grid.getCell(getPosition()).add(this);
    ... if collision, reset x

    grid.getCell(getPosition()).remove(this);
    ... move y
    grid.getCell(getPosition()).add(this);
    ... if collision, reset y
}

Entity::checkCollision()
{
    list<Entity*> possibleColliders;

    possibleColliders = grid.getEntitiesInRectangle(x - s, y - s, x + s, y + s);

   ... now only check collision against possibleColliders
}

Answer 1

我认为四叉树可以很好地工作，因为它是独立的，所以将它添加到当前系统中确实没有问题。

您问的重要问题可能是，何时填充和更新四叉树。我认为这在很大程度上取决于您的用例。由于您有大约400个字符可以更改每个帧的位置，因此，如果您尝试移动四叉树中的节点或完全重建四叉树，则可能不会有太大区别。哪个真正性能更高取决于您的算法和数据结构，这需要一些性能测试。

在本教程中，他们还建议在每次帧迭代中重建四叉树。

对于“如何修复冲突处理”，您需要提供更多信息/一个单独的SO问题，因为问题是什么并不清楚。