Computer: Algorithm
Balls-based Physics Engine   (+2, -2)  [vote for, against]
All balls.

Many years ago, I wrote a little asteroids style game for windows. It was a bit rubbish, but was based on a super-simple basic physics engine that provided the following exciting features:
• Real Collision† Detection!
• Simulated Gravity!
• Accurate‡ bounces!
• Intelligent Enemies! (with 3 separate behavioural modes - angry, flock, and flee!)
• Homing Missiles
• Bullets

And all that - the way it worked was there was an abstract object called an "Arena" which held both a series of parameters (e.g. a vector describing the magnitude and direction of the prevailing gravity) and a collection of "Entities" that could either be human or computer controlled. Each entity was described by a triangle that was inscribed within a circle.

Whenever one circle collided with another one (when their distances from one another was less than their combined radii) then a collision routine was run that determined the angle of collision, figured out the component forces, and applied the appropriate amount of acceleration to their movement/velocity vectors.

I would have liked to have had larger, non circular objects that would, rather than just acting like snooker-balls, had a richer set of behaviours, such as spinning, breaking, pivoting and all-round acting in a physical manner. But moving away from the general form of a circle poses some real mathematical process-hoggers.

Take a long beam-like object for example. Now, you have to consider whether there are any other objects that may be colliding/in a near collision with it all the way along its surface. Nightmare.

So, instead - and this may be completely already the way they do it - but I've looked it up all over, and not found any widely known methods for doing this yet - instead - I figure a good way to approximate any shape is to replace it with a series of interconnected balls.

So, consider a square. Within it is inscribed a large circle, leaving gaps at each of the four corners. At each of the corners, insert another circle, so that each new circle's circumference touches two edges of the square, and a third edge touching the circle. Now there are some remaining gaps, so fill in these now with an additional 12 smaller circles - again, their edges touching the sides of the square, and any already drawn circles.

Now you've probably filled the square with a series of differently sized circles, to a degree of say 99% - yes there are gaps, but if you wanted to, you could fill them in with smaller circles.

Next, form links between these circles, store both the distance from centre to centre, and also the natural angle formed showing the bearings between each circle. You don't need to link all the circles to all the other ones, just maybe have 4 links from the main circle out to the 4 next-size-down ones, and from each of those, another 3 out to the next-size-down again ones. That's 16 links for our square.

Now what we have is 17 circles, linked by 16 links, arranged to approximate a square.

If I launch another square at this one, I can continue to use my nice simple circular-physics to inform motion, collision detection etc, and upon impact, impart a couple* of forces, to be resolved at the impact points and distributed via the links by applying simple, pre-stored tensors based on the movement of the impacted circle away from the angle and distance of the link. Super-simple (I think) and capable now of enabling some (hopefully) fast number-crunching in order to do the calculations for lots of objects on-screen (and possibly off-screen) at the same time.

The same technique should be applicable to virtually any shape, and if I provide a mass to each of my particles, my objects made up of same should behave as if they were proper, physical entities.

On the tensions felt by the pre-defined links - these could also be parameterised, giving one value to the amount of 'springyness' that it exerts when out of its ideal position. Springier links would mean taughter shapes, while more relaxed ones might provide more blancmange-type objects.

A second link-style parameter might be the 'breaking-point' at which a tension is no longer exerted. Either in the angular tensor, or in the distance tensor, or both. This would allow long, straight things undergoing bending to suddenly break in the middle, or for bullets to smash through a barrier or pillar and causing that to fail.

The point is that a rich mix of physical interaction is made available by use of this simplifying strategy, with the developer only having to describe the shapes to be placed, and overlay a front-end. The rest takes care of itself, so to speak.

The iPhone application§ can then be built and fame and fortune will thence be mine.

† - based on everything being circular.
‡ - on the assumption that everything is circular.
* - technical usage there
§ - pending deal with Android programmer

-- zen_tom, Mar 15 2011

This reminds me of the shapes made from balls joined with sticks that you construct in the game "World of Goo" (a very good game - I think you can download the first level for free). I believe "World of Goo" is built on top of a standard "Physics engine" common to many games.
-- hippo, Mar 15 2011

I remember reading an article about how the game Worms, and similar games with destructive terrain, calculate collisions.

One of the possible ways was to construct your terrain from large squares and add smaller squares to fill in the curve of the landscape. When an explosion overlaps a square, it splits into four smaller squares, and if any of them are partially overlapped, they split into four further squares, etc.

I quite liked this way of doing it but on this particular game-making website, someone provided conclusive evidence that it's quicker to have the entire map as an image with a transparent background. An explosion draws transparent pixels over this image, and collisions can be calculated very quickly since it's all done by the graphics card.
-- mitxela, Mar 15 2011

[+] - because I learnt something. Thank you.
-- The_Saint, Mar 15 2011

[mixtela] - interesting idea about the "corroding" background - also, I was thinking that since you can write a simple, repeatable procedure that can split a single circle into a "filled" set of smaller circles - you could code a kind of degredation of an object from complete (i.e. containing nice, big stable circles) to fragmentary (consisting of a much finer mesh of smaller circles connected by stretchy links) the degredation happening whenever there's a particularly hard impact.

<wiggles s-t-r-i-n-g-o-f-c-h-a-r-s at [bigsleep]> yes, I guess the overarching idea of splitting complicated things down into smaller bits is widely known to exist but (and this is solely my trying to come up with a suitable defence that makes this unique and remarkable) perhaps not in exactly in the way I've described - e.g. I took a look at a couple of 2d physics engines (Box2D primarily) and they all seem to adopt the full-fat approach (interesting manual on the Box2D page, describing in good detail how each element works)

[hippo] will take a look at Goo World to see if it offers any inspiration.

I'm currently at the stage where I'm trying to create a function that, given an arbitrary shape (defined by a sequence of points that describe the location of corners) I can iteratively populate it with a number of touching circles that cover at least a parameterised amount of its surface - starting with the largest possible circle at somewhere near the centre, and placing smaller ones into the gaps. It's quite an interesting problem when you get into it.
-- zen_tom, Mar 16 2011

random, halfbakery