Allegro.cc Forums » Programming Questions » Dozens of collisions every frame

Credits go to Ben Delacob, Paul whoknows, Sol Blast, TeamTerradactyl, Thomas Harte, and Tobias Dammers for helping out!
 This thread is locked; no one can reply to it.
 Dozens of collisions every frame
 Sol Blast Member #9,655 April 2008 Have you thought about screen regions?
 Tobias Dammers Member #2,604 August 2002 OnlineCop said: Is there a better way to keep the number of balls I have to test low so I don't have a Big-O value of O(n^2) or there-abouts? In ascending order of effectiveness, here are your options:1. Axis-sort. Pretty much what you describe: Sort everything along one axis, and when you find an object that is farther away than the maximum possible collision distance (usually the sum of the radii of the largest objects), stop iterating. This is still O(n²), but typically, you can reduce the number of tests by something like 90%.2. Sector-based space partitioning. Divide your area into sectors that are easy to describe mathematically (typically squares), and keep a list of objects in each square. When testing for collisions, only test against objects in sectors that are nearby. Assuming that there is a maximum number of objects for each sector, this algorithm is O(n): For each moving object, a constant maximum number of other objects needs to be checked.3. Quadtrees. Like 2., but the sectors are created dynamically, and each sector is divided into sub-sectors until it contains a minimum number of objects, or until it has reached the minimum size. The partitioning part can be quite costly, but in most scenarios, the quadtree doesn't change much from one frame to the next. In your case especially, the objects in the quadtree (the ones from the second container) don't move at all, so you only need to update the tree when you add a static object. ---Me make music: Triofobie---"We need Tobias and his awesome trombone, too." - Johan Halmén
 Thomas Harte Member #33 April 2000 Tobias Dammers said:In your case especially, the objects in the quadtree (the ones from the second container) don't move at all, so you only need to update the tree when you add a static object. cough and when you remove a static object (since the static balls are eventually retired). Single removals from a quadtree aren't very expensive though — if you're collecting things in leaf nodes in a linked list then in principle you can merge into a super node by setting three pointers and releasing some memory. And most deletes probably won't require a subsequent merge.EDIT: or, I suppose, if you never merge then your quadtree approaches a sector implementation automatically, albeit one where it takes O(log4(n)) to find the sector you want rather than O(1) [My site] [Tetrominoes]
 Ben Delacob Member #6,141 August 2005 If you happen to use a sorted list, sorting every frame shouldn't be costly so long as most of the balls aren't moving too fast and changing order entirely every frame. Don't dismiss old bubble sort - Edit: Use Insertion sort. See Thomas Harte's post below - for a situation with less that ~100 items or especially in a mostly sorted array. The worst case would still be poor with more than ~100 items but the general case will be faster than quicksort. It depends on the exact environment. You should probably use some partitioning for your problem though. __________________________________Allegro html mockup code thread -website-"two to the fighting eighth power"
 Thomas Harte Member #33 April 2000 Ben Delacob said:Don't dismiss old bubble sort for a situation with less that ~100 items On the contrary: dismiss bubble sort, but don't dismiss insertion sort, which is bubble sort with most of the memory shuffling taken out. Though the two become completely indistinguishable in any list where no object needs to move by more than one position.Nit picking aside, I agree — sorting is nowhere near as bad a solution as you think. [My site] [Tetrominoes]
 Paul whoknows Member #5,081 September 2004 If you store your balls in ordinary arrays, and if you use an in-lined bounding box collision detection function, probably you are not going to need to implement any optimization at all. ____"The unlimited potential has been replaced by the concrete reality of what I programmed today." - Jordan Mechner.
 OnlineCop Member #7,919 October 2006 Have any of you taken a look at Boomshine? It's essentially what Facebook's Chain Rxn is based off of, which I am trying to mimic. They don't actually use more than about 60 balls in either case, but I'm going to try to make my work more data-driven so users can actually make their own tweaks: let them customize the size, speed, and number of balls in play... which could mean that there is the potential of hundreds or thousands in play simultaneously.I guess at this point, I don't need to do any optimization and I'm just "thinking too hard" about it... I should "get it working" before trying to "get it working well". But if implementing some sort of optimization like sorting (axis-sort, sector-sort, quadtrees, screen regions), I can see how I would need to actually build AROUND those and it would require a significant rewrite to the code, making my current code almost worthless.So getting this right beforehand is important to me. But I'd be happy to post my current progress(es) as I go and get feedback.What I'm worried about is that sometimes, the mobiles balls in Container One can all clump together (actually, the player hopes for this, since they can get better scores if they can pop a bunch of balls, and this gives them a perfect opportunity), which would fill up one of the sectors, like Tobias was mentioning earlier:Tobias Dammers said:When testing for collisions, only test against objects in sectors that are nearby. Assuming that there is a maximum number of objects for each sector, this algorithm is O(n): For each moving object, a constant maximum number of other objects needs to be checked. See, the problem with this, is that there is no maximum number of objects for each sector, unless the sectors are dynamic (not fixed) in size. All balls are moving around randomly, and so they can all converge on a single spot during a particular instance. You can probably see then effect when playing Boomshine (from the link above).
 Ben Delacob Member #6,141 August 2005 You could make an exploding ball collision bitmap (or just use the regular buffer if you can) and test some pixels under a moving ball. That way would be O(n) but would require more drawing if you can't use the buffer and more checking for larger balls.Edit: Although size would be a hard variable to handle if things got larger. Alternating the pixels checked under a ball between frames might produce acceptable results. __________________________________Allegro html mockup code thread -website-"two to the fighting eighth power"
 OnlineCop Member #7,919 October 2006 The ball DOES get larger every frame, at least for a short amount of time. It also shrinks in size after a while.What I'm trying to do is figure out how to get Events to work in this.I have the ball's size actually keyframed so when the player drops the first non-moving ball onto the field, it begins to grow. It then hits its maximum size, holds that for about a second, then shrinks to nothing. I then hope that when its size reaches 0 that it will fire an Event that states that the ball needs to be removed from the Arena (and the list), so it is no longer considered for collision during the collision-testing.If, during every Update() cycle, I loop through each item found in the second container (of stationary balls) and check for collisions, the radius shouldn't really matter, since it will be the same mathematical calculations to check for collisions if the radius is small or large: simply a distance formula.I'm just trying to figure out how to cut down the NUMBER of collision checks I need to be doing on every frame, since sorting seems like it would be rather expensive to do.However, I will say this: The speed that the balls will be able to travel is fixed to a specific range (so it will be, for example, +/- 2.0 pixels/second, or something like that). Knowing that, I may be able to get away with only resorting the balls every few frames, and checking to see "if the ball is within this distance +/- 2.0 pixels", and then exclude balls further than that. That may help optimize slightly so I won't have quite the O(n2) that I was worried about...
 Tobias Dammers Member #2,604 August 2002 Paul whoknows said: If you store your balls in ordinary arrays, and if you use an in-lined bounding box collision detection function, probably you are not going to need to implement any optimization at all. If the number of balls is unknown and potentially very large, then an algorithm complexity of O(n²) is not really acceptable. ---Me make music: Triofobie---"We need Tobias and his awesome trombone, too." - Johan Halmén
 OnlineCop Member #7,919 October 2006 I've only seen two implementations of the game online so far, but I'm sure it's going to be something akin to Sudoku: once people figure out how it's implemented, it'll be everywhere. I just wanted to be the one to have his name in some official "ported to Linux/Windows/Mac/iPhone by OnlineCop" credits. Good design dictates that everything isn't hard-coded, and that anything that can be data-defined should be. So the size of the balls on each level, the number of levels, the number of balls per level, the number of balls to advance to the next level, etc., should all be in the hands of the players. Potentially, like Tobias pointed out:Tobias Dammers said:the number of balls is unknown and potentially very large so there's got to be some sort of optimization to keep this collision detection low...
 Paul whoknows Member #5,081 September 2004 Tobias said:the number of balls is unknown and potentially very large It should not be unknown, you should know the maximum number of balls allowed in order to prevent performance problems and/or crashes. ____"The unlimited potential has been replaced by the concrete reality of what I programmed today." - Jordan Mechner.
 Tobias Dammers Member #2,604 August 2002 If that number is potentially very large, then the limit needs to be very large as well, say, 10k balls; coding for numbers that large does require a space partitioning algorithm of some sort, there is simply no way you can efficiently do 10k² (100 million) collision detections per frame. ---Me make music: Triofobie---"We need Tobias and his awesome trombone, too." - Johan Halmén
 OnlineCop Member #7,919 October 2006 I believe I can keep the number of balls pretty low. I doubt the game will be very fun if there are 1,000 in-play balls flying around (even 100 is pushing it, since no implementation currently on the web or on iPhones support that many yet, though none are supporting full-screen and multiple monitors, either...).I will probably want to use a sorting algorithm that takes into account that the list will almost always be mostly-sorted, though will I want to sort the list only once, or will I want to sort it once along the y-axis before sorting it along the x-axis?It would let me use optimizations on both my x- and y-axis when checking to see if I can eliminate balls for collisions. There may be between 1 and a few dozen balls that line up vertically with a non-moving ball, so they may benefit from this, though passing them through two sorts every frame would get very time-consuming.Unless there were a way to sort only those balls that didn't "fail" the x-axis quick-elimination?
 TeamTerradactyl Member #7,733 September 2006 Use a merge sort, then. Or look on Wikipedia or some other site that explains the differences and benefits of different sorting algorithms and find one that specializes in nearly-sorted small lists, since you're not going to be doing much more than about 100 or so.I can see someone using multiple monitors or full-screen where you'd use more than 100 balls in play at once, but if that many balls are getting popped at the same time, you're also going to have that many balls being removed just as rapidly, so if there's any slow-down or stuttering going on, they'll only notice it for a second or two before the number drops back down to a reasonable rate, and the stuttering goes away. There... problem solved.Now quit whining and show us some source code. What do you have so far? I want to play this game already.
 Go to: Allegro Development Installation, Setup & Configuration Allegro.cc Comments Off-Topic Ordeals The Depot Game Design & Concepts Programming Questions Recent Threads