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.
!
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!
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.
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
amount of memory used to store the game data
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
maximum number of collision detections (i.e. number_of_enemies X number_of_bullets)
the cell size in relation to enemy and bullet size
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.
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.
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.
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.
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.
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
Maybe you can pick up some pointers here for speeding up your collision detection algorithm.
@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.
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.
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.
While answering this question I noticed a slight inefficiency in my GameObject update function so alter the end on the function from
// 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
// 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);
}
}
).