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: