Bullets vs. many Aliens collision  Need "efficient" method
Author 
Message 
BigSams

Posted: Sat Jun 11, 2011 5:53 pm Post subject: Bullets vs. many Aliens collision  Need "efficient" method 


So there are lots of bullets flying around in 2D. And a lot of aliens flying around. Both are circles. Aliens = red. Bullets = green. We need to detect exactly which bullet collides with which alien and get rid of both.
I need help with doing this efficiently because we can't just create the classic distance function and detect when one circle crosses the other by going through all pairings  apparently this is inefficient. We are supposed to "limit our use of the distance formula", but not necessarily forsake it entirely.
We are supposed to detect which bullet by color detection (when the central pixel of a bullet is red), which I have done. But now I have to detect which alien it hit, and I can't think of anything worthwhile other than comparing the distances between the bullet and each alien and choosing the smallest one... which we are not allowed to do as mentioned.
Since September, we've done ifs, nested ifs, for loops, do loops, nested loops, variable arrays, strings, control arrays, three basic sorting algorithms, recursive functions.. so most of the the elementary concepts.
Any ideas? I don't need code (unless you're willing), just good ideas. 





Sponsor Sponsor



Tony

Posted: Sat Jun 11, 2011 6:16 pm Post subject: RE:Bullets vs. many Aliens collision  Need "efficient" method 


To check if a specific bullet has hit something, do you need to calculate and compare the distance to every alien, or could you skip some? 
Tony's programming blog. DWITE  a programming contest. 




BigSams

Posted: Sat Jun 11, 2011 6:22 pm Post subject: Re: Bullets vs. many Aliens collision  Need "efficient" method 


We just need to detect inside which alien is the center of the bullet located. I already know how to detect the bullet though, so just need an efficient way of checking exactly which alien it hit.
Not entirely sure what you mean by skipping, but if have a method of detection that doesn't check all alins, I'm all ears. 





Tony

Posted: Sat Jun 11, 2011 6:42 pm Post subject: RE:Bullets vs. many Aliens collision  Need "efficient" method 


Some aliens would be far enough away that it would be impossible for them to have been hit by this particular bullet. You wouldn't need to calculate the distance for those. 
Tony's programming blog. DWITE  a programming contest. 




Raknarg

Posted: Sat Jun 11, 2011 7:42 pm Post subject: RE:Bullets vs. many Aliens collision  Need "efficient" method 


So, you haven't tried an array of bullets with an array of aliens and using rectangle collision detection, seeing as Math.Distance is out of the question? 





BigSams

Posted: Sat Jun 11, 2011 8:20 pm Post subject: Re: Bullets vs. many Aliens collision  Need "efficient" method 


I have an array for the x and y of aliens and each bullets, so 4 total arrays.
But both aliens and bullets must be circles. 





Raknarg

Posted: Sat Jun 11, 2011 8:23 pm Post subject: RE:Bullets vs. many Aliens collision  Need "efficient" method 


That doesn't matter, you can still use rectangular collision. When I say that, I mean something like this:
Turing: 
if x > 50 and x < 100 and y > 50 and y < 100 then...

You can use that. It wont be perfect collision, but if its pulled off well it'll work just as fine. 





Tony

Posted: Sat Jun 11, 2011 9:05 pm Post subject: RE:Bullets vs. many Aliens collision  Need "efficient" method 


@Raknarg  you are thinking in the right direction. Nice. The approximation is reasonable enough for small enough radii, but will be visibly buggy for large enough circles. But,
the square box around the bullet creates an area such that anything outside is guaranteed to not be in a collision. Statistically there will be very few items in this area. 
Tony's programming blog. DWITE  a programming contest. 




Sponsor Sponsor



RandomLetters

Posted: Sun Jun 12, 2011 11:35 am Post subject: RE:Bullets vs. many Aliens collision  Need "efficient" method 


You could also divide the screen into grids, check which objects are in each grid, and only compare objects in the same grid (using circle, or rectangular, or just pixel). This would do nboxes*n comparisons, plus (n/nboxes)^2 comparisons, i think that's better than n^2. Although this only really matters for huge numbers of enemies. 





Ultrahex

Posted: Sun Jun 12, 2011 10:31 pm Post subject: Re: Bullets vs. many Aliens collision  Need "efficient" method 


Just to be clear, splitting the screen into a grid, does not make the worst case runtime any better, since all things could potentially exist in the same "section", however in practice this is generally not the case. 






