C ++ реализует обнаружение и обработку столкновений для мозаичного 2D-мира с плавным движением стен

Я использую SFML 2.1 для графики, и моя структура игры очень близко следует книге SFML (реализация SceneGraph и т. Д.)
Мой мир состоит в основном из персонажей (около 1-400, движется вокруг) и плиток (3600, неподвижно), и я буду проверять наличие столкновений каждый раз, когда что-то движется

В худшем случае с ~ 400 символами, перемещающимися вокруг и ~ 3600 плитами, у меня есть 4000 возможных объектов с коллизиями и 800 вызовов проверки коллизий (раздельное движение X и Y) в каждом кадре -> 3.2M проверок коллизий в общей сложности.

Почти все мои объекты имеют размер 16×16 пикселей, и я искал реализацию либо дерева квадрантов, либо более простой сетки для обнаружения столкновений, что должно значительно снизить количество проверок столкновений. Под сеткой я имею в виду http://conkerjo.wordpress.com/2009/06/13/spatial-hashing-implementation-for-fast-2d-collisions/

Но я понятия не имею, как я должен реализовать простую сетку, например. Любая помощь приветствуется. Вероятно, есть даже намного лучшие способы сделать это.

Шаг обновления сущности.
Я делаю движение по осям X / Y отдельно. Потому что я хочу скользить против объектов при столкновении по диагонали.

1. Переместить объект горизонтально

2. Проверьте и обработайте столкновения

3. Переместить объект вертикально

4. Проверьте и обработайте столкновения

5. Повторите 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 одновременно:

Я понятия не имел, должен ли я сбросить положение X или Y после столкновения.

Обработка столкновений.
Я буду обрабатывать столкновения только тогда, когда движущиеся объекты (в настоящее время только персонажи, более поздние снаряды и некоторые специальные плитки)

1. если сущность есть тайл -> ничего не делать

2. если сущность является персонажем -> проверить столкновения с персонажами и плитками и сбросить движение, если столкновение произошло

.

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 движущихся персонажа. Должен ли я искать сущность каждый раз, когда кто-то перемещается в сетке, и пытаться переместить ее в другую ячейку сетки / ветвь дерева?

Редактировать:

Что я, вероятно, попробую дальше, если никто не даст лучший совет

Обновлен шаг обновления.
Это умный или в любом случае разумный способ сделать это?

1. Удалить сущность из сетки / дерева квадрантов

2. Переместить объект горизонтально

3. Добавить объект в сетку / дерево квадрантов

4. Проверьте и обработайте столкновения

5. Удалить сущность из сетки / дерева квадрантов

6. Переместить объект вертикально

7. Добавить объект в сетку / дерево квадрантов

8. Проверьте и обработайте столкновения

9. Повторите 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
}