Auto-zooming view

This week I started by trying to improve my powered-landing cutoff elevation by using the correct equation for gravitational acceleration as a function of altitude:



This is a differential equation; the acceleration due to gravity is a function of the inverse squared distance above the planet. Mu is a constant based on the size and density of the planet. I was attempting to come up with an equation for y given t. Unfortunately I didn't get anywhere with it. I'm not sure if it has a closed-form solution or not.

After that I turned to a couple of other parts of my lander program that needed improvement. The first was computation of the impact site. Because I am currently assuming all the gravity comes from the one planet, the spacecraft trajectory is a conic section (ellipse, parabola, or hyperbola). I can thus do an analytical intersection between the trajectory curve and the circle of the planet's surface.

My old code was an ellipse/circle intersection. It thus couldn't handle parabolic or hyperbolic trajectories. It also suffered from numerical accuracy problems right around takeoff and landing, when the trajectory is just barely larger than the circle and has an eccentricity near one.

I switched to the polar representation for a conic:



p is the semi-latus rectum, a measure of the size of the conic. e is the eccentricity, a measure of the shape of the conic.

This handles hyperbolic and parabolic trajectories just fine. Its problem is that it falls down when the trajectory becomes degenerate. When you take off vertically, the trajectory follows a straight line. In this case, p is 0, so the equation returns 0 for the radius no matter what angle theta you put in. So, I need to switch to a different algorithm in those cases. I still need to do that.

The third thing I worked on was my view-framing algorithm. I try to zoom the camera in and out so that you can see what's important. When you're in orbit, I frame the entire orbit:



Once you are on a collision trajectory, I want to frame the unflown portion of the trajectory:



Once you've landed, I want to have a close-up view of the spacecraft:



There are still some cases that aren't covered. For instance, what should I frame when the trajectory is hyperbolic? In this case it's infinite. I currently cap the amount that I will zoom out, but if the spacecraft exceeds the limit I zoom out further.

It turns out that the specific mechanical energy is a good measure to use for identifying the different situations. It's the sum of the kinetic energy and the potential energy, divided by the spacecraft's mass:



The kinetic energy is the first term; you probably recognize it (minus the mass) from physics textbooks. The potential energy is the second term; it's set up such that it is zero when the spacecraft is infinitely far away, and gets more negative as the spacecraft approaches the planet.

The specific mechanical energy stays constant as the spacecraft moves around a given trajectory. For non-circular trajectories, potential energy is traded with kinetic energy as the spacecraft orbits.

When the specific mechanical energy is positive, the spacecraft is on a hyperbolic trajectory. When it is zero, the trajectory is parabolic. Negative means an elliptic orbit. The size of the orbit is related to the energy. I use the energy in a low circular orbit as the cutoff point for blending between a landing camera and an orbit camera. Since the energy changes smoothly as the player fires the rockets, it is a good parameter for interpolating between camera modes.



Fundamentals of Astrodynamics, by Bate, Mueller, and White, is the book I am dog-earing as I work through this stuff. It's an unbeatable value, as is typical of Dover books. If you are at all interested in astrodynamics it's a must-have.

Trajectory Feedback

This week I've been working on feedback in my lunar lander program.



The screenshot is not terribly clear. The ugly disc on the bottom is the moon. The tilted green arrow in the center marks the lander's position and orientation; when the camera zooms in you can see the lander itself. The curve passing through the lander that leads to the the little arrow on the ground is the ballistic trajectory (the arrow marks its impact site), while the second curve which intersects the ground is the maximum deceleration trajectory.

The ballistic trajectory is handy for some things. It shows you the “default” behavior of the spacecraft if you don't do anything. You can make a pinpoint landing reasonably well by aiming the ballistic impact site at your target and then throttling and steering to keep it there as the rocket decelerates.

I've been experimenting with some other displays. One I'd like to have is an indication, when you're in orbit, of the nearest point on the planet that you can safely land on. My first attempt toward that is the maximum deceleration trajectory. This simply integrates the spacecraft's position while choosing to decelerate in the direction opposite the velocity vector at each step.

When the rocket is flying high enough, it can reach zero velocity above the ground, in which case this trajectory is good. When you're orbiting lower, though, the trajectory may not reach zero velocity until under the ground somewhere, which isn't as useful.

What I really need is a trajectory that diverts power as necessary away from maximum deceleration and toward maintaining positive elevation. I haven't figured out quite how to do this yet, though. There are a variety of papers about how to compute optimal soft-landing trajectories, but they are almost all for sale at $25 each from IEEE and AIAA. I don't want to buy papers sight-unseen so I'm still trying to figure out a way to see them.

Another display I'd like is an indication, on the ballistic trajectory, of the point beyond which there is nothing you can do to prevent a crash. My first attempt toward that assumes only vertical motion, constant gravity acceleration, and constant rocket acceleration. It computes the altitude at which you must begin decelerating (at your current rocket thrust level) in order to bring the rocket to a soft landing.

Constants:



Variables:



Initial equations:



The position and velocity need to match up at the boundary between the unpowered and powered flight segments. Equating these yields two equations in two unknowns: s and t, the durations of the unpowered and powered segments, respectively:



Via a lot of tedious algebra, these can be solved for t, which can then be plugged into one of the initial equations to yield the altitude at which the powered braking segment begins:



I was surprised at first to see that the direction of initial velocity doesn't matter. You can be going up, or down, and the elevation is the same. On thinking about it, this makes sense, because if you are going up, you are on a parabolic arc that will come back down to the same elevation with exactly opposite velocity.

This equation assumes that gravity is constant. Near the surface this is a reasonable approximation but as you get higher, gravity drops off and it becomes less accurate. Initially I chose to use surface gravity as the approximation. This is conservative because it makes the equation think the rocket will fall faster than it actually does. Choosing gravity at the spacecraft's initial elevation would sometimes cause the equation to underestimate the height at which to start braking. I've experimented with using the average of the gravity at ground and at the spacecraft's initial altitude; this works pretty well. If we were to make gravity dependent on altitude the equations would become differential equations. I might take a look at solving that, eventually.

Even as it is, this display is pretty useful. I can tune the throttle up and down and the indicated altitude rises and falls; if I set it to the bottom of the spacecraft then it will make a perfect soft landing.

Throttling Experiments

This week I returned to my lunar lander project.

The Lunar Lander family of games is ancient (i.e. as old as me), but I've always found them both difficult and dull. I'm attempting to improve the user interface to address these problems. I'm also using a circular world rather than a rectangular chunk, so it's possible to go into and out of orbit.

Orbit comes with its own set of challenges. One of the biggest is time scale. Orbit period increases with the two-thirds power of the orbit altitude, so if you've got a world with a low-altitude orbit of a minute, say, then when you get one radius away from the surface the orbit will take 2.8 minutes. Depending on how frugal the player needs to be with fuel, they may have to wait quite a while between burns. I've got some basic time acceleration implemented to counteract this, and will probably enhance it further as I learn more about what's needed. For instance, the time scale could vary with altitude so that orbits take the same amount of time under acceleration, regardless of size.

At the moment, though, I'm engaged mostly in improving the interface for throttling near the planet. Currently, you steer with the mouse and hold buttons to fire the main rocket. The steering is simple; moving the mouse left or right rotates the rocket. Stop moving the mouse and the rocket stops rotating.

If you were perfect and knew exactly what you were doing, you could land a rocket with a single burn without adjusting the throttle. Nobody's perfect, though, so it's necessary to either stop and restart the engine, or equivalently to adjust the throttle to lower and higher thrust levels.

It might seem obvious to put the throttle on the other mouse axis, but having unrelated inputs on the mouse axes introduces unwanted coupling: it's hard to steer without adjusting the throttle, and vice versa.

Putting the throttle on the mouse wheel works pretty well, if the mouse wheel scrolls smoothly. It makes it harder for the player to use the other mouse buttons, though, since their focus is on precisely positioning both the mouse and wheel. In this mode I offload other things to the other hand, on the keyboard.

Putting the throttle on the keyboard has been problematic. I tried absolute throttle settings on the 1-9 keys, but it's very hard to keep track of where you are. Most of the time when you're landing you want “a little bit more” or “a little bit less” throttle; these are relative adjustments, so the absolute settings are a bad fit.

Another keyboard interface I've tried is to hold A or Z to increment or decrement the throttle setting. Again this is tricky because the adjustment happens at a constant speed. At times this speed is too fast, while other times it's too slow.

The final throttling interface I have is to just use the left and right mouse buttons. Holding the left button generates 1.1 G's of thrust, and holding the right mouse button generates 0.5 G's of thrust. Holding both together generates 1.6 G's of thrust. This interface is nice in that the thrust values are well-known; the player can get an intuitive feel for how strong they will be in each circumstance. On the other hand, because there is so little throttle control, the player has to resort to pulsing the rockets to simulate intermediate thrusts.

Of all of these, I'm most familiar with the last one, but the mouse wheel one is probably my favorite. It allows smooth control of the rocket.

Finally, it looks like putting the throttle indicator up in the top-right corner is a bad idea. When landing, the focus is entirely on the vehicle and its trajectory toward the ground; it's hard to look anywhere else. I am trying to think of ways to communicate necessary information about throttling in this context.

Forcing a window to maintain a particular aspect ratio

This is a piece of code I removed from my framework recently. I first wrote something like this many years ago, back when computer monitors were virtually all 4:3 aspect ratio.

Games typically run full-screen, but during development it's much more convenient to have them run in a window. For 3D games it's easy to resize the window. The problem is what to do when the window's client area doesn't match the aspect ratio of the full-screen monitor. You can letterbox the image, putting black borders on the sides, or you can crop, trimming part of the image off.

I opted to make the program restrict window resizing so that the window's aspect ratio would always match the target monitor's aspect ratio. This turns out not to be too hard to do in Windows.

First, you need to catch the WM_SIZING message in your message handler:

LRESULT WINAPI MsgProc(HWND hWnd, UINT msg, WPARAM wParam, LPARAM lParam)
{
    switch (msg)
    {
    case WM_SIZING:
        resize(int(wParam), *reinterpret_cast<LPRECT>(lParam));
        return TRUE;

        ...
    }

    return DefWindowProc(hWnd, msg, wParam, lParam);
}

Second, you need to modify the rectangle that comes in with the WM_SIZING message so that it obeys your restrictions:

void resize(int edge, RECT & rect)
{
    int size_x_desired = (rect.right - rect.left) - g_window_adjust_x;
    int size_y_desired = (rect.bottom - rect.top) - g_window_adjust_y;

    switch (edge)
    {
    case WMSZ_BOTTOM:
    case WMSZ_TOP:
        {
            int size_x = g_window_adjust_x + (size_y_desired * window_ratio_x) / window_ratio_y;
            rect.left = (rect.left + rect.right) / 2 - size_x / 2;
            rect.right = rect.left + size_x;
        }
        break;
    case WMSZ_BOTTOMLEFT:
        {
            int size_x, size_y;

            if (size_x_desired * window_ratio_y > size_y_desired * window_ratio_x)
            {
                size_x = rect.right - rect.left;
                size_y = g_window_adjust_y + ((size_x - g_window_adjust_x) * window_ratio_y) / window_ratio_x;
            }
            else
            {
                size_y = rect.bottom - rect.top;
                size_x = g_window_adjust_x + ((size_y - g_window_adjust_y) * window_ratio_x) / window_ratio_y;
            }

            rect.left = rect.right - size_x;
            rect.bottom = rect.top + size_y;
        }
        break;
    case WMSZ_BOTTOMRIGHT:
        {
            int size_x, size_y;

            if (size_x_desired * window_ratio_y > size_y_desired * window_ratio_x)
            {
                size_x = rect.right - rect.left;
                size_y = g_window_adjust_y + ((size_x - g_window_adjust_x) * window_ratio_y) / window_ratio_x;
            }
            else
            {
                size_y = rect.bottom - rect.top;
                size_x = g_window_adjust_x + ((size_y - g_window_adjust_y) * window_ratio_x) / window_ratio_y;
            }

            rect.right = rect.left + size_x;
            rect.bottom = rect.top + size_y;
        }
        break;
    case WMSZ_LEFT:
    case WMSZ_RIGHT:
        {
            int size_y = g_window_adjust_y + (size_x_desired * window_ratio_y) / window_ratio_x;
            rect.top = (rect.top + rect.bottom) / 2 - size_y / 2;
            rect.bottom = rect.top + size_y;
        }
        break;
    case WMSZ_TOPLEFT:
        {
            int size_x, size_y;

            if (size_x_desired * window_ratio_y > size_y_desired * window_ratio_x)
            {
                size_x = rect.right - rect.left;
                size_y = g_window_adjust_y + ((size_x - g_window_adjust_x) * window_ratio_y) / window_ratio_x;
            }
            else
            {
                size_y = rect.bottom - rect.top;
                size_x = g_window_adjust_x + ((size_y - g_window_adjust_y) * window_ratio_x) / window_ratio_y;
            }

            rect.left = rect.right - size_x;
            rect.top = rect.bottom - size_y;
        }
        break;
    case WMSZ_TOPRIGHT:
        {
            int size_x, size_y;

            if (size_x_desired * window_ratio_y > size_y_desired * window_ratio_x)
            {
                size_x = rect.right - rect.left;
                size_y = g_window_adjust_y + ((size_x - g_window_adjust_x) * window_ratio_y) / window_ratio_x;
            }
            else
            {
                size_y = rect.bottom - rect.top;
                size_x = g_window_adjust_x + ((size_y - g_window_adjust_y) * window_ratio_x) / window_ratio_y;
            }

            rect.right = rect.left + size_x;
            rect.top = rect.bottom - size_y;
        }
        break;
    }
}

window_ratio_x and window_ratio_y are integer constants that define the desired aspect ratio.

We want to enforce a specific aspect ratio for the client area, but the resize code is dealing with the dimensions of the overall window. To handle this, at startup I use AdjustWindowRect to find out how much padding there is in each dimension, and store it off in g_window_adjust_x and g_window_adjust_y:

int WINAPI WinMain(HINSTANCE hinstance, HINSTANCE, LPSTR, int nShowCmd)
{
    ... // register window class

    const int window_style = WS_OVERLAPPEDWINDOW;

    RECT rect = { 0, 0, start_size_x, start_size_y };
    AdjustWindowRect(&rect, window_style, FALSE);
    g_window_adjust_x = (rect.right - rect.left) - start_size_x;
    g_window_adjust_y = (rect.bottom - rect.top) - start_size_y;

    ... // create window, message handling loop, etc.
}

Finally, you can restrict the minimum window size so that it obeys the aspect ratio restriction. This involves answering the WM_GETMINMAXINFO message:

    case WM_GETMINMAXINFO:
        {
            MINMAXINFO * info = reinterpret_cast<MINMAXINFO *>(lParam);
            info->ptMinTrackSize.y = ((info->ptMinTrackSize.x - g_window_adjust_x) * window_ratio_y) / window_ratio_x + g_window_adjust_y;
        }
        break;

I ended up removing this code this week because monitors have gotten much less homogeneous in their aspect ratios. My notebook computer, for instance, is 1440 by 900, which is an 8:5 ratio. HDTV aspect ratios are 16:9. A 1280x1024 notebook (with square pixels) has a 5:4 aspect ratio. I decided that it was better to just have my games adapt their UI and viewport to whatever resolution they're given.

Subdivision curve planet

My week of vacation was a bit of an adventure. An old friend of ours went into labor five weeks early so we took care of her three-year-old for a night. Nobody slept much that night. After that I caught a cold.

Overall it was a good vacation, though. I put together a tricycle for my daughter, read some books, and got caught up on a lot of backlogged household chores. We also spent time with our new neighbors who also have a two-year-old daughter.

I did some computer chores as well. I'm going to give Windows Vista's backup system a try, and back up my work to my external USB hard drive once a week. The old computer is almost back to normal with its new hard drive; we've been installing stuff on it. My notebook computer had some divergent versions of my projects due to my switch from version 7 to version 8 of Visual C++. I've been reconciling and consolidating those.

Early in the week I did some work on terrain modeling. I had been thinking about using subdivision curves, and I wrote a test application that generated a random “planet” out of them. Since the world is two-dimensional the planet consists of a single polygon. I implemented scalar-valued creasing, so the vertices in the control polygon each have a hardness ranging from zero (completely smooth) upward. Basically, if a vertex's hardness is n, it will be not be smoothed for the first n subdivision steps, and then it will be smoothed for all steps thereafter. Fractional values are handled by blending the smooth and hard solutions at the transitional subdivision level.

Here's a screenshot:



The control polygon is drawn in faint gray; you can see it on some of the smoother corners.

Ultimately, though, I decided it's not time yet to make a terrain editor. I really need to focus on basic gameplay and functionality right now.

Riding the bus

I'm vacationing this week, but not going anywhere in particular. Today and tomorrow I'm looking after my daughter while my wife goes to Continuing Legal Education classes on trusts and estates. We're watching Sesame Street right now, and I think we may go hop on the bus and ride somewhere in a bit.

I'll get a proper update up soon, after I've actually gotten something done.