The weekend, while long, was busy. We hosted two events: Thanksgiving and my daughter's fourth birthday party. I wasted what little free time was left reading Child of Fire: A Twenty Palaces Novel and watching John Woo's historical epic Red Cliff.
Child of Fire came to my attention via John Scalzi's Big Idea series, where authors get to plug their new books. First-time author Harry Connolly wrote an entry about his book that intrigued me despite the book's atrocious name. I finally got around to picking up a copy of the book and reading it. It's very well written and I'm looking forward to his future work. Recommended if you like Dashiell Hammett or Chandler.
Red Cliff is based on a 3rd-century battle retold in the 14th century Chinese novel Romance of the Three Kingdoms. When I worked at Midway we watched a bunch of Woo's films in preparation for working on a videogame with him. A lot of his trademark Wooisms can be found in this massive historical epic (cut down to 2.5 hours for US release). For instance, in Hard Boiled Chow Yun Fat's character blasts his way out of a hospital with a shotgun in one hand and a baby in the other. The opening of Red Cliff features a very similar incident, which I'm guessing was not in the original novel. Other Woo-bits include doves (of course) and Mexican standoffs, albeit with swords rather than guns. And random slo-mo of the duplicated-frame sort.
The characters felt really stale to me. I am interested in reading the original novel now to see if they are this one-dimensional there. The two characters that I felt stood out were Kong Rong (played by Wang Qingxiang), who was the tactical genius on the rebel side; and Xiao Qiao (played by Lin Chi-ling) who holds a Helen-of-Troy position in the story but with a strong Judith moment near the end.
I'd played one or two of the Dynasty Warriors games previously so a lot of the supporting hero characters (like Guan Yu) felt familiar. It is a little odd to have my scant historical knowledge derived from there, but that's how it is!
Monday, November 30, 2009
Monday, November 23, 2009
PID controllers
My brother is an electrical engineer; he's working on unmanned aircraft autopilots, among other things. He recommended using a PID controller. “PID” is an acronym for proportional, integral, derivative, the three terms that make up the control equation. The controller measures the error between current and desired position. It also maintains an integral of the error, and estimates the current derivative of the error. Then it linearly combines these three values to drive something intended to correct for the error.
I tried out a PD controller (leaving out the integral term). The error is the difference between the target heading and the current heading. The derivative of the error is then the current angular velocity. These are combined to drive the nozzle angle, which is clamped to stay within its movement range. It's an extremely simple controller but the results are much smoother than what I had before:
In the video I'm aiming the green arrow and manually firing the rocket. The rocket rotates freely in between firings. The steering algorithm is applied to the nozzle even when I'm not firing so you'll see it rotating in preparation to align the rocket with the arrow.
In terms of control I'm pretty happy with this. I may add some additional rotation jets to the rocket to allow rotation without adding large linear velocities; they would probably be controlled with the same algorithm.
Oh yeah: this PD controller is pretty much the same thing as a damped spring. The nozzle angle doesn't translate linearly into rotational acceleration but otherwise it is the same thing.
I tried out a PD controller (leaving out the integral term). The error is the difference between the target heading and the current heading. The derivative of the error is then the current angular velocity. These are combined to drive the nozzle angle, which is clamped to stay within its movement range. It's an extremely simple controller but the results are much smoother than what I had before:
In the video I'm aiming the green arrow and manually firing the rocket. The rocket rotates freely in between firings. The steering algorithm is applied to the nozzle even when I'm not firing so you'll see it rotating in preparation to align the rocket with the arrow.
In terms of control I'm pretty happy with this. I may add some additional rotation jets to the rocket to allow rotation without adding large linear velocities; they would probably be controlled with the same algorithm.
Oh yeah: this PD controller is pretty much the same thing as a damped spring. The nozzle angle doesn't translate linearly into rotational acceleration but otherwise it is the same thing.
Monday, November 16, 2009
Rocket steering methods
My primary lunar lander prototype (not the one shown below) does not have true rigid body dynamics yet. The rocket's heading is driven directly by mouse movement. This makes it really easy to steer the nozzle but I have been unsure about how to alter it once the rocket can actually collide with the terrain in a way that applies torque. If you are able to directly rotate the rocket that could introduce unwanted interpenetration or arbitrary launch velocities.
I have a separate prototype at the moment where I am testing out the rigid body dynamics. The rocket, at the moment, has a single steerable nozzle. It will probably be necessary to add steering jets to make it easier to fly. Right now when you apply a torque to the rocket you are also applying a hefty linear acceleration as well.
The first control method is very simple to implement. The mouse rotates the rocket nozzle; the mouse button fires it. This is demonstrated in the first clip above.
In the second control method (shown in the latter half of the movie) the mouse sets a desired thrust direction. While the rocket is firing, an autopilot steers the rocket nozzle to align thrust in the specified direction. At the moment it's snapping the nozzle to one of three positions: extreme left, extreme right, and center. This is not terribly realistic; I'm still figuring out how to make it more natural.
I have a separate prototype at the moment where I am testing out the rigid body dynamics. The rocket, at the moment, has a single steerable nozzle. It will probably be necessary to add steering jets to make it easier to fly. Right now when you apply a torque to the rocket you are also applying a hefty linear acceleration as well.
The first control method is very simple to implement. The mouse rotates the rocket nozzle; the mouse button fires it. This is demonstrated in the first clip above.
In the second control method (shown in the latter half of the movie) the mouse sets a desired thrust direction. While the rocket is firing, an autopilot steers the rocket nozzle to align thrust in the specified direction. At the moment it's snapping the nozzle to one of three positions: extreme left, extreme right, and center. This is not terribly realistic; I'm still figuring out how to make it more natural.
Friday, November 13, 2009
Landing gear
(The Khrest from Perry Rhodan. Artwork by Ingolf Thaler. From Perry Rhodan Nr 278, 16 December 1967. From Winchell Chung's Atomic Rocket.)
There's a plague going around at work; I eventually succumbed. Being sick for a few days has given me the opportunity to spend a bit more time working on my lunar lander program. I have been studying a couple of 2D physics engines (Chipmunk and Box2D) because I want to add rigid-body dynamics to it.
I'd already done a previous lunar rover test with Chipmunk (it comes with a rover sample) so I added a round rocket to that to try and figure out how to design the landing gear:
In this landing gear, the upper strut is a shock absorber, while the lower strut is just a swing arm. The foot's orientation is locked to the swing arm. This is OK, but the feet are forced to slide outward as the rocket comes to rest. If they hit an immovable obstacle there is an abrupt shock to the rocket. Ideally the feet would not have any lateral force but I haven't been able to come up with a geometry for that, short of just having some pistons sticking straight down out of the rocket. Adding some shock absorption capability to the lower struts would help.
I have decided to try and use Box2D (possibly modified to use my own vector class) instead of Chipmunk. That will take some time to install. Neither engine deals with BSPs so I will probably initially represent the planet with a collection of convex polygons (which will likely take a fair amount of memory), and add support for BSPs later.
Monday, November 2, 2009
Planet terrain collision
When I started my lunar lander project several years ago the planet was a smooth disc. Detecting landings and collisions involved a simple radius check. Recently I dusted off the project and made a more complex, randomly generated terrain, invalidating that collision model. After putting the kids down for quiet time yesterday, I brewed a pot of coffee and set to work adapting collision code I'd written previously for Abyss, my Ultima Underworld hacking experiment. I have something that basically works, now, which is exciting as it is a big step toward this being a playable game.
Unfortunately there isn't much to see in still images. The rocket is prevented from going into the ground, that's all. I've included a couple of random screenshots just to have something to look at. Here's a shot of the final approach for a landing. The dim blue line is the ballistic trajectory and the brighter line is the powered trajectory. It's important not to let the powered trajectory dip below ground level!
This is zoomed out a lot more and shows the chaotic nature of the terrain that I've got at the moment:
The terrain generator is very simple, and generates inaccessible pockets of air inside the planet as well as floating islands in the sky. The floating islands are kind of cool; the inaccessible caves are just taunting; I need to remove them in a post-process.
For physics purposes, the terrain is represented by a binary space partition; the BSP divides up space into about 20,000 convex polygons (depending on the random terrain), some of which are solid and some of which are air. I use sentinel values in the child pointer slots of a BSP split node to signal solid and empty leaves, so there is no storage allocated for the leaves themselves. Each split node costs 20 bytes: the three line equation coefficients and pointers to its two children.
The rocket is currently represented by a disc. (Yes, eventually it will be more complex.) To detect intersections between the BSP and this disc, I traverse the BSP tree depth-first, building a stack of the currently active splitting lines. If the disc straddles a split line, the branch not taken is saved on a stack to be visited later. Otherwise I just go down the side containing the disc.
When the recursion hits a solid leaf, the stack of active splitting lines implicitly defines the polygonal region for that leaf. I have a function that returns the smallest separating axis between this region and the disc. If it turns out that the disc and the leaf region are overlapping, I generate a contact constraint in the direction of the separating axis.
This week I also switched all the code to 32-bit floating point arithmetic; large portions of it used 64-bit precision as a holdover from my orrery project. I also was able to reduce the integration from fourth-order Runge Kutta to a second-order method (Heun's). The main place this shows differences is when orbiting under high time acceleration.
One of the remaining top priorities is coming up with an adequate camera control algorithm. I'd really like to minimize the amount of manual control necessary, so I have to figure out what is important to show. Making a more complex rocket model, with shock absorbing landing gear, is another.
Unfortunately there isn't much to see in still images. The rocket is prevented from going into the ground, that's all. I've included a couple of random screenshots just to have something to look at. Here's a shot of the final approach for a landing. The dim blue line is the ballistic trajectory and the brighter line is the powered trajectory. It's important not to let the powered trajectory dip below ground level!
This is zoomed out a lot more and shows the chaotic nature of the terrain that I've got at the moment:
The terrain generator is very simple, and generates inaccessible pockets of air inside the planet as well as floating islands in the sky. The floating islands are kind of cool; the inaccessible caves are just taunting; I need to remove them in a post-process.
For physics purposes, the terrain is represented by a binary space partition; the BSP divides up space into about 20,000 convex polygons (depending on the random terrain), some of which are solid and some of which are air. I use sentinel values in the child pointer slots of a BSP split node to signal solid and empty leaves, so there is no storage allocated for the leaves themselves. Each split node costs 20 bytes: the three line equation coefficients and pointers to its two children.
The rocket is currently represented by a disc. (Yes, eventually it will be more complex.) To detect intersections between the BSP and this disc, I traverse the BSP tree depth-first, building a stack of the currently active splitting lines. If the disc straddles a split line, the branch not taken is saved on a stack to be visited later. Otherwise I just go down the side containing the disc.
When the recursion hits a solid leaf, the stack of active splitting lines implicitly defines the polygonal region for that leaf. I have a function that returns the smallest separating axis between this region and the disc. If it turns out that the disc and the leaf region are overlapping, I generate a contact constraint in the direction of the separating axis.
This week I also switched all the code to 32-bit floating point arithmetic; large portions of it used 64-bit precision as a holdover from my orrery project. I also was able to reduce the integration from fourth-order Runge Kutta to a second-order method (Heun's). The main place this shows differences is when orbiting under high time acceleration.
One of the remaining top priorities is coming up with an adequate camera control algorithm. I'd really like to minimize the amount of manual control necessary, so I have to figure out what is important to show. Making a more complex rocket model, with shock absorbing landing gear, is another.
Monday, October 26, 2009
Lunar lander terrain progress
I've been working on the terrain and camera control for my “Lunar Lander on a round planet” project.
The planet generator now creates a BSP representation of the terrain in addition to the boundary representation, to be used for collision and contact.
I downloaded the latest version of the Box2D physics engine to use as a reference. The released version has only convex polygons and circles as its physics primitives; I would need to compose a bunch of convex polygons to make the terrain. Apparently there is an unreleased version with an edge-list primitive, which could also work for the terrain.
Box2D and Chipmunk use spatial hashing rather than BSPs. I'm not sure yet which would be best for my planet; I'm going forward with a BSP for now. I have an idea for computing contact with BSP leaf nodes using the split planes to implicitly define the convex polygon around the leaf. That ought to use memory fairly efficiently.
When I started the BSP implementation I tried to set it up such that the deepest splits would identify which of their leaves were inside and which were outside (based on the surface normal). The idea is to avoid having any storage for the leaves; only for the splits. I think that only works if your splits always lie on the surface somewhere, though. I ended up using two sentinel values to represent inside and outside leaves (instead of the one sentinel value you'd need for the other scheme) and it simplified things considerably.
Implementing ray intersection against the BSP terrain has allowed me to experiment with some camera framing algorithms. Framing the ballistic trajectory is good for some situations. One problem is that the impact point can change distance instantaneously which makes the camera jump around. I also tried shooting a bunch of rays in all directions to form some sort of idea of the locally visible terrain, but this also tends to change in jumpy ways. Currently I'm working on an algorithm that is based primarily on the specific mechanical energy, since that changes smoothly.
Generating terrain with lots of tunnels made me realize that I needed to enhance my gravitation formula to work inside the planet. The force of gravity falls off linearly as you work your way from the surface to the center.
The planet generator now creates a BSP representation of the terrain in addition to the boundary representation, to be used for collision and contact.
I downloaded the latest version of the Box2D physics engine to use as a reference. The released version has only convex polygons and circles as its physics primitives; I would need to compose a bunch of convex polygons to make the terrain. Apparently there is an unreleased version with an edge-list primitive, which could also work for the terrain.
Box2D and Chipmunk use spatial hashing rather than BSPs. I'm not sure yet which would be best for my planet; I'm going forward with a BSP for now. I have an idea for computing contact with BSP leaf nodes using the split planes to implicitly define the convex polygon around the leaf. That ought to use memory fairly efficiently.
When I started the BSP implementation I tried to set it up such that the deepest splits would identify which of their leaves were inside and which were outside (based on the surface normal). The idea is to avoid having any storage for the leaves; only for the splits. I think that only works if your splits always lie on the surface somewhere, though. I ended up using two sentinel values to represent inside and outside leaves (instead of the one sentinel value you'd need for the other scheme) and it simplified things considerably.
Implementing ray intersection against the BSP terrain has allowed me to experiment with some camera framing algorithms. Framing the ballistic trajectory is good for some situations. One problem is that the impact point can change distance instantaneously which makes the camera jump around. I also tried shooting a bunch of rays in all directions to form some sort of idea of the locally visible terrain, but this also tends to change in jumpy ways. Currently I'm working on an algorithm that is based primarily on the specific mechanical energy, since that changes smoothly.
Generating terrain with lots of tunnels made me realize that I needed to enhance my gravitation formula to work inside the planet. The force of gravity falls off linearly as you work your way from the surface to the center.
Monday, October 12, 2009
Perlin simplex noise
I'm now working on my lunar lander program again. The core idea is to adapt Thrust gameplay for a circular planet, so that orbiting is a possibility. My goal is to release something in early December.
The top priority is to get an interesting planet to land on. I am working from these sources, albeit translating everything into two dimensions:
The basic idea I'm trying out is to define a density function over the plane, and then evaluate it to find the boundary where density crosses from negative to positive. The density function can be built up out of a variety of pieces; at the moment I'm starting with a radial increase with an offset (d = r - 1):
Layered on top of that are several octaves of Perlin's simplex noise. The first two are shown below:
I convert the implicit function to a surface by subdividing a large triangle that encompasses the planet; you can see its outline (cropped by the window rectangle) in the pictures above.
Below are the results of layering the radius function with three octaves of noise:
There are lots of other things to try; this is as far as I got last night.
The next step is to build a BSP or spatial hash in order to make the terrain solid. That should not be hard. After that I will probably want to triangulate the interior and texture it; I'm still thinking about the best way to accomplish that.
The noise functions don't guarantee that everything will be interconnected. You can see free-floating bits, as well as isolated pockets of air inside the ground. It might be nice to filter out the isolated pockets, and maybe justify the floating junks of rock by rendering a background layer to suggest that it's the cross section of an arch.
The top priority is to get an interesting planet to land on. I am working from these sources, albeit translating everything into two dimensions:
The basic idea I'm trying out is to define a density function over the plane, and then evaluate it to find the boundary where density crosses from negative to positive. The density function can be built up out of a variety of pieces; at the moment I'm starting with a radial increase with an offset (d = r - 1):
Layered on top of that are several octaves of Perlin's simplex noise. The first two are shown below:
I convert the implicit function to a surface by subdividing a large triangle that encompasses the planet; you can see its outline (cropped by the window rectangle) in the pictures above.
Below are the results of layering the radius function with three octaves of noise:
There are lots of other things to try; this is as far as I got last night.
The next step is to build a BSP or spatial hash in order to make the terrain solid. That should not be hard. After that I will probably want to triangulate the interior and texture it; I'm still thinking about the best way to accomplish that.
The noise functions don't guarantee that everything will be interconnected. You can see free-floating bits, as well as isolated pockets of air inside the ground. It might be nice to filter out the isolated pockets, and maybe justify the floating junks of rock by rendering a background layer to suggest that it's the cross section of an arch.
Subscribe to:
Posts (Atom)
