Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Bullets vs. many Aliens collision - Need "efficient" method
Index -> Programming, Visual Basic and Other Basics -> Visual Basic Help
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
BigSams




PostPosted: 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
Sponsor
sponsor
Tony




PostPosted: 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?
Latest from compsci.ca/blog: Tony's programming blog. DWITE - a programming contest.
BigSams




PostPosted: 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




PostPosted: 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.
Latest from compsci.ca/blog: Tony's programming blog. DWITE - a programming contest.
Raknarg




PostPosted: 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




PostPosted: 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




PostPosted: 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




PostPosted: 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.
Latest from compsci.ca/blog: Tony's programming blog. DWITE - a programming contest.
Sponsor
Sponsor
Sponsor
sponsor
RandomLetters




PostPosted: 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




PostPosted: 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.
Display posts from previous:   
   Index -> Programming, Visual Basic and Other Basics -> Visual Basic Help
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 10 Posts ]
Jump to:   


Style:  
Search: