Implementing pixel-perfect collision - Libgdx

Question

I just started learning game programming through the libgdx framework and I am at the collision detection stage of development. I made a pretty simple game that has some basic bounding-box collision detection system. However, I want to implement pixel-perfect collision for accuracy.

I will be showing snippets of code that I think are important to help you understand what is going on.

A two-dimensional array is created to define the position of the tiles on the screen:

int[][] map = {
        {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
        {1,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
        {1,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
        {1,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
        {1,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
        {1,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
        {1,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
        {1,0,1,1,0,0,0,0,0,0,0,0,0,0,1},
        {1,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
        {1,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
        {1,0,0,0,0,1,1,0,0,0,0,0,0,0,1},
        {1,0,0,0,0,0,1,0,0,0,0,0,0,0,1},
        {1,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
        {1,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
        {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
    };

This create() method from my main game class adds a player and three entities to an ArrayList of type Entity.

  @Override
  public void create () {
      batch = new SpriteBatch();
      tileTexture = new Texture("block.png");  
      screenWidth = Gdx.graphics.getWidth();
      screenHeight = Gdx.graphics.getHeight();

      // add some entities including a player
      entities.add(new Player(this, 100, 150, 20, 20, 120.0f, new Texture("player.png")));
      entities.add(new Entity(this, 50, 150, 20, 20, 120.0f, new Texture("enemy.png")));
      entities.add(new Entity(this, 200, 200, 20, 20, 120.0f, new Texture("enemy.png")));
      entities.add(new Entity(this, 180, 50, 20, 20, 120.0f, new Texture("enemy.png")));
  }

The render() method draws the tile map and the entities when the game is run. Another class named Entity holds the data of a particular entity (can be a block/player). The data can be the x and y position of that entity.

      // draw tile map
      // go over each row bottom to top
      for(int y = 0; y < mapHeight; y++) {
          // go over each column left to right      
          for(int x = 0; x < mapWidth; x++) {
              // tile
              if(map[x][y] == 1) {
                  batch.draw(tileTexture, x * tileSize, y * tileSize);
              }
          }
      }

      // draw all entities
      for(int i = entities.size() - 1; i >= 0; i--) {
          Entity e = entities.get(i);
          batch.draw(e.texture, e.x, e.y);
      }

This produces:

To check for collision when the player (green block) moves, I have two methods that check if the player is colliding with an entity or a tile.

The tileCollision() method:

  public boolean tileCollision(Entity e, Direction direction, float newX, float newY) {
      boolean collision = false;

      // determine affected tiles
      int x1 = (int) Math.floor(Math.min(e.x, newX) / tileSize);
      int y1 = (int) Math.floor(Math.min(e.y, newY) / tileSize);
      int x2 = (int) Math.floor((Math.max(e.x, newX) + e.width - 0.1f) / tileSize);
      int y2 = (int) Math.floor((Math.max(e.y, newY) + e.height - 0.1f) / tileSize);

      // tile checks
      for(int x = x1; x <= x2; x++) {
          for(int y = y1; y <= y2; y++) {
              if(map[x][y] == 1) {
                  collision = true;
                  e.tileCollision(map[x][y], x, y, newX, newY, direction);
              }
          }
      }
      return collision;
  }

The line of code e.tileCollision(map[x][y], x, y, newX, newY, direction); in this method calls the tileCollision() method in the Entity class that prints the position of where the block collides with a tile.

To check collisions between entities, we have this method:

  public boolean entityCollision(Entity e1, Direction direction, float newX, float newY) {
      boolean collision = false;

      for(int i = 0; i < entities.size(); i++) {
          Entity e2 = entities.get(i);

          // we don't want to check for collisions between the same entity
          if(e1 != e2) {
              // axis aligned rectangle rectangle collision detection
              if(newX < e2.x + e2.width && e2.x < newX + e1.width &&
                  newY < e2.y + e2.height && e2.y < newY + e1.height) {
                  collision = true;

                  e1.entityCollision(e2, newX, newY, direction);
              }
          }
      }

      return collision;
  }

NOTE: The green block can move across an entity but cannot go through tiles. This is because the line e1.entityCollision(e2, newX, newY, direction); calls the entityCollision() method in the class Entity that lets the green block move.

This type of collision detection seems basic and inefficient (time complexity of O(n^2)).

How do I implement pixel-perfect collision in this context?

Additional question: If I want to improve the efficiency, what collision detection system can I use to eliminate unnecessary checks?

Answer 1

The terms to google are Broad Phase and Narrow Phase collision detection. Broad phase is used to eliminate invalid collisions. One way to do broad phase is just divide the screen into grids, then only iterate through neighboring grids instead of the whole entity list. Here is another technique.