*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:

foreach {ourX ourY} $State(pos,$tag) {} 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

foreach {ourX ourY} $State(pos,$tag) {}

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,

foreach {x1 y1 x2 y2} [$State(canvas) coords $tag] break set ourX' [expr {($x1+$x2)/2.0}] set ourY' [expr {($y1+$y2)/2.0}]

In most circumstances the points (*ourX*,*ourY*) and (*ourX ,*

proc checkForCollision { tag } { global State set c $State(canvas) set r $State(rad,$tag) foreach { x1 y1 x2 y2 } [$c coords $tag] break 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.35619449019

Notice 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.