"i know it's not efficient too ( O(n^2)"
The only way it should be O(n^2) is if you were checking bullets vs bullets. If you're just checking player vs enemy bullets, and enemy vs player bullets, then it should be O(n).
If you MUST check bullets vs bullets, then one way as others have mentioned is to use a grid to speed things up.
The grid would be an array of pointers to lists.
(You could use a 3D array but it might require a lot of ram if you have a lot of bullets)
Create the array then create a list for each square.
Clear the grid each frame by clearing the lists, then determine which squares a bullet overlaps and stick a pointer to it in the list for each square it overlaps.
Then go through the array and for each square test all objects in that square that may collide with one another against eachother. (A typical square might have no bullets, one bullet, or two bullets, though many more are possible.)
For each pair that collides, place that pair in a list.
Once you have all the colliding pairs, go through the list, and for each pair, swap their pointers so the smaller pointer is the first one.
Then sort the list such that you sort first by the pointer of the first object in the collision, and second by the pointer to the second object.
Ie, if we use letters to represent pointers, then your collision list initially might look like this:
D-E
B-C
A-D
A-C
C-B
A-D
After swapping it would look like this:
D-E
B-C
A-D
A-C
B-C <- This one changed
A-D
And after sorting it would look like this:
A-C
B-C
A-D
A-D
B-C
D-E
Now, go through the list, and check each pair with the next pair in the list. If the pair is the same as the next pair, then remove it from the list, leaving only one copy. (You could have three copies in a row, so don't skip checking slot 2 against slot 3 if slot 1 matched slot 2 and you removed slot 1.)
NOW we have a list where we have each pair of objects that are potentially colliding listed only once. We can now loop through this list and do a pixel perfect comparison between each pair of objects, or test their bounding rectangles or whatever you want to do, but there'll only be a few objects to test so the complexity of the test won't be so important, and there won't be millions of possible combiations to look at.
You might ask how many tiles you should have in your initial array. A good place to start would be making the grid squares twice the size of a bullet. This would give you a reasonably fine grid, and reduce the number of bullets that end up in more than one square by quite a bit. Four times the size of a bullet might be better. The only way to know is to test. There may be no noticable speed difference between the two though. If four is no faster than two, then you don't need to bother testing eight.
Btw, the reason you can't just stick each bullet in one square is if you do that, two bullets might be overlapping, but be in different squares so they wouldn't be tested. Or a large object might overlap many squares on the screen but would only end up in one. You can just use the objects bounding rect to decide which squares to put it in. If the top left corner is at 0,0 and the bottom right is at 2,3 then loop x 0 to 2 and loop y 0 to 3 and stick it in each of those squares.
The only way it should be O(n^2) is if you were checking bullets vs bullets. If you're just checking player vs enemy bullets, and enemy vs player bullets, then it should be O(n).
If you MUST check bullets vs bullets, then one way as others have mentioned is to use a grid to speed things up.
The grid would be an array of pointers to lists.
(You could use a 3D array but it might require a lot of ram if you have a lot of bullets)
Create the array then create a list for each square.
Clear the grid each frame by clearing the lists, then determine which squares a bullet overlaps and stick a pointer to it in the list for each square it overlaps.
Then go through the array and for each square test all objects in that square that may collide with one another against eachother. (A typical square might have no bullets, one bullet, or two bullets, though many more are possible.)
For each pair that collides, place that pair in a list.
Once you have all the colliding pairs, go through the list, and for each pair, swap their pointers so the smaller pointer is the first one.
Then sort the list such that you sort first by the pointer of the first object in the collision, and second by the pointer to the second object.
Ie, if we use letters to represent pointers, then your collision list initially might look like this:
D-E
B-C
A-D
A-C
C-B
A-D
After swapping it would look like this:
D-E
B-C
A-D
A-C
B-C <- This one changed
A-D
And after sorting it would look like this:
A-C
B-C
A-D
A-D
B-C
D-E
Now, go through the list, and check each pair with the next pair in the list. If the pair is the same as the next pair, then remove it from the list, leaving only one copy. (You could have three copies in a row, so don't skip checking slot 2 against slot 3 if slot 1 matched slot 2 and you removed slot 1.)
NOW we have a list where we have each pair of objects that are potentially colliding listed only once. We can now loop through this list and do a pixel perfect comparison between each pair of objects, or test their bounding rectangles or whatever you want to do, but there'll only be a few objects to test so the complexity of the test won't be so important, and there won't be millions of possible combiations to look at.
You might ask how many tiles you should have in your initial array. A good place to start would be making the grid squares twice the size of a bullet. This would give you a reasonably fine grid, and reduce the number of bullets that end up in more than one square by quite a bit. Four times the size of a bullet might be better. The only way to know is to test. There may be no noticable speed difference between the two though. If four is no faster than two, then you don't need to bother testing eight.
Btw, the reason you can't just stick each bullet in one square is if you do that, two bullets might be overlapping, but be in different squares so they wouldn't be tested. Or a large object might overlap many squares on the screen but would only end up in one. You can just use the objects bounding rect to decide which squares to put it in. If the top left corner is at 0,0 and the bottom right is at 2,3 then loop x 0 to 2 and loop y 0 to 3 and stick it in each of those squares.