# Implementing Grid-Based Collision System

**URL:** <https://discourse.processing.org/t/implementing-grid-based-collision-system/3248>\
**Category:** Processing\
**Created:** [September 4, 2018, 12:09pm UTC](https://discourse.processing.org/t/implementing-grid-based-collision-system/3248 "2018-09-04T12:09:27Z")\
**Posts on this page:** 13\
**Page:** 1

<div class="post-metadata">

**Author:** ![Sarah](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/sarah/32/1675_2.png) [@Sarah](https://discourse.processing.org/u/Sarah)\
**Post date:** [September 4, 2018, 12:09pm UTC](https://discourse.processing.org/t/implementing-grid-based-collision-system/3248/1 "2018-09-04T12:09:27Z")

</div>

Hi,  
Recently I’ve been creating a game with a player and enemies (Both classes). The player and enemies both shoot at each other, and I’ve been checking the collision between them a function `void hit(Bullet b) { if (<Colliding>) {<...>} }`.  
However as I add more and more enemies, the brute force method doesn’t seem to be working that efficiently. In the _Nature of Code_ book, it was mentioned briefly that a more efficient way would be to split up the canvas into sections and check the objects in each section against one another.

 ![Untitled%20drawing%20(5)](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/5/56814cce57e305ced6771be5408cbd49f97b76ae.png) !  
I’ve tried to do it by making a 2D ArrayList and adding the objects to the section they’re in, but I’ve run into some problems/questions:

- If you create a 2D ArrayList, wouldn’t you have to loop through all of the Arrays, thus using extra cycles?
- When using the grid system, how would you deal with border cases?
- How should I store the objects (In the sections)? Would it be best for a `class Grid {}` to organize them, or should I use an ArrayList to store them?
- Would it be possible to store all the entities (Player, enemies) in 1 ArrayList? (I’ve considered making a `class Entity` and `class Player/Enemy extends Entity`)

I’m not sure how understandable this is, so if you need any clarification, please ask! I’m relatively new to this topic, so any advice, whether it is a tip or some code, would be helpful!

Thanks! 🙂

---

<div class="post-metadata">

**Author:** ![jb4x](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/jb4x/32/789_2.png) [@jb4x](https://discourse.processing.org/u/jb4x)\
**Post date:** [September 4, 2018, 1:38pm UTC](https://discourse.processing.org/t/implementing-grid-based-collision-system/3248/2 "2018-09-04T13:38:50Z")

</div>

Hi Sarah,

The goal with a grid system is that you can reduce the number of entities you need to check. So if a bullet is in 1 cell of that grid you need to check only the star-ships that are 1 cell away from that bullet.

This would be also the way you handle your border cases. Since you are also checking your neighbors, you make sure that you won’t miss any star-ships.

The thing is that there is no perfect grid size for every game. It would depends on the way things react in your game, the size of each entities…

Your grid however, is way to wide. It need to be small enough so you won’t have to check all the game area but big enough so you won’t have to change the position of your bullet or start-ship every time it moves by 1 pixel.

It should answer your first 2 points.

For the 3rd points you can do both but I think making a class you make things a bit easier to handle.

And for the 4rth one: yes you can do it.

Hope I answered your questions 🙂

---

<div class="post-metadata">

**Author:** ![quark](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/quark/32/26_2.png) [@quark](https://discourse.processing.org/u/quark)\
**Post date:** [September 4, 2018, 4:40pm UTC](https://discourse.processing.org/t/implementing-grid-based-collision-system/3248/3 "2018-09-04T16:40:27Z")

</div>

The technique you are talking about is called _ **cell-space partitioning** _ which can be used in a number of scenarios but is particularly useful for large scale collision detection. Each cell would have its own data structures to store enemies and bullets in its cell so creating a `Cell` class is highly recommended.

In computing the word _efficiency_ can mean different things, in this case there are two types of efficiency to consider

1. amount of memory used to store the game data
2. the amount of CPU time to update the game data between frames - that includes movement and collision detection

Using cell-space partitioning (CSP) will always require more memory but on modern computers this is rarely a problem.

On the other hand the amount of CPU time required for brute force collision detection is proportional to - number\_of\_enemies X number\_of\_bullets and might be improved using CSP?

The answer depends on several factors

1. maximum number of collision detections (i.e. number\_of\_enemies X number\_of\_bullets)
2. the cell size in relation to enemy and bullet size
3. algorithm used to process border cases

- In general the more collisions to test the more likely CSP will help.
- If the cell size is too small then there will be more border cases which we would like to minimise.
- If the cell size is too large then we might have many enemies and bullets in the cell which again is undesirable
- The algorithm used for border cases depends on the actual data structure you create for the CSP but can be difficult to implement.
- Every time an object moves you need to confirm it is in the same cell, if not you have to remove it from the current cell and add it to the new cell.

I would suggest using a _quadtree_ data structure but it would be a very hard challenge for a beginner to implement.

---

<div class="post-metadata">

**Author:** ![Kevin](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/kevin/32/2297_2.png) [@Kevin](https://discourse.processing.org/u/Kevin)\
**Post date:** [September 4, 2018, 4:43pm UTC](https://discourse.processing.org/t/implementing-grid-based-collision-system/3248/4 "2018-09-04T16:43:30Z")

</div>

You might want to look into [quadtrees](https://en.wikipedia.org/wiki/Quadtree).

---

<div class="post-metadata">

**Author:** ![quark](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/quark/32/26_2.png) [@quark](https://discourse.processing.org/u/quark)\
**Post date:** [September 4, 2018, 5:10pm UTC](https://discourse.processing.org/t/implementing-grid-based-collision-system/3248/5 "2018-09-04T17:10:54Z")

</div>

The link below is for a Processing sketch I created which uses a quadtree data structure and allows the user to change the ball (moving object) size and configure some of the quadtree factors.

You might like to try it.  
[QuadTreeDemo](http://lagers.org.uk/zzz/QuadtreeDemo-180904.zip)

It requires the G4P library to be installed, can be done through the Contributions Manager

![10](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/d/ded501ceb1b093cbf5b7a724fcba96fcac31e069.png)

---

<div class="post-metadata">

**Author:** ![Sarah](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/sarah/32/1675_2.png) [@Sarah](https://discourse.processing.org/u/Sarah)\
**Post date:** [September 4, 2018, 11:48pm UTC](https://discourse.processing.org/t/implementing-grid-based-collision-system/3248/6 "2018-09-04T23:48:52Z")

</div>

Hi everyone!  
Thank you for your quick replies, they’ve been very helpful, I’ve been looking around google but couldn’t find much. I think I am going to start by making a class for a grid.

@jb4x, Thanks for your advice! You mentioned that you could have multiple objects in an ArrayList, would you do something like this: `ArrayList<Object> = new ArrayList<Object>();`?

@quark Thanks for your tips and your example - It really helped a lot. Are you okay if I use some of the principles in your code? (Not copying) Also, do you recommend multiple ArrayLists (One for Enemy, Player), or one ArrayList[][] for all of them?

@Kevin, I was going to but I felt that it was too complex and that a uniform grid would be easier to code.

Thanks, everyone for your help!

---

<div class="post-metadata">

**Author:** ![quark](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/quark/32/26_2.png) [@quark](https://discourse.processing.org/u/quark)\
**Post date:** [September 5, 2018, 10:09am UTC](https://discourse.processing.org/t/implementing-grid-based-collision-system/3248/7 "2018-09-05T10:09:43Z")

</div>

> [@Sarah](#):
>
> Are you okay if I use some of the principles in your code?

The principles / algorithms underlying cell-space partitioning and quadtrees were developed by others decades ago so are free for anyone to use. As for the actual code used in my sketch, you are free to use it in anyway you wish. This applies to any code that I create and place in a public domain.👍

> [@Sarah](#):
>
> Also, do you recommend multiple ArrayLists (One for Enemy, Player), or one ArrayList for all of them?

As far as I am concerned this is a no-brainer, always type your Java collections in other words each cell would have an `ArralList<Enemy>` and an `ArrayList<Bullet>` and if you had multiple players `ArrayList<Player>`. This is called generics and was introduced in Java 5 (I think it was V5 😁).

Before generics programmers like myself used simple arraylists e.g. `ArrayList enemies = new ArrayList();` (equivalent to `ArrayList<Object> enemies = new ArrayList<Object>();` with generics). This allowed the list to hold objects of any type/class which could lead to _logical_ errors that would crash the program at run-time. With generics the code that caused these errors are picked up at compile time as `syntax` errors which are easier to debug.

---

<div class="post-metadata">

**Author:** ![makoho](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/makoho/32/2176_2.png) [@makoho](https://discourse.processing.org/u/makoho)\
**Post date:** [September 5, 2018, 10:15am UTC](https://discourse.processing.org/t/implementing-grid-based-collision-system/3248/8 "2018-09-05T10:15:27Z")

</div>

Hi,

Daniel Shiffman has a set of Coding Train videos about precisely this issue, where he builds a quadtree from scratch and explain how it works and how it (drastically) improves performance:  
[https://www.youtube.com/watch?v=OJxEcs0w\_kE&t=477s](https://www.youtube.com/watch?v=OJxEcs0w_kE&t=477s)

Maybe you can pick up some pointers here for speeding up your collision detection algorithm.

---

<div class="post-metadata">

**Author:** ![Sarah](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/sarah/32/1675_2.png) [@Sarah](https://discourse.processing.org/u/Sarah)\
**Post date:** [September 8, 2018, 10:58am UTC](https://discourse.processing.org/t/implementing-grid-based-collision-system/3248/9 "2018-09-08T10:58:07Z")

</div>

@quark, In your example, when the parent `QuadTree` divides, how/does it transfer it’s current objects to it’s children? When I’ve tried to replicate this, I’ve only been able to split the parent into 4 `QuadTree`'s, but not have the children inherit the parents currents `GameObject`'s. I could insert all of the points into the children in the subdividing function, but I’m not sure if it’s the best way to do it.

Thanks!

---

<div class="post-metadata">

**Author:** ![quark](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/quark/32/26_2.png) [@quark](https://discourse.processing.org/u/quark)\
**Post date:** [September 8, 2018, 11:51am UTC](https://discourse.processing.org/t/implementing-grid-based-collision-system/3248/10 "2018-09-08T11:51:29Z")

</div>

In the demo the I created the QuadTree to keep overall statistics for the tree any is not needed in a production situation. The core class is the QuadPartition and the key QuadPartition object is `root` which represents the whole game domain and the topmost level of the tree.

This sketch demonstrates a _dynamic_ quadtree in which partitions sub divide only when they get a certain number of objects inside them. It is also possible to create a _static_ quadtree where all the partitions for each level are created from the start.

> [@Sarah](#):
>
> In your example, when the parent `QuadTree` divides, how/does it transfer it’s current objects to it’s children?

In this sketch the key is in the `GameObject update(float)` method. When the object’s position is changed it then checks to see if the partition has children _or_ if the object no longer fits into the partition, if either is true then the object is removed from the partition and then added back to the tree root. The object will sink down to the lowest partition that can hold it, if this partition has no sub-partitions and now has too many objects it will sub-divide.

So in my sketch the first call to `update` moves the objects and causes the subdivision (if needed) and the next call to `update` will cause the sub-divisions to be populated. Effectively the whole procedure works over two frames.

---

<div class="post-metadata">

**Author:** ![quark](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/quark/32/26_2.png) [@quark](https://discourse.processing.org/u/quark)\
**Post date:** [September 8, 2018, 11:59am UTC](https://discourse.processing.org/t/implementing-grid-based-collision-system/3248/11 "2018-09-08T11:59:25Z")

</div>

While answering this question I noticed a slight inefficiency in my `GameObject update` function so alter the end on the function from

```auto
	// If the node no longer fits in this partition or if the partition now
	// has children then reposition the node in the tree
	if(qp.children != null || !qp.contains(this)){
		qp.removeObject(this);
		root.addGameObject(this);
	}
}

```

to this

```auto
	// If the node no longer fits in this partition or if the partition now
	// has children then reposition the node in the tree
	if(!qp.contains(this)){
		qp.removeObject(this);
		root.addGameObject(this);
	}
	else if(qp.children != null){
		qp.removeObject(this);
		qp.addGameObject(this);
	}
}

```

---

<div class="post-metadata">

**Author:** ![Sarah](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/sarah/32/1675_2.png) [@Sarah](https://discourse.processing.org/u/Sarah)\
**Post date:** [September 8, 2018, 12:00pm UTC](https://discourse.processing.org/t/implementing-grid-based-collision-system/3248/12 "2018-09-08T12:00:29Z")

</div>

Thanks for your quick reply! I’m almost done with my QuadTree now, hopefully soon I’ll finish it!

---

<div class="post-metadata">

**Author:** ![Sarah](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/sarah/32/1675_2.png) [@Sarah](https://discourse.processing.org/u/Sarah)\
**Post date:** [September 9, 2018, 12:17pm UTC](https://discourse.processing.org/t/implementing-grid-based-collision-system/3248/13 "2018-09-09T12:17:18Z")

</div>

I’ve finished my grid-based collision system. Thanks to everyone who’s helped me!