'Efficient algorithm for collisions in 2D game?

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.

java2dcollision-detectionmemory-efficient


Solution 1:[1]

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.

Solution 2:[2]

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.

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1
Solution 2 YagaoDirac

Related Questions