Thread: Efficient Object Detecting?

Hi, I'm currently working on a 2d platformer engine and I'm trying to make it as optomised as possible. The problem however, is that I can't figure out how to efficiently detect objects in an Arraylist without going through the whole thing like so:

for(int f=0;f<Level.tile.size();f++){
			if(Level.tile.get(f).contains(pt1) || Level.tile.get(f).contains(pt2)){
				if(Level.tile.get(f).id==1 || Level.tile.get(f).id==2 || Level.tile.get(f).id==3 || Level.tile.get(f).id==10){
				tiley=Level.tile.get(f).y;
				isTouchingFloor=true;
				return true;
				}
			}
		}

Is it possible to only check the objects that are in between two specific x and y points king of like:

If the object's x and y are greater than the screen's top right corner and less than the screen's bottom right corner, then check the object in relation to the player.

Use a spatially-aware data structure.

The simplest would be a grid. For most cases this will probably be good.

It's possible to also do some type of hierarchical structure like a QuadTree or a Kd-tree, though I would say these are overkill in 2d space (especially with many moving items).

From what you posted, grids seem a bit complicated helloworld, especially when trying to implement them with the current format. Is there some sort of way to check only objects that are being touched by the player object perhaps?

You need to find which objects could be touching your player first before you actually can check if they do touch.

That's where your spatial data structures come in: they arrange your objects in such a way that you can navigate through them based off of spatial coordinates rather than indices. A grid just happens to be the simplest one in 2D space I know of.

A grid isn't that complicated of an idea, you just take your 2D space and divide it into an evenly spaced 2D grid buckets. Every object who's bounding box happens to be in a certain grid gets added to that grid's list of objects. When you want to find objects which could potentially collide with a certain object (say, your player), you first figure out which grid buckets your player's bounds overlap with, then retrieve all the objects which happen to be in those grid buckets. It's easy to figure out which grids your player's bounding box overlaps with because the data structure has a simple linear transform from (row,col) indices to spatial (x,y) dimensions.

grids do have down sides, for example they don't do so well when you have objects have very different sizes from each other or when you have to move large objects, but for the most part they work really well in 2D space.

You could also use a basic scan-line method (I can't remember the actual name).

Basic idea:

Sort your objects in the array by their coordinate (say, first by x then by y). Then run from one side of the array to the other (or use a modified binary search), comparing bounding boxes with your player's bounding box.

This method works fine if you're not expecting a lot of objects to be cluttered around a certain portion of the primary axis (say a lot of objects between x=0 and x=10 where you're searching). A grid improves on this by first making the spatial searching much quicker/easier and reducing the size of the search so there would have to be a lot of objects close to your player in both the x and y directions before you start having issues.

If you have a 2D side-scroller application where there really isn't much an up/down direction, a scan-line method would probably be good enough. However, if your application has a 2d map with objects scattered more or less in both x and y coordinates, you may want to consider using a grid. Note that a grid would probably do about as well in 2D side-scroller applications (it's hard to tell because there are some factors which a scan-line method has the advantage and others where a grid has the advantage).

Last note:

You may not need anything at all. Profile and test your program before you begin optimizing to help you identify if it is even required and if so, what areas can provide the biggest gains. You may also find that a simple scan-line works better or good enough for your needs. That's part of the fun.

Yes I know about the case method and have used it in other places, I just haven't bothered to change that yet, as I'm not 100% familiar with it yet. I'll try and see if it really needs a grid, and if so, I'll try to implement it, but the problem is that I tend to be a very visual person, so that's why the page you linked seems a bit complex to me. The main reason I'm asking though, is that larger stages might need more memory because of having to check every object.