Re: looking for suggestions to detect collisions in a java.awt.Graphics2D plane

My initial (and admittedly not well-thought) reaction is to not  
involve the GUI in the collision detection. It involves lots of  
needless overhead and I'm not sure you could have a couple of million  
Swing objects running around a system.

Instead, move towards MVC for the encapsulation, with the View being  
the GUI with Swing components, the Model being an array or matrix data  
structure, and the Controller being some clever matrix math routines  
or just simple array collision detection.

Each point in the array (or matrix) would represent one of your 15  
pixel creatures... unless you'll want arbitrary size critters in the  
future. Then I'd go to one pixel per array entry. Just set the "bit"  
in the array to on if it's occupied.

If you really want it to scale, split the area into arrays of arrays.  
You only have to compare agents within the same array to see if they  
collide unless they're edge cases... but even then you only have to  
compare them to an adjacent array.

By moving to arrays of arrays, you could scale the system to a size  
that has no practical limits. A given point on your "index matrix"  
could represent a "sub matrix" with 100, 10,000, or a million points  
internally.  The view into the system would only have to poll the area  
that's viewable on the screen.

By then you'll be thinking about threading and multi-machine to scale,  
but those are other fun problems to solve.

Jared
http://AgileArtisans.com
http://6sa.com


On Dec 1, 2007, at 8:31 PM, Richard O. Hammer wrote:

> I am writing an agent-based simulation in Java and I am looking for
> suggestions on how I can detect collisions between my critters as they
> move about on a two-dimensional plane.  These critters simulate living
> things (people perhaps) all continuously moving about, but no two of
> them should be able to occupy the same space at the same time.
>
> I have a way to detect collisions which works okay for small N, but  
> the
> required computation is N-squared, it increases with the square of the
> number of critters, and I want to find better.
>
> Let me describe more specifically:  The GUI is being drawn with Java
> Swing.  Each critter is circle shaped, a java.awt.geom.Area  
> constructed
> with a java.awt.geom.Ellipse2D, and 15 pixels in diameter.  In each
> increment of time in the simulation each critter can move some  
> distance
> in some random direction.
>
> To compute the move for each critter first I create the proposed Area
> that will be occupied if the move succeeds without collision, by  
> calling
> the Area method createTransformedArea(AffineTransform).  Then I test  
> to
> see if the proposed Area is already occupied by any other critter's  
> Area
> by looping through the other critters, subtracting each critter's area
> from the proposed area (with the Area.subtract() method).  If the
> proposed area is not changed by this subtraction then there is no
> collision, and the proposed move is allowed.  That works but it is
> N-squared.
>
> So I am looking for suggestions.
>
> One wishful idea I've had is to look at the color of the pixels in the
> proposed Area.  The background in my simulation is all white, but the
> Critters and other things are non-white.  So a proposed Area would be
> allowed if it was all white.  But I don't know the way to learn that.
> Can someone tell me that?
>
> Thanks very much,
> Rich Hammer
> Hillsborough
> <http://richard-o-hammer.org/firm.model.html>
>
>
>
>
> _______________________________________________
> Juglist mailing list
> [email protected]
> http://trijug.org/mailman/listinfo/juglist_trijug.org