LH 3 Apr 2003 - This is a minor improvement to Colliding Balls by David Easton. Devoting a separate page for this material is not meant to suggest any special importance of what follows. The real reason is not to break reapability of the original code (see wish-reaper or wiki-reaper for an explanation). See also Colliding Coins.
David Easton 4 Apr 2003 - Great improvements and simplifications. They make a huge difference to the performance - one tenth the CPU usage on my NT machine!
The calculations in postColVels can be simplified as follows:
proc postColVels {u1 u2 m1 m2} {
set u [expr {2*($m1*$u1+$m2*$u2)/($m1+$m2)}]
list [expr {$u-$u1}] [expr {$u-$u2}]
}In collide, one can do without the fragment
# Always call the ball on the right (2) and the one on the left (1) ...
by changing
# If they are not going towards each other, then they will not collide
if { $uparr2 > $uparr1 } {
return
}to
# If they are not going towards each other, then they will not collide
if { $x1 != $x2 } {
if { $x1<$x2 && $uparr2>$uparr1 || $x1>$x2 && $uparr2<$uparr1 } return
} else {
if { $y1<$y2 && $uparr2>$uparr1 || $y1>$y2 && $uparr2<$uparr1 } return
}In collide, the angle of the collision axis is computed by
set diffX [expr 1.0 * ($x2 - $x1)] set diffY [expr 1.0 * ($y2 - $y1)] set phi [expr atan ($diffY / $diffX)]
Unfortunately, phi is undefined if diffX is zero. A correct version:
if { $x1 != $x2 } {
set phi [expr {atan(double($y2-$y1)/double($x2-$x1))}]
} else {
set phi [expr {asin(1)}] ;# 90 degrees
}In checkForCollision, an infinite loop is possible. This is a subtle bug that manifests in rather rare circumstances. Details below.
The following code is used to find other balls that overlap with the given tag ball:
lassign $State(pos,$tag) ourX ourY
set ourId [$State(canvas) find withtag $tag]
set id [$State(canvas) find closest $ourX $ourY $State(rad,$tag) $ourId]
while { $id != $ourId } {
...
set id [$State(canvas) find closest $ourX $ourY $State(rad,$tag) $id]
}Unfortunately, the loop does not always terminate. This is caused by the line
lassign $State(pos,$tag) ourX ourY
that is supposed to compute the center point of the tag ball. The problem is that the tag ball has been moved on canvas by its velocity vector (in moveBalls) without updating the State(pos,$tag), so its real center is somewhere else. Delaying the update of State(pos,$tag) is done on purpose, so we cannot simply correct moveBalls. We should rather compute the real center point. For example,
lassign [$State(canvas) coords $tag] x1 y1 x2 y2
set ourX' [expr {($x1+$x2)/2.0}]
set ourY' [expr {($y1+$y2)/2.0}]In most circumstances the points (ourX,ourY) and (ourX,ourY) are very close and the difference has no visible effects during animation. However, if point (ourX,ourY) happens to be outside the tag ball and close to another ball, say B, then find closest statement will constantly return B. As a consequence, the loop's guard will stay true forever (or rather till we kill Colliding Balls :). The following version of checkForCollision seems to be correct:
proc checkForCollision { tag } {
global State
set c $State(canvas)
set r $State(rad,$tag)
lassign [$c coords $tag] x1 y1 x2 y2
set x [expr {($x1+$x2)/2.0}]
set y [expr {($y1+$y2)/2.0}]
set overlapList [list]
set id [set ourId [$c find withtag $tag]]
$c raise $tag ;# not sure whether really needed
while { [set id [$c find closest $x $y $r $id]] != $ourId } {
lappend overlapList $id
}
if { [llength $overlapList] > 0 } {
foreach id $overlapList {
collide $tag $State(id2tag,$id)
}
return 1
}
return 0
}Also, it is easy to add some configurable parameters that control the number of balls, their sizes, colours and velocities. For details, have a look at Colliding Coins.
JE In general, you can always replace
set phi [expr {atan($y / $x)} ]with
set phi [expr {atan2($y, $x)}]which correctly handles the case $x == 0.0.
Also, it's usually a good idea to replace the idiom:
set phi [expr {atan2($y, $x)}]
set cos [expr {cos($phi)}]
set sin [expr {sin($phi)}]where phi is not subsequently used for anything else, with:
set h [expr {hypot($y, $x)}]
if {$h != 0.0} {
set cos [expr {$x / $h}]
set sin [expr {$y / $h}]
} else {
# ... exceptional case depends on the application
# ... oftentimes [set sin [set cos 0.0]] is appropriate
}This replaces three transcendental functions (expensive) with two divisions and a call to hypot (usually much cheaper). Don't know how big a difference this makes in Tcl, where the interpreter overhead may dominate the cost of atan2, sin and cos, but in compiled languages this is almost always a win.
(If the language doesn't support hypot, google for "Pythagorean sums" to find a fast implementation.)
LH 11 Apr 2003 - You cannot always replace atan(y/x) with atan2(y,x). For example,
% set phi [expr {atan(-1/-1)}]
0.785398163397
% set phi [expr {atan2(-1,-1)}]
-2.35619449019Notice that atan is the inverse of tan and as such its value is always between -pi/2 and pi/2. On the other hand, atan2(y,x) is the angle of vector (x,y) and its value is between -pi and pi. In fact, atan(y/x) = atan2(y,x) only if x > 0.
In David's version, ball 1 is always positioned on the left side of ball 2 so x >= 0, and it would seem that atan can be safely replaced with atan2. The problem is that the formulae for computing the projections of velocities are correct only for -pi/2 < phi <= pi/2. For x = 0 and y < 0, atan2(x,y) = -pi/2 and the projections would be wrongly computed in this case.
In my version, substituting atan2 for atan is out of question since I don't reorder the two balls and thus phi could easily go outside the range that guarantees the correct computation of the projections.
As far as the more efficient computation of sin and cos is concerned, I prefer the present version. The gain would be too small to sacrifice the uniformity of the present code.