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.

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.