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?