Not logged in, Join Here! or Log In Below:  
 
News Articles Search    
 

 Home / Game Design & Programming / speeding up pool game physics Account Manager
 
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.
 
marc74

February 06, 2005, 11:50 AM

Hi,

One of my programmers is working on a pool game for a platform of very limited cpu power and this shows in the speed of the physics.

He's looking for a way to speed things up so can anyone recommend some of the general approaches ?

Firstly with 16 balls on the table there probably needs to be some sort of spatial partitioning test to reduce the 256 trivial reject tests. Perhaps maintaining a list of all the balls sorted along the longest axis which would mean we only to need to check each ball forward until the first ball that doesn't collide in that axis which would mean all successive balls laos don't collide.

Secondly, what, if anything can be pre-calculated ? Although the cpu power of the system is quite limited we still have a few hundred kb of memory to play with.

Any pointers from people with experience of writing pool games greatfully received...

Thanks

 
Reedbeta

February 06, 2005, 12:49 PM

The longest-axis list seems like it would have problems. For instance, consider the following situation (sorry for ASCII art):

  1. --------------------------------
  2. |             (2)              |
  3. |                              |
  4. |                              |
  5. |            (1)(3)            |
  6. |                              |
  7. --------------------------------


If you only sort the balls by longest axis, you would first check balls 1 and 2 and see that they are not colliding, and then conclude that (1) was not colliding with any ball to the right of (2), which is incorrect since it's colliding with (3).

I think a better system would be to just lay out a grid over the pool table, and keep a list of which balls are in each grid square. Then, to check collisions, you only have to check each ball against the balls in its grid square and the eight neighboring ones.

 
Victor Widell

February 06, 2005, 02:49 PM

You can also keep a list of moving balls, and only do the collission detection on moving-moving and moving-still.

 
marc74

February 06, 2005, 03:15 PM

Sorry, I should have explained it better - in this case you would still check (1) against (2) and (3). You only stop checking against (1) when the 1d scalar distance to the next ball along that axis exceeds the diameter of a ball.

Reedbeta wrote: The longest-axis list seems like it would have problems. For instance, consider the following situation (sorry for ASCII art):
  1. --------------------------------
  2. |             (2)              |
  3. |                              |
  4. |                              |
  5. |            (1)(3)            |
  6. |                              |
  7. --------------------------------
If you only sort the balls by longest axis, you would first check balls 1 and 2 and see that they are not colliding, and then conclude that (1) was not colliding with any ball to the right of (2), which is incorrect since it's colliding with (3). I think a better system would be to just lay out a grid over the pool table, and keep a list of which balls are in each grid square. Then, to check collisions, you only have to check each ball against the balls in its grid square and the eight neighboring ones.

 
Moe

February 06, 2005, 03:42 PM

You mention 16 balls, so you probably play 8-ball. It could be 14-1 tough. Even if you intend to write a 9-ball or a snooker game when you put up all balls to start the game, a list along the longest axis seems quite unfortunate. Also during a game there are many situations when more balls are aligned closely along the shorter axis (a bulk of balls).

So, I would also go with a grid if you have enough memory.

Moreover the balls might have a high speed so you could probably easier (more efficiently) expand into a sweep test if you have a grid. Anything more than a grid seams over complex since your pool table has a limited size. Maybe a quadtree but then walking though the tree is likely to need more time than traversing a grid.

 
Danny Chapman

February 06, 2005, 05:14 PM

It's not clear from what you wrote what's already been coded, and thus whether this is a real problem or an anticipated one. I wouldn't discount the brute-force (N^2) approach out of hand - code it up and then at least you'll have something to compare the spatial partitioning schemes to. For one thing, it isn't as bad as you say - 16 potentially colliders is 120 collision pairs, not 256. You may find that if you do things like use a simplified distance function (not hypot(x, y)), only check pairs if one ball is moving etc then the actual number of substantial calculations is pretty small. Implementing a grid scheme for so few objects is bound to introduce overhead in the processing, and maybe more cache misses (if you have a cache :). When "N" is so small the these things may matter than the complexity-order of the algorithm.

 
This thread contains 6 messages.
 
 
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.