The Mote in God's Eye

I do not think that one who basks in political correctness should bother with The Mote in God's Eye, by Larry Niven and Jerry Pournelle.  If one looks both closely and shallowly at this book, one might decide that one has found trove of male chauvinism and racism.  I tend to do so, though only for my own personal entertainment.

The imperial navy, for example, seems to be comprised entirely of men.  This is not unusual, historically or currently, but the great assumption is often that the future will hold greater equality in all things.  Another example here is that the purpose of aristocratic women is apparently to perform as social butterflies, get married, and pop out heirs.  Once again, equality is generally expected in future settings, but then again: who is to say how the future and future human attitudes will develop?  The assumption of equality is based on current conditions facing no drastic changes -- which is entirely naive.  (There is another example, but it's a spoiler, so I won't reveal it.)

As for racism, the Moties (the alien race described) are a species with several genetic castes somewhat akin to polymorphism in insects.  There is a master caste, a mediator caste, a medical caste, a warrior caste, an engineer caste, etc.  Key in the argument of racism is that the master caste is white and the engineer caste (intrinsicly gifted in making things, but incapable of higher thought processes) is brown.  Here I can say that dark and light are used as the easily recognisable archetyes that they are, in western culture.  If that's not clear enough, think of the terms "white-collar" and "blue-collar".

Enough of the self-indulgent under-thinking, though.  Mote is basically a story of first contact -- the first first-contact -- with an intelligent alien civilisation.  Most books that I've read that deal with such a scenario assume a human civilisation that has yet to explore and colonise beyond the solar system -- assuming they got far off Earth at all.  Basically: contemporary settings.  In Mote, humanity has gone through the cycles of multi-stellar civilisation twice (the CoDominion and the First Empire), each followed by a collapse and period of barbarism, and has once again risen to a vast Empire.  For me, this is a unique experience.

The book is presented largely as a political drama, with several mysteries involving characters motivations.  There is little physical action, though what there is gripped my eyes and I had little desire to pull away.  All-in-all it had a somewhat Asimovian feel.  If you've read Isaac Asimov's Foundation series, you'll know what I mean.  Dramatic irony and discovery are where most of the action is, and I think Pournelle and Niven did a great job.

To be honest, though, I do have a couple gripes.  First is due to my own misconceptions: I expected more military science fiction; an interstellar war.  I didn't get that, but I probably should have read the synopsis more closely.  I don't like to do that, though, as it may spoil too much.  The second is related to the romance in the novel.  The pairing is far too obvious and it develops far to quickly and suddenly.  I have this problem with a great many books by a great many authors, though, so it shouldn't be surprising, anymore.

As I said, though, it's overall a great book.  Probably because it doesn't involve war and high military drama, it may be one of the best first-contact stories out there.  Definitely a recommended read to all interested in such things.

Acceleration/Decelleration

Say we want to move an object to a particular point in the shortest amount of time, given a maximum acceleration. It follows that the object must accelerate constantly until it comes to a point where it must decellerate constantly in order to come to a stop at the destination. Looking at this problem we have a known starting velocity, a known final velocity, a known total distance, and a known acceleration. There is a kinematics equation that uses all of those values:

v**2 = v0**2 + 2 * a * d

Unfortunately, that's only one acceleration, but our problem actually consists of two parts: an acceleration and a decelleration. At the end of the object's acceleration it reaches a maximum velocity, the final velocity for that part. The maximum velocity then becomes the starting velocity for the second part. Therefore we have two equations:

v_max**2 = v0**2 + 2 * a * d1
vf**2 = v_max**2 + 2 * -a * d2

This leads to two more unknowns: d1 and d2, the distances travelled during the first and second parts, respectively. However, the total of d1 and d2 is known as the distance from the start to the destination. Therefore, if we solve for d1 and d2 and add the results, it should equal the total distance.

d1 = (v_max**2 - v0**2) / (2 * a)
d2 = (vf**2 - v_max**2) / (2 * -a)
d = d1 + d2

The maximum velocity is still unknown, though, so let's sub in the formulas for d1 and d2:

d = (v_max**2 - v0**2) / (2 * a) + (vf**2 - v_max**2) / (2 * -a)

... simply it:
   
d = (2 * v_max**2 - v0**2 - vf**2) / (2 * a)

... and solve for the maximum velocity:

v_max = sqrt ((2.0 * a * d + v0**2 + vf**2) / 2.0)

Now, we simply have the object accelerate to that velocity and then decellerate back down to the final velocity. In the end, the object should be at the destination. Of course, now that the maximum velocity is a known value, one can now calculate d1 and use that value to determine how long the object should accelerate.

King David's Spaceship

I just finished reading King David's Spaceship, by Jerry Pournelle.  It's part of his Future History series, though very far removed from the Codominion era books.  Those books ended with a prequel to a galactic empire, though the empire itself is never touched upon except as a history to later books.  This one takes place after that empire's fall and the during the rise of a new one.

Anyway, for a title that indicates a plot about building a spaceship, the story itself has little to do with that.  It is the ultimate goal, but the bulk of the plot takes place in a medieval environment.  That's not to say that I am disappointed, though.  Pournelle writes plenty of military science fiction and he's good at it, even when the 'military' part is with early medieval technology.  No, instead of disappointed I was merely surprised at where the focus ended up.

Cyborg

Just finished watching Cyborg, a Jean-Claude Van Damme film from 1989. When I was young I remember Super Channel (a pay movie channel, back then) occasionally had promotions whereby they provided free viewing for a week. Those were the only times I ever saw anything from that channel. Once in a while, my sister would set her alarm clock to an early morning hour and wake me up so we could watch a late movie that looked interesting. That's how I first saw this film.

I really enjoyed it back then, having never before seen anything like the post-apocalyptic vision presented. It had good action, with a particularily menacing villain, and an element of drama that made it yet more memorable. Watching it again, I recognise the old, cheap effects (by modern standards), and the generally bad acting (not just from Van Damme). I can still enjoy it, though, and perhaps not all of that is simply due to nostalgia.

On another note, the movie reminds me alot of Fallout. :) The world presented is more lush outside of urban areas, but the ruined cities and the scavenged look of the costuming is definitely Fallout-like.

Collision Detection for Fast Objects and Circle-Line Intersection

In my current project I produced my own little set of classes for simulating physics.  It's very unrealistic, at this point, because realistic physics makes it very difficult to implement a thrust control AI.  More on that another time.  For now, I'm talking collision detection.

The objects I'm dealing with are very small relative to the velocities at which they may travel.  These are spacecraft and projectiles moving at realistic speeds -- not like one would see in a game like Star Control or indeed most other space sims, where craft seem to move slower than modern aircraft do.  In my program, projectiles like missiles are often moving so fast that simply collision detection allows them to pass right through their targets.  That's a problem.

The easiest solution to this is to simply use a smaller timestep.  I've locked the framerate at only 25 Hz, but I step through the physics update functions four times per frame.  As far as the physics is concerned, the actual framerate is 100 Hz.  Even with such a framerate, collisions often fail to register.  The solution I decided upon was to implement a second step to collision detection whereby the system would also look at the area between the object's current position and its previous position.

The basic collision detection simply uses circles.  I detect collisions between the circular collision hulls of the current and previous position by defining a rectangle between them whose side lie tangent to both circles.  The slope of those tangent lines is no chore to discover as the radius of each circle is the same.  The slope is simply the slope of the vector that connects their centres:

# get the positions
x0, y0 = pos
x0p, y0p = prev_pos

# get the distance between the two
dx, dy = x0 - x0p, y0 - y0p
dist = math.hypot (dx, dy)

# normalize the vector
ndx, ndy = dx / dist, dy / dist

slope = ndy / ndx

We will use the normalized vector to determine where the corners of the rectangle lie.  This is found simply by rotating the vector 90 degrees left and right.  Multiply the results by the radius of the circles to produce vectors and add them to the current and previous positions to get the corners.

# get the end-piece slopes
ex0, ey0 = -ndy, ndx
ex1, ey1 = ndy, -ndx

# get the corners of the rectangle
px0, py0 = x0p + ex0 * radius, y0p + ey0 * radius
px1, py1 = x0 + ex0 * radius, y0 + ey0 * radius
px2, py2 = x0 + ex1 * radius, y0 + ey1 * radius
px3, py3 = x0p + ex1 * radius, y0p + ey1 * radius

Assuming that the previous position (x0p, y0p) is to the left of the current position (x0, y0), the top-left point is (px0, py0).  The rest of the points continue clockwise around the rectangle.

What we now need to do is test for a collision between the rectangle and the circular collision hull of the other object.  Cirlce-Rectangle collision occurs when either the circle touches a rectangle edge or when the centre of the circle falls with the bounds of the rectangle.  The latter is easier to test for, of course.

Determining whether a point is within a rectangle is simply a matter of finding which side of each edge the point lies.  Simply:

def get_side (p0, p1, point):
  x, y = point
  x0, y0 = p0
  x1, y1 = p1
   
  ex0 = x1 - x0
  ey0 = y1 - y0
   
  ex1 = x - x1
  ey1 = y - y1
   
  return ex0 * ey1 - ey0 * ex1

The order in which points are entered into this function is important.  Entered clockwise: if the return value is positive, the point lies above the line; if the value is zero, the point lies on the line; if the value is negative, the point lies below the line.  Therefore the point lies within the rectangle if the return value is negative for all sides.

If the centre of the circle is not within the rectangle, it is still possible that it touches one of the edges.  The only two edges we have to test are the top and bottom edges.  The end-pieces lie within the circles of the current and previous position circles, so we need not test them.

I must admit that I had great difficult trying to find an algorithm for Circle-Line Intersection.  I found a few sources where simply code was given, but I prefer an explanation to accompany code.  Eventually it dawned upon me to simply use the equations for lines and circles:

# line
y = m * x + b

# circle
r**2 = (x + x0)**2 + (y + y0)**2

The circle equation is easiest to deal with if simplified to assume that its origin is (0, 0).  Therefore:

r**2 = x**2 + y**2

If we do that, however, we must account for that in the for the line equation.  The easiest way to do that is to simply subtract the origin coordinates from the coordinates of the current and previous positions.

For the line equation, we found the slope, m, previously, and can find b by substituting either the current or previous position coordinates (modified as in the previous paragraph) into x and y.  Solving for b:

b = y0 - m * x0

Now, let us take the original line equation and substitute it for y in the circle equation:

r**2 = x**2 + (m * x + b)**2

Before we try to solve for x, let's evaluate the equation as far as it can go:

r**2 = x**2 + m**2 * x**2 + m * x * b + m * b + b**2

It looks intimidating, but we can turn it into a quadratic equation:

0 = (1 + m**2) * x**2 + m * x * b + m * b + b**2 - r**2

We can then solve for x via the quadratic formula, but to be honest we don't actually need it.  As it turns out, all we need is the result of the discriminant:

D = b**2 - 4 * a * c

The discriminant, after all, exists within the quadratic formula's square-root, which will not result in a real number if the discriminant is negative.  Ultimately, what this means is that the circle does not intersect the line if the discriminant is negative.  If it is not negative, the circle intersects the line at one or two points.

The expressions a, b, and c are extracted from our quadratic equation as follows:

a = 1 + m**2

b = m * b

c = m * b + b**2 - r**2

The resulting discriminant is:

D = m**2 * b**2 - 4 * (1 + m**2) * (m * b + b**2 - r**2)

There are no unknown values in this equation.  We have m, the slope, r, the radius, and b.  Here's the final function for Circle-Line Intersection:

def circle_line_intersection (p0, p1, origin, radius):
    x, y = origin
   
    px0, py0 = p0[0] - x, p0[1] - y
    px1, py1 = p1[0] - x, p1[1] - y
   
    dx, dy = px1 - px0, py1 - py0
   
    if dx == 0.0:
        return radius > abs (px0)
   
    m = dy / dx
    b = py0 - m * px0
   
    return m**2 * b**2 - 4 * (1 + m**2) * (m * b + b**2 - radius**2) >= 0.0

I test if dx is equal to zero because if it is, we'll end up with a division-by-zero error.  However, all that means is that the line is vertical.  As such, we can simply test one of the positions' x-coordinates against the radius of the circle.

This form of collision detection will not tell you exactly where the collision occured, of course.  However, that was not relevant to my needs, so I gratefully never considered it.  All I needed to know was whether my projectile had hit something or not, and this works quite well.

There are some problems with this solution, of course.  For example, if the projectile is moving along a curved path, this does not provide a perfect solution, as a rectangle has entirely flat sides.  Right now, however, I don't particularily feel like looking into collisions with arbitrary curves. . .

Circular number systems

When one deals with angles one must eventually find a way to work around the barrier between 359 degrees and 0 degrees.  For example, if one has an angle at 5 degrees and another at 355 degrees, what is the distance between them?  If one subtracts normally the result will be either 350 or -350, depending on the order one places them in the expression.  This is mathematically correct, producing the difference, but rarely is that what one wants.

The general case is finding out how to rotate an object to a particular destination.  Ideally one should rotate the object such that the shortest amount of time is taken, which means taking the shortest distance.  Rotating 350 degrees is obviously, to human perception, not the shortest distance.  The shortest distance is -10 degrees, of course, but the problem is how to write a program to give that result.

It is easy, if one uses a couple 'if-else' statements.  We start at 5 degrees and need to get to 355, so try the basic equation:

distance = destination - origin

distance = 355 - 5

350

This is, as mentioned earlier not the answer we want, so subtract maximum span of angle values, 360, and we have our answer: -10.  This works as long as the distance crosses over zero and the basic equation results in a positive number.  If it results in a negative number, then we add 360 instead.  If we are not crossing over zero, we add or subtract nothing.  One can always tell if the distance crosses over zero if the result of the basic equation is outside of the range (-180, 180).

Let's turn this into Python code:

def diff (start, end):
    dist = end - start
   
    if dist < -180:
        dist += 360
    if dist > 180:
        dist -= 360
   
  return dist

Simple enough and it works to a degree even when the values are not clamped to (0, 360].  However, I said 'to a degree'.  If the starting angle is 721 and the end is -1, the distance, according to this function is -362.  721 degrees is actually just 1 degree, so the distance should be -2.  To solve for this we should convert all values such that they appear between the standard range of (0, 360].  Therefore the new function is:

def diff (start, end):
    start = start - int (start / 360) * 360
    end = end - int (end / 360) * 360
   
    dist = end - start
   
    if dist < -180:
        dist += 360
    if dist > 180:
        dist -= 360
   
    return dist

This works, perfectly, but it's a rather long function.  For a time I was satisfied with it, but thought that a shorter way was possible.  I presented my problem and solution on the PyGame newsgroup and was greeted with some much better solutions.  Here's one:

def diff (start, end):
    return (end - start + 180) % 360 - 180

I started with a function with an 8-line body of code (not counting whitespace) and got back a function with a single line of code.  There's no conditional statements, either.  It is simply perfect.

This function is easily modified to work with whatever range of values one chooses.  If one works with radians instead of degrees:

def diff (start, end):
    return (end - start + 0.5 * pi) % pi - 0.5 * pi

Or how about a twelve-hour clock?

def diff (start, end):
    return (end - start + 6) % 12 - 6

Perfect!