Обнаружение столкновений - любой язык

Question

Я пишу простую игру прямо сейчас, и мне нужно иметь возможность обнаруживать столкновения между многими объектами (проверяя, сталкиваются ли 10 объектов с любыми 20 другими объектами, но не между двумя группами).Я написал простой код, который работает сейчас, но заставляет игру сильно замедляться после обнаружения столкновения (кстати, в Java):

        //Check for collisions between tanks and bullets
        ArrayList<Object> objectsToRemove = new ArrayList<Object>();
        for (int i = 0; i < tanksOnScreen.size(); i += 1) {
            //Get tank
            Tank tank = tanksOnScreen.get(i);

            for (int e = 0; e < bulletsOnScreen.size(); e += 1) {
                //Get bullet
                Bullet bullet = bulletsOnScreen.get(e);

                //Check for collision
                if (tank.collides(bullet.x, bullet.y, 10, 10)) {
                    System.out.println("Collide");
                    objectsToRemove.add(bullet);
                    objectsToRemove.add(tank);
                    break;
                }
            }
        }

        for (Object obj:objectsToRemove) {
            if (obj.getClass().equals(Bullet.class)) {
                bulletsOnScreen.remove(bulletsOnScreen.indexOf(obj));
            } else if (obj.getClass().equals(Tank.class)) {
                tanksOnScreen.remove(tanksOnScreen.indexOf(obj));
            }
        }

И метод collides() танка:

public boolean collides(float px, float py, float pwidth, float pheight) {
    // If the distance between the two centers of the lines on x and y axis
    // Is less than the distance of half the w and h added together, the objects
    // Are colliding
    float x1 = (px > x) ? x : px, x2 = (px > x) ? px : x, y1 = (py > y) ? y : py, y2 = (py > y) ? py : y;
    float w1 = (x1 < x2) ? width : pwidth, w2 = (x1 < x2) ? pwidth : width, h1 = (y1 < y2) ? height : pheight, h2 = (y1 < y2) ? pheight : height;
    if ((x2 + w2/2) - (x1 + w1/2) < (w1/2 + w2/2)&&(y2 + h2/2) - (y1 + h1/2) < (h1/2 + h2/2)) {
        return true;
    } else {
        return false;
    }
}

Я предполагаю, что задержка из-за двойных циклов for, для итерации по объектам.Я не уверен, как уничтожить эти петли или как получить маркеры в определенной области экрана и проверять только эти маркеры, не используя другой цикл (сегрегация, я думаю).Кто-нибудь может указать мне правильное направление для обнаружения столкновения со многими объектами?Я не против, на каком языке ответ, даже если это псевдокод.

Спасибо,

Бен

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

Сейчас я использую графический интерфейс Slick для Java, который предоставляет вам метод update и render для добавления рендеринга и игровой логики.Я поместил это обнаружение столкновений в метод обновления (который вызывается каждый кадр - около 60 раз в секунду).Замедление происходит после столкновения, и объекты удаляются с экрана - что я нахожу странным.Может быть, команда break после удаления объектов в цикле for уничтожит ее?

Edit 2

Спасибо за ответы, ребята, и ссылкиотличная помощь на будущее.Я исправил проблему только путем замены пули и бака на петли, чтобы он не продолжал работать после разрушения пули.Я не должен был задавать вопрос, так как это было довольно легко исправить в конце.Дейв и Бантар были правы, говоря, что проблема не в коде, а в том, что он должен быть мгновенным.

Answer 1

Хорошая идея - использовать октри .Поскольку пули будут двигаться, я предполагаю, что вам понадобится кинетическая версия - в Интернете есть множество статей о кинетических структурах данных.

Также, если вы хотите обнаружить столкновения между более сложными выпуклыми полигонами, я рекомендую вам использовать алгоритм gjk , который очень быстр для такого расчета.Обратите внимание, что это ускорит только время обнаружения столкновений для пары объектов, количество пар останется неизменным.

Answer 2

Если я что-то упустил или есть дополнительный код, который вы не показали, вы запускаете в O (n ^ 2), где n равно 20. Это должно показаться пользователю мгновенным.* Попробуйте пройти через него в отладчике, чтобы увидеть, где он замедляется.

Редактируйте, чтобы уточнить: ваша дорогая операция не в том коде, который вы опубликовали.Это где-то еще, вызывается кодом, который вы опубликовали.

Answer 3

Спасибо за ответы на все вопросы, ребята, и ссылки являются большой помощью на будущее.Я исправил проблему только путем замены пули и бака на петли, чтобы он не продолжал работать после разрушения пули.Я не должен был задавать вопрос, так как это было довольно легко исправить в конце.Дейв и Бантар были правы, говоря, что проблема не в коде, а в том, что он должен быть мгновенным.