How to get the tiles around a player for collision detection?

Newbie & Debugging Questions
#1

I implemented some basic collision detection using AABBs and it mostly works, except for the fact that when I move down towards a collidable object, the player can pass through, but only when approaching the object after moving to the left. Here’s a picture of what I mean:

If you can see, the player (the white square), is intersecting a tile. The player can only pass through a tile when there is no tiles under the player, and you are moving left and then down. Here’s my collision detection code:


    public static boolean isColliding(AABB a, AABB b) {
		if (Math.abs(a.pos.getX() - b.pos.getX()) < a.size + b.size) {
			if (Math.abs(a.pos.getY() - b.pos.getY()) < a.size + b.size) {
				return true;
			}
		}
		return false;
	}

The pos variable is actually the center of the AABB, and the size variable is half the size. Here’s how I detect a collision in the entity class:


    private void move(float x, float y, float sx, float sy) {
		if (getX() / 32 + x >= 0 && getX() / 32 + x <= world.mx && getY() / 32 + y >= 0 && getY() / 32 + y <= world.my) {
			if (world.tiles[(int) ((int) getX() / 32 + x)][(int) ((int) getY() / 32 + y)] != null) {
				Vector2f tempPos = new Vector2f((pos.getX() + (pos.getX() + 32)) / 2, (pos.getY() + (pos.getY() + 32)) / 2);
				box.update(new Vector2f(tempPos.getX() + sx, tempPos.getY() + sy), 16);
				Tile t = world.tiles[(int) ((int) getX() / 32 + x)][(int) ((int) getY() / 32 + y)];
				t.color = true;
				if (!Collision.isColliding(box, t.getBox())) {
					setPos(getX() + sx, getY() + sy);
				} else if (Collision.isColliding(box, t.getBox())) {
					if (!onGround)
						onGround = true;
				}
			} else {
				setPos(getX() + sx, getY() + sy);
			}
		} else {
			setPos(getX() + sx, getY() + sy);
		}
		glPushMatrix();
		glTranslatef(getX(), getY(), 0);
		glPopMatrix();
	}

Specifically these lines are important:


    Vector2f tempPos = new Vector2f((pos.getX() + (pos.getX() + 32)) / 2, (pos.getY() + (pos.getY() + 32)) / 2);
				box.update(new Vector2f(tempPos.getX() + sx, tempPos.getY() + sy), 16);
				Tile t = world.tiles[(int) ((int) getX() / 32 + x)][(int) ((int) getY() / 32 + y)];
				t.color = true;
				if (!Collision.isColliding(box, t.getBox())) {
					setPos(getX() + sx, getY() + sy);

I construct a new Vector (tempPos) that is the center of the entity in question. Then I update the AABB with the center of the entity, and then I add either sx or sy, which is the movespeed, generally speaking this is usually set to 8, so I move 8 pixels every update, and the tiles are 32 pixels in size. Then I get the tile immediately to the wherever the player is moving using the x and y variables.

Just for reference, here is my keyboard update code for the player:


    if (Keyboard.isKeyDown(Keyboard.KEY_SPACE)) {
			move(0, 1, 0, MOVESPEED);
		}
		if (Keyboard.isKeyDown(Keyboard.KEY_D)) {
			move(1, 0, MOVESPEED, 0);
		}
		if (Keyboard.isKeyDown(Keyboard.KEY_A)) {
			move(-1, 0, -MOVESPEED, 0);
		}
		if (Keyboard.isKeyDown(Keyboard.KEY_LSHIFT)) {
			move(0, -1, 0, -MOVESPEED);
		}
		if (Keyboard.isKeyDown(Keyboard.KEY_SPACE) && onGround) {
			onGround = false;
			vY = 4f;
		}

If I change this line:


    box.update(new Vector2f(tempPos.getX() + sx, tempPos.getY() + sy), 16);

To instead add the x and y variables, like this:


    				box.update(new Vector2f(tempPos.getX() + x, tempPos.getY() + y), 16);

Then the collision works correctly, but now it doesn’t detect collisions on the y axis at all. x and y are constrained between 1 and -1, as you can see in the keyboard update code. It’s used to look up the tile where the player wants to move, so I don’t know why only the x axis is working, and not the y.

Sorry if I didn’t explain this well enough, ask me and I’ll clarify anything!

#2

So I figured out my problem was that when I move onto two tiles at once, I get the tile that I am standing on, but I actually round down so that the tile I get is actually the incorrect one. My question is, how do I get the tiles surrounding the player, and then check to see if any of them collide with the player? My player is one tile tall/wide so I only need to get the four tiles around him. But I think the way I am doing it right now is wrong because it’s so hard to implement, and it’s such an easy idea. Any help?

#3

Since all tiles are of uniform size you can store all collidable tiles in a 2d array by their column and row. That would mean tile[8][5] would be column 8 and row 5 and their world position 8 * 32, 5 *32. Now if you divide the player center coordinates by it´s tile size you´ll get an approximate position in tile coordinates and then you can check against the surrounding tiles simply by looping those tiles.

Let´s say the player coordinates are y100, x100. Divide by 32 and you get column 3, row 3. Now you just need to check the tiles in column 2, 3, 4 and row 2, 3, 4 since those are the only possible tiles that can collide with the player.

I hope it helps.

#4

Guys, I really need help please. I’ve been trying to figure this out for a week now and I can’t…

I tried to rewrite my move method, and now it’s this:

private void move(int x, int y, float sx, float sy) {
		Vector2f tempPos = new Vector2f((pos.getX() + (pos.getX() + 32)) / 2, (pos.getY() + (pos.getY() + 32)) / 2);
		box.update(new Vector2f(tempPos.getX() + sx, tempPos.getY() + sy), 16);
		if (getX() / 32 + x > 0 && getX() / 32 + x < world.mx && getY() / 32 + y > 0 && getY() / 32 + y < world.my) {

			for (int xx = 0; xx <= 1; xx++) {
				for (int yy = 0; yy <= 1; yy++) {
					if (world.getTile((int) (getX() / 32) + xx, (int) (getY() / 32) + yy) != null) {
						Tile t = world.getTile((int) (getX() / 32) + xx, (int) (getY() / 32) + yy);
						t.color = true;
						if (t.type != 0 && !Collision.isColliding(box, t.getBox())) {
							setPos(getX() + sx, getY() + sy);
						} else if (t.type == 0) {
							setPos(getX() + sx, getY() + sy);
						}
					} else {
						setPos(getX() + sx, getY() + sy);
					}
				}
			}

		} else {
			setPos(getX() + sx, getY() + sy);
		}
		glPushMatrix();
		glTranslatef(getX(), getY(), 0);
		glPopMatrix();
	}

I now have two four loops to get the tiles above and below the player, but now he only collides with tiles if he is in the middle of four solid tiles. I’m using this for my collision detection:

public static boolean isColliding(AABB a, AABB b) {
		if (Math.abs(a.pos.getX() - b.pos.getX()) < a.size + b.size) {
			if (Math.abs(a.pos.getY() - b.pos.getY()) < a.size + b.size) {
				return true;
			}
		}
		return false;
	}

But my main issue is that the move method does not work at all, and I have no idea why. Can anyone please just point me to a link or show me some code that selects the tiles around the player, and then checks to see if the player is colliding with them?

I’m so desperate!

#5

Really, no one can help me solve this simple problem? It’s not like what I’m doing is hard… I just don’t know what I’m doing wrong.

#6

This is my Array based collision code. It’s not as good as it could be though.

	public void playerMoveLeft(int x){
		for(int h = 0; h < x; h++){
			if(playerRect.x > 1){
			playerRect.x--;
			}else return;
				for(int i = (int)(playerRect.y / 64 - 1);i <= playerRect.y/64 + 1; i++){
					if(playerRect.overlaps(tileRect[(int) (playerRect.x/64)][i].rect)){
						playerRect.x++;
						return;
					}
				}
		}
	}
	public void playerMoveRight(int x){
		for(int h = 0; h < x; h++){
			if(playerRect.x < 64 * (mx - 2)){
				playerRect.x++;
				}else return;
				for(int i = (int)(playerRect.y / 64 - 1);i <= playerRect.y/64 + 1; i++){
					if(playerRect.overlaps(tileRect[(int) (playerRect.x/64 + 1)][i].rect)){
						playerRect.x--;
						return;
					}
				}
		}
	}
	public void playerFall(int y){
		for(int h = 0; h < y; h++){
			if(playerRect.y > 1){
			playerRect.y--;
			}else{
				reset();
				return;
			}
			for(int i = (int)(playerRect.x / 64 - 1);i <= playerRect.x/64 + 1; i++){
				if(playerRect.overlaps(tileRect[i][(int) (playerRect.y/64)].rect)){
					playerRect.y++;
					grounded = true;
					return;
				}
			}
		}
	}
	public void playerJump(int y){
		for(int h = 0; h < y; h++){
			if(playerRect.y < 64 * (my - 2)){
				playerRect.y++;
				}else return;
			for(int i = (int)(playerRect.x / 64 - 1);i <= playerRect.x/64 + 1; i++){
				if(playerRect.overlaps(tileRect[i][(int) (playerRect.y/64 + 1)].rect)){
					playerRect.y--;
					return;
				}
			}
		}
	}

It’s split up because that’s just how I roll.

#7

No offense, but that really doesn’t help as you’re using the Rectangle class, and I’m using my own AABB class. If I was using the Rectangle.intersects method, I would already be done. But I don’t want to, I want to figure it out my own way.

#8

An AABB is a rectangle. The actual collision isn’t what was even important, as all you need to know is how I choose which rectangles to check for collision.

#9

Correct, but I’m simply trying to get the four tiles around the player. Your method is far to advanced for what I need to do, and it’s driving me crazy that no one can help me.

#10

The issue is most likely due to you only detecting the 4 neighbouring tiles. You should check all 8 around you. The way you described it sounds like your player’s centre is too high(or too far left) for it to check the tile it is going through. Until it gets halfway through the tile, you are checking the empty tile next to it for collision.

I’d suggest checking the 8 tiles around the player, instead of just 4.

#11

You should really check all 8 surrounding tiles like I and RawringNymNym pointed out. I don´t know if you read my earlier post but here´s one simple way: a double for-loop, getting the x/y tilecoordinates of the tiles and then check if there is an overlap. Here´s some psudocode I threw together:

for (int y = player.tilePositionY - 1; y <= player.tilePositionY + 1; y++)
   for (int x = player.tilePositionX - 1; x <= player.tilePositionX + 1; x++)

   {
   if(tiles[y][x].isCollidable == true)
       Collision.checkCollision(tiles.[y][x].box(), player.box());
   }

If you´re having problems then try to simplify it so you just try out the core function. For example, forget about the color for now, just use a simple System.out.println(“Collision”) and what tilecoordinates are colliding. Another thing that can cause trouble is stuff like this: “(pos.getX() + (pos.getX() + 32)) / 2”. Calcuations like has caused me a lot of headache, ´cause it´s so easy to slip in an error and they can be a pain to find.

#12

Here’s something I wrote last month (haven’t been bothered refactoring it so it’s slightly messy):
Bounds class: http://pastebin.com/vcXA3C4h

Tile class (can be nested in a map class for example):


public class Tile extends Bounds {
	private boolean empty; // this would specify if the tile can be collided with

	Tile(int x, int y, int size, boolean isEmpty) {
		super(x, y, size, size);
		this.empty = isEmpty;
	}
		
	public boolean isEmpty() {
		return empty;
	}
}

Collision detection:


public static ArrayList<Tile> getMapOverlap(Bounds bounds) {
	overlap = new ArrayList<Tile>();
	for (Tile[] columns : cells) { // cells is a 2d array of tile objects
		for (Tile tile : columns) {
			if (bounds.touches(tile) && !tile.isEmpty()) { // remove !tile.isEmpty() check if you want all 4 tiles
				overlap.add(tile);
			}
		}
	}
		
		return overlap;
	}

The method getMapOverlap would return all the tiles overlapping the bounding box. You could easily change this to fit your code. If for example you have an array of ints just change the getMapOverlap() method.

Your loop cycle would be something similar to:

  • Update positions
  • Check for collision on those positions and respond accordingly
  • Render and repeat
#13

This is the code I use for collision detection.


public boolean bump(Obj obj) {
	for(int x = 0, y = 0; y <= obj.height;) {
		if(this.getX() + x >= obj.getX() && this.getX() <= obj.getX()-1 + obj.getWidth() && this.getY()-1 + y >= obj.getY() && this.getY() <= obj.getY()-1 + obj.getHeight()) {
			return true;
		}
		
		x++;
		if(x >= obj.width) {
			y++;
			x = 0;
		}
	}
	
	return false;
}

And this is the move code;


public void move(double xS, double yS, GamePanel panel) {
	this.x += Math.round(xS);

	for(Map mp : panel.mapList) {
		if(mp.name.equals(panel.actualMap)) {
			for(Obj obj : mp.objList) {
				if(this.bump(obj) && obj != this) {
					this.x -= Math.round(xS);
					
					this.xSpeed = 0;
					
					break;
				}
			}
		}
	}
	
	this.y += Math.round(yS);
	
	for(Map mp : panel.mapList) {
		if(mp.name.equals(panel.actualMap)) {
			for(Obj obj : mp.objList) {
				if(this.bump(obj) && obj != this) {
					this.y -= Math.round(yS);
					
					this.ySpeed = 0;
					
					return;
				}
			}
		}
	}
}

As you can see in the second code, I add the xSpeed/ySpeed to the obj’s x/y, and then I check if it bumps any obj, if it does, I subtract the xSpeed/ySpeed from the obj’s x/y, if it doesn’t bump anything, the method terminates.

I don’t think this is a good idea for collision detection, but I don’t know other way, so, I hope it helped you.

#14

Take a look at this.