Thanksgiving was a busy weekend, with lots of friends and family at our house. I played a bunch of Super Mario Galaxy, too. I like the bite-size gameplay pieces, and the live orchestral soundtrack.
On the downside, the camera is even crazier than in other third-person action games, which reduces the game's appeal for non-hardcore gamers. There are a couple of reasons for this. One is that there is almost no manual control over the camera. Sometimes you can press the D-pad to reorient the camera, but due to the controller geometry this is not something you can do easily. The other reason the camera is squirrelly is because the worlds have unusual geometries. As a result there is a lot of camera hinting (at my day job we call them camera volumes). This is where designers mark a region of space and give a preferred direction for the camera for that region. Due to the crazy gravity it's necessary to swing the camera direction wildly from region to region.
As anyone who's worked on 3D action games knows, there is a fundamental conflict between character control and camera control. You've got two basic choices for character control: character-relative and screen-relative. Character-relative is characterized by the Tomb Raider series (at least the early games; I'm not familiar with the more recent efforts). I call this “radio-control car” control because it has the familiar problem that if the character is moving toward the camera, you have to push right on the stick to get them to go left on-screen, and vice versa. As a result of this, virtually all third-person games (including Super Mario) use screen-relative control. The joystick deflection is projected to the screen and the character moves directly in that direction. Right is always right and left is always left.
Screen-relative control is great, until you need to rotate the camera. Suddenly the frame of reference that the player is using to control their character has shifted. If they're trying to run along a narrow beam, say, and you rotate the camera, suddenly their character will veer off and plunge to her death. If the player manually rotated the camera then they're expecting it and can adjust their movement to compensate, but if the game is controlling the camera the problem is much worse.
There are various tricks that we've tried to get around this. For instance, if the movement joystick is deflected and then the camera rotates, you can continue the character on their previous course until the player lets up on the joystick, after which any subsequent deflection will be projected to the current camera frame. This has mixed results, and probably works best when you're outright cutting the camera from one view to another.
Super Mario Galaxy has an additional problem with screen-relative control that most other games don't. I mentioned above that you project the joystick deflection onto the screen. There are various ways to do this, but usually they involve projecting the controller deflection onto a ground plane, so that pushing up on the stick moves the character further away on the ground (upstage), and pushing down moves the character nearer (downstage). In Mario, the player is sometimes running around on the ceiling, which introduces a new problem: should pushing up on the stick move Mario further away, or toward the top of the screen (which means running closer to the camera)?
In order to make screen-relative character movement work as well as possible, you basically want to make smooth, slow adjustments to the camera so the player has ample time to correct for the change in their character movement. On top of that you can add a manual control to snap the camera quickly to a better direction. That way, the player can stand still when they adjust the camera.
Unfortunately Super Mario Galaxy's environments don't lend themselves well to smooth camera adjustments. Gravity changes directions suddenly, or worlds will be tight and twisty, necessitating rapid camera movements to keep Mario in view. I'm having fun with the game, but it makes my wife really dizzy just to watch it.
Monday, November 26, 2007
Monday, November 19, 2007
Soonest-landing trajectory
In my rocket game, it is difficult to know when to begin a braking burn in order to land at a given target. I've been working on the math for a trajectory that lands at the nearest possible point. (To clarify: I want the nearest point that doesn't involve backtracking or waiting for the next orbit. Given unlimited fuel and time you can land anywhere.)
To start with I'm making some simplifying assumptions. These boil down to assuming you're close to the ground. Gravity is constant; it doesn't vary with position. The ground is a flat plane at y=0, and the gravity vector is pointed in the -y direction. With the constant-gravity assumption, the rocket's trajectory becomes a parabola and can be solved easily.
If the rocket starts out high enough, the trajectory is simple. The rocket is pointed completely sideways and fired until the horizontal velocity is zero. After that it is turned upright, falls a bit if necessary, and then fires vertically to brake to a soft landing.
A sample rocket trajectory of this type is plotted below. For this graph, the rocket's acceleration is 2 and its initial velocity is (4, 0). Gravity acceleration is -1. The graphs end when horizontal velocity reaches zero; they do not show the vertical braking component (if any).
Sometimes, though, canceling all horizontal velocity before addressing vertical velocity doesn't work because the rocket falls too far and hits the ground before it's done, or else there isn't enough altitude, given its vertical velocity, to complete the vertical braking. In these cases the rocket has to be tilted upward somewhat, diverting some acceleration toward staying above ground. We want to divert the minimum necessary, so as to extend the braking distance as little as possible.
In the example below, the rocket acceleration is still 2, but the initial velocity is increased to (6, 0). As a result, the rocket has to be tilted at an angle of 76.86 degrees from vertical in order to have space for the vertical descent:
Finally, sometimes the initial velocity is such that the rocket has to actually gain altitude in order to make a soft landing. Here, I've reduced the rocket's acceleration to 1.25, set the initial velocity to (6, -0.5), and put the initial rocket altitude at 1. The rocket angle is 25.84 degrees from vertical:
I've let the rocket graze the ground in the trajectory above. In reality you'd pick a safe minimum altitude and adjust the angle to keep it above that.
Thus, the rocket's trajectory consists of one or two pieces. If the horizontal velocity is nonzero, the rocket will execute a burn while tilted to the side by some amount. Once the horizontal velocity is zero, if there is remaining elevation, there will be a vertical burn to cancel that. (There may be a coasting period in between the two burns.) For simplicity I'm assuming that the rocket can change heading instantly. Time for turning could be added to the problem without too much trouble.
I've covered the coast-and-vertical-braking phase in a previous entry. The remaining problem is to find the angle for the first burn. The general approach is as follows:
For a given angle of the rocket, we can compute when it will cancel its horizontal velocity (divide horizontal velocity by horizontal acceleration). We plug this time into the equations for vertical motion to find out the rocket's elevation and vertical velocity at that time. This elevation and velocity can then be plugged into the equation for the altitude at which to begin vertical braking, developed in the above-mentioned blog entry. If the braking altitude is at or below us, we're good. If it's above us, we can't do it, and this angle is not usable.
Since we're comparing two altitudes, the natural thing to do is to make an equation which says that their difference equals zero. By solving this we get the minimum angle which will result in a successful landing. The minimum angle equals minimum distance traveled since we put as much thrust as possible toward horizontal braking.
Unfortunately since the variable we're solving for is encased in sines and cosines I don't know if there's an analytical way to solve for it. However, it should be easy to search for the value. Here's a sample plot illustrating the type of curve it is:
The curve above corresponds to the second case given earlier. It crosses the x axis at around 76.86 degrees.
The only remaining wrinkle (that I know of) is presented in the third case above. We can't ever let the rocket's elevation dip below zero. We need to determine when its vertical velocity reaches zero (this is a possible point of minimum altitude). If this time is earlier than the time for zero horizontal velocity (and greater than zero), then we need to check the rocket's elevation at that time. If it's less than zero (or whatever safe altitude we choose), then we need to search for a rocket angle closer to vertical that keeps the rocket above-ground.
I've been working this out in Excel; the next thing to do is to implement it in-game. There are a variety of ways it could be used: I could plot the earliest-landing point on the ground, or plot the trajectory to it, or have an attitude indicator showing which direction to burn. Once it's in I'll see how valid the flat-earth assumptions are. They do become more correct as the rocket approaches the ground so they may not be a problem.
Another thing this could be useful for is the beginning of a rocket AI. Computer-controlled rockets will probably have slightly different trajectory needs. They'll be wanting to land at a specific spot, rather than at the earliest possible spot. It shouldn't be too different, though.
To start with I'm making some simplifying assumptions. These boil down to assuming you're close to the ground. Gravity is constant; it doesn't vary with position. The ground is a flat plane at y=0, and the gravity vector is pointed in the -y direction. With the constant-gravity assumption, the rocket's trajectory becomes a parabola and can be solved easily.
If the rocket starts out high enough, the trajectory is simple. The rocket is pointed completely sideways and fired until the horizontal velocity is zero. After that it is turned upright, falls a bit if necessary, and then fires vertically to brake to a soft landing.
A sample rocket trajectory of this type is plotted below. For this graph, the rocket's acceleration is 2 and its initial velocity is (4, 0). Gravity acceleration is -1. The graphs end when horizontal velocity reaches zero; they do not show the vertical braking component (if any).
Sometimes, though, canceling all horizontal velocity before addressing vertical velocity doesn't work because the rocket falls too far and hits the ground before it's done, or else there isn't enough altitude, given its vertical velocity, to complete the vertical braking. In these cases the rocket has to be tilted upward somewhat, diverting some acceleration toward staying above ground. We want to divert the minimum necessary, so as to extend the braking distance as little as possible.
In the example below, the rocket acceleration is still 2, but the initial velocity is increased to (6, 0). As a result, the rocket has to be tilted at an angle of 76.86 degrees from vertical in order to have space for the vertical descent:
Finally, sometimes the initial velocity is such that the rocket has to actually gain altitude in order to make a soft landing. Here, I've reduced the rocket's acceleration to 1.25, set the initial velocity to (6, -0.5), and put the initial rocket altitude at 1. The rocket angle is 25.84 degrees from vertical:
I've let the rocket graze the ground in the trajectory above. In reality you'd pick a safe minimum altitude and adjust the angle to keep it above that.
Thus, the rocket's trajectory consists of one or two pieces. If the horizontal velocity is nonzero, the rocket will execute a burn while tilted to the side by some amount. Once the horizontal velocity is zero, if there is remaining elevation, there will be a vertical burn to cancel that. (There may be a coasting period in between the two burns.) For simplicity I'm assuming that the rocket can change heading instantly. Time for turning could be added to the problem without too much trouble.
I've covered the coast-and-vertical-braking phase in a previous entry. The remaining problem is to find the angle for the first burn. The general approach is as follows:
For a given angle of the rocket, we can compute when it will cancel its horizontal velocity (divide horizontal velocity by horizontal acceleration). We plug this time into the equations for vertical motion to find out the rocket's elevation and vertical velocity at that time. This elevation and velocity can then be plugged into the equation for the altitude at which to begin vertical braking, developed in the above-mentioned blog entry. If the braking altitude is at or below us, we're good. If it's above us, we can't do it, and this angle is not usable.
Since we're comparing two altitudes, the natural thing to do is to make an equation which says that their difference equals zero. By solving this we get the minimum angle which will result in a successful landing. The minimum angle equals minimum distance traveled since we put as much thrust as possible toward horizontal braking.
Unfortunately since the variable we're solving for is encased in sines and cosines I don't know if there's an analytical way to solve for it. However, it should be easy to search for the value. Here's a sample plot illustrating the type of curve it is:
The curve above corresponds to the second case given earlier. It crosses the x axis at around 76.86 degrees.
The only remaining wrinkle (that I know of) is presented in the third case above. We can't ever let the rocket's elevation dip below zero. We need to determine when its vertical velocity reaches zero (this is a possible point of minimum altitude). If this time is earlier than the time for zero horizontal velocity (and greater than zero), then we need to check the rocket's elevation at that time. If it's less than zero (or whatever safe altitude we choose), then we need to search for a rocket angle closer to vertical that keeps the rocket above-ground.
I've been working this out in Excel; the next thing to do is to implement it in-game. There are a variety of ways it could be used: I could plot the earliest-landing point on the ground, or plot the trajectory to it, or have an attitude indicator showing which direction to burn. Once it's in I'll see how valid the flat-earth assumptions are. They do become more correct as the rocket approaches the ground so they may not be a problem.
Another thing this could be useful for is the beginning of a rocket AI. Computer-controlled rockets will probably have slightly different trajectory needs. They'll be wanting to land at a specific spot, rather than at the earliest possible spot. It shouldn't be too different, though.
Monday, November 12, 2007
Flying over eastern Washington
This weekend we visited my parents. My father took me up for a couple of hours in his little yellow Super Cub, which is always fun. We toured the Hanford site, the Coyote Ridge Corrections Center in Connell, Palouse Falls, Lower Monumental Dam, the Kahlotus Cemetery, and we did touch and gos at a couple of farm landing strips. There are always a lot of deer on the wheat fields, and we scared up a coyote yesterday as well.
I'd never been over Hanford before. It's a very interesting place. During World War 2 the US Department of Energy took over a vast swath of land next to the Columbia River in order to produce the plutonium for the nation's nuclear weapons. The river provided cooling water, and the barren land provided isolation.
There was a town named Hanford on the site, which was dismantled. You can still see the streets and the trees; the only walls still standing are the high school building.
The “B” reactor was the “world's first industrial-scale nuclear reactor.” Here's a picture:
About a dozen more reactors were built. In the early 1990s (I believe; I'm writing from memory) the government decided to shut it all down. Most of the reactors have been encased in concrete and steel sarcophagi; the B reactor has been left standing free due to sentimental reasons, but as you can see in the picture, all the ancillary buildings have been torn down.
I don't know the details off-hand, but I think the reactors were shut down fairly suddenly, and their fuel rods were dumped into the nearby processing ponds and tanks. They were left alone for a while and made a mess, which the Hanford site is now cleaning up at great expense.
The nuclear reactors from our nation's decommissioned subs are shipped up the river and placed in neat rows in a pit on the Hanford site:
I'm convinced that nuclear energy will be needed to help solve the coming energy shortages. Nuclear physics is pretty far removed from daily experience in most people's lives, and I think this, combined with its use in weapons, has given it an almost religious aura in many minds, occupying space next to Satan. What people don't realize is that there isn't necessarily a reason why nuclear power generation has to produce lots of radioactive waste. We just haven't been trying to make nuclear reactors any better. In particular, thorium-based reactors look promising. See this blog for details.
The prison in Connell was depressing. They have a medium-security facility already, but are building a huge expansion that looks (from the air) like it will have considerably more security, with a double fence enclosing a no-man's-land.
Forcing people who have done something wrong to only associate with other people like themselves seems like just about the stupidest idea possible, if “correction” is at all a goal. It's a hard problem, I'm sure; it just seems like there must be a better way.
The Kahlotus Cemetery is a small plot in a small town. It apparently contains quite a few graves of anonymous Chinese laborers who were killed in accidents while building the railroad.
I'd never been over Hanford before. It's a very interesting place. During World War 2 the US Department of Energy took over a vast swath of land next to the Columbia River in order to produce the plutonium for the nation's nuclear weapons. The river provided cooling water, and the barren land provided isolation.
There was a town named Hanford on the site, which was dismantled. You can still see the streets and the trees; the only walls still standing are the high school building.
The “B” reactor was the “world's first industrial-scale nuclear reactor.” Here's a picture:
About a dozen more reactors were built. In the early 1990s (I believe; I'm writing from memory) the government decided to shut it all down. Most of the reactors have been encased in concrete and steel sarcophagi; the B reactor has been left standing free due to sentimental reasons, but as you can see in the picture, all the ancillary buildings have been torn down.
I don't know the details off-hand, but I think the reactors were shut down fairly suddenly, and their fuel rods were dumped into the nearby processing ponds and tanks. They were left alone for a while and made a mess, which the Hanford site is now cleaning up at great expense.
The nuclear reactors from our nation's decommissioned subs are shipped up the river and placed in neat rows in a pit on the Hanford site:
I'm convinced that nuclear energy will be needed to help solve the coming energy shortages. Nuclear physics is pretty far removed from daily experience in most people's lives, and I think this, combined with its use in weapons, has given it an almost religious aura in many minds, occupying space next to Satan. What people don't realize is that there isn't necessarily a reason why nuclear power generation has to produce lots of radioactive waste. We just haven't been trying to make nuclear reactors any better. In particular, thorium-based reactors look promising. See this blog for details.
The prison in Connell was depressing. They have a medium-security facility already, but are building a huge expansion that looks (from the air) like it will have considerably more security, with a double fence enclosing a no-man's-land.
Forcing people who have done something wrong to only associate with other people like themselves seems like just about the stupidest idea possible, if “correction” is at all a goal. It's a hard problem, I'm sure; it just seems like there must be a better way.
The Kahlotus Cemetery is a small plot in a small town. It apparently contains quite a few graves of anonymous Chinese laborers who were killed in accidents while building the railroad.
Thursday, November 8, 2007
James McColl and The Hussy's
James McColl is a Glasgow-based songwriter. He was a member of The Supernaturals in the 1990s, and now has a female-fronted band called The Hussy's (their spelling, not mine). Very catchy songs. My personal favorites are “Tiger” and “We Expected”.
The band is recording an album right now. They aren't signed to a label and it looks from their blog entries like they're undergoing some internal friction as a result. Here's hoping they weather their difficulties and get the album out.
The band is recording an album right now. They aren't signed to a label and it looks from their blog entries like they're undergoing some internal friction as a result. Here's hoping they weather their difficulties and get the album out.
Monday, November 5, 2007
Time Acceleration, Hyperbolic View
Library Trip
I made the trek over to the engineering library at the University of Washington this weekend and looked up several of the papers about powered soft-landing trajectory optimization that I wasn't able to view online. The papers weren't as useful as I'd hoped; they all tend to assume a flat earth with constant gravity, which makes the problem much simpler. My world is exaggerated (smaller world, faster time) so my powered flight occurs over a larger range of gravity strength and direction.
Unsurprisingly, it turns out that fuel-minimizing trajectories get as close as they can to two impulsive maneuvers: one at the start, and one at the end. One paper I read calls this a “bang-bang” trajectory. Cute!
Engine Cutoff
On my program, I did a few minor things. I put in an engine cutoff at touchdown to keep the rocket from rebounding off the ground. It's hard to let off on the rocket at the exact instant it touches down, so it is nice to have the game do it for you.
Time Acceleration
I also enhanced my time acceleration. On a “bang-bang” trajectory you spend the middle part just waiting while the rocket coasts. This is boring. Holding down the Tab key speeds up the game clock. Previously it just accelerated time by 25 times. This was fine for low orbits but much too slow for larger orbits, so I decided to make it variable.
My first attempt was to try to keep on-screen speed constant. This meant that the acceleration was proportional to the view radius (which changes as the camera control algorithm zooms in and out), and inversely proportional to the rocket speed. This worked great, except when it didn't. You can probably guess when it didn't: When the rocket speed approached zero. For example, you're sitting on the ground and press Tab. Bang! Infinite speedup. The other bad case is when you're flying straight up; the rocket will slow to a stop at the apex of the trajectory, then start falling back down. If you are accelerating time through the stop, suddenly your rocket is back on the ground, in pieces.
Because of these problems, I have dropped the inverse proportionality with rocket speed; the time acceleration is simply proportional to the view radius. I'm not sure whether this is wholly satisfactory. The camera frames orbits (up to a certain size), so if you are flying a highly elliptical orbit you will zoom around the periapsis at high speed and then dawdle through the apoapsis. Periapsis is a common location for doing burns, and having the time acceleration too high there makes it hard to hit the right spot in the orbit.
I added a game clock and a wall clock to the HUD, and a display of the time multiplier when the Tab key is down.
Hyperbolic Camera
Finally, I spent some time trying out various possibilities for the camera-framing algorithm when the orbit is very large, or hyperbolic. I don't have anything satisfactory yet. Ideally it should return similar results near the boundary with the orbit-framing regime, so the camera adjusts smoothly from one to the other. It needs to show the rocket at all times, and probably some portion of the unflown trajectory. It's also probably important to have the planet always be in view.
An example I tried: find the periapsis point, and the axis of the orbit. Expand a bounding circle from the periapsis point in the direction of the orbit's axis until it hits the rocket. Unfortunately this suffers from problems when the rocket is near periapsis. It also doesn't show too much ahead of the rocket for elliptical trajectories. On the plus side, it shows almost all of trajectories that are not too eccentric. It's probably my favorite out of the things I've tried so far, though.
Portal
A couple of years ago I was at the Game Developer Conference, looking over the entrants for the Independent Games competition. A couple of Digipen students (Kim Swift and another guy whose name escapes me) were there demonstrating their student project, a little game called Narbacular Drop. Valve saw the game, too, and hired the entire team of students to turn it into a shipping product, a process that took about two and a half years. I spent a couple hours this weekend playing it. It's pretty fun up to the point where I'm at (room 18), where it turned maddeningly difficult.
I made the trek over to the engineering library at the University of Washington this weekend and looked up several of the papers about powered soft-landing trajectory optimization that I wasn't able to view online. The papers weren't as useful as I'd hoped; they all tend to assume a flat earth with constant gravity, which makes the problem much simpler. My world is exaggerated (smaller world, faster time) so my powered flight occurs over a larger range of gravity strength and direction.
Unsurprisingly, it turns out that fuel-minimizing trajectories get as close as they can to two impulsive maneuvers: one at the start, and one at the end. One paper I read calls this a “bang-bang” trajectory. Cute!
Engine Cutoff
On my program, I did a few minor things. I put in an engine cutoff at touchdown to keep the rocket from rebounding off the ground. It's hard to let off on the rocket at the exact instant it touches down, so it is nice to have the game do it for you.
Time Acceleration
I also enhanced my time acceleration. On a “bang-bang” trajectory you spend the middle part just waiting while the rocket coasts. This is boring. Holding down the Tab key speeds up the game clock. Previously it just accelerated time by 25 times. This was fine for low orbits but much too slow for larger orbits, so I decided to make it variable.
My first attempt was to try to keep on-screen speed constant. This meant that the acceleration was proportional to the view radius (which changes as the camera control algorithm zooms in and out), and inversely proportional to the rocket speed. This worked great, except when it didn't. You can probably guess when it didn't: When the rocket speed approached zero. For example, you're sitting on the ground and press Tab. Bang! Infinite speedup. The other bad case is when you're flying straight up; the rocket will slow to a stop at the apex of the trajectory, then start falling back down. If you are accelerating time through the stop, suddenly your rocket is back on the ground, in pieces.
Because of these problems, I have dropped the inverse proportionality with rocket speed; the time acceleration is simply proportional to the view radius. I'm not sure whether this is wholly satisfactory. The camera frames orbits (up to a certain size), so if you are flying a highly elliptical orbit you will zoom around the periapsis at high speed and then dawdle through the apoapsis. Periapsis is a common location for doing burns, and having the time acceleration too high there makes it hard to hit the right spot in the orbit.
I added a game clock and a wall clock to the HUD, and a display of the time multiplier when the Tab key is down.
Hyperbolic Camera
Finally, I spent some time trying out various possibilities for the camera-framing algorithm when the orbit is very large, or hyperbolic. I don't have anything satisfactory yet. Ideally it should return similar results near the boundary with the orbit-framing regime, so the camera adjusts smoothly from one to the other. It needs to show the rocket at all times, and probably some portion of the unflown trajectory. It's also probably important to have the planet always be in view.
An example I tried: find the periapsis point, and the axis of the orbit. Expand a bounding circle from the periapsis point in the direction of the orbit's axis until it hits the rocket. Unfortunately this suffers from problems when the rocket is near periapsis. It also doesn't show too much ahead of the rocket for elliptical trajectories. On the plus side, it shows almost all of trajectories that are not too eccentric. It's probably my favorite out of the things I've tried so far, though.
Portal
A couple of years ago I was at the Game Developer Conference, looking over the entrants for the Independent Games competition. A couple of Digipen students (Kim Swift and another guy whose name escapes me) were there demonstrating their student project, a little game called Narbacular Drop. Valve saw the game, too, and hired the entire team of students to turn it into a shipping product, a process that took about two and a half years. I spent a couple hours this weekend playing it. It's pretty fun up to the point where I'm at (room 18), where it turned maddeningly difficult.
Subscribe to:
Posts (Atom)