2D game collision problems

Newbie & Debugging Questions
#1

Hey geys, I’m a long time lurker but I got stuck on a pretty big problem, so I decided to finally create an account and ask for some help for this issue. I would really appreciate it.
Anyways, let’s go right in to it shall we?

I’m creating a very simple 2D platformer game for learning purposes. To this point it has gone pretty good. I got almost all the basics in the game. I have read alot regarding collision the last couple days, because that was the feature I still had not implemented. I have created simple collision, where you shoot a bullet, and when it hits the enemy both objects removes.

But I have failed at implementing good collision for the player. What I am trying to do, is make in this case four boxes, one for every side, and for example when the player jumps on a platform object, the bottom collision box returns true and he stays on place. The code I have done so far glitch out like a crazy person. And after a few days trying to fix this problem I have not come much further then when I started on this issue.

I would post the code I have so far, but It’s on my other computer. If needed, I can post it later. But what I am looking for are some links to good articles, tutorials and so on. Because after alot of searching I haven’t found much that fits my needs.

And sorry for my bad english, it isn’t my native language.

Thanks!

#2

For a simple platformer you can use simple AABB collision. The basic idea is to assign a bounding box to everything that can collide and be collided with. So if your player is 32 x 32 pixels, create a bounding box for the player which holds its position and size, e.g:


public abstract class Bounds {

	int x, y;
	int width, height;

	public Bounds(int x, int y, int width, int height) {
		this.x = x;
		this.y = y;
		this.width = width;
		this.height = height;
	}

	public boolean collides(Bounds other) {
		return (x + width <= other.x && x >= other.x + other.width) &&
		(y + height<= other.y && y >= other.y + other.height);
	}

}

You’d extend the bounds class for everything that can be collided with, then you’d check for collision, e.g:


public boolean onGround(Player player) {
	for(Tile tile : tiles) { // tiles must have a bounding box
		if(player.collides(tile)) {
			return true;
		}
	}
	return false;
}

Collision response is much more complicated but would be easier if you use vectors for movement. You have a few basic options:

  • When the player collides with a tile, shift the player to the side of the tile that has the least distance between the edge. This is one of the easier options but can be inaccurate when the player moves quite fast.
  • Move the player back to its position at the previous frame. This is the easiest option but isn’t usually accurate enough for a platformer.
  • Calculate which side of the tile that the player collided with first. This is most easily done using vectors but isn’t that easy to do.

If you want pixel perfect collision which isn’t for rectangular objects then you have a lot of research to do. It’s a vast and somewhat complex topic.

#3

Faster AABB implementation: Here. (Does half the checks)

#4

Sorry to say, but it seems that your algorithm is almost 2 times slower than mine… You can try it for yourself. Here is the code. Just swap the comments to change which mode to use.

public class AABBTest {

	public static void main(String args[]) {
		
		long time0 = System.nanoTime();
		
		AABB r1 = new AABB(new Vector2Float(0, 0), new Vector2Float(50, 50));
		AABB r2 = new AABB(new Vector2Float(99, 99), new Vector2Float(50, 50));
		boolean bool = AABB.collides(r1, r2);
		
//		Rect rect1 = new Rect(0, 0, 100, 100);
//		Rect rect2 = new Rect(50, 50, 100, 100);
//		boolean bool = rect1.collides(rect2) && rect2.collides(rect1);
		
		long time1 = System.nanoTime();
		
		float time = (time1 - time0) / 1000;
		System.out.println(time + "  " + bool);
		
	}

	private static class Rect {
		
		public float x,y,width,height;
		
		public Rect(float x, float y, float width, float height) {
			this.x=x;
			this.y=y;
			this.width=width;
			this.height=height;
		}
		
		public boolean collides(Rect rect) {
			return collides(rect.x, rect.y) || collides(rect.x + rect.width, rect.y) ||
					collides(rect.x + rect.width, rect.y + rect.height) || collides(rect.x, rect.y + rect.height);
		}
		public boolean collides(float x, float y) {
			return (x >= this.x && x < this.x + this.width && y >= this.y && y < this.y + this.height);
		}
	}
	
	private static class AABB
	{
	   protected Vector2Float pos, size;
	   
	   public AABB(Vector2Float pos, Vector2Float size)
	   {
	      this.pos = pos;
	      this.size = size;
	   }
	   
	   public static boolean collides(AABB a, AABB b)
	   {
	      if(Math.abs(a.pos.x - b.pos.x) < a.size.x + b.size.x)
	      {
	         if(Math.abs(a.pos.y - b.pos.y) < a.size.y + b.size.y)
	         {
	            return true;
	         }
	      }
	      
	      return false;
	   }
	   
	   public static boolean inside(AABB a, Vector2Float b)
	   {
	      if(Math.abs(a.pos.x - b.x) < a.size.x)
	      {
	         if(Math.abs(a.pos.y - b.y) < a.size.y)
	         {
	            return true;
	         }
	      }
	      return false;
	   }
	   
	   
	}
	
	
	public static class Vector2Float {
		   
		   public float x, y;
		   
		   public Vector2Float(float x, float y) {
			   this.x=x;
			   this.y=y;
		   }
		   
	   }
}

When using AABB from your code, times were 750-1300.
When using Rect from your code, times were 410-700.

if() is almost free… Math.abs(), on the other hand, probably requires a lot more calculations.

#5

I have read your guys code. It seems like vectors are the best practise. I’m currently using the rectangle intersects method.
I have done alot of coding and I think I have solved most of my problems. It’s far from good code but it’s doing the job.

	//Check for bottom collision.
	public void bottomCollision(LinkedList<ObjectEntity> oEnt) {
		bottomCollision = false;
		
		for(int i = 0; i < oEnt.size(); i++) {
			if(this.getBoundsBottom().intersects(oEnt.get(i).getBounds()) && dy >= 0) {
				object = oEnt.get(i);
				y = object.getY() - (height -1);
				jumping = false;
				canJump = true;
				jumpSpeed = 18;
				bottomCollision = true;
			} 
		}
		if(!bottomCollision && !jumping) {
			dy += 10;
		}
	}

I have similiar code to this for my four collision boxes. I’m not having any lag at the moment, But I can guess this is pretty heavy on the performence?

#6

A benchmark doing one pass without any warmup period means nothing.

#7

I don’t really get your thought man o-O What is wrong with my bench-mark? Maybe if you’re trying to be 100% accurate, ofcourse. But I just wanted to prove that “my” way of doing that is faster. And it is.

#8

No, you did not prove anything. Take some time and read up on doing Java micro benchmarks correctly (let the VM warm up, beware of optimizations, etc.).

#9

Without doing any testing, I’d guess that using Math.abs() for collision detection has a very similar performance to the method I posted. [icode]Math.abs()[/icode] is the equivalent of using one if check, so in total that’s 4 if checks and 4 calculations. The method I posted also uses the equivalent of 4 if checks and 4 calculations. Lets also note that to calculate the central position, you’d have to do [icode]x + width / 2[/icode] and [icode]y + height / 2[/icode].

@OP: My advice is to not use the rectangle class. The intersects method is pretty much the same as the one I posted, however it unnecessarily declares and initializes new local variables for each side position of the rectangle. That won’t have much impact on performance, but if you’re fussy like me then it’s probably best to create an abstract class for the bounds and save a few bytes.

The main idea of AABB collision is to reduce the number of collision checks. You should create a big bounding box for the whole sprite, then you should do further collision checks only if necessary. In the image below, the black box would be the sprites dimensions, and the green boxes would be your four collision boxes.

Since the black box is not colliding with the ground, you would not need to do the further four collision checks.