Allegro.cc - Online Community

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. rss feed Print
Dozens of collisions every frame
OnlineCop
Member #7,919
October 2006
avatar

I'm going to have two containers filled with Ball objects. The containers will be either arrays (std::vector<Ball*>) or linked lists (std::list<Ball*>). (I'm not talking about literal "containers", like a box or some confining area or anything like that.)

Balls within the first container will be mobile and bounce all around the screen. There will be no collision detection taking place between them and any other balls in the same container. This container may have up to several dozen (or low hundreds) of Ball* objects bouncing around.

To start out with, there are no balls within the second container. When the player clicks somewhere within the playing arena, they drop a stationary ball that is placed immediately into this second container. All mobile balls from the first container will test for collisions against any and all Balls in the second container.

Any time a mobile ball from the first container collides with a stationary ball from container two, it too becomes stationary and gets moves into the second container as well.

Now comes my question about the collisions:

For every logic update (probably happens every frame update, or 1/20th or 1/30th of a second), all Balls in container one will move.

I guess what I can do is sort all the balls in the field at this point by either their x or y coordinates (every frame? :o) and check against all known immobile balls found in container two (these will already be sorted, since their positions are fixed). If a ball's x-coordinate (if sorting by x) is less-than the first "container two" ball's x-coordinate, it can be safely discarded since it hasn't collided. Similarly, if a ball's x-coordinate is greater-than the last "container two" ball's x-coordinate, it (and all the other "sorted" balls we'd need to test) are further away, and don't need to be tested for collision either.

So that's optimization option #1.

Another idea is to have a messaging system where each ball in container two broadcasts its position while it's still alive (balls in container two only have a short lifespan before dying, kind of like a particle system), and all balls in container one can listen for those coordinate and notify the system if it collides with one of those "container two" balls. The only disadvantage would be a message flurry if a player happens to hit a patch of tightly-packed balls close together, until all of the balls died away.

But I'm not sure how to sort the balls in this case. Or would I sort the coordinates of the balls that the messages are about, and discard too-far-away balls?

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?

Cookies if I can get this working!

EDIT: In case anyone's wondering, it's the same game as what I posted earlier: kind of like Chain Rxn (Facebook) or Boomshine.

Sol Blast
Member #9,655
April 2008
avatar

Have you thought about screen regions?

Tobias Dammers
Member #2,604
August 2002
avatar

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
avatar

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)

Ben Delacob
Member #6,141
August 2005
avatar

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
avatar

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.

Paul whoknows
Member #5,081
September 2004
avatar

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
avatar

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:

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
avatar

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
avatar

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
avatar

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
avatar

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. 8-)

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:

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
avatar

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
avatar

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
avatar

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
avatar

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: