Only checking for 2D collision that matters

Game Mechanics
#1

Hello, I am a complete newb in this forum and in java gaming in general. Reason why I started java gaming is because JAVA IS THE FUTURE
ok so with that out of the way I have a question.
I have made simple 2D java game, and for collision detection I use AABB(bounding box) method, and it was working just fine, as long as the amount of objects I used was below 30. But now that my map got bigger, the method checks for collision of every single object with main character and its slowing down the gameplay greatly.
So I was wondering how to do collision detection with objects that are in close proximity of main character rather than all the objects on map.
If someone could guide me to a great collision detection tutorial, I would be ever so thankful.
All my collision detection knowledge came only from http://www.metanetsoftware.com/technique/tutorialA.html

Thanks in advance to all who help ^^

#2

Think buckets! Break your play area down into regions (or ‘buckets’) and keep a separate list of objects for each. That way you only have to check nearby buckets for collision, rather than every object in the game.

#3

You want some kind of spatial tree, probably something like a quad tree.

Although 30 objects is nothing, you should be able to brute-force the collisions with 1000+ objects without breaking a sweat, so it sounds like you’re doing something wrong. Try posting code so we can have a look at it.

#4

This is my code
Its probably pretty crazy, hope you guys will understand it.
But yeah pretty much my for loop is too long


	public void move(Wall walls[]])
	{
		standing = false;
		for(int i = 0; i<walls.length; i++)
		{
			// sideways collision
			if(walls[i].getTopY()<this.getBottomY()-6 && walls[i].getBottomY()>this.getTopY())
			{
				if(walls[i].getRightX()>=this.getLeftX() && walls[i].getRightX()<=this.getLeftX()-dx)
				{
					//System.out.println("Hit from right (object to your left) on a wall");
					x = walls[i].getRightX()+5-leftOffset;
					dx = 0;
				}
				else if(walls[i].getLeftX()<=this.getRightX() && walls[i].getLeftX()>this.getRightX()-dx)
				{
					//System.out.println("Hit from left (object to your right) on a wall");
					x = walls[i].getLeftX()-5-image.getWidth(null)+rightOffset;
					dx = 0;
				}
			}
			//if statement for falling down and detecting collision from top or bottom of object
			if(walls[i].getLeftX()<this.getRightX() && walls[i].getRightX()>this.getLeftX())
			{
				// hitting a wall from top
				if(walls[i].getTopY()<this.getBottomY() && walls[i].getTopY()>this.getBottomY()-dy && dy>=0)
				{
					//System.out.println("Landed on a wall");
					standing = true;
					hit = false;
					y = walls[i].getTopY()-this.getHeight()+1+bottomOffset;
					dy = 0;
				}
				else if(walls[i].getBottomY()>=this.getTopY() && walls[i].getBottomY()<this.getTopY()-dy && dy<=0)
				{
					//System.out.println("Hitting head on ceiling of a wall");
					y = walls[i].getBottomY()-topOffset;
					dy = 0;
				}
				else if(walls[i].getTopY()<this.getBottomY() && walls[i].getTopY()>this.getTopY() && dy>=0)
				{
					//System.out.println("Standing");
					standing = true;
					hit = false;
					y = walls[i].getTopY()-this.getHeight()+1+bottomOffset;
					dy = 0;
				}
			}
		}
		
		if(!standing)
		{
			//System.out.println("Falling");
			dy = dy+GRAVITY;
		}
		y += dy;
		x += dx;
	}

And what did you mean by buckets SimonH?

#5

Ok, so you’re representing your walls in a 1d array, when you say you’re having slowdown with 30 objects, do you mean 30 walls or 30 objects? How big is your Wall[] array?

Your walls seem to be rectangles - are they positioned freely or are they tiles in a grid? Because if they’re tiles you should use a 2d array so you can directly index into them. If not then a quad tree is probably a good choice, but it depends what your levels actually look like and what your collision shapes are likely to look like.

#6

Yeah I meant 30 walls pretty much, anything beyond that shows a great slowdown. My wall is just an object which has an image, and x and y and width and height, and from there I get the rest. Also they are located freely, so I will probably end up using Quad trees.
By any chance would happen to have an example code or some explanation of how that might speed up things? Because I looked at it, and got the idea but I am still not understanding how its going to speed up the process. Because how I see it, is that quad tree would first check everything to see where I am located and then check the objects in that vicinity for collision, which still pretty much does what my for loop does. I mean probably by employing it, I will be able to go from 30 walls to maybe 60 walls without a slowdown, but is that the limit I will have to face? I mean how in the world do games like maple story (sorry for bad example) or mario have so many objects working all at once. I am pretty sure they got more than 60 objects.
Or would you suggest that I switch to the array method to speed things up.

#7

30 walls still sounds very low. Could you share the entire class that method is in to something like pastebin.com ?

#8

Ok so this is my main character class

http://pastebin.com/1pzgGTVq

And this is my main class where I draw all the images, and as soon as I get more than 30 lag begins.

http://pastebin.com/0yvS3Nhs

And this is my Wall class just in case you were wondering

http://pastebin.com/mz6ra3Kd

Sorry I am off to write exam on java, so I will read this once I get back home in about 7 hours.

But thank you very much for all of your help Orangy Tang, you are awesome.
The only reason why I tried to tackle this project is because I want to make a mario based game for my younger brother’s birthday, but I hit a brick wall.
Thanks a lot again

#9

After a quick look through I wonder if your cause of slowness is not the collision with the walls but actually drawing them. If you replace your g.drawImage(wall.getImage… with a g.fillRect, do you still get the same slowdown with 30 walls? If not then it’s your drawing and you probably need to fix your image loading. Search for usage of ‘createCompatibileImage’ to load your sprites rather than using ImageIcon should do it.

#10

umm, coulndt u just check if something is within a certain number of pixels of it(to answer OP)

#11

I agree with everybody here already. I’m pretty positive that the collision is not your bottleneck - it’s probably you’re rendering. Do you know how to profile?

#12

Just comment out all the rendering except for a FPS counter.

#13

So which rendering method should I use?
I kinda threw it together, but having had no classes in my university that deal with drawing to screen, I do not know anything.
Thanks a lot to everyone’s help, my brother will be very happy