How to implement Spatial Partitioning.

Newbie & Debugging Questions
#1

First a bit of background. I’m quite new to programming only learned Java in Uni about 6 months ago and I do my best to improve myself on it everyday. So what seems obvious to you is not that obvious to me. Apologies.

My game is a Simple 2d side scrolling platformer. Right now I’m just tweaking the engine and everything is just running on shapes.

The problem I’m encountering is having to update(), render(), and checkCollision(), if I have 1000 objects.

Note I store all my created game objects in a LinkedList object;

For example my checkCollision goes someting like this using .intersects from the Rectangle class.


for (int i = 0; i < object.size(); i++) {
			if (object.get(i).getObjectId() == ObjectId.Block) {
				if(player.getBounds().intersects(object.get(i).getBounds())){
					//Collision Detected! Do someting
				}
			}
		}

And my render and update would be similar and it looks like this;


for (int i = 0; i < object.size(); i++) {
			object.get(i).render(g); or object.get(i).update(); 
		}

My game runs fine with a few hundred objects which is more than enough for 1 level but I really don’t want it to be inefficient.
I’ve tried something like only checking for objects that are in a specific proximity to the current position of the player. using Math.abs
and it goes something like this

getX() = object’s current X coordinate.


for (int i = 0; i < object.size(); i++) {
			if(Math.abs(player.getX() - object.get(i).getX()) < 100){
				//Then this object is in proximity so you can render, update and checkforCollision.
				//action
			}
		}

The above code runs better however it still has to getX() from 1000 different objects everytime. I googled quite a bit and I’ve come across 2 terms that I don’t know how to implement to my game. 2 techniques for broad phase collision. 1. Spatial Partitioning and 2. Sweep and Prune. Spatial Partitioning is the one I think I want to apply.

I’ve read a bit of it and watch videos about Spatial Partitioning but I think I need to have more experience in programming to fully understand and be able to implement it. The video talked about putting grids/sections on my game space. Then check my collision to objects with other objects only those in close proximity via the grid.

So yeah my trouble is trying to use this technique; How do I create the grid and how do i insert my game objects in a Linked List into it.

If anyone has time here is my eclipse project link

https://github.com/andrevicencio21/onepiecegame/tree/master/OnePieceGame

and here is the video of a guy explaining spatial partitioning/

Thanks :slight_smile:

#2

Change the one line “LinkedList” to “ArrayList” and watch your performance magically skyrocket!
Don’t use LinkedLists. Especially don’t use them and then repeatedly call get() on them.

You don’t need spatial partitioning for less then a few thousand entities. “Brute force” is faster than you think, at least if you steer clear of linked lists.

Also as a general rule, don’t try to make things faster if you don’t yet need them to be faster, meaning you are having a problem, or are experienced enough to know that it will be a problem.
I’m telling you that a simple 2D sidescroller is not going to be a problem.

#3

I gasped as this line! A few thousand… haha.

Alright ill rewrite my objects to be stored in ArrayList and I’ll see how it goes. Thank you! :slight_smile:

#4

Yeah as long as the checks aren’t too expensive, just go ahead and chug through the whole list. If it’s not slow, then no need to add complexity.
If it was handling a few hundred or whatever using a linked list, then it will handle a few thousand no sweat without it.
Google around for “linked list vs arraylist time complexity” or similar to see why.

Consider the fact that modern CPU speed could be measured in operations per light inch, and that that number would often be greater than one. They’re fast.

#5

partitioning is much about distributing computation and trading for memory. we cannot tell how many “entities” we’d need to get better performance from partitioning in general … it depends on too many things :

  • cost of indexing “entities” into the partition (depends on the implementation of the partition, grid, tree, points/volume)
  • cost of selecting from the partition (depends on the query type, nearest, range, shape, line, ray …)
  • cost of processing selection (why do we select at all ?)

sum of those should be less than brute-force.

for instance, if you do n-body simulations, galaxies … a all-pairs computation … you can process 2000-3000 point-mass objects, multithreaded. using a grid-partition (and cutting of gravity 1/r^2 at a low value) would boost speed by alot … if objects are spreaded in space. once everything collapsed into a single grid-cell, the purpose of the partition is defeated.

in this case : grid = fast indexing, slow processing.

using a octree/quadtree partition instead … and using the nodes to average data can boost things by alot more. in this case : tree = slow indexing, fast processing.

another example: simulating water with particles, also n-body but with “negative gravity”. using a simple grid partition would yield better performance over a tree. fast indexing, small radius selection.

in your case, a 2D collision test, a grid partition would be a good choice. collision means you separate objects which lowers the chance of having all objects in a single cell. selection candidates with aabb’s is natural for grid-partitions. it depends on the complexity of the shapes you collide then … i guess even with just 20 entities you could get it to be not more expensive than brute-force.

even if it would be 10 times slower than brute-force, with just a few entities this process would still be silly fast. question if you “need” a partition is absurd now but i think it’s good to start using one early. adding it later, if you really need one can be painful and frustrating.

o/

#6

Stuff like quad/oct-trees are a PITA in java since there isn’t an easy way to do plain old data arrays.