Newbie Help : Object

[Jerome David Sallinger]

Hello,

This question may be more to do with my understanding of OOP that the
actual contructs of Ruby so please be patient with me.

I am interested in visualizing data so am teaching myself to Programming
using Ruby via computer graphics. I am steadily building up my knowledge
and experience by writing by and executing rudimentary code around the
new thngs I learn. Now I'm stuck so i'll make the question as simple as
I can:

I create a window of Ball objects based on a Ball class that I have
written. Each Ball object is instantiated at a randon x,y location on
the screen and has random speed.

Each Ball object is able to reverse its driection (bounce) if it hits
the edge of the window.

If I have two balls and I want to detect whether they instersect with
each other as they move around the screen this is simple enough; the
ball class has an intersect() method which i can use to pass in a
reference to the other ball object. But what if there are are random
number of balls. How do I make it such that any Ball object would be
aware of the location of any other Ball object without having to resort
to nested for loops where I check the location of each Ball against
every other Ball?

Any ideas

 

[Jason Watson]

[Note: parts of this message were removed to make it a legal post.]

You might get more help if you show some code.

On Sat, Mar 13, 2010 at 1:15 PM, Jerome David Sallinger <

 

[Riccardo Cecolin]

Hello,

This question may be more to do with my understanding of OOP that the
actual contructs of Ruby so please be patient with me.

I am interested in visualizing data so am teaching myself to Programming
using Ruby via computer graphics. I am steadily building up my knowledge
and experience by writing by and executing rudimentary code around the
new thngs I learn. Now I'm stuck so i'll make the question as simple as
I can:

I create a window of Ball objects based on a Ball class that I have
written. Each Ball object is instantiated at a randon x,y location on
the screen and has random speed.

Each Ball object is able to reverse its driection (bounce) if it hits
the edge of the window.

If I have two balls and I want to detect whether they instersect with
each other as they move around the screen this is simple enough; the
ball class has an intersect() method which i can use to pass in a
reference to the other ball object. But what if there are are random
number of balls. How do I make it such that any Ball object would be
aware of the location of any other Ball object without having to resort
to nested for loops where I check the location of each Ball against
every other Ball?

Any ideas

You could set an array of n "Ball"s, check one against each other
element of the array then pop it out and repeat with remaining elements.
So the amount of intersect() methods you will call will be
\sum_{k=1}^{n-1} k instead of (n-1)*(n). Feel free to correct me if i'm
wrong.

Riccardo

 

[William Rutiser]

First, look at the #each method and its siblings. These will encapsulate
the loops.

For a reasonable number of balls, you could use an array to keep track
of all the balls, then something like:

intersects_with = []
balls.each do | a_ball |
if my_ball.intersect( a_ball )
intersects_with << a_ball
end
end

There are other similar iterator methods that can help simplify that
code. Incidently, it hasn't been executed.

When you have lots of balls or more complicated shapes, this problem
becomes computationally "interesting". It is very likely to be discussed
in books on graphics targeted for game programmers or others working
with 3D graphics.

All the comparisons have to be done. With suitable data structures and
algorithms, you may be able to save the results of the comparisons and
not have to do some of them again. But the algorithms and structures
get complicated quickly.

Perhaps someone will point you to a ruby library that is intended for
this sort of thing.

-- Bill

 

[Gary Wright]

This question may be more to do with my understanding of OOP that the
actual contructs of Ruby so please be patient with me.

Actually I think your question isn't really about OOP or Ruby at
all but instead is just an algorithm question related to
computer graphics or even a more general question about
combinations of things.

To bring this back to Ruby. If you have a collection of
objects and you want to consider all possible combinations
of two objects:

irb> collection = [1,2,3,4]
=> [1, 2, 3, 4]
irb> collection.combination(2).to_a
=> [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
irb> collection.combination(2).select { |a,b| (a-b).abs == 1 }
=> [[1, 2], [2, 3], [3, 4]]

I just showed selecting pairs based on a simple mathematical
criteria but the collection could have been your balls, and
the selection could have utilized your #intersect? method.

Note, you have to be using Ruby 1.8.7 or 1.9.X to have
the combination method.

Gary

 

[jbw]

[Note: parts of this message were removed to make it a legal post.]

I imagine an event library like ruby-event would suit this, but it might not

This question may be more to do with my understanding of OOP that the
actual contructs of Ruby so please be patient with me.

Actually I think your question isn't really about OOP or Ruby at
all but instead is just an algorithm question related to
computer graphics or even a more general question about
combinations of things.

To bring this back to Ruby. If you have a collection of
objects and you want to consider all possible combinations
of two objects:

irb> collection = [1,2,3,4]
=> [1, 2, 3, 4]
irb> collection.combination(2).to_a
=> [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
irb> collection.combination(2).select { |a,b| (a-b).abs == 1 }
=> [[1, 2], [2, 3], [3, 4]]

I just showed selecting pairs based on a simple mathematical
criteria but the collection could have been your balls, and
the selection could have utilized your #intersect? method.

Note, you have to be using Ruby 1.8.7 or 1.9.X to have
the combination method.

Gary

 

[Jerome David Sallinger]

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.

 

[Hassan Schroeder]

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

FWIW,

 

[Jerome David Sallinger]

Hassan Schroeder wrote:
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

FWIW,

Awesome! Thanx

 

[William Rutiser]

Hassan Schroeder wrote:
I'd suggest looking at the Observer pattern.


Awesome! Thanx

You may find it useful to look at the Wikipedia entries for "collision
detection" and "game physics".

-- Bill

 

[Ian Hobson]

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

 

[Hassan Schroeder]

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.

Sorry, I don't see that at all.

If every point on the surface maps to a data structure that holds the
identifier of the object that occupies it, it's a simple comparison to
determine if a given point is occupied or not.

 

[Jerome David Sallinger]

If every point on the surface maps to a data structure that holds the
identifier of the object that occupies it, it's a simple comparison to
determine if a given point is occupied or not.

Perhaps if there some games programmers reading this they could let us
know how its done in industry

 

[Bill Kelly]

Perhaps if there some games programmers reading this they could let us
know how its done in industry

I seem to recall encountering both techniques Ian mentioned in
games, many years ago. Definitely the 2D grid-based bucket sort.
The the one-dimensional bucket sort based on Y-coordinate sounds
familiar too. (Of course, if the balls can all become aligned
horizontally very often, then the 1D optimization breaks down.)


Note, collision can start to get pretty fancy. If you're moving
objects in discrete steps, and their velocity vector(s) have
sufficient magnitude, the objects can skip right past one another
when they should have collided. So there are various techniques,
depending on how accurate your collision detection needs to be.

Also, these days, there are a number of pre-existing 2D
collision libraries availble.


But anyway, you'll need something akin to the approaches Ian
mentioned to reduce the number of collision tests per frame.


Regards,

Bill