Efficient algorithm for collisions in 2D game?

Question

I'm programming a Bomberman in Java following a tutorial (this is my first game). The tutorial suggests the following code for detecting collisions.

        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);
                }
            }

By now, entities is an array list containing the enemies and the player. As I want to also detect the player collides with walls, should I put every single wall or bricks tile in the level into the entities arraylist? If so, isn't this algorithm very inefficient? These tiles aren't going to collide with other tiles, so I was thinking to manage game entities in different lists. What do you suggest? Is there a more efficient algorithm to do it?

Note: I already read other questions related to collisions in 2D games. Thanks a lot.

Evaleen

Answer 1

I suggest reading this excellent article about how ghost movement and collision detection works in PacMan.

Then I would suggest logically modeling your Bomberman levels as a collection of tiles. Each tile represents a discrete position in your level, and it is not logically possible to ever be "between" tiles or occupying two tiles at the same time. Each tile can track what sort of terrain feature is currently on it, and whether or not it is a valid destination tile for the player (and the enemies, potentially with different rules for each if the enemies are allowed to traverse terrain that is normally impassable for the player).

Then you don't need a collision detection algorithm for every object in the world. When it comes time for an enemy to move, or when the user tries to move their character, all you have to do is check all the tiles that are adjacent to their current tile (4, or 8 max if you allow diagonal movement), see if each tile represents a valid movement direction, and block the movement if it is not in a valid direction.

And to answer your question, yes, iterating every object in the world on every position update will be very inefficient.

Vulgar

Thank you so much for your answer, it was very clear and useful :) I'll read the article now. – Evaleen

Grid collisions can reduce the collision calculations from doing hundreds of rectangular check to a few Boolean check. It also is like it has its own built-in direction of collision checker. It is probably hundreds of times faster if not thousands. I'm using a system that allows to move freely inside of the empty grids.Only problem I've encountered is diagonal entering into a grid. Your post gave me an idea to fix that problem though. – Chausses

Answer 2

There is another way to use grids for collision system. I'm using more complex version of the Aroth's suggestion and using this to fix collision bugs.

Theoretically this system is the fastest(assuming you are doing this check if(Grid[x][y] ==true)) because it only uses a single Boolean check for each entity(the things that can move).

Note: In the above grid check example, I've used a 2 dimensional array of booleans that sets the coordinates of impassable grids to false.`

If you are not worried about physics like bouncing from a wall you can use this:

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). 

If you want to allow entities to move freely inside the grids(the grids are bigger than the minimum distance they can move) then you need to put them adjacent to the grids they've entered and they weren't supposed to. Otherwise just return them back to the previous grid.

If you want them to bounce from the wall you can still use this but I'm not sure how many features can be added to a collision system like this.

Chausses

Answer 3

May I recommend my own project. But it's still wip. https://github.com/YagaoDirac/Dirac-2d-collision-detection-for-games It's based on quad-tree which handles sparse pretty well. It supplies collision group. This conception is also used in both UE and Unity. It support only circle vs circle and overlapping only for now(2022 feb 22).

I plan to make at least AABB, and collision which at least stop your pawn from leaving the map.

I may also provide another system based on fixed grid.

Mcmillan