From: Ian Hobson <ian.hobson@...>
Date: 2010-03-15T01:09:57+09:00
Subject: Re: Newbie Help : Object

Hassan Schroeder wrote:
> On Sat, Mar 13, 2010 at 3:55 PM, Jerome David Sallinger
> <imran.nazir@yahoo.co.uk> wrote:
>   
>> Thank you for all the ideas peeps. Much appreciated, I was hoping that
>> there was some way to avoid iterators/loops such that a 'Ball' object
>> would be aware of its locatation in, for simplicities sake, '2D' space
>> and weather it shares it with anything else. If not then that cool but
>> maybe there is some undiscovered territory concept wise for me to
>> explore.
>>     
>
> I'd suggest looking at the Observer pattern.
>
> Have each Ball continuously register its location (x,y) with a single
> Observer object; an attempt to register to an occupied location can
> be handled however you want -- throw an exception, send the Ball
> a message to reverse direction, vaporize the Ball, etc.
>
> No loops or iterators in sight  :-)
>   
Hi Hassan, Jerome,

The observer object will have to do the same (computationally explosive) 
work to detect that the currently registering ball does not collide with 
any of the others. Each must be tested against the others, every time it 
moves, so this simply hides the calculations.

Three ways to reduce the computation occur to me....

1) The collision detection is transitive (If ball A touches B, then B is 
touching A), so there is no need to test both ways round. Simply ensure 
both balls respond correctly upon collision.

2) If you order the balls by their height (y coordinate) in space. Each 
ball would then only need to be tested against the few balls higher than 
itself until you find one so much higher it could not possibly touch 
even if they had the same x coordinate. (This could be modified to order 
the remaining balls by the distance from the first ball, which you 
discover on the first pass. Then you only need to test each ball against 
those that returned larger distances, in the range of distances d, from 
x<d<=D     where D is the diameter of the largest ball, and x is the 
distance of this ball from the first one.

3) Divide the space up into squares that are the same size as the 
largest ball. When a ball moves, calculate the 4 squares that it would 
partially cover (if it was the max size). This is a simple round and 
compare computation. Don't worry about claiming a square that it can't 
actually reach.

Then test that two balls have no claimed square in common. This will 
quickly reveal that they could not possibly be touching, (using simple 
integer computation) without dropping to floating point maths to 
calculate distance between centres.

Regards

Ian