Эффективный алгоритм столкновений в 2D игре?

Question

Я программирую Bomberman на Java, следуя инструкции (это моя первая игра). В руководстве предлагается следующий код для обнаружения столкновений.

        for (int p=0; p<entities.size(); p++) {
            for (int s=p+1; s<entities.size(); s++) {
                Entity me = (Entity) entities.get(p);
                Entity him = (Entity) entities.get(s);

                if (me.collidesWith(him)) {
                    me.collidedWith(him);
                    him.collidedWith(me);
                }
            }

К настоящему времени entity - это список массивов, содержащий врагов и игрока. Поскольку я также хочу обнаружить, что игрок сталкивается со стенами, должен ли я помещать каждую отдельную плитку стены или кирпичей на уровне в массив объектов? Если так, разве этот алгоритм не очень неэффективен? Эти плитки не будут сталкиваться с другими плитками, поэтому я думал об управлении игровыми объектами в разных списках. Что ты предлагаешь? Есть ли более эффективный алгоритм для этого?

Примечание: я уже читал другие вопросы, связанные со столкновениями в 2D играх. Большое спасибо.

Answer 1

Предлагаю прочитать эту превосходную статью о том, как работает призрачное движение и обнаружение столкновений в PacMan .

Тогда я бы предложил логически смоделировать ваши уровни Bomberman в виде набора плиток.Каждая плитка представляет собой отдельную позицию на вашем уровне, и логически невозможно когда-либо оказаться «между» плитками или занимать две плитки одновременно.Каждый тайл может отслеживать, какой тип рельефа местности в настоящее время находится на нем, и является ли он действительным тайл-ориентиром для игрока (и врагов, потенциально с разными правилами для каждого, если врагам разрешено пересекать местность, которая обычно непроходима).для игрока).

Тогда вам не нужен алгоритм обнаружения столкновений для каждого объекта в мире.Когда приходит время для перемещения врага или когда пользователь пытается переместить своего персонажа, все, что вам нужно сделать, это проверить все плитки, которые находятся рядом с их текущей плиткой (4 или 8 максимум, если вы разрешаете движение по диагонали),посмотрите, представляет ли каждая плитка правильное направление движения, и заблокируйте движение, если оно не в правильном направлении.

И чтобы ответить на ваш вопрос, да, повторение каждого объекта в мире при каждом обновлении позиции будет очень неэффективным.

Answer 2

Существует еще один способ использования сеток для системы столкновений.Я использую более сложную версию предложения Арот и использую ее для исправления ошибок столкновения.

Теоретически эта система является самой быстрой (если вы делаете эту проверку if(Grid[x][y] ==true)), потому что она использует только одну логическую проверкудля каждой сущности (вещи, которые могут двигаться).

Примечание : В приведенном выше примере проверки сетки я использовал двумерный массив логических значений, который устанавливает координаты непроходимых сеток вfalse.

Если вы не беспокоитесь о физике, такой как отскакивание от стены, вы можете использовать это:

1- Divide the map into grids. 
2- Making every entity only fill a tile would be better but not necessary. 
3- Store the previous position or the grid of the entities.
4- Whenever an entity moves, before visually updating their location (also before 
doing other calculations) check the grids they are in. If they are in grid 
that is not empty or simply in a grid that they are not supposed to 
be, return their position back to the previous position (which you have stored). 

Если вы хотите, чтобы объекты могли свободно перемещаться внутри сетки (сетки)больше минимального расстояния, на которое они могут двигаться), тогда вам нужно поместить их рядом с сетками, в которые они вошли, и они не должны были это делать.В противном случае просто верните их обратно в предыдущую сетку.

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